PDF《Exchangeable Equilibria》

Computer Science Class of

1943 Career Development Professor Thesis Co-Supervisor: Pablo A. Parrilo Title: Professor of Electrical Engineering &

Computer Science Finmeccanica Career Development Professor Dedicated to Marianne Cavanaugh, who once said she would be slightly disappointed if I never wrote this. Thank you for everything. Contents Acknowledgments

11 1 Introduction

15 1.1 Overview

18 1.2 Previous work

21 1.2.1 Leading towards exchangeable equilibria

21 1.2.2 Literature related to extreme correlated equilibria

23 2 Background

27 2.1 Game theory

27 2.1.1 Games and equilibria

28 2.1.2 The Hart-Schmeidler argument

35 2.1.3 Groups acting on games

37 2.2 Exchangeability

42 2.3 Tensors

47 2.4 Complete positivity

49 2.5 Semide?nite relaxations

52 2.5.1 Conic programming

52 2.5.2 Linear, semide?nite, and completely positive programming

53 2.5.3 Polynomial nonnegativity and sums of squares

55 2.5.4 Double nonnegativity

57 3 Symmetric Exchangeable Equilibria

63 3.1 Generalized exchangeable distributions

63 3.2 De?nition and properties

65 3.3 Examples

71 3.4 Convex relaxations of Nash equilibria

85 4 Interpretations of Symmetric Exchangeable Equilibria

91 7

8 CONTENTS 4.1 Hidden variable interpretation

91 4.2 Unknown opponent interpretation

94 4.3 Many player interpretation

96 4.4 Sealed envelope implementation

100 5 Higher Order Exchangeable Equilibria

101 5.1 Re?nement of the sealed envelope implementation

101 5.2 Powers of games

106 5.3 Order k exchangeable equilibria

111 5.4 Order ∞ exchangeable equilibria

113 5.5 Nash equilibria from higher order exchangeable equilibria

114 5.5.1 The player-transitive case

114 5.5.2 Arbitrary symmetry groups

116 6 Asymmetric Exchangeable Equilibria

119 6.1 Partial exchangeability

119 6.2 De?ning asymmetric exchangeable equilibria

123 6.3 Convex relaxations of Nash equilibria

132 7 Computation of Symmetric Exchangeable Equilibria

137 7.1 Computational complexity

137 7.1.1 Background

138 7.1.2 The Ellipsoid Against Hope algorithm

140 7.1.3 Paradox

142 7.1.4 Resolution

142 7.1.5 Approximate Ellipsoid Against Hope

146 7.1.6 Run time

150 7.1.7 Hardness of optimizing over exchangeable equilibria . . . .

150 7.2 Linear and semide?nite relaxations

151 8 Structure of Extreme Correlated Equilibria

155 8.1 Background

156 8.1.1 Extreme equilibria in ?nite games

156 8.1.2 Ergodic theory

159 8.2 Description of the examples

160 8.3 Extreme Nash equilibria

161 8.4 Extreme correlated equilibria

163 9 Future Directions

173 9.1 Open questions

174 CONTENTS

9 9.1.1 Higher order exchangeable equilibria

174 9.1.2 Finitely-supported correlated equilibria in polynomial games

174 9.1.3 The correlated equilibrium conundrum

175 9.1.4 Rational exchangeable equilibria

176 9.1.5 Symmetric identical interest games

177 9.1.6 Further computational questions

177 9.1.7 Applications of exchangeable equilibria

178 9.1.8 Structuralist game theory

178 References

183 Notation

189 Acknowledgements My deepest thanks go to my thesis advisors, Asuman Ozdaglar and Pablo Parrilo. Each has provided a constant source of ideas and research directions to pursue. Through some sort of resonance, constructive interference, or positive feedback, the rate at which these suggestions come at least quadruples whenever they are in the same room. At ?rst I found this daunting, but they taught me a great deal quickly and I became comfortable with this process faster than I expected. Knowing how stubborn I can be, they have managed to maintain this endless enthusiasm while almost never pushing me, except on a few occasions when they could sense I really needed it. While Asu and Pablo were always interested in whatever I was working on, one of these occasions came when they were worried that I was not interested enough in my own work. At this point the push came in the form of a no-strings-attached assignment to explore and ?nd a project which I thought was great, not merely good enough. In the end this gamble paid o? and I am much prouder of the ?nal product than I would have been. This principle of never trying to pigeonhole me into a particular area extended to the other aspects of my graduate studies as well. Though Asu and Pablo suggested enough research-relevant coursework to ?ll many more Ph.D.'