Online Combinatorial Allocations and Auctions with Few Samples
In online combinatorial allocations/auctions, n bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of m indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving O(1)-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a $(2+\epsilon)$-competitive online truthful mechanism for submodular/XOS valuations and any constant $\epsilon>0$. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Rank-Guaranteed Auctions
We propose a combinatorial ascending auction that is "approximately" optimal, requiring minimal rationality to achieve this level of optimality, and is robust to strategic and distributional uncertainties. Specifically, …
Sample Complexity of Automated Mechanism Design
The design of revenue-maximizing combinatorial auctions, i.e. multi-item auctions over bundles of goods, is one of the most fundamental problems in computational economics, unsolved even for two bidders and two items for…
Combinatorial OptimizationLearning TheoryEfficient allocations in double auction markets
This paper proposes a simple descriptive model of discrete-time double auction markets for divisible assets. As in the classical models of exchange economies, we consider a finite set of agents described by their initial…
DescriptiveIndividual Fairness in Advertising Auctions through Inverse Proportionality
Recent empirical work demonstrates that online advertisement can exhibit bias in the delivery of ads across users even when all advertisers bid in a non-discriminatory manner. We study the design of ad auctions that, giv…
FairnessPackage Bids in Combinatorial Electricity Auctions: Selection, Welfare Losses, and Alternatives
A key challenge in combinatorial auctions is designing bid formats that accurately capture agents' preferences while remaining computationally feasible. This is especially true for electricity auctions, where complex pre…