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

Theorem 1. If for all ${\displaystyle p}$ the function ${\displaystyle u(p,\cdot )}$ is continuous, 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 ${\displaystyle \int _{P}x}$ (the integral of ${\displaystyle x}$ over ${\displaystyle P}$^{[ clarification needed ]}), 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 an 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.