The Competition Complexity of Prophet Inequalities
Authors: 
Johannes Brustle, José Correa, Paul Dütting, Tomer Ezra, Michal Feldman, Victor VerdugoAuthors Info & Claims
Pages 807 - 830
Abstract
We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the (1 - ε)-competition complexity of different types of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance, is at least a (1 - ε)-approximation to the expected offline optimum on a single copy.
We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of k = Θ(log log 1/ε). This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of k = Θ(log 1/ε), establishing an exponential gap between block threshold algorithms and single threshold algorithms.
Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications.
References
[1]
M. Abolhassani, S. Ehsani, H. Esfandriari, M. Hajiaghayi, R. Kleinberg, and B. Lucier. 2017. Beating 1-1/e for Ordered Prophets. In STOC 2017. 61--71.
[2]
S. Alaei. 2011. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. In FOCS 2011. 512--521.
[3]
N. Arnosti and W. Ma. 2022. Tight guarantees for static threshold policies in the prophet secretary problem. Operations Research (2022).
[4]
M. Babaioff, K. Goldner, and Y. A. Gonczarowski. 2020. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. In SODA 2020. 2452--2471.
[5]
H. Beyhaghi and S. M. Weinberg. 2019. Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items. In STOC 2019. 686--696.
[6]
J. Brustle, J. Correa, P. Dütting, and V. Verdugo. 2022. The Competition Complexity of Dynamic Pricing. In EC 2022. 303--320.
[7]
J. Bulow and P. Klemperer. 1996. Auctions versus Negotiations. American Economic Review 86, 1 (1996), 180--94.
[8]
S. Chawla, J. Hartline, D. Malec, and B. Sivan. 2010. Multiparameter Mechanism Design and Sequential Posted Pricing. In STOC 2010. 311--320.
[9]
J. Correa and A. Cristi. 2023. A constant-factor prophet inequality for online combinatorial auctions. In STOC 2023. 686--697.
[10]
J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld. 2021. Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals. Math. Oper. Res. 46, 4 (2021), 1452--1478.
[11]
J. Csirik and G.J. Woeginger. 2000. Resource Augmentation for Online Bounded Space Bin Packing. In ICALP 2000. 296--304.
[12]
P. Dütting, M. Feldman, T. Kesselheim, and B. Lucier. 2017. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. In FOCS 2017. 540--551.
[13]
P. Dütting, T. Kesselheim, and B. Lucier. 2020. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. In FOCS 2020. 306--317.
[14]
A. Eden, M. Feldman, O. Friedler, I. Talgam-Cohen, and S. M. Weinberg. 2017. The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders. In EC 2017. 343.
[15]
T. Ezra, M. Feldman, N. Gravin, and Z. G. Tang. 2022. Prophet matching with general arrivals. Mathematics of Operations Research 47, 2 (2022), 878--898.
[16]
Tomer Ezra, Michal Feldman, Tim Roughgarden, and Warut Suksompong. 2020. Pricing multi-unit markets. ACM Transactions on Economics and Computation 7, 4 (2020), 1--29.
[17]
M. Feldman, N. Gravin, and B. Lucier. 2015. Combinatorial Auctions via Posted Prices. In SODA 2015. 123--135.
[18]
M. Feldman, O. Svensson, and R. Zenklusen. 2016. Online Contention Resolution Schemes. In SODA 2016, Robert Krauthgamer (Ed.). 1014--1033.
[19]
N. Gravin and H. Wang. 2019. Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive. In EC 2019. 93--109.
[20]
M. Hajiaghayi, R. Kleinberg, and T. Sandholm. 2007. Automated Mechanism Design and Prophet Inequalities. In AAAI 2007. 58--65.
[21]
B. Kalyanasundaram and K. Pruhs. 2000. Speed is as powerful as clairvoyance. Journal of the ACM 47, 4 (2000), 617--643.
[22]
R. Kleinberg and S. M. Weinberg. 2012. Matroid Prophet Inequalities. In STOC 2012. 123--136.
[23]
U. Krengel and L. Sucheston. 1977. Semiamarts and finite values. Bull. Amer. Math. Soc. 83 (1977), 745--747.
[24]
U. Krengel and L. Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics 4 (1978), 197--266.
[25]
A. Liu, R. Paes Leme, M. Pál, J. Schneider, and B. Sivan. 2021. Variable Decomposition for Prophet Inequalities and Optimal Ordering. In EC 2021. 692.
[26]
C. A. Phillips, C. Stein, E. Torng, and J. Wein. 1997. Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). In STOC 1997. 140--149.
[27]
T. Roughgarden and E. Tardos. 2002. How bad is selfish routing? J. ACM 2 (2002), 236--259. Issue 49.
[28]
A. Rubinstein and S. Singla. 2017. Combinatorial Prophet Inequalities. In SODA 2017. 1671--1687.
[29]
E. Samuel-Cahn. 1984. Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables. The Annals of Probability 12, 4 (1984), 1213 -- 1216.
[30]
D. D. Sleator and R. E. Tarjan. 1984. Amortized Efficiency of List Update Rules. In STOC 1984. 488--492.
Index Terms
- The Competition Complexity of Prophet Inequalities
Index terms have been assigned to the content through auto-classification.
Recommendations
Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
EC '21: Proceedings of the 22nd ACM Conference on Economics and ComputationWe design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are ...
Settling the Competition Complexity of Additive Buyers over Independent Items
EC '24: Proceedings of the 25th ACM Conference on Economics and ComputationThe competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) achieves greater revenue than the optimal but complex (randomized, prior-...
Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
We design novel mechanisms for welfare maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1340 pages
ISBN:9798400707049
DOI:10.1145/3670865
- Chair:
- Dirk Bergemann,
- Program Chairs:
- Robert Kleinberg,
- Daniela Saban
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 December 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- ANID
- Harvard University Center of Mathematical Sciences and Applications
- European Research Council
- Amazon Research
- NSF-BSF
- TAU Center for AI and Data Science
Conference
EC '24
Sponsor:
Upcoming Conference
EC '25
- Sponsor:
- sigecom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 7Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)7
Reflects downloads up to 24 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in