Non-atomic game
Non-atomic game
In game-theory, a non-atomic game (NAG) is a generalization of the normal-form-game to a situation in which there are so many players so that they can be considered as a continuum. NAG-s were introduced by david-schmeidler; he extended the theorem on existence of a nash-equilibrium, which John Nash originally proved for finite games, to NAG-s.
Motivation Schmeidler motivates the study of NAG-s as follows: Friedman and Blonsky. Roughgarden and Tardos studied the price-of-anarchy in NCG-s.
Computing an equilibrium in an NCG can be rephrased as a convex optimization problem, and thus can be solved in wealky-polynomial time (e.g. by the ellipsoid method). Fabrikant, Papadimitriou and Talwar presented a strongly-polytime algorithm for finding a PNE in the special case of network NCG-s. In this special case there is a graph <math>G</math>; for each type <math>i</math> there are two nodes <math>s_i</math> and <math>t_i</math> from <math>G</math>; and the set of strategies available to type <math>i</math> is the set of all paths from <math>s_i</math> to <math>t_i</math>. If the utility functions of all players are Lipschitz continuous with constant <math>L</math>, then their algorithm computes an <math>e</math>-approximate PNE in strongly-polynomial time - polynomial in <math>n</math>, <math>L</math> and <math>1/e</math>.
Generalizations The two theorems of Schmeidler can be generalized in several ways:
- In Theorem 2, instead of requiring that <math>u(p,x)</math> depends only on <math>\int_P x</math>, one can require that <math>u(p,x)</math> depends only on <math>\int_{P_1} x, \ldots, \int_{P_k} x</math>, where <math>P_1,\dots,P_k</math> are Lebesgue-measureable subsets of <math>P</math>.
- In Theorem 1, instead of requiring that each player's strategy space is a simplex, it is sufficient to require that each player's strategy space is a compact convex subset of <math>\R^m</math>. If the additional assumption of Theorem 2 holds, then there exists an equilibrium in which the strategy of almost every player <math>p</math> is an extreme point of the strategy space of <math>p</math>.