Exchangeable equilibria
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/66465 |
| _version_ | 1826215531908169728 |
|---|---|
| author | Stein, Noah D. (Noah Daniel) |
| author2 | Asuman Ozdaglar and Pablo A. Parrilo |
| author_facet | Asuman Ozdaglar and Pablo A. Parrilo Stein, Noah D. (Noah Daniel) |
| author_sort | Stein, Noah D. (Noah Daniel) |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. |
| first_indexed | 2024-09-23T16:33:47Z |
| format | Thesis |
| id | mit-1721.1/66465 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:33:47Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/664652019-04-10T18:11:41Z Exchangeable equilibria Stein, Noah D. (Noah Daniel) Asuman Ozdaglar and Pablo A. Parrilo Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. Cataloged from PDF version of thesis. Includes bibliographical references (p. 183-188). The main contribution of this thesis is a new solution concept for symmetric games (of complete information in strategic form), the exchangeable equilibrium. This is an intermediate notion between symmetric Nash and symmetric correlated equilibrium. While a variety of weaker solution concepts than correlated equilibrium and a variety of refinements of Nash equilibrium are known, there is little previous work on "interpolating" between Nash and correlated equilibrium. Several game-theoretic interpretations suggest that exchangeable equilibria are natural objects to study. Moreover, these show that the notion of symmetric correlated equilibrium is too weak and exchangeable equilibrium is a more natural analog of correlated equilibrium for symmetric games. The geometric properties of exchangeable equilibria are a mix of those of Nash and correlated equilibria. The set of exchangeable equilibria is convex, compact, and semi-algebraic, but not necessarily a polytope. A variety of examples illustrate how it relates to the Nash and correlated equilibria. The same ideas which lead to the notion of exchangeable equilibria can be used to construct tighter convex relaxations of the symmetric Nash equilibria as well as convex relaxations of the set of all Nash equilibria in asymmetric games. These have similar mathematical properties to the exchangeable equilibria. An example game reveals an algebraic obstruction to computing exact exchangeable equilibria, but these can be approximated to any degree of accuracy in polynomial time. On the other hand, optimizing a linear function over the exchangeable equilibria is NP-hard. There are practical linear and semidefinite programming heuristics for both problems. A secondary contribution of this thesis is the computation of extreme points of the set of correlated equilibria in a simple family of games. These examples illustrate that in finite games there can be factorially many more extreme correlated equilibria than extreme Nash equilibria, so enumerating extreme correlated equilibria is not an effective method for enumerating extreme Nash equilibria. In the case of games with a continuum of strategies and polynomial utilities, the examples illustrate that while the set of Nash equilibria has a known finite-dimensional description in terms of moments, the set of correlated equilibria admits no such finite-dimensional characterization. by Noah D. Stein. Ph.D. 2011-10-17T21:29:14Z 2011-10-17T21:29:14Z 2011 2011 Thesis http://hdl.handle.net/1721.1/66465 756046914 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 191 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Stein, Noah D. (Noah Daniel) Exchangeable equilibria |
| title | Exchangeable equilibria |
| title_full | Exchangeable equilibria |
| title_fullStr | Exchangeable equilibria |
| title_full_unstemmed | Exchangeable equilibria |
| title_short | Exchangeable equilibria |
| title_sort | exchangeable equilibria |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/66465 |
| work_keys_str_mv | AT steinnoahdnoahdaniel exchangeableequilibria |