Quantal Correlated Equilibrium in Normal Form Games
Authors: 
Jakub Černý, 
Bo An, Allan N. ZhangAuthors Info & Claims
Pages 210 - 239
Abstract
Correlated equilibrium is an established solution concept in game theory describing a situation when players condition their strategies on external signals produced by a correlation device. In recent years, the concept has begun gaining traction also in general artificial intelligence because of its suitability for studying coordinated multi-agent systems. Yet the original formulation of correlated equilibrium assumes entirely rational players and hence fails to capture the subrational behavior of human decision-makers. We investigate the analogue of quantal response for correlated equilibrium, which is among the most commonly used models of bounded rationality. We coin the solution concept the quantal correlated equilibrium and study its relation to quantal response and correlated equilibria. The definition corroborates with prior conception as every quantal response equilibrium is a quantal correlated equilibrium, and correlated equilibrium is its limit as quantal responses approach the best response. We prove the concept remains PPAD-hard but searching for an optimal correlation device is beneficial for the signaler. To this end, we introduce a homotopic algorithm that simultaneously traces the equilibrium and optimizes the signaling distribution. Empirical results on one structured and one random domain show that our approach is sufficiently precise and several orders of magnitude faster than a state-of-the-art non-convex optimization solver.
References
[1]
Eugene L Allgower and Kurt Georg. 2012. Numerical continuation methods: an introduction. Vol. 13. Springer Science & Business Media.
[2]
Bo An, Fernando Ordó nez, Milind Tambe, Eric Shieh, Rong Yang, Craig Baldwin, Joseph DiRenzo III, Kathryn Moretti, Ben Maule, and Garrett Meyer. 2013. A deployed quantal response-based patrol planning system for the US Coast Guard. Interfaces, Vol. 43, 5 (2013), 400--420.
[3]
Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. 2008. On the value of correlation. Journal of Artificial Intelligence Research, Vol. 33 (2008), 575--613.
[4]
Robert Aumann. 1974. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, Vol. 1, 1 (1974), 67--96.
[5]
Robert J Aumann. 1987. Correlated equilibrium as an expression of Bayesian rationality. Econometrica: Journal of the Econometric Society (1987), 1--18.
[6]
Mordecai Avriel. 2003. Nonlinear programming: analysis and methods .Courier Corporation.
[7]
Yu Bai and Chi Jin. 2020. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning. PMLR, 551--560.
[8]
Anjon Basak, Jakub Cerný, Marcus Gutierrez, Shelby Curtis, Charles Kamhoua, Daniel Jones, Branislav Bosanský, and Christopher Kiekintveld. 2018. An initial study of targeted personality models in the FlipIt game. In International Conference on Decision and Game Theory for Security. Springer, 623--636.
[9]
Adi Ben-Israel and Thomas NE Greville. 2003. Generalized inverses: theory and applications. Vol. 15. Springer Science & Business Media.
[10]
Noam Brown and Tuomas Sandholm. 2018. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, Vol. 359, 6374 (2018), 418--424.
[11]
Noam Brown and Tuomas Sandholm. 2019. Superhuman AI for multiplayer poker. Science, Vol. 365, 6456 (2019), 885--890.
[12]
Colin F Camerer. 2011. Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press.
[13]
Ozan Candogan and Kimon Drakopoulos. 2020. Optimal signaling of content accuracy: Engagement vs. misinformation. Operations Research, Vol. 68, 2 (2020), 497--515.
[14]
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. 2020. No-regret learning dynamics for extensive-form correlated equilibrium. In Conference on Neural Information Processing Systems (NeurIPS).
[15]
Jakub vCerný, Viliam Lisý, Branislav Boanský, and Bo An. 2020. Dinkelbach-type algorithm for computing Quantal Stackelberg equilibrium. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, Christian Bessiere (Ed.). International Joint Conferences on Artificial Intelligence Organization, 246--253.
[16]
Jakub vCerný, Viliam Lisý, Branislav Boanský, and Bo An. 2021. Computing Quantal Stackelberg equilibrium in extensive-form games. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, 6 (May 2021), 5260--5268.
[17]
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput., Vol. 39, 1 (2009), 195--259.
[18]
Amrita Dhillon and Jean Francc ois Mertens. 1996. Perfect correlated equilibria. Journal of Economic Theory, Vol. 68, 2 (1996), 279--302.
[19]
Fei Fang, Thanh H Nguyen, Rob Pickles, Wai Y Lam, Gopalasamy R Clements, Bo An, Amandeep Singh, Brian C Schwedock, Milind Tambe, and Andrew Lemieux. 2017. PAWS -- A deployed game-theoretic application to combat poaching. AI Magazine (2017).
[20]
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. 2021 a. Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results. In International Conference on Machine Learning.
[21]
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. 2019. Online convex optimization for sequential decision processes and extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 1917--1925.
[22]
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. 2021 b. Better regularization for sequential decision spaces: Fast convergence rates for Nash, correlated, and team equilibria. In ACM Conference on Economics and Computation.
[23]
Francc oise Forges. 1986. An approach to communication equilibria. Econometrica, Vol. 54, 6 (1986), 1375--85.
[24]
Francc oise Forges. 2020. Correlated equilibria and communication in games. Complex Social and Behavioral Systems: Game Theory and Agent-Based Models (2020), 107--118.
[25]
CB Garcia and WI Zangwill. 1981. Pathways to Solutions, Fixed Points, and Equilibria.
[26]
K Georg. 1983. A note on stepsize control for numerical curve following. In Homotopy methods and global convergence. Springer, 145--154.
[27]
Gerd Gigerenzer and Daniel G Goldstein. 1996. Reasoning the fast and frugal way: Models of bounded rationality. Psychological Review, Vol. 103, 4 (1996), 650.
[28]
Jacob K Goeree, Charles A Holt, and Thomas R Palfrey. 2010. Quantal response equilibria. In Behavioural and Experimental Economics. Springer, 234--242.
[29]
Jacob K Goeree, Charles A Holt, and Thomas R Palfrey. 2016. Quantal Response Equilibrium. Princeton University Press.
[30]
Jeremy R Gray. 1999. A bias toward short-term thinking in threat-related negative emotional states. Personality and Social Psychology Bulletin, Vol. 25, 1 (1999), 65--75.
[31]
Philip A Haile, Ali Hortacc su, and Grigory Kosenok. 2008. On the empirical content of quantal response equilibrium. American Economic Review, Vol. 98, 1 (2008), 180--200.
[32]
Albert Xin Jiang, Kevin Leyton-Brown, and Navin AR Bhat. 2011. Action-graph games. Games and Economic Behavior, Vol. 71, 1 (2011), 141--173.
[33]
Albert Xin Jiang, Ariel D Procaccia, Yundi Qian, Nisarg Shah, and Milind Tambe. 2013. Defender (mis) coordination in security games. In Twenty-Third International Joint Conference on Artificial Intelligence.
[34]
Michael Johanson and Michael Bowling. 2009. Data biased robust counter strategies. In Artificial Intelligence and Statistics. 264--271.
[35]
Daniel Kahneman and Amos Tversky. 2013. Prospect theory: An analysis of decision under risk. In Handbook of the Fundamentals of Financial Decision Making: Part I. World Scientific, 99--127.
[36]
Madasamy Kaliappan and Balasubramanian Paramasivan. 2015. Enhancing secure routing in mobile ad hoc networks using a dynamic bayesian signalling game model. Computers & Electrical Engineering, Vol. 41 (2015), 301--313.
[37]
Harvey E Lapan and Todd Sandler. 1993. Terrorism and signalling. European Journal of Political Economy, Vol. 9, 3 (1993), 383--397.
[38]
Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. 2021. Exploration-exploitation in multi-agent competition: Convergence with bounded rationality. Advances in Neural Information Processing Systems, Vol. 34 (2021).
[39]
Chun Kai Ling, Fei Fang, and J Zico Kolter. 2018. What game are we playing? End-to-end learning in normal and extensive form games. In Proceedings of the 27th International Joint Conference on Artificial Intelligence. 396--402.
[40]
Naresh K Malhotra. 1982. Information load and consumer decision making. Journal of Consumer Research, Vol. 8, 4 (1982), 419--430.
[41]
Alberto Marchesi and Nicola Gatti. 2021. Trembling-hand perfection and correlation in sequential games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5566--5574.
[42]
Richard D McKelvey, Andrew M McLennan, and Theodore L Turocy. 2006. Gambit: Software tools for game theory. (2006).
[43]
Richard D. McKelvey and Thomas R. Palfrey. 1995. Quantal response equilibria for normal form games. Games and Economic Behavior, Vol. 10, 1 (1995), 6--38.
[44]
Richard D McKelvey and Thomas R Palfrey. 1998. Quantal response equilibria for extensive form games. Experimental Economics, Vol. 1, 1 (1998), 9--41.
[45]
Panayotis Mertikopoulos and William H Sandholm. 2016. Learning in games via reinforcement and regularization. Mathematics of Operations Research, Vol. 41, 4 (2016), 1297--1324.
[46]
Panayotis Mertikopoulos and Zhengyuan Zhou. 2019. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, Vol. 173, 1 (2019), 465--507.
[47]
David Milec, Jakuberný, Viliam Lisý, and Bo An. 2021. Complexity and algorithms for exploiting quantal opponents in large two-player games. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, 6 (May 2021), 5575--5583.
[48]
Matvej Moravcík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. 2017. DeepStack: Expert-level artificial intelligence in no-limit poker. Science (2017).
[49]
Anna Nagurney. 2021. Supply chain game theory network modeling under labor constraints: Applications to the Covid-19 pandemic. European Journal of Operational Research, Vol. 293, 3 (2021), 880--891.
[50]
John F. Nash. 1951. Non-Cooperative Games. Annals of Mathematics, Vol. 54, 2 (1951).
[51]
Thanh Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe. 2013. Analyzing the effectiveness of adversary modeling in security games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 27. 718--724.
[52]
Jiang Rong, Tao Qin, Bo An, and Tie-Yan Liu. 2016. Modeling bounded rationality for sponsored search auctions. In Proceedings of the Twenty-second European Conference on Artificial Intelligence. 515--523.
[53]
Reinhard Selten. 1975. Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, Vol. 4 (1975).
[54]
Wen Jun Tan, Allan N Zhang, and Wentong Cai. 2019. A graph-based model to measure structural redundancy for supply chain resilience. International Journal of Production Research, Vol. 57, 20 (2019), 6385--6404.
[55]
Theodore L Turocy. 2005. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, Vol. 51, 2 (2005), 243--263.
[56]
Theodore L Turocy. 2010. Computing sequential equilibria using agent quantal response equilibria. Economic Theory, Vol. 42, 1 (2010), 255--269.
[57]
Kai Wang, Lily Xu, Andrew Perrault, Michael K Reiter, and Milind Tambe. 2021. Coordinating followers to reach better equilibria: End-to-end gradient descent for Stackelberg games. arXiv preprint arXiv:2106.03278 (2021).
[58]
Rong Yang, Fernando Ordonez, and Milind Tambe. 2012. Computing optimal strategy against quantal response in security games. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2. 847--854.
[59]
Sisi Yin, Tatsushi Nishi, and Ignacio E Grossmann. 2015. Optimal quantity discount coordination for supply chain optimization with one manufacturer and multiple suppliers under demand uncertainty. The International Journal of Advanced Manufacturing Technology, Vol. 76, 5--8 (2015), 1173--1184.
[60]
Youzhi Zhang, Bo An, and Jakub Cerný. 2021. Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5813--5821.
Index Terms
- Quantal Correlated Equilibrium in Normal Form Games
Recommendations
Modeling Bounded Rationality in Capacity Allocation Games with the Quantal Response Equilibrium
We consider a supply chain with a single supplier and two retailers. The retailers choose their orders strategically, and if their orders exceed the supplier's capacity, quantities are allocated proportionally to the orders. We experimentally study the ...
Computing Quantal Response Equilibrium for Sponsored Search Auctions
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent SystemsSponsored search auctions (SSAs) have attracted much research attention in recent years and different equilibrium concepts have been studied to understand advertisers' behaviors. However, the assumption that bidders are perfectly rational in these ...
Testing the foundations of quantal response equilibrium
SBP'13: Proceedings of the 6th international conference on Social Computing, Behavioral-Cultural Modeling and PredictionQuantal response equilibrium (QRE) has become a popular alternative to the standard Nash equilibrium concept in game theoretic applications. It is well known that human subjects do not regularly choose Nash equilibrium strategies. It has been ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
1269 pages
ISBN:9781450391504
DOI:10.1145/3490486
- General Chair:
- David M. Pennock,
- Program Chairs:
- Ilya Segal,
- Sven Seuken
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Ministry of Education, Singapore
Conference
EC '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 104Total Downloads
- Downloads (Last 12 months)24
- Downloads (Last 6 weeks)1
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in