Learning in Repeated Multiunit Pay-as-Bid Auctions

References

• Abbasi-yadkori Y, Pál D, Szepesvári C (2011) Improved algorithms for linear stochastic bandits. Shawe-Taylor J, Zemel R, Bartlett P, Pereira F, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 24 (Curran Associates, Inc., Red Hook, NY), 2312–2320.Google Scholar
• Aggarwal G, Badanidiyuru A, Mehta A (2019) Autobidding with constraints. Proc. 15th Internat. Conf. Web Internet Economics (Springer, Berlin), 17–30.Google Scholar
• Akbarpour M, Li S (2020) Credible auctions: A trilemma. Econometrica 88(2):425–467.Crossref, Google Scholar
• Audibert J-Y, Bubeck S, Lugosi G (2011) Minimax policies for combinatorial prediction games. Proc. 24th Annual Conf. Learn. Theory (JMLR, New York), 107–132.Google Scholar
• Ausubel LM (2004) An efficient ascending-bid auction for multiple objects. Amer. Econom. Rev. 94(5):1452–1475.Crossref, Google Scholar
• Ausubel LM, Cramton P (2006) Dynamic auctions in procurement. Handbook of Procurement (Cambridge University Press, Cambridge, UK), 220–246.Google Scholar
• Ausubel L, Milgrom P (2006) Chapter 1: The lovely but lonely Vickrey auction. Combinatorial Auctions (MIT Press, Cambridge, MA), 17–40.Google Scholar
• Ausubel LM, Cramton P, Pycia M, Rostek M, Weretka M (2014) Demand reduction and inefficiency in multi-unit auctions. Rev. Econom. Stud. 81(289):1366–1400.Crossref, Google Scholar
• Babaioff M, Immorlica N, Li Y, Lucier B (2023) Making auctions robust to aftermarkets. 14th Innovations Theoret. Comput. Sci. Conf. (ITCS 2023) (Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Wadern, Germany).Google Scholar
• Baisa B, Burkett J (2018) Large multi-unit auctions with a large bidder. J. Econom. Theory 174:1–15.Crossref, Google Scholar
• Balseiro S, Golrezaei N, Mahdian M, Mirrokni V, Schneider J (2023) Contextual bandits with cross-learning. Math. Oper. Res. 48(3):1607–1629.Link, Google Scholar
• Bergemann D, Brooks B, Morris S (2020) Countering the winner’s curse: Optimal auction design in a common value model. Theoretical Econom. 15(4):1399–1434.Crossref, 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
• Bigler J (2019) An update on first price auctions for Google Ad Manager. Accessed November 26, 2024, https://blog.google/products/ads-commerce/update-first-price-auctions-google-ad-manager.Google Scholar
• Binmore K, Swierzbinski J (2000) Treasury auctions: Uniform or discriminatory? Rev. Econom. Design 5:387–410.Crossref, Google Scholar
• Blum A, Mansour Y (2007) From external to internal regret. J. Machine Learn. Res. 8(47):1307–1324.Google Scholar
• Brânzei S, Derakhshan M, Golrezaei N, Han Y (2023) Learning and collusion in multi-unit auctions. Adv. Neural Inform. Processing Systems 36:22191–22225.Google Scholar
• Braverman M, Mao J, Schneider J, Weinberg M (2018) Selling to a no-regret buyer. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 523–538.Google Scholar
• Burkett J, Woodward K (2020) Uniform price auctions with a last accepted bid pricing rule. J. Econom. Theory 185:104954.Crossref, Google Scholar
• Cai Y, Daskalakis C (2017) Learning multi-item auctions with (or without) samples. 2017 IEEE 58th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 516–527.Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, MA).Crossref, Google Scholar
• Chen W, Wang Y, Yuan Y (2013) Combinatorial multi-armed bandit: General framework and applications. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learn., vol. 28 (PMLR), 151–159.Google Scholar
• Chu W, Li L, Reyzin L, Schapire R (2011) Contextual bandits with linear payoff functions. Gordon G, Dunson D, Dudík M, eds. Proc. 14th Internat. Conf. Artificial Intelligence Statist., vol. 15 (PMLR), 208–214.Google Scholar
• Cramton P (1998) Ascending auctions. Eur. Econom. Rev. 42(3):745–756.Crossref, Google Scholar
• Cramton P, Shoham Y, Steinberg R (2004) Combinatorial Auctions (University of Maryland, Department of Economics).Google Scholar
• Dani V, Hayes TP, Kakade SM (2008) Stochastic linear optimization under Bandit feedback. COLT, vol. 2, 3.Google Scholar
• de Keijzer B, Markakis E, Schäfer G, Telelis O (2013a) Inefficiency of standard multi-unit auctions. Bodlaender HL, Italiano GF, eds. Algorithms–ESA 2013 (Springer, Berlin), 385–396.Crossref, Google Scholar
• de Keijzer B, Markakis E, Schäfer G, Telelis O (2013b) On the inefficiency of standard multi-unit auctions. Preprint, submitted March 7, https://arxiv.org/abs/1303.1646.Google Scholar
• Deng X, Hu X, Lin T, Zheng W (2022) Nash convergence of mean-based learning algorithms in first price auctions. Proc. ACM Web Conf. (ACM, New York).Google Scholar
• Deng Y, Golrezaei N, Jaillet P, Cheuk Nam Liang J, Mirrokni V (2023) Multi-channel autobidding with budget and ROI constraints. Internat. Conf. Machine Learn. (PMLR, New York), 7617–7644.Google Scholar
• Deospotakis S, Ravi R, Sayedi A (2021) First-price auctions in online display advertising. J. Marketing Res. 58(5):888–907.Crossref, Google Scholar
• Derakhshan M, Golrezaei N, Leme RP (2022) Linear program-based approximation for personalized reserve prices. Management Sci. 68(3):1849–1864.Link, Google Scholar
• Derakhshan M, Pennock DM, Slivkins A (2021) Beating greedy for approximating reserve prices in multi-unit VCG auctions. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1099–1118.Google Scholar
• Dobzinski S, Nisan N (2007) Mechanisms for multi-unit auctions. Proc. 8th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 346–351.Google Scholar
• Dudík M, Haghtalab N, Luo H, Schapire RE, Syrgkanis V, Vaughan JW (2020) Oracle-efficient online learning and auction design. J. ACM 67(5):1–57.Google Scholar
• EEX (2023) EU ETS auctions. Accessed November 26, 2024, https://www.eex.com/en/markets/environmental-markets/eu-ets-auctions\#:∼:text=Bids\%20are\%20sorted\%20in\%20descending,selection\%20according\%20to\%20an\%20algorithm.Google Scholar
• Erbach G, Jensen L (2022) Fit for 55 package. EPRS, European Parliament.Google Scholar
• Fabra N, von der Fehr N-H, Harbord D (2006) Designing electricity auctions. RAND J. Econom. 37(1):23–46.Crossref, Google Scholar
• Federico G, Rahman D (2003) Bidding in an electricity pay-as-bid auction. J. Regulatory Econom. 24(2):175–211.Crossref, Google Scholar
• Feldman M, Lucier B, Nisan N (2016) Correlated and coarse equilibria of single-item auctions. Web Internet Econom. 12th Internat. Conf. WINE 2016 (Springer, Berlin, Heidelberg), 131–144.Google Scholar
• Foster DJ, Li Z, Lykouris T, Sridharan K, Tardos E (2016) Learning in games: Robustness of fast convergence. Proc. 30th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 4734–4742.Google Scholar
• Garbade KD, Ingber JF (2005) The Treasury auction process: Objectives, structure, and recent acquisitions. Current Issues Econom. Finance 11.Google Scholar
• Goldner K, Immorlica N, Lucier B (2020) Reducing inefficiency in carbon auctions with imperfect competition. 11th Innovations Theoret. Comput. Sci. Conf. (ITCS 2020) (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Golrezaei N, Jaillet P, Jason CNL (2023a) Incentive-aware contextual pricing with non-parametric market noise. Proc. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 9331–9361.Google Scholar
• Golrezaei N, Javanmard A, Mirrokni V (2021a) Dynamic incentive-aware learning: Robust pricing in contextual auctions. Oper. Res. 69(1):297–314.Link, Google Scholar
• Golrezaei N, Jaillet P, Jason CNL, Mirrokni V (2023b) Pricing against a budget and ROI constrained buyer. Proc. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 9282–9307.Google Scholar
• Golrezaei N, Lin M, Mirrokni V, Nazerzadeh H (2021b) Boosted second price auctions: Revenue optimization for heterogeneous bidders. Proc. 27th ACM SIGKDD Conf. Knowledge Discovery Data Mining, 447–457.Google Scholar
• Goulder LH, Schein AR (2013) Carbon taxes versus cap and trade: A critical review. Climate Change Econom. 4(3):1350010.Google Scholar
• Han Y, Weissman T, Zhou Z (2024) Optimal no-regret learning in repeated first-price auctions. Oper. Res., ePub ahead of print July 8, https://doi.org/10.1287/opre.2020.0282.Google Scholar
• Han Y, Zhou Z, Flores A, Ordentlich E, Weissman T (2020) Learning to bid optimally and efficiently in adversarial first-price auctions. Preprint, submitted July 9, https://arxiv.org/abs/2007.04568.Google Scholar
• Haoyu Z, Wei C (2020) Online second price auction with semi-bandit feedback under the non-stationary setting. Proc. Conf. AAAI Artificial Intelligence 34(04):6893–6900.Crossref, Google Scholar
• Heim S, Götz G (2021) Do pay-as-bid auctions favor collusion? Evidence from Germany’s market for reserve power. Energy Policy 155:112308.Crossref, Google Scholar
• Hortaçsu A, McAdams D (2010) Mechanism choice and strategic bidding in divisible good auctions: An empirical analysis of the Turkish Treasury auction market. J. Political Econom. 118(5):833–865.Crossref, Google Scholar
• Huang Z, Liu J, Wang X (2018) Learning optimal reserve price against non-myopic bidders. Preprint, submitted April 30, https://arxiv.org/abs/1804.11060.Google Scholar
• Kagel JH, Levin D (1986) The winner’s curse and public information in common value auctions. Amer. Econom. Rev. 76(5):894–920.Google Scholar
• Kanoria Y, Nazerzadeh H (2014) Dynamic reserve prices for repeated auctions: Learning from bids. Proc. 10th Internat. Conf. Web Internet Econom., vol. 8877 (Springer, Berlin), 232.Crossref, Google Scholar
• Kleinberg R, Leighton T (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci., 594–605.Google Scholar
• Koolen WM, Warmuth MK, Kivinen J (2010) Hedging structured concepts. Proc. Conf. Learn. Theory, vol. 23, 93–105.Google Scholar
• Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Littlestone N, Warmuth MK (1994) The weighted majority algorithm. Inform. Comput. 108(2):212–261.Crossref, Google Scholar
• Lucier B, Pattathil S, Slivkins A, Zhang M (2023) Autobidders with budget and ROI constraints: Efficiency, regret, and pacing dynamics. Preprint, submitted January 30, https://arxiv.org/abs/2301.13306.Google Scholar
• Mohri M, Medina AM (2013) Learning theory and algorithms for revenue optimization in second-price auctions with reserve. Preprint, submitted October 21, https://arxiv.org/abs/1310.5665.Google Scholar
• Mohri M, Medina AM (2016) Learning algorithms for second-price auctions with reserve. J. Machine Learn. Res. 17(1):2632–2656.Google Scholar
• Morgenstern J, Roughgarden T (2016) Learning simple auctions. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Annual Conf. Learn. Theory, vol. 49 (PMLR, New York), 1298–1318.Google Scholar
• Nautz D (1995) Optimal bidding in multi-unit auctions with many bidders. Econom. Lett. 48(3):301–306.Crossref, Google Scholar
• Nedelec T, El Karoui N, Perchet V (2019) Learning to bid in revenue-maximizing auctions. Preprint, submitted February 27, https://arxiv.org/abs/1902.10427.Google Scholar
• Niazadeh R, Golrezaei N, Wang J, Susan F, Badanidiyuru A (2023) Online learning via offline greedy algorithms: Applications in market design and optimization. Management Sci. 69(7):3797–3817.Link, Google Scholar
• Nyborg KG, Sundaresan S (1996) Discriminatory vs. uniform Treasury auctions: Evidence from when-issued transactions. J. Financial Econom. 42(1):63–104.Crossref, Google Scholar
• Pesendorfer M (2000) A study of collusion in first-price auctions. Rev. Econom. Stud. 67(3):381–411.Crossref, Google Scholar
• Porter D, Rassenti S, Roopnarine A, Smith V (2003) Combinatorial auction design. Proc. Natl. Acad. Sci. USA 100(19):11153–11157.Crossref, Google Scholar
• Pycia M, Woodward K (2021) Auctions of homogeneous goods: A case for pay-as-bid. Preprint, submitted June 15, https://dx.doi.org/10.2139/ssrn.3865760.Google Scholar
• Roughgarden T (2012) The price of anarchy in games of incomplete information. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 862–879.Google Scholar
• Roughgarden T, Wang JR (2016) Minimizing regret with multiple reserves. Proc. ACM Conf. Econom. Comput., 601–616.Google Scholar
• Roughgarden T, Syrgkanis V, Tardos É (2017) The price of anarchy in auctions. J. Artificial Intelligence Res. 59(1):59–101.Crossref, Google Scholar
• Schmalensee R, Stavins RN (2017) Lessons learned from three decades of experience with cap-and-trade. Rev. Environment. Econom. Policy 11(1):59–79.Crossref, Google Scholar
• Susan F, Golrezaei N, Schrijvers O (2023) Multi-platform budget management in ad markets with non-IC auctions. Preprint, submitted June 12, https://arxiv.org/abs/2306.07352.Google Scholar
• Syrgkanis V, Tardos E (2012) Composable and efficient mechanisms. Preprint, submitted November 6, https://doi.org/10.48550/arXiv.1211.1325.Google Scholar
• Syrgkanis V, Agarwal A, Luo H, Schapire RE (2015) Fast convergence of regularized learning in games. Preprint, submitted July 2, https://doi.org/10.48550/arXiv.1507.00407.Google Scholar
• Takimoto E, Warmuth MK (2003) Path kernels and multiplicative updates. J. Machine Learn. Res. 4:773–818.Google Scholar
• Tierney S, Schatzki T, Mukerji R (2008) Uniform-pricing vs. pay-as-bid in wholesale electricity markets: Does it make a difference? https://kylewoodward.com/blog-data/pdfs/references/tierney+schatzki+mukerji-new-york-iso-2008A.pdf.Google Scholar
• Tsybakov AB (2008) Introduction to Nonparametric Estimation, 1st ed. (Springer Publishing Company, Berlin).Google Scholar
• U.S. Environmental Protection Agency (2023) Supplementary material for the regulatory impact analysis for the final rulemaking, “standards of performance for new, reconstructed, and modified sources and emissions guidelines for existing sources: Oil and natural gas sector climate review.” EPA report on the Social Cost of Greenhouse Gases: Estimates Incorporating Recent Scientific Advances, U.S. Environmental Protection Agency, Washington, DC.Google Scholar
• Van Parys BPG, Golrezaei N (2024) Optimal learning for structured bandits. Management Sci. 70(6):3951–3998.Google Scholar
• Weng Z, Ma Z, Xie Y, Cheng C (2022) Effect of China’s carbon market on the promotion of green technological innovation. J. Clean Production 373:133820.Google Scholar
• Zimin A, Neu G (2013) Online learning in episodic Markovian decision processes by relative entropy policy search. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Inc., Red Hook, NY), 1583–1591.Google Scholar