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 aggregative 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 ${\displaystyle P}$ , which can be modeled e.g. by the unit interval ${\displaystyle [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 ${\displaystyle 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 ${\displaystyle P}$ to the set of probability distributions on actions; the function assigns to each point ${\displaystyle p}$ in ${\displaystyle P}$ a probability distribution ${\displaystyle x(p)}$ ; it represents the fact that the infinitesimal player ${\displaystyle p}$ has chosen the mixed strategy ${\displaystyle x(p)}$ .

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

A strategy profile ${\displaystyle x}$ is called pure if ${\displaystyle x(p)}$ is a pure strategy for almost every ${\displaystyle p}$ in ${\displaystyle P}$ .

A strategy profile ${\displaystyle x}$ is called an equilibrium if for almost every player ${\displaystyle p}$ and every mixed strategy ${\displaystyle y}$ , it holds that $${\displaystyle x(p)\cdot u(p,x)\geq y\cdot u(p,x).}$$

Existence of equilibrium

David Schmeidler proved the following theorems for the case ${\displaystyle P=[0,1]}$ :^[1]

Theorem 1. If for all ${\displaystyle p}$ the function ${\displaystyle u(p,\cdot )}$ is weakly continuous from ${\displaystyle L^{1}([0,1])}$ to ${\displaystyle \mathbb {R} }$ , and for all ${\displaystyle x}$ and ${\displaystyle i}$ , ${\displaystyle j}$ the set ${\displaystyle \{p\mid u_{i}(p,x)>u_{j}(p,x)\}}$ is measureable, then an equilibrium exists.

The proof uses the Glicksberg fixed-point theorem.

Theorem 2. If, in addition to the above conditions, ${\displaystyle u(p,x)}$ depends only on the action-integrals of the strategy profile, that is, on $${\displaystyle \left(\int _{P}x_{j}(t)\,\mathrm {d} t\right)_{j\in \{1,\dots ,m\}},}$$ then a pure-strategy equilibrium exists.

The proof uses a theorem by Robert Aumann. The additional condition in Theorem 2 is essential: there is an example of a game satisfying the conditions of Theorem 1, with no pure-strategy equilibrium. David Schmeidler also showed that Nash's equilibrium theorem follows as a corollary from Theorem 2. Specifically, given a finite normal-form game ${\displaystyle G}$ with ${\displaystyle n}$ players, one can construct a non-atomic game ${\displaystyle H}$ such that each player in ${\displaystyle G}$ corresponds to a sub-interval of ${\displaystyle P}$ of length ${\displaystyle 1/n}$ . The utility function is defined in a way that satisfies the conditions of Theorem 2. A pure-strategy equilibrium in ${\displaystyle H}$ corresponds to a Nash equilibrium (with possibly mixed strategies) in ${\displaystyle G}$ .

Finite number of types

A special case of the general model is that there is a finite set ${\displaystyle T}$ of player types. Each player type ${\displaystyle t}$ is represented by a sub-interval of ${\displaystyle P_{t}}$ of the set of players ${\displaystyle P}$ . The length of the sub-interval represents the amount of players of that type. For example, it is possible that ${\displaystyle 1/2}$ the players are of type ${\displaystyle 1}$ , ${\displaystyle 1/3}$ are of type ${\displaystyle 2}$ , and ${\displaystyle 1/6}$ are of type ${\displaystyle 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 ${\displaystyle E}$ of congestible elements (e.g. roads or resources).
• There are ${\displaystyle n}$ types of players. For each type ${\displaystyle 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 ${\displaystyle i}$ there is a set ${\displaystyle S_{i}}$ of possible strategies (possible subsets of ${\displaystyle E}$ ).
• Different players of the same type may choose different strategies. For every strategy ${\displaystyle s}$ in ${\displaystyle S_{i}}$ , let ${\displaystyle x_{i,s}}$ denote the fraction of players in type ${\displaystyle i}$ using strategy ${\displaystyle s}$ . By definition, ${\displaystyle \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 ${\displaystyle e}$ in ${\displaystyle E}$ , the load on ${\displaystyle e}$ is defined as the sum of fractions of players using ${\displaystyle e}$ , that is, ${\displaystyle x_{e}=\sum _{s\ni e}x_{s}}$ . The delay experienced by players using ${\displaystyle 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 ${\displaystyle s}$ is the sum of delays on all edges in the subset ${\displaystyle s}$ : ${\displaystyle d_{s}(x)=\sum _{e\in s}d_{e}(x_{e})}$ .
• A strategy profile is an equilibrium if for every player type ${\displaystyle i}$ , and for every two strategies ${\displaystyle s_{1},s_{2}}$ in ${\displaystyle 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 ${\displaystyle i}$ choose ${\displaystyle s_{1}}$ , 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 ${\displaystyle G}$ ; for each type ${\displaystyle i}$ there are two nodes ${\displaystyle s_{i}}$ and ${\displaystyle t_{i}}$ from ${\displaystyle G}$ ; and the set of strategies available to type ${\displaystyle i}$ is the set of all paths from ${\displaystyle s_{i}}$ to ${\displaystyle t_{i}}$ . If the utility functions of all players are Lipschitz continuous with constant ${\displaystyle L}$ , then their algorithm computes an ${\displaystyle e}$ -approximate PNE in strongly-polynomial time - polynomial in ${\displaystyle n}$ , ${\displaystyle L}$ and ${\displaystyle 1/e}$ .

Generalizations

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

• In Theorem 2, instead of requiring that ${\displaystyle u(p,x)}$ depends only on ${\displaystyle \int _{P}x}$ , one can require that ${\displaystyle u(p,x)}$ depends only on ${\displaystyle \int _{P_{1}}x,\ldots ,\int _{P_{k}}x}$ , where ${\displaystyle P_{1},\dots ,P_{k}}$ are Lebesgue-measureable subsets of ${\displaystyle 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 ${\displaystyle \mathbb {R} ^{m}}$ . If the additional assumption of Theorem 2 holds, then there exists an equilibrium in which the strategy of almost every player ${\displaystyle p}$ is an extreme point of the strategy space of ${\displaystyle 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. Bibcode:1973JSP.....7..295S. doi:10.1007/BF01014905. ISSN 1572-9613.
2. Milchtaich, Igal (1996). "Congestion Models of Competition". The American Naturalist. 147 (5): 760–783. Bibcode:1996ANat..147..760M. 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.