Characterization and computation of equilibria in infinite games

Broadly, we study continuous games (those with continuous strategy spaces and utility functions) with a view towards computation of equilibria. We cover all of the game-theoretic background needed to understand these results in detail. Then we present new work, which can be divided into three parts. First, it is known that arbitrary continuous games may have arbitrarily complicated equilibria, so we investigate some properties of games with polynomial utility functions and a class of games with polynomial-like utility functions called separable games. We prove new bounds on the complexity of equilibria of separable games in terms of the complexity of the utility functions. In order to measure this complexity we propose a new definition for the rank of a continuous game; when applied to the case of finite games this improves on the results known in that setting. Furthermore, we prove a characterization theorem showing that several conditions which are necessary for a game to possess a finite-dimensional representation each define the class of separable games precisely, providing evidence that separable games are the natural class of continuous games in which to study computation. The characterization theorem also provides a natural connection between separability and the notion of the rank of a game. Second, we apply this theory to give an algorithm for computing e-Nash equilibria of two-player separable games with continuous strategy spaces. While a direct comparison to corresponding algorithms for finite games is not possible, the asymptotic running time in the complexity of the game grows slower for our algorithm than for any known algorithm for finite games.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Stein, Noah D. (Noah Daniel)

Advisor dc:contributor.advisor

• Asuman Ozdaglar and Pablo A. Parrilo.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/40326

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/40326