Continuous game

Template:Short description Template:Refimprove Template:Use dmy dates 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,𝐂,𝐔)$ where

$P=1,2,3,\dots ,n$ is the set of $n$ players,

$𝐂=(C_1,C_2,\dots ,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_1,u_2,\dots ,u_n)$ where $u_i:𝐂\to ℝ$ 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 $𝝈=({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)$ where ${\sigma }_i\in {\Delta }_i$

Let ${𝝈}_{-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 of

$b_i({\sigma }_{-i})$

is a best response to ${\sigma }_{-i}$. Define

$𝐛(𝝈)=b_1({\sigma }_{-1})\times b_2({\sigma }_{-2})\times \cdots \times b_n({\sigma }_{-n})$.

A strategy profile $𝝈\ast$ is a Nash equilibrium if and only if $𝝈\ast \in 𝐛(𝝈\ast )$ 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. 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:𝐂\to ℝ$ can be expressed in the sum-of-products form:

$u_i(𝐬)=\sum _{k_1=1}^{m_1}\dots \sum _{k_n=1}^{m_n}{a}_{i,k_1\dots k_n}{f}_1(s_1)\dots f_n(s_n)$, where $𝐬\in 𝐂$, $s_i\in C_i$, $a_{i,k_1\dots k_n}\in ℝ$, and the functions $f_{i,k}:C_i\to ℝ$ are continuous.

A polynomial game is a separable game where each $C_i$ is a compact interval on $ℝ$ 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.

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=[0,1]$. 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)$ where

$H(x,y)=(x-y{)}^2$.

The pure strategy best response relations are:

$b_X(y)=\{\begin{array}{cc}1,& \text{if }y\in [0,1/2)\\ 0\text{ or }1,& \text{if }y=1/2\\ 0,& \text{if }y\in (1/2,1]\end{array}$

$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=𝔼[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}=𝔼[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{array}{c}{\mu }_{X1}\ge {\mu }_{X2}\\ {\mu }_{X1}^2\le {\mu }_{X2}\end{array}\begin{array}{c}{\mu }_{Y1}\ge {\mu }_{Y2}\\ {\mu }_{Y1}^2\le {\mu }_{Y2}\end{array}$

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}\text{ or }{\mu }_{i1}^2={\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}\ast ,{\mu }_{X2}\ast ,{\mu }_{Y1}\ast ,{\mu }_{Y2}\ast )=(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=[0,1]$. 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)$ where

$H(x,y)=\frac{(1+x)(1+y)(1-xy)}{(1+xy{)}^2}.$

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

$F^{\ast }(x)=\frac{4}{\pi }\arctan \sqrt{x}{G}^{\ast }(y)=\frac{4}{\pi }\arctan \sqrt{y}.$

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

$f^{\ast }(x)=\frac{2}{\pi \sqrt{x}(1+x)}{g}^{\ast }(y)=\frac{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=[0,1]$. 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)$ where

$H(x,y)=\sum _{n=0}^{\mathrm{\infty }}\frac{1}{2^n}(2x^n-({(1-\frac{x}{3})}^n-{\left(\frac{x}{3}\right)}^n))(2y^n-({(1-\frac{y}{3})}^n-{\left(\frac{y}{3}\right)}^n))$.

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.

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. Template:ISBN.

See also

• Graph continuous