Journal
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023
Volume -, Issue -, Pages 686-697Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3564246.3585151
Keywords
prophet inequality; combinatorial auction; subadditive valuation; mechanism design
Ask authors/readers for more resources
In online combinatorial auctions, a constant factor prophet inequality has been proven to exist for subadditive valuations using a novel sampling idea called the Mirror Lemma, resolving a central open problem in the field.
In online combinatorial auctions.. indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents' valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best known prophet inequality has an approximation guarantee of O(log log m). In this paper, we prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area. Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding online algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem. Finally, we note that our prophet inequality works against an almighty adversary and even can be implemented in an incentive compatible way.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available