Non-atomic game

Template:Short description 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:

"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 $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 $\{1,\dots ,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 $x(p)\cdot u(p,x)$.

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

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

Existence of equilibrium

David Schmeidler proved the following theorems for the case $P=[0,1]$:

Theorem 1. If for all $p$ the function $u(p,\cdot )$ is weakly continuous from $L^1([0,1])$ to $ℝ$, and for all $x$ and $i$, $j$ the set $\{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, $u(p,x)$ depends only on the action-integrals of the strategy profile, that is, on $${({\int }_P{x}_j(t)\mathrm{d}t)}_{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 $G$ with $n$ players, one can construct a non-atomic game $H$ such that each player in $G$ corresponds to a sub-interval of $P$ of length $1/n$. The utility function is defined in a way that satisfies the conditions of Theorem 2. A pure-strategy equilibrium in $H$ corresponds to a 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 $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 $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 $x_{i,s}$ denote the fraction of players in type $i$ using strategy $s$. By definition, $\sum _{s\in S_i}{x}_{i,s}=r_i$. We denote $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, $x_e=\sum _{s\ni e}{x}_s$. The delay experienced by players using $e$ is defined by a delay function $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$: $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_1,s_2$ in $S_i$, if $x_{i,s_1}>0$, then $d_{s_1}(x)\le d_{s_2}(x)$. That is: if a positive measure of players of type $i$ choose $s_1$, then no other possible strategy would give them a strictly lower delay.

NCG-s were first studied by Milchtaich, 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 $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:Template:Reference page

• In Theorem 2, instead of requiring that $u(p,x)$ depends only on ${\int }_{P}x$, one can require that $u(p,x)$ depends only on ${\int }_{P_1}x,\dots ,{\int }_{P_k}x$, where $P_1,\dots ,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 ${ℝ}^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.
• Congestion game#nonatomic.