The Competition Complexity of Dynamic Pricing

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, Hartline JD, Niazadeh R, Pountourakis E, Yuan Y (2015) Optimal auctions vs. anonymous pricing. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 1446–1463.Google Scholar
• [3] 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
• [4] Bulow J, Klemperer P (1996) Auctions vs. negotiations. Amer. Econom. Rev. 86(1):180–194.Google Scholar
• [5] Chawla S, Hartline J, Kleinberg R (2007) Algorithmic pricing via virtual valuations. Proc. 2007 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 243–251.Google Scholar
• [6] Chawla S, Hartline J, Malec D, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• [7] Correa J, Hartline J, Immorlica N (2022) A semester virtual institute. Blog@CACM. Accessed September 2021, https://cacm.acm.org/blogs/blog-cacm/258538-a-semester-virtual-institute/fulltext.Google Scholar
• [8] Correa J, Dütting P, Fischer F, Schewior K (2019) Prophet inequalities for I.I.D. random variables from an unknown distribution. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 3–17.Google Scholar
• [9] Correa J, Foncea P, Pizarro D, Verdugo V (2019b) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [10] 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
• [11] Dütting P, Fischer F, Klimm M (2016) Revenue gaps for discriminatory and anonymous sequential posted pricing. Preprint, submitted July 24, https://arxiv.org/abs/1607.07105.Google Scholar
• [12] 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 Computer Society, Washington, DC), 306–317.Google Scholar
• [13] 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 Computer Society, Washington, DC), 540–551.Google Scholar
• [14] 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
• [15] Feldman M, Friedler O, Rubinstein A (2018) 99% revenue via enhanced competition. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 443–460.Google Scholar
• [16] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 123–135.Google Scholar
• [17] Gilbert J, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61(313):35–73.Crossref, Google Scholar
• [18] Hajiaghayi M, Kleinberg R, Sandholm T (2007) Automated mechanism design and prophet inequalities. Proc. 22nd National Conf. Artificial Intelligence, vol. 1 (AAAI Press, Palo Alto, CA), 58–65.Google Scholar
• [19] Hartline J (2020) Mechanism design and approximation. Accessed December 2021, https://jasonhartline.com/MDnA/.Google Scholar
• [20] Hartline J, Roughgarden T (2009) Simple vs. optimal mechanisms. Proc. 10th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 225–234.Google Scholar
• [21] Hill T, Kertz R (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab. 10(2):336–345.Crossref, Google Scholar
• [22] Jin Y, Jiang S, Lu P, Zhang H (2021) Tight revenue gaps among multi-unit mechanisms. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 654–673.Google Scholar
• [23] Jin Y, Lu P, Tang ZG, Xiao T (2019) Tight revenue gaps among simple mechanisms. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 209–228.Google Scholar
• [24] Jin Y, Lu P, Qi Q, Tang ZG, Xiao T (2019) Tight approximation ratio of anonymous pricing. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 674–685.Google Scholar
• [25] Kertz RP (1986) Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality. J. Multivariate Anal. 19(1):88–112.Google Scholar
• [26] Kleinberg J, Kleinberg R (2018) Delegated search approximates efficient search. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 287–302.Google Scholar
• [27] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [28] Liu A, Paes Leme R, 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
• [29] Liu S, Psomas C (2018) On the competition complexity of dynamic mechanism design. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2008–2025.Google Scholar
• [30] Moser L (1956) On a problem of Cayley. Scripta Math. 22:289–292.Google Scholar
• [31] Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• [32] Picard E (1893) Sur l’application des méthodes d’approximations successives à l’étude de certaines équations différentielles ordinaires. J. Math. Pures Appl. 9:217–272.Google Scholar
• [33] Singla S (2018) Combinatorial optimization under uncertainty: Probing and stopping-time algorithms. Unpublished PhD thesis, Carnegie Mellon University, Pittsburgh, PA.Google Scholar