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;^[1] 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:^[1]

"Nonatomic games enable us to analyze a conflict situation where the single player has no influence on the situation but the agregative behavior of "large" sets of players can change the payoffs. The examples are numerous: Elections, many small buyers from a few competing firms, drivers that can choose among several roads, and so on."

Definitions

In a standard ("atomic") game, the set of players is a finite set. In a NAG, the set of players is an infinite and continuous set P, which can be modeled e.g. by the unit interval [0,1]. There is a Lebesgue measure defined on the set of players, which represents how many players of each "type" there are.

Each player can choose one of m actions ("pure strategies"). Note that the set of actions, in contrast to the set of players, remains finite as in standard games. Players can also choose a mixed strategy - a probability distribution over actions. A strategy profile is a measurable function from the set of players P to the set of probability distributions on actions; the function assigns to each point p in P a probability distribution x(p); it represents the fact that the infinitesimal player p has chosen the mixed strategy x(p).

Let x be a strategy profile. The choice of an infinitesimal player p has no effect on the general outcome, but affects his own payoff. Specifically, for each pure action j in [m] there is a function u_j that maps each player p in P and each strategy profile x to the utility that player p receives when he plays j and all the other players play as in x. As player p plays a mixed strategy x(p), his payoff is the inner product ${\displaystyle x(p)\cdot u(p,x)}$ .

A strategy profile x is called pure if x(p) is a pure strategy almost everywhere on P.

A strategy profile x is called an equilibrium if for every player p and every mixed strategy y, the following holds almost everywhere:

${\displaystyle x(p)\cdot u(p,x)\geq y\cdot u(p,x)}$ 

Existence of equilibrium

David Schmeidler proved the following theorems:^[1]

1. If for all p the function u(p,*) is continuous, and for all x and i,j the set {p | u_i(p,x) > u_j(p,x)} is measureable, then an equilibrium exists. The proof uses the Glicksberg fixed-point theorem.
2. If, in addition to the above conditions, u(p,x) depends only on ${\displaystyle \int _{P}x}$  (the integral of x over P^{[clarification needed]}), then a pure-strategy equilibrium exists. The proof uses a theorem by Robert Aumann. The additional condition is essential: there is an example of a game satisfying the conditions of Theorem 1, with no pure-strategy equilibrium.

He also showed that Nash's equilibrium theorem follows as a corollary from Theorem 2. Specifically, given a finite normal-form game G with n players, one can construct a non-atomic game H such that each player in G corresponds to an sub-interval of P of length 1/n. The utility function is defined in a way that satisfies the conditions to Theorem 2. A pure-strategy equilibrium in H corresponds to an Nash equilibrium (with possibly mixed strategies) in G.

Finite number of types

A special case of the general model is that there is a finite set T of player types. Each player type t is represented by a sub-interval of P_t of the set of players P. The length of the sub-interval represents the amount of players of that type. For example, it is possible that 1/2 the players are of type 1, 1/3 are of type 2, and 1/6 are of type 3. Players of the same type have the same utility function, but they may choose different strategies.

Nonatomic congestion games

A special sub-class of nonatomic games contains the nonatomic variants of congestion games (NCG). This special case can be described as follows.

• There is a finite set E of congestible elements (e.g. roads or resources).
• There are n types of players. For each type i there is a number ${\displaystyle r_{i}}$ , representing the amount of players of that type (the rate of traffic for that type).
• For each type i there is a set ${\displaystyle S_{i}}$  of possible strategies (possible subsets of E).
• Different players of the same type may choose different strategies. For every strategy s in S_i, let ${\displaystyle x_{i,s}}$  denote the fraction of players in type i using strategy s. By definition, ${\displaystyle \textstyle \sum _{s\in S_{i}}x_{i,s}=r_{i}}$ . We denote ${\displaystyle x_{s}:=\sum _{i:s\in S_{i}}f_{s,i}}$ 
• For each element e in E, the load on e is defined as the sum of fractions of players using e, that is, ${\displaystyle x_{e}=\sum _{s\ni e}x_{s}}$ . The delay experienced by players using e is defined by a delay function ${\displaystyle d_{e}}$ . This function must be monotone, positive, and continuous.
• The total disutility of each player choosing strategy s is the sum of delays on all edges in the subset s: ${\displaystyle d_{s}(x)=\sum _{e\in s}d_{e}(x_{e})}$ .
• A strategy profile is an equilibrium if for every player type i, and for every two strategies s₁,s₂ in S_i, if ${\displaystyle x_{i,s_{1}}>0}$ , then ${\displaystyle d_{s_{1}}(x)\leq d_{s_{2}}(x)}$ . That is: if a positive measure of players of type i choose s₁, then no other possible strategy would give them a strictly lower delay.

NCG-s were first studied by Milchtaich,^[2] Friedman^[3] and Blonsky.^[4] Roughgarden and Tardos^[5] 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^[6] 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 G; for each type i there are two nodes s_i and t_i from G; and the set of strategies available to type i is the set of all paths from s_i to t_i. If the utility functions of all players are Lipschitz continuous with constant L, then their algorithm computes an e-approximate PNE in strongly-polynomial time - polynomial in n, L and 1/e.

Generalizations

The two theorems of Schmeidler can be generalized in several ways:^{[1]: Final remarks}

• In Theorem 2, instead of requiring that u(p,x) depends only on ${\displaystyle \int _{P}x}$  , one an require that u(p,x) depends only on ${\displaystyle \int _{P_{1}}x,\ldots ,\int _{P_{k}}x}$  , where P₁,...,P_k are Lebesgue-measureable subsets of P.
• 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 R^m. If the additional assumption of Theorem 2 holds, then there exists an equilibrium in which the strategy of almost every player p is an extreme point of the strategy space of p.

See also

• Continuous game - a game with finitely many players, but a continuously-large set of strategies.
• Congesion game#nonatomic.

References

1. Schmeidler, David (1973-04-01). "Equilibrium points of nonatomic games". Journal of Statistical Physics. 7 (4): 295–300. doi:10.1007/BF01014905. ISSN 1572-9613.
2. Milchtaich, Igal (1996). "Congestion Models of Competition". The American Naturalist. 147 (5): 760–783. doi:10.1086/285878. ISSN 0003-0147. JSTOR 2463089. S2CID 55004212.
3. Friedman, Eric J. (1996-09-01). "Dynamics and Rationality in Ordered Externality Games". Games and Economic Behavior. 16 (1): 65–76. doi:10.1006/game.1996.0074. ISSN 0899-8256.
4. Blonski, Matthias (1999-08-01). "Anonymous Games with Binary Actions". Games and Economic Behavior. 28 (2): 171–180. doi:10.1006/game.1998.0699. ISSN 0899-8256.
5. Roughgarden, Tim; Tardos, Éva (2004-05-01). "Bounding the inefficiency of equilibria in nonatomic congestion games". Games and Economic Behavior. 47 (2): 389–403. doi:10.1016/j.geb.2003.06.004. ISSN 0899-8256. S2CID 10778635.
6. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004-06-13). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. New York, NY, USA: Association for Computing Machinery. pp. 604–612. doi:10.1145/1007352.1007445. ISBN 978-1-58113-852-8. S2CID 1037326.