Online Optimization Algorithms in Repeated Price Competition: Equilibrium Learning and Algorithmic Collusion

References

• Abada I, Lambin X (2023) Artificial intelligence: Can seemingly collusive outcomes be avoided? Management Sci. 69(9):5042–5065.Link, Google Scholar
• Abada I, Lambin X, Tchakarov N (2024a) Collusion by mistake: Does algorithmic sophistication drive supra-competitive profits? Eur. J. Oper. Res. 318(3):927–953.Crossref, Google Scholar
• Abada I, Harrington JE Jr, Lambin X, Meylahn JM (2024b) Algorithmic collusion: Where are we and where should we be going? Preprint, submitted August 7, https://doi.org/10.2139/ssrn.4891033.Google Scholar
• Aguiar-Curry C, Ward C (2025) AB-325 Cartwright Act: Violations. California Legislative Information, https://leginfo.legislature.ca.gov/faces/billNavClient.xhtml?bill_id=202520260AB325.Google Scholar
• Anagnostides I, Panageas I, Farina G, Sandholm T (2023) On the convergence of no-regret learning dynamics in time-varying games. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 16367–16405.Crossref, Google Scholar
• Asker J, Fershtman C, Pakes A (2024) The impact of artificial intelligence design on pricing. J. Econom. Management Strategy 33(2):276–304.Crossref, Google Scholar
• Auer P, Cesa-Bianchi N, Freund Y, Schapire RE (2002) The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32(1):48–77.Crossref, Google Scholar
• Auer P, Cesa-Bianchi N, Freund Y, Shapire RE (1995) Gambling in a rigged casino: The adversarial multi-armed bandit problem. Proc. IEEE 36th Annual Foundations Comput. Sci. (IEEE Computer Society, Washington, DC).Google Scholar
• Aumann RJ (1987) Correlated equilibrium as an expression of Bayesian rationality. Econometrica 55(1):1–18. Crossref, Google Scholar
• Bailey JP, Piliouras G (2018) Multiplicative weights update in zero-sum games. Tardos E, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York).Google Scholar
• Ballard D, Costello K, Lo M, Scarborough M (2025) California looks to crack down on algorithmic pricing and clarify antitrust pleading standards. JD Supra, https://www.jdsupra.com/legalnews/california-looks-to-crack-down-on-3793901/.Google Scholar
• Bauer J, Jannach D (2018) Optimal pricing in e-commerce based on sparse and noisy data. Decision Support Systems 106:53–63.Crossref, Google Scholar
• Bernheim BD (1984) Rationalizable strategic behavior. Econometrica 52(4):1007–1028.Crossref, Google Scholar
• Bertrand J (1883a) Review of “Theorie mathematique de la richesse sociale” and of “Recherches sur les principles mathematiques de la theorie des richesses. J. De Savants 67:499.Google Scholar
• Bertrand J (1883b) Théorie mathématique de la richesse sociale. J. Des Savants 67(1883):499–508.Google Scholar
• Bichler M, Fichtl M, Oberlechner M (2023) Computing Bayes–Nash equilibrium strategies in auction games via simultaneous online dual averaging. Oper. Res. 73(2):1102–1127.Link, Google Scholar
• Brandenburger A, Dekel E (1987) Rationalizability and correlated equilibria. Econometrica 55(6):1391–1402.Crossref, Google Scholar
• Braverman M, Mao J, Schneider J, Weinberg M (2018) Selling to a no-regret buyer. Tardos E, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York).Google Scholar
• Brown GW (1951) Iterative solution of games by fictitious play. Activity Anal. Production Allocation 13(1):374–376.Google Scholar
• Brown ZY, MacKay A (2023) Competition in pricing algorithms. Amer. Econom. J. Microeconom. 15(2):109–156.Crossref, Google Scholar
• Bubeck S (2011) Introduction to online optimization. Lecture notes, Princeton University, Princeton, NJ. Google Scholar
• Calvano E, Calzolari G, Denicoló V, Pastorello S (2021b) Algorithmic collusion with imperfect monitoring. Internat. J. Indust. Organ. 79:102712.Crossref, Google Scholar
• Calvano E, Calzolari G, Denicolò V, Pastorello S (2019) Algorithmic pricing what implications for competition policy? Rev. Industrial Organ. 55(1):155–171.Crossref, Google Scholar
• Calvano E, Calzolari G, Denicolò V, Pastorello S (2020a) Artificial intelligence, algorithmic pricing, and collusion. Amer. Econom. Rev. 110(10):3267–3297.Crossref, Google Scholar
• Calvano E, Calzolari G, Denicolò V, Pastorello S (2021a) Algorithmic Collusion, Genuine and Spurious. Social Science Research Network.Google Scholar
• Calzolari G, Hanspach P (2024) Pricing algorithms out of the box: A study of the repricing industry. Preprint, submitted July 1, http://dx.doi.org/10.2139/ssrn.4871394.Google Scholar
• Calvano E, Calzolari G, Denicolò V, Harrington JE, Pastorello S (2020b) Protecting consumers from collusive prices due to AI. Science (1979) 370(6520):1040–1042.Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chen L, Mislove A, Wilson C (2011) An empirical analysis of algorithmic pricing on Amazon marketplace. Bourdeau J, Hendler JA, Nkambou Nkambou R, Horrocks I, Zhao BY, eds. Proc. 25th Internat. Conf. World Wide Web (International World Wide Web Conferences Steering Committee, Geneva, CHE).Google Scholar
• Conlon C, Gortmaker J (2025) PyBLP.Google Scholar
• Cournot AA (1838) Recherches Sur Les Principes Mathématiques De La Théorie Des Richesses (L. Hachette).Google Scholar
• Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• den Boer AV (2015) Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys Oper. Res. Management Sci. 20(1):1–18.Crossref, Google Scholar
• den Boer AV (2023) Algorithmic collusion: A mathematical definition and research agenda for the OR/MS community. Preprint, submitted November 7, https://dx.doi.org/10.2139/ssrn.5012923.Google Scholar
• den Boer AV, Meylahn JM, Schinkel MP (2024) Artificial collusion: Examining supracompetitive pricing by Q-learning algorithms. Preprint, submitted September 13, http://dx.doi.org/10.2139/ssrn.4213600.Google Scholar
• Deng S, Schiffer M, Bichler M (2024) On the existence of algorithmic collusion in dynamic pricing with deep reinforcement learning. Flath CM, Gust G, Thiesse F, Winkelmann A, eds. Wirtschaftsinformatik 2024 Proc. (Association for Information Systems (AIS), Atlanta).Google Scholar
• Deng X, Hu X, Lin T, Zheng W (2022) Nash convergence of mean-based learning algorithms in first price auctions. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. Proc. ACM Web Conf. 2022 (Association for Computing Machinery, New York).Google Scholar
• Douglas C, Provost F, Sundararajan A (2024) Naive algorithmic collusion: When do bandit learners cooperate and when do they compete? Susarla A, Chau M, Hinz O, eds. ICIS 2024 Proc. (Association for Information Systems (AIS), Atlanta).Google Scholar
• Elreedy D, Atiya AF, Shaheen SI (2021) Novel pricing strategies for revenue maximization and demand learning using an exploration–exploitation framework. Soft Comput. 25(17):11711–11733.Crossref, Google Scholar
• Eschenbaum N, Mellgren F, Zahn P (2022) Robust algorithmic collusion. Preprint, submitted January 2, https://arxiv.org/abs/2201.00345.Google Scholar
• Feng Z, Guruganesh G, Liaw C, Mehta A, Sethi A (2021) Convergence analysis of no-regret bidding algorithms in repeated auctions. Proc. AAAI Conf. Artificial Intelligence 35(6):5399–5406.Crossref, Google Scholar
• Foster D P, Vohra R V (1997) Calibrated learning and correlated equilibrium. Games Econ. Behav. 21(1):40–55.Crossref, Google Scholar
• Foster DP, Vohra R (1999) Regret in the on-line decision problem. Games Econom. Behav. 29(1):7–35.Crossref, Google Scholar
• Fudenberg D, Levine DK (1999) The Theory of Learning in Games, MIT Press Series on Economic Learning and Social Evolution, 2nd ed., vol. 2 (MIT Press, Cambridge, MA).Google Scholar
• Fudenberg D, Tirole J (1991) Game Theory (MIT Press, Cambridge, MA).Google Scholar
• Goyal V, Li S, Mehrotra S (2023) Learning to price under competition for multinomial logit demand. Preprint, submitted October 10, https://doi.org/10.2139/ssrn.4572453.Google Scholar
• Hansen KT, Misra K, Pai MM (2021) Frontiers: Algorithmic collusion: Supra-competitive prices via independent algorithms. Marketing Sci. 40(1):1–12.Link, Google Scholar
• Harrington JE (2018) Developing competition law for collusion by autonomous artificial agents. J. Competition Law Econom. 14(3):331–363.Crossref, Google Scholar
• Hart S, Mas-Colell A (2003) Uncoupled dynamics do not lead to Nash equilibrium. Amer. Econom. Rev. 93(5):1830–1836.Crossref, Google Scholar
• Hart S, Mas-Colell A (2006) Stochastic uncoupled dynamics and Nash equilibrium. Games Econom. Behav. 57(2):286–303.Crossref, Google Scholar
• Hartline J (2026) Clarification of ‘Algorithmic collusion without threats’. Preprint, submitted February 15, https://arxiv.org/abs/2602.22232.Google Scholar
• Hartline JD, Long S, Zhang C (2024) Regulation of algorithmic collusion. Weitzner DJ, Yoo CS, Canetti R, eds. Proc. 2024 Sympos. Comput. Sci. Law (Association for Computing Machinery, New York).Google Scholar
• Heliou A, Cohen J, Mertikopoulos P (2017) Learning with bandit feedback in potential games. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Jann O, Schottmüller C (2015) Correlated equilibria in homogeneous good Bertrand competition. J. Math. Econom. 57:31–37.Crossref, Google Scholar
• Jin C, Liu Q, Wang Y, Yu T (2024) V-Learning—A simple, efficient, decentralized algorithm for multiagent reinforcement learning. Math. Oper. Res. 49(4):2295–2322.Link, Google Scholar
• Johnson JP, Rhodes A, Wildenbeest M (2023) Platform design when sellers use pricing algorithms. Econometrica 91(5):1841–1879.Crossref, Google Scholar
• Kastius A, Schlosser R (2022) Dynamic pricing under competition using reinforcement learning. J. Revenue Pricing Management 21(1):50–63.Crossref, Google Scholar
• Klein T (2021) Autonomous algorithmic collusion: Q-learning under sequential pricing. RAND J. Econom. 52(3):538–558.Crossref, Google Scholar
• Kolpin V (2009) Strict dominance solvability without equilibrium. Econom. Bull. 29(1):51–55. Google Scholar
• Kolumbus Y, Nisan N (2022) Auctions between regret-minimizing agents. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. Proc. ACM Web Conf. 2022 (Association for Computing Machinery, New York).Google Scholar
• Lambin X (2024) Less than meets the eye: Simultaneous experiments as a source of algorithmic seeming collusion. Preprint, submitted July 5, https://doi.org/10.2139/ssrn.4498926.Google Scholar
• Levin J (2006) Solution concepts. Notes. https://web.stanford.edu/∼jdlevin/Econ%20286/Solution%20Concepts.pdf.Google Scholar
• Loots T, den Boer AV (2023) Data‐driven collusion and competition in a pricing duopoly with multinomial logit demand. Production Oper. Management 32(4):1169–1186.Crossref, Google Scholar
• Mertikopoulos P, Zhou Z (2019) Learning in games with continuous action sets and unknown payoff functions. Math. Programming 173(1–2):465–507.Crossref, Google Scholar
• Mertikopoulos P, Hsieh YP, Cevher V (2024) A unified stochastic approximation framework for learning in games. Math. Programming 203(1):559–609.Crossref, Google Scholar
• Mertikopoulos P, Papadimitriou C, Piliouras G (2018) Cycles in adversarial regularized learning. Proc. 29th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2703–2717.Google Scholar
• Meylahn JM, den Boer AV (2022) Learning to collude in a pricing duopoly. Manufacturing Service Oper. Management 24(5):2577–2594.Link, Google Scholar
• Milgrom P, Roberts J (1990) Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica 1255–1277.Crossref, Google Scholar
• Milgrom P, Roberts J (1991) Adaptive and sophisticated learning in normal form games. Games Econom. Behav. 3(1):82–100.Crossref, Google Scholar
• Milionis J, Papadimitriou C, Piliouras G, Spendlove K (2022) Nash, conley, and computation: Impossibility and incompleteness in game dynamics. Preprint, submitted March 26, https://arxiv.org/abs/2203.14129.Google Scholar
• Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• Mueller JW, Syrgkanis V, Taddy M (2019) Low-rank bandit methods for high-dimensional dynamic pricing. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY).Google Scholar
• OECD (2017) Algorithms and collusion: Competition policy in the digital age. Technical report, OECD, Paris.Google Scholar
• Palaiopanos G, Panageas I, Piliouras G (2017) Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Pearce DG (1984) Rationalizable strategic behavior and the problem of perfection. Econometrica 52(4):1029–1050.Crossref, Google Scholar
• Qu J (2024) Survey of dynamic pricing based on Multi-Armed Bandit algorithms. ACE 37(1):160–165. Crossref, Google Scholar
• Rana R, Oliveira FS (2014) Real-time dynamic pricing in a non-stationary environment using model-free reinforcement learning. Omega 47:116–126.Crossref, Google Scholar
• Rothschild M (1974) A two-armed bandit theory of market pricing. J. Econom. Theory 9(2):185–202.Crossref, Google Scholar
• Sanders JB, Farmer JD, Galla T (2018) The prevalence of chaotic dynamics in games with many players. Sci. Rep. 8(1):1–13.Crossref, Google Scholar
• Sandholm WH (2010) Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution (MIT Press, Cambridge, MA).Google Scholar
• Schaefer M (2022) On the emergence of cooperation in the repeated prisoner’s dilemma. Preprint, submitted November 24, https://arxiv.org/abs/2211.15331.Google Scholar
• Shalev-Shwartz S (2011) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Crossref, Google Scholar
• Shapley L (1964) Some topics in two-person games. Adv. Game Theory 52:1–29. Google Scholar
• Swenson B, Murray R, Kar S (2018) On best-response dynamics in potential games. SIAM J. Control Optim. 56(4):2734–2767.Crossref, Google Scholar
• Taywade K, Goldsmith J, Harrison B, Bagh A (2023) Multi-armed bandit algorithms for cournot games. Research Square, https://www.researchsquare.com/article/rs-2928787/v1.Google Scholar
• Topkis DM (1979) Equilibrium points in nonzero-sum n-person submodular games. SIAM J. Control Optim. 17(6):773–787.Crossref, Google Scholar
• Topkis DM (1998) Supermodularity and Complementarity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Trovo F, Paladino S, Restelli M, Gatti N (2015) Multi-armed bandit for pricing. Proc. 12th Eur. Workshop Reinforcement Learn.Google Scholar
• Viossat Y, Zapechelnyuk A (2013) No-regret dynamics and fictitious play. J. Econom. Theory 148(2):825–842.Crossref, Google Scholar
• Vives X (2001) Oligopoly Pricing: Old Ideas and New Tools (MIT Press, Cambridge, MA).Google Scholar
• Vlatakis-Gkaragkounis EV, Flokas L, Lianeas T, Mertikopoulos P, Piliouras G (2020) No-regret learning and mixed Nash equilibria: They do not mix. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 1380–1391. Google Scholar
• Waltman L, Kaymak U (2008) Learning agents in a Cournot oligopoly model. J. Econom. Dynamic Control 32(10):3275–3293.Crossref, Google Scholar
• Wang Y, Kong D, Bai Y, Jin C (2022) Learning rationalizable equilibria in multiplayer games. Preprint, submitted October 20, https://arxiv.org/abs/2210.11402.Google Scholar
• Wu J (2008) Correlated equilibrium of bertrand competition. Papadimitriou C, Zhang S, eds. Internet and Network Economics (Springer, Berlin, Heidelberg), 166–177.Crossref, Google Scholar
• Yang Y, Lee Y-C, Chen P-A (2024) Competitive demand learning: A noncooperative pricing algorithm with coordinated price experimentation. Production Oper. Management 33(1):48–68. Google Scholar
• Young HP (2010) Strategic Learning and Its Limits (Oxford University Press, Oxford, UK).Google Scholar