Bayesian and Randomized Clock Auctions

References

• Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi M, Kleinberg R, Lucier B (2017) Beating 1-1/e for ordered prophets. Hatami H, McKenzie P, King V, eds. Proc. 49th Ann. ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 61–71.Google Scholar
• Akbarpour M, Li S (2020) Credible auctions: A trilemma. Econometrica 88(2):425–467.Crossref, Google Scholar
• Alaei S, Makhdoumi A, Malekian A, Niazadeh R (2022) Descending price auctions with bounded number of price levels and batched prophet inequality. Segal I, Seuken S, Pennock D, eds. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 246.Google Scholar
• Azar PD, Micali S (2013) Parametric digital auctions. Kleinberg RD, ed. Proc. Innovations Theoretical Comput. Sci. (Association for Computing Machinery, New York), 231–232.Google Scholar
• Azar PD, Kleinberg R, Weinberg SM (2019) Prior independent mechanisms via prophet inequalities with limited information. Games Econom. Behav. 118(November):511–532.Crossref, Google Scholar
• Azar P, Micali S, Daskalakis C, Weinberg SM (2013) Optimal and efficient parametric auctions. Khanna S, ed. Proc. 24th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 596–604.Google Scholar
• Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. Gabow H, ed. Proc. 18th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 434–443.Google Scholar
• Babaioff M, Immorlica N, Lucier B, Weinberg SM (2020) A simple and approximately optimal mechanism for an additive buyer. J. ACM 67(4):1–40.Crossref, Google Scholar
• Balkanski E, Garimidi P, Gkatzelis V, Schoepflin D, Tan X (2022) Deterministic budget-feasible clock auctions. Naor J (Seffi), Buchbinder N, eds. Proc. 33rd Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia).Google Scholar
• Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. Oper. Res. 69(6):1805–1822.Link, Google Scholar
• Bichler M, Hao Z, Littmann R, Waldherr S (2020) Strategy-proof auction mechanisms for network procurement. OR Spectrum 42(4):965–994.Crossref, Google Scholar
• Brandt F, Sandholm T (2005) Unconditional privacy in social choice. van der Meyden R, ed. Proc. 10th Conf. Theoretical Aspects Rationality Knowledge (National University of Singapore, Singapore), 207–218.Google Scholar
• Caramanis C, Dütting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, et al. (2022) Single-sample prophet inequalities via greedy-ordered selection. Naor J (Seffi), Buchbinder N, eds. Proc. Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1298–1325.Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Mitzenmacher M, Schulman LJ, eds. Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• Christodoulou G, Gkatzelis V, Schoepflin D (2022) Optimal deterministic clock auctions and beyond. Braverman M, ed. Proc. 13th Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Cole R, Roughgarden T (2014) The sample complexity of revenue maximization. Shmoys DB, ed. Proc. Sympos. Theory Comput. (ACM, New York), 243–252.Google Scholar
• Correa J, Saona R, Ziliotto B (2019c) Prophet secretary through blind strategies. Chan T, ed. Proc. 30th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1946–1961.Google Scholar
• Correa JR, Cristi A, Epstein B, Soto JA (2020) The two-sided game of googol and sample-based prophet inequalities. Chawla S, ed. Proc. 14th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2066–2081.Google Scholar
• Correa J, Dütting P, Fischer F, Schewior K (2019a) Prophet inequalities for IID random variables from an unknown distribution. Karlin AR, Immorlica N, Johari R, eds. Proc. ACM Conf. Econom. Comput. (ACM, New York), 3–17.Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Daskalakis C, Babaioff M, Moulin H, eds. Proc. ACM Conf. Econom. Computa. (Association for Computing Machinery, New York), 169–186.Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019b) Recent developments in prophet inequalities. Sigecom Exchange 17(1):61–70.Crossref, Google Scholar
• Daskalakis C, Fishelson M, Lucier B, Syrgkanis V, Velusamy S (2020) Simple, credible, and approximately-optimal auctions. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 713–713.Google Scholar
• De Keijzer B, Kyropoulou M, Ventre C (2020) Obviously strategy-proof single-minded combinatorial auctions. Czumaj A, Dawar A, Merelli E, eds. Proc. 47th Internat. Colloquium Automata Languages Programming (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 71.Google Scholar
• den Hollander F (2008) Large Deviations. Fields Institute Monographs (American Mathematical Society, Providence, RI).Google Scholar
• Dütting P, Kleinberg R (2015) Polymatroid prophet inequalities. Bansal N, Finocchi I, eds. Proc. Algorithms-ESA (Springer, Berlin, Heidelberg), 437–449.Google Scholar
• Dütting P, Gkatzelis V, Roughgarden T (2017) The performance of deferred-acceptance auctions. Math. OR 42(4):897–914.Link, Google Scholar
• Dütting P, Kesselheim T, Lucier B (2020b) An o(log logm) prophet inequality for subadditive combinatorial auctions. Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, eds. Proc. IEEE 61st Ann. Sympos. Foundations Comput. Sci., 306–317 (IEEE, Piscataway, NJ).Google Scholar
• Dütting P, Talgam-Cohen I, Roughgarden T (2017) Modularity and greed in double auctions. Games Econom. Behav. 105:59–83.Crossref, Google Scholar
• Dütting P, Feldman M, Kesselheim T, Lucier B (2020a) Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3):540–582.Crossref, Google Scholar
• Dütting P, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2021) Efficient two-sided markets with limited information. Khuller S, Vassilevska Williams V, eds. Proc. 53rd Ann. ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1452–1465.Google Scholar
• Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Czumaj A, ed. Proc. 29th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 700–714 .Google Scholar
• Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701.Crossref, Google Scholar
• Essaidi M, Ferreira MVX, Weinberg SM (2022) Credible, strategy-proof, optimal, and bounded expected-round single-item auctions for all distributions. Braverman M, ed. Proc. 13th Innovations Theoretical Comput. Sci. Conf., LIPIcs, vol. 215 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 66:1–66:19.Google Scholar
• Ezra T, Feldman M, Nehama I (2018) Prophets and secretaries with overbooking. Tardos É, Elkind E, Vohra R, eds. Proc. ACM Conf. Econom. Comput. (ACM, New York), 319–320.Google Scholar
• FCC (2017) Broadcast incentive auction. Accessed January 23, 2025, https://www.fcc.gov/about-fcc/fcc-initiatives/incentive-auctions.Google Scholar
• Feldman M, Gravin N, Lucier B (2014) Combinatorial auctions via posted prices. Chekuri C, ed. Proc. 26th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 123–135.Google Scholar
• Ferraioli D, Penna P, Ventre C (2021) Two-way greedy: Algorithms for imperfect rationality. Feldman M, Fu H, Talgam-Cohen I, eds. Proc. Internat. Conf. Web Internet Econom. (Springer, Berlin, Heidelberg), 3–21.Google Scholar
• Ferreira MV, Weinberg SM (2020) Credible, truthful, and two-round (optimal) auctions via cryptographic commitments. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 683–712.Google Scholar
• Gkatzelis V, Markakis E, Roughgarden T (2017) Deferred-acceptance auctions for multiple levels of service. Daskalakis C, Babaioff M, Moulin H, eds. Proc. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 21–38.Google Scholar
• Gkatzelis V, Patel R, Pountourakis E, Schoepflin D (2021) Prior-free clock auctions for bidders with interdependent values. Caragiannis I, Hansen KA, eds. Proc. Algorithmic Game Theory 14th Internat. Sympos., Lecture Notes in Computer Science, vol. 12885 (Springer, Berlin, Heidelberg), 64–78.Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd Natl. Conf. Artificial Intelligence, vol. 1 (AAAI Press), 58–65.Google Scholar
• Hartline JD, Roughgarden T (2009) Simple versus optimal mechanisms. Chuang J, Fortnow L, Pu P, eds. Proc. 10th ACM Conf. Electronic Commerce (ACM, New York), 225–234.Google Scholar
• Huang Z, Mansour Y, Roughgarden T (2018) Making the most of your samples. SIAM J. Comput. 47(3):651–674.Crossref, Google Scholar
• Kagel JH, Harstad RM, Levin D (1987) Information impact and allocation rules in auctions with affiliated private values: A laboratory study. Econometrica 55(6):1275–1304.Crossref, Google Scholar
• Kaplan H, Naori D, Raz D (2022) Online weighted matching with a sample. Naor J (Seffi), Buchbinder N, eds. Proc. Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1247–1272.Google Scholar
• Kim A (2015) Welfare maximization with deferred acceptance auctions in reallocation problems. Bansal N, Finocchi I, eds. Algorithms-ESA (Springer, Berlin, Heidelberg), 804–815.Crossref, Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Karloff HJ, Pitassi T, eds. Proc. 44th Ann. ACM Sympos. Theory Comput. (ACM, New York), 123–136.Google Scholar
• Korte B, Hausmann D (1978) An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2:65–74.Crossref, Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probab. Related Topics 4:197–266.Google Scholar
• Li S (2017) Obviously strategy-proof mechanisms. Amer. Econom. Rev. 107(11):3257–3287.Crossref, Google Scholar
• Loertscher S, Marx LM (2020) Asymptotically optimal prior-free clock auctions. J. Econom. Theory 187:105030.Crossref, Google Scholar
• Lucier B (2017) An economic view of prophet inequalities. Sigecom Exchange 16(1):24–47.Crossref, Google Scholar
• Milgrom P, Segal I (2014) Deferred-acceptance auctions and radio spectrum reallocation. Babaioff M, Conitzer V, Easley DA, eds. Proc. ACM Conf. Econom. Comput. (ACM, New York), 185–186.Google Scholar
• Milgrom P, Segal I (2019) Clock auctions and radio spectrum reallocation. J. Political Econom. 128(1):1–31.Google Scholar
• Myerson RB (1981) Optimal auction design. Math. OR 6(1):58–73.Link, Google Scholar
• Rubinstein A (2016a) Beyond matroids: Secretary problem and prophet inequality with general constraints. Wichs D, Mansour Y, eds. Proc. 48th Ann. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 324–332.Google Scholar
• Rubinstein A (2016b) On the computational complexity of optimal simple mechanisms. Sudan M, ed. Proc. ACM Conf. Innovations Theoretical Comput. Sci. (ACM, New York), 21–28.Google Scholar
• Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Klein PN, ed. Proc. 28th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1671–1687.Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Vidick T, ed. Proc. 11th Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Waldern, Germany), 60:1–60:10.Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. Randall D, ed. Proc. 22nd Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 710–719.Google Scholar