More Web Proxy on the site http://driver.im/

research-article

Computing Optimal Ex Ante Correlated Equilibria in Two-Player Sequential Games

Authors:

Stefano Coniglio,

Nicola GattiAuthors Info & Claims

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

Pages 909 - 917

Published: 08 May 2019 Publication History

Abstract

We investigate the computation of equilibria in extensive-form games when ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by hardness results on normal-form correlated equilibria, we investigate whether it is possible to compute normal-form coarse correlated equilibria efficiently. We show that an optimal (e.g., social welfare maximizing) normal-form coarse correlated equilibrium can be computed in polynomial time in two-player games without chance moves, and that in general multi-player games (including two-player games with chance) the problem is NP-hard. For the two-player case, we provide both a polynomial-time algorithm based on the ellipsoid method and a column generation algorithm based on the simplex method which can be efficiently applied in practice. We also show that the pricing oracle employed in the column generation procedure can be extended to games with two players and chance.

References

[1]

E. Amaldi, S. Coniglio, and S. Gualandi. 2010. Improving Cutting Plane Generation with 0--1 Inequalities by Bi-criteria Separation. In Experimental Algorithms, Paola Festa (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 266--275.

Digital Library

[2]

E. Amaldi, S. Coniglio, and S. Gualandi. 2014. Coordinated cutting plane generation via multi-objective separation. Mathematical Programming, Vol. 143, 1 (2014), 87--110.

[3]

R. Aumann. 1974. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, Vol. 1, 1 (1974), 67--96.

[4]

S. Barman and K. Ligett. 2015. Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard. In Proceedings of the ACM Conference on Economics and Computation (EC). 815--816.

Digital Library

[5]

B. Basilico, A. Celli, G. De Nittis, and N. Gatti. 2017a. Coordinating Multiple Defensive Resources in Patrolling Games with Alarm Systems. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS) . 678--686.

Digital Library

[6]

N. Basilico, A. Celli, G. De Nittis, and N. Gatti. 2017b. Team-maxmin equilibrium: efficiency bounds and algorithms. In AAAI Conference on Artificial Intelligence (AAAI) .

Digital Library

[7]

D. Bertsimas and J. N. Tsitsiklis. 1997. Introduction to linear optimization . Vol. 6. Athena Scientific Belmont.

Digital Library

[8]

J. R. S. Blair, D. Mutchler, and M. Lent. 1996. Perfect recall and pruning in games with imperfect information. Computational Intelligence, Vol. 12, 1 (1996), 131--154.

[9]

N. Brown and T. Sandholm. 2017a. Safe and nested subgame solving for imperfect-information games. In Advances in Neural Information Processing Systems (NeurIPS). 689--699.

Digital Library

[10]

N. Brown and T. Sandholm. 2017b. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science (2017), eaao1733.

[11]

A. Celli and N. Gatti. 2018. Computational Results for Extensive-Form Adversarial Team Games. In AAAI Conference on Artificial Intelligence (AAAI) .

[12]

S. Ceppi, N. Gatti, G. Patrini, and M. Rocco. 2010. Local search techniques for computing equilibria in two-player general-sum strategic-form games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 1469--1470.

Digital Library

[13]

N. Cesa-Bianchi and G. Lugosi. 2006. Prediction, learning, and games .Cambridge university press.

Digital Library

[14]

S. Coniglio and M. Tieves. 2015. On the Generation of Cutting Planes which Maximize the Bound Improvement. In Experimental Algorithms, Evripidis Bampis (Ed.). Springer International Publishing, 97--109.

Digital Library

[15]

S. Dughmi and H. Xu. 2016. Algorithmic Bayesian persuasion. In ACM STOC. ACM, 412--425.

Digital Library

[16]

G. Farina, A. Celli, N. Gatti, and T. Sandholm. 2018. Ex ante coordination and collusion in zero-sum multi-player extensive-form games. In Advances in Neural Information Processing Systems (NeurIPS) .

Digital Library

[17]

F. Forges. 1986. An approach to communication equilibria. Econometrica (1986), 1375--1385.

[18]

F. Forges. 1993. Five legitimate definitions of correlated equilibrium in games with incomplete information. Theory and Decision, Vol. 35, 3 (01 Nov 1993), 277--310.

[19]

F. Forges. 2006. Correlated Equilibrium in Games with Incomplete Information Revisited. Theory and Decision, Vol. 61, 4 (01 Dec 2006), 329--344.

[20]

N. Gatti, G. Patrini, M. Rocco, and T. Sandholm. 2012. Combining local search techniques and path following for bimatrix games. arXiv preprint arXiv:1210.4858 (2012).

Digital Library

[21]

M. Grötschel, L. Lovász, and A. Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, Vol. 1, 2 (01 Jun 1981), 169--197.

[22]

K. A. Hansen, P. B. Miltersen, and T. B. Sørensen. 2007. Finding equilibria in games of no chance. In International Computing and Combinatorics Conference. Springer, 274--284.

Digital Library

[23]

S. Hart and A. Mas-Colell. 2000. A simple adaptive procedure leading to correlated equilibrium. Econometrica, Vol. 68, 5 (2000), 1127--1150.

[24]

J. Hartline, V. Syrgkanis, and E. Tardos. 2015. No-regret learning in Bayesian games. In Advances in Neural Information Processing Systems (NeurIPS). 3061--3069.

Digital Library

[25]

W. Huang and B. von Stengel. 2008. Computing an extensive-form correlated equilibrium in polynomial time. Internet and Network Economics (2008), 506--513.

Digital Library

[26]

A. X. Jiang and K. Leyton-Brown. 2015. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior, Vol. 91 (2015), 347--359.

[27]

E. Kamenica and M. Gentzkow. 2011. Bayesian persuasion. AM ECON REV, Vol. 101, 6 (2011), 2590--2615.

[28]

L. G. Khachiyan. 1980. Polynomial algorithms in linear programming. U. S. S. R. Comput. Math. and Math. Phys., Vol. 20, 1 (1980), 53--72.

[29]

G. P. McCormick. 1976. Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical programming, Vol. 10, 1 (1976), 147--175.

Digital Library

[30]

H. Moulin and J-P Vial. 1978. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, Vol. 7, 3 (1978), 201--221.

[31]

R. B. Myerson. 1986. Multistage Games with Communication. Econometrica, Vol. 54, 2 (1986), 323--358.

[32]

C. H. Papadimitriou and T. Roughgarden. 2008. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), Vol. 55, 3 (2008), 14.

Digital Library

[33]

S. M. Ross. 1971. Goofspiel--the game of pure strategy. Journal of Applied Probability, Vol. 8, 3 (1971), 621--625.

[34]

T. Roughgarden. 2009. Intrinsic robustness of the price of anarchy. In Proceedings of the forty-first annual ACM symposium on Theory of computing. ACM, 513--522.

Digital Library

[35]

A. Saffidine, H. Finnsson, and M. Buro. 2012. Alpha-Beta Pruning for Games with Simultaneous Moves. In AAAI Conference on Artificial Intelligence (AAAI) .

Digital Library

[36]

Y. Shoham and K. Leyton-Brown. 2009. Multiagent systems: Algorithmic, game-theoretic, and logical foundations .Cambridge University Press.

Digital Library

[37]

B. von Stengel. 1996. Efficient Computation of Behavior Strategies. Games and Economic Behavior, Vol. 14, 2 (1996), 220 -- 246.

[38]

B. von Stengel and F. Forges. 2008. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, Vol. 33, 4 (2008), 1002--1022.

Cited By

Peng BRubinstein AMohar BShinkar IO'Donnell R(2024)Fast Swap Regret Minimization and Applications to Approximate Correlated EquilibriaProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649691(1223-1234)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649691
Celli AMarchesi ABianchi TGatti NWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning to correlate in multi-player general-sum sequential gamesProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455458(13076-13086)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455458

Index Terms

Computing Optimal Ex Ante Correlated Equilibria in Two-Player Sequential Games
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design

Recommendations

Computing sequential equilibria for two-player games
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear programming and avoiding conversion to normal form. Koller and ...
Computing correlated equilibria in multi-player games

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous ...
Correlated Equilibrium in Quitting Games

A quitting game is a sequential game where each player has two actions: to continue or to quit. The game continues as long as all players decide to continue. The moment at least one player decides to quit, the game terminates. The terminal payoff depends ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

May 2019

2518 pages

ISBN:9781450363099

General Chairs:
Edith Elkind
University of Oxford, UK
,
Manuela Veloso
CMU (on leave), JPMorgan, USA
,
Program Chairs:
Noa Agmon
Bar-Ilan University, Israel
,
Matthew E. Taylor
Borealis AI, Canada

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 08 May 2019

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '19

Sponsor:

SIGAI

AAMAS '19: International Conference on Autonomous Agents and Multiagent Systems

May 13 - 17, 2019

Montreal QC, Canada

Acceptance Rates

AAMAS '19 Paper Acceptance Rate 193 of 793 submissions, 24%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
57
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Peng BRubinstein AMohar BShinkar IO'Donnell R(2024)Fast Swap Regret Minimization and Applications to Approximate Correlated EquilibriaProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649691(1223-1234)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649691
Celli AMarchesi ABianchi TGatti NWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning to correlate in multi-player general-sum sequential gamesProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455458(13076-13086)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455458

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents