Structure of extreme correlated equilibria: a zero-sum example and its implications
We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite g...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90813 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811083195941126144 |
|---|---|
| author | Parrilo, Pablo A. Stein, Noah Daniel Ozdaglar, Asuman E. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Parrilo, Pablo A. Stein, Noah Daniel Ozdaglar, Asuman E. |
| author_sort | Parrilo, Pablo A. |
| collection | MIT |
| description | We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments. |
| first_indexed | 2024-09-23T12:26:57Z |
| format | Article |
| id | mit-1721.1/90813 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:26:57Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/908132022-09-28T08:01:24Z Structure of extreme correlated equilibria: a zero-sum example and its implications Parrilo, Pablo A. Stein, Noah Daniel Ozdaglar, Asuman E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Stein, Noah Daniel Ozdaglar, Asuman E. Parrilo, Pablo A. We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments. National Science Foundation (U.S.) (Grant DMI-0545910) National Science Foundation (U.S.) (Grant ECCS-0621922) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (Subaward 2003-07688-1) 2014-10-09T12:44:02Z 2014-10-09T12:44:02Z 2011-01 2010-11 Article http://purl.org/eprint/type/JournalArticle 0020-7276 1432-1270 http://hdl.handle.net/1721.1/90813 Stein, Noah D., Asuman Ozdaglar, and Pablo A. Parrilo. “Structure of Extreme Correlated Equilibria: a Zero-Sum Example and Its Implications.” Int J Game Theory 40, no. 4 (January 4, 2011): 749–767. https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1007/s00182-010-0267-1 International Journal of Game Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Parrilo, Pablo A. Stein, Noah Daniel Ozdaglar, Asuman E. Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title | Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title_full | Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title_fullStr | Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title_full_unstemmed | Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title_short | Structure of extreme correlated equilibria: a zero-sum example and its implications |
| title_sort | structure of extreme correlated equilibria a zero sum example and its implications |
| url | http://hdl.handle.net/1721.1/90813 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT parrilopabloa structureofextremecorrelatedequilibriaazerosumexampleanditsimplications AT steinnoahdaniel structureofextremecorrelatedequilibriaazerosumexampleanditsimplications AT ozdaglarasumane structureofextremecorrelatedequilibriaazerosumexampleanditsimplications |