The Competition Complexity of Prophet Inequalities

References

• [1] Abolhassani M, Ehsani S, Esfandriari H, Hajiaghayi M, Kleinberg R, Lucier B (2017) Beating 1-1/e for ordered prophets. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 61–71.Google Scholar
• [2] Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. 2011 IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 512–521.Google Scholar
• [3] Arnosti N, Ma W (2022) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.Link, Google Scholar
• [4] Babaioff M, Goldner K, Gonczarowski YA (2020) Bulow-Klemperer-style results for welfare maximization in two-sided markets. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2452–2471.Google Scholar
• [5] Beyhaghi H, Weinberg SM (2019) Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 686–696.Google Scholar
• [6] Brustle J, Correa J, Duetting P, Verdugo V (2023) The competition complexity of dynamic pricing. Math. Oper. Res. 49(3):1986–2008.Link, Google Scholar
• [7] Bulow J, Klemperer P (1996) Auctions versus negotiations. Amer. Econom. Rev. 86(1):180–194.Google Scholar
• [8] Chawla S, Hartline J, Malec D, Sivan B (2010) Multiparameter mechanism design and sequential posted pricing. Proc. Forty-Second ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• [9] Correa J, Cristi A (2023) A constant-factor prophet inequality for online combinatorial auctions. Proc. 55th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 686–697.Google Scholar
• [10] Correa J, Foncea P, Pizarro D, Verdugo V (2019) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [11] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• [12] Csirik J, Woeginger G (2000) Resource augmentation for online bounded space bin packing. Automata Languages Programming. ICALP 2000 (Springer, Berlin, Heidelberg), 296–304.Google Scholar
• [13] Dütting P, Kesselheim T, Lucier B (2020) An O(log log m) prophet inequality for subadditive combinatorial auctions. 2020 IEEE 61st Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 306–317.Google Scholar
• [14] Dütting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. 2017 IEEE 58th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 540–551.Google Scholar
• [15] Eden A, Feldman M, Friedler O, Talgam-Cohen I, Weinberg SM (2017) The competition complexity of auctions: A Bulow-Klemperer result for multi-dimensional bidders. Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 343.Google Scholar
• [16] Ezra T, Garbuz T (2024) The competition complexity of prophet inequalities with correlations. Preprint, submitted September 10, https://arxiv.org/abs/2409.06868.Google Scholar
• [17] Ezra T, Garbuz T (2024) The competition complexity of prophet secretary. Preprint, submitted November 16, https://arxiv.org/abs/2411.10892.Google Scholar
• [18] Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
• [19] Ezra T, Feldman M, Roughgarden T, Suksompong W (2020) Pricing multi-unit markets. ACM Trans. Econom. Comput. 7(4):1–29.Google Scholar
• [20] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 123–135.Google Scholar
• [21] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Krauthgamer R, ed. Proc. Twenty-Seventh Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1033.Google Scholar
• [22] Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 93–109.Google Scholar
• [23] Hajiaghayi M, Kleinberg R, Sandholm T (2007) Automated mechanism design and prophet inequalities. Proc. 22nd Natl. Conf. Artificial Intelligence - Volume 1 (AAAI Press, Palo Alto, CA), 58–65.Google Scholar
• [24] Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J. ACM 47(4):617–643.Crossref, Google Scholar
• [25] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. Forty-Fourth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [26] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83:745–747.Crossref, Google Scholar
• [27] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probab. Related Topics 4:197–266.Google Scholar
• [28] Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• [29] Liu A, Leme RP, Pál M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 692.Google Scholar
• [30] Phillips CA, Stein C, Torng E, Wein J (1997) Optimal time-critical scheduling via resource augmentation (extended abstract). Proc. Twenty-Ninth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 140–149.Google Scholar
• [31] Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• [32] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1671–1687.Google Scholar
• [33] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• [34] Sleator DD, Tarjan RE (1984) Amortized efficiency of list update rules. Proc. Sixteenth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 488–492.Google Scholar