PDF《Exchangeable Equilibria》

Exchangeable Equilibria by Noah D.

Stein B.S., Electrical &

Computer Engineering, Cornell University,

2005 S.M., Electrical Engineering &

Computer Science, MIT,

2007 Submitted to the Department of Electrical Engineering &

Computer Science in partial ful?llment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering &

Computer Science at the Massachusetts Institute of Technology June

2011 c

2011 Massachusetts Institute of Technology. All rights reserved. Signature of Author: Department of Electrical Engineering &

Computer Science May 20,

2011 Certi?ed by: Asuman Ozdaglar Associate Professor of Electrical Engineering &

Computer Science Class of

1943 Career Development Professor Thesis Co-Supervisor Certi?ed by: Pablo A. Parrilo Professor of Electrical Engineering &

Computer Science Finmeccanica Career Development Professor Thesis Co-Supervisor Accepted by: Leslie A. Kolodziejski Professor of Electrical Engineering Chair, Committee for Graduate Students Exchangeable Equilibria by Noah D. Stein Submitted to the Department of Electrical Engineering and Computer Science on May 20,

2011 in partial ful?llment of the requirements for the degree of Doctor of Philosophy Abstract 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 equi- librium. While a variety of weaker solution concepts than correlated equilibrium and a variety of re?nements 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 ex- changeable 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 semide?nite 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 illus-

4 trate that in ?nite games there can be factorially many more extreme correlated equilibria than extreme Nash equilibria, so enumerating extreme correlated equi- libria is not an e?ective method for enumerating extreme Nash equilibria. In the case of games with a continuum of strategies and polynomial utilities, the exam- ples illustrate that while the set of Nash equilibria has a known ?nite-dimensional description in terms of moments, the set of correlated equilibria admits no such ?nite-dimensional characterization. Thesis Co-Supervisor: Asuman Ozdaglar Title: Associate Professor of Electrical Engineering &