Continuous game explained

A continuous game is a mathematical concept, used in game theory, that generalizes the idea of an ordinary game like tic-tac-toe (noughts and crosses) or checkers (draughts). In other words, it extends the notion of a discrete game, where the players choose from a finite set of pure strategies. The continuous game concepts allows games to include more general sets of pure strategies, which may be uncountably infinite.

In general, a game with uncountably infinite strategy sets will not necessarily have a Nash equilibrium solution. If, however, the strategy sets are required to be compact and the utility functions continuous, then a Nash equilibrium will be guaranteed; this is by Glicksberg's generalization of the Kakutani fixed point theorem. The class of continuous games is for this reason usually defined and studied as a subset of the larger class of infinite games (i.e. games with infinite strategy sets) in which the strategy sets are compact and the utility functions continuous.

Formal definition

Define the n-player continuous game

G = (P, C , U ) whereP = { 1 , 2 , 3 ,\ldots, n} is the set of n players,C = (C _{1,} C _{2,} \ldots, C _{n)} where each C _{i} is a compact set, in a metric space, corresponding to the i th player's set of pure strategies,U = (u _{1,} u _{2,} \ldots, u _{n)} where u _{i:C\to} \R is the utility function of player i

We define

\Delta _{i} to be the set of Borel probability measures on C _{i} , giving us the mixed strategy space of player i.

Define the strategy profile

\boldsymbol{\sigma} = (\sigma _{1,} \sigma _{2,} \ldots, \sigma _{n)} where \sigma _{i} \in \Delta _{i} Let \boldsymbol{\sigma} _{-i} be a strategy profile of all players except for player i . As with discrete games, we can define a best response correspondence for player i , b _{i} . b _{i} is a relation from the set of all probability distributions over opponent player profiles to a set of player i 's strategies, such that each element ofb _{i(\sigma} _{-i} ) is a best response to \sigma _{-i} . Defineb (\boldsymbol{\sigma}) = b _{1(\sigma} _{-1} ) x b _{2(\sigma} _{-2} ) x … x b _{n(\sigma} _{-n} ) .A strategy profile \boldsymbol{\sigma}* is a Nash equilibrium if and only if\boldsymbol{\sigma}* \in b (\boldsymbol{\sigma}*) The existence of a Nash equilibrium for any continuous game with continuous utility functions can be proven using Irving Glicksberg's generalization of the Kakutani fixed point theorem.^[1] In general, there may not be a solution if we allow strategy spaces, C _{i} 's which are not compact, or if we allow non-continuous utility functions.

Separable games

A separable game is a continuous game where, for any i, the utility function

u _{i:C\to} \R can be expressed in the sum-of-products form:u _{i(s)} = \sum ^{m _{1}} _{k _{1=1}} \ldots \sum ^{m _{n}} _{k _{n=1}} a _{i , k _{1\ldots} k _{n}} f _{1(s} _{1)\ldots} f _{n(s} _{n)} , where s \in C , s _{i} \in C _{i} , a _{i , k _{1\ldots} k _{n}} \in \R , and the functions f _{i} :C _{i} \to \R are continuous.A polynomial game is a separable game where each C _{i} is a compact interval on \R and each utility function can be written as a multivariate polynomial.

In general, mixed Nash equilibria of separable games are easier to compute than non-separable games as implied by the following theorem:

For any separable game there exists at least one Nash equilibrium where player i mixes at most

m _{i+1} pure strategies.^[2] Whereas an equilibrium strategy for a non-separable game may require an uncountably infinite support, a separable game is guaranteed to have at least one Nash equilibrium with finitely supported mixed strategies.

Examples

Separable games

A polynomial game

Consider a zero-sum 2-player game between players X and Y, with

C _{X} = C _{Y} = \left [ 0 , 1 \right ] . Denote elements of C _{X} and C _{Y} as x and y respectively. Define the utility functions H(x,y) = u _{x(x,y)} = - u _{y(x,y)} whereH(x,y) = (x - y) ^{2} .

The pure strategy best response relations are:

b _{X(y)} = \begin{cases} 1 , & if y \in \left [ 0 , 1 / 2 \right ) \\ 0 or 1 , & if y = 1 / 2 \\ 0 , & if y \in \left ( 1 / 2 , 1 \right ] \end{cases} b _{Y(x)} = x b _{X(y)} and b _{Y(x)} do not intersect, so there is no pure strategy Nash equilibrium.However, there should be a mixed strategy equilibrium. To find it, express the expected value, v = E [H(x,y)] as a linear combination of the first and second moments of the probability distributions of X and Y:v = \mu _{X2} - 2 \mu _{X1} \mu _{Y1} + \mu _{Y2}

(where

\mu _{XN} = E [x ^{N]} and similarly for Y).

The constraints on

\mu _{X1} and \mu _{X2} (with similar constraints for y,) are given by Hausdorff as:\begin{align} \mu _{X1} \ge \mu _{X2} \\ \mu ^{2} _{X 1} \le \mu _{X2} \end{align} \begin{align} \mu _{Y1} \ge \mu _{Y2} \\ \mu ^{2} _{Y 1} \le \mu _{Y2} \end{align}

Each pair of constraints defines a compact convex subset in the plane. Since

v is linear, any extrema with respect to a player's first two moments will lie on the boundary of this subset. Player i's equilibrium strategy will lie on\mu _{i1} = \mu _{i2} or \mu ^{2} _{i 1} = \mu _{i2}

Note that the first equation only permits mixtures of 0 and 1 whereas the second equation only permits pure strategies. Moreover, if the best response at a certain point to player i lies on

\mu _{i1} = \mu _{i2} , it will lie on the whole line, so that both 0 and 1 are a best response. b _{Y(\mu} _{X1} ,\mu _{X2} ) simply gives the pure strategy y = \mu _{X1} , so b _{Y} will never give both 0 and 1.However b _{x} gives both 0 and 1 when y = 1/2.A Nash equilibrium exists when:(\mu _{X1} *, \mu _{X2} *, \mu _{Y1} *, \mu _{Y2} *) = ( 1 / 2 , 1 / 2 , 1 / 2 , 1 / 4 )

This determines one unique equilibrium where Player X plays a random mixture of 0 for 1/2 of the time and 1 the other 1/2 of the time. Player Y plays the pure strategy of 1/2. The value of the game is 1/4.

Non-Separable Games

A rational payoff function

Consider a zero-sum 2-player game between players X and Y, with

C _{X} = C _{Y} = \left [ 0 , 1 \right ] . Denote elements of C _{X} and C _{Y} as x and y respectively. Define the utility functions H(x,y) = u _{x(x,y)} = - u _{y(x,y)} whereH(x,y) = (( 1+ x)( 1+ y)( 1- xy))/(( 1+ xy) ^{2}) .

This game has no pure strategy Nash equilibrium. It can be shown^[3] that a unique mixed strategy Nash equilibrium exists with the following pair of cumulative distribution functions:

F ^{*(x)} = (4)/(\pi) \arctan{\sqrt{x}} G ^{*(y)} = (4)/(\pi) \arctan{\sqrt{y}}.

Or, equivalently, the following pair of probability density functions:

f ^{*(x)} = (2)/(\pi \sqrt{x) ( 1+ x)} g ^{*(y)} = (2)/(\pi \sqrt{y) ( 1+ y)}.

The value of the game is

4 /\pi .

Requiring a Cantor distribution

Consider a zero-sum 2-player game between players X and Y, with

C _{X} = C _{Y} = \left [ 0 , 1 \right ] . Denote elements of C _{X} and C _{Y} as x and y respectively. Define the utility functions H(x,y) = u _{x(x,y)} = - u _{y(x,y)} whereH(x,y) = \sum ^{inf ty} _{n =0} (1)/(2 ^{n}) \left( 2 x ^{n-\left} (\left( 1- (x)/(3) \right ) ^{n-\left} ( (x)/(3) \right) ^{n} \right ) \right ) \left( 2 y ^{n} - \left (\left( 1- (y)/(3) \right ) ^{n-\left} ( (y)/(3) \right) ^{n} \right ) \right ) .This game has a unique mixed strategy equilibrium where each player plays a mixed strategy with the Cantor singular function as the cumulative distribution function.^[4]

Further reading

• H. W. Kuhn and A. W. Tucker, eds. (1950). Contributions to the Theory of Games: Vol. II. Annals of Mathematics Studies 28. Princeton University Press. .

See also

• Graph continuous

References

1. I.L. Glicksberg. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proceedings of the American Mathematical Society, 3(1):170–174, February 1952.
2. N. Stein, A. Ozdaglar and P.A. Parrilo. "Separable and Low-Rank Continuous Games". International Journal of Game Theory, 37(4):475–504, December 2008. https://arxiv.org/abs/0707.3462
3. Irving Leonard Glicksberg & Oliver Alfred Gross (1950). "Notes on Games over the Square." Kuhn, H.W. & Tucker, A.W. eds. Contributions to the Theory of Games: Volume II. Annals of Mathematics Studies 28, p.173–183. Princeton University Press.
4. Gross, O. (1952). "A rational payoff characterization of the Cantor distribution." TechnicalReport D-1349, The RAND Corporation.