Non-atomic game

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) \geq 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 \mathbb R, 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 \left(\int_P x_j(t)\,\mathrm dt\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 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) \leq 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: • 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, \ldots, \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 \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 ==