返回Google圖書搜尋

Characterization and Computation of Equilibria in Infinite Games

出版	Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2007
URL	http://books.google.com.hk/books?id=dvdsNwAACAAJ&hl=&source=gbs_api

註釋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.