continuous game

Define the n-player continuous game $G\; =\; (P,\; \backslash mathbf\{C\},\; \backslash mathbf\{U\})$ where

::$P\; =\; \{1,\; 2,\; 3,\backslash ldots,\; n\}$ is the set of $n\backslash ,$ players,

:: $\backslash mathbf\{C\}=\; (C\_1,\; C\_2,\; \backslash ldots,\; C\_n)$ where each $C\_i\backslash ,$ is a compact set, in a metric space, corresponding to the $i\backslash ,$ th player's set of pure strategies,

:: $\backslash mathbf\{U\}=\; (u\_1,\; u\_2,\; \backslash ldots,\; u\_n)$ where $u\_i:\backslash mathbf\{C\}\backslash to\; \backslash R$ is the utility function of player $i\backslash ,$

: We define $\backslash Delta\_i\backslash ,$ to be the set of Borel probability measures on $C\_i\backslash ,$, giving us the mixed strategy space of player i.

: Define the strategy profile $\backslash boldsymbol\{\backslash sigma\}\; =\; (\backslash sigma\_1,\; \backslash sigma\_2,\; \backslash ldots,\; \backslash sigma\_n)$ where $\backslash sigma\_i\; \backslash in\; \backslash Delta\_i\backslash ,$

Let $\backslash boldsymbol\{\backslash 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\backslash ,$, $b\_i\backslash$. $b\_i\backslash ,$ 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(\backslash sigma\_\{-i\})\backslash ,$

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

:$\backslash mathbf\{b\}(\backslash boldsymbol\{\backslash sigma\})\; =\; b\_1(\backslash sigma\_\{-1\})\; \backslash times\; b\_2(\backslash sigma\_\{-2\})\; \backslash times\; \backslash cdots\; \backslash times\; b\_n(\backslash sigma\_\{-n\})$.

A strategy profile $\backslash boldsymbol\{\backslash sigma\}*$ is a Nash equilibrium if and only if

$\backslash boldsymbol\{\backslash sigma\}*\; \backslash in\; \backslash mathbf\{b\}(\backslash boldsymbol\{\backslash 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.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. In general, there may not be a solution if we allow strategy spaces, $C\_i\backslash ,$'s which are not compact, or if we allow non-continuous utility functions.

A separable game is a continuous game where, for any i, the utility function $u\_i:\backslash mathbf\{C\}\backslash to\; \backslash R$ can be expressed in the sum-of-products form:

: $u\_i(\backslash mathbf\{s\})\; =\; \backslash sum\_\{k\_1=1\}^\{m\_1\}\; \backslash ldots\; \backslash sum\_\{k\_n=1\}^\{m\_n\}\; a\_\{i\backslash ,\; ,\backslash ,\; k\_1\backslash ldots\; k\_n\}\; f\_1(s\_1)\backslash ldots\; f\_n(s\_n)$, where $\backslash mathbf\{s\}\; \backslash in\; \backslash mathbf\{C\}$, $s\_i\; \backslash in\; C\_i$, $a\_\{i\backslash ,\; ,\backslash ,\; k\_1\backslash ldots\; k\_n\}\; \backslash in\; \backslash R$, and the functions $f\_\{i\backslash ,\; ,\backslash ,\; k\}:C\_i\; \backslash to\; \backslash R$ are continuous.

A polynomial game is a separable game where each $C\_i\backslash ,$ is a compact interval on $\backslash R\backslash ,$ 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\backslash ,$ pure strategies.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

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.

Consider a zero-sum 2-player game between players X and Y, with $C\_X\; =\; C\_Y\; =\; \backslash left\; [0,1\; \backslash right\; ]$. Denote elements of $C\_X\backslash ,$ and $C\_Y\backslash ,$ as $x\backslash ,$ and $y\backslash ,$ respectively. Define the utility functions $H(x,y)\; =\; u\_x(x,y)\; =\; -u\_y(x,y)\backslash ,$ where

:$H(x,y)=(x-y)^2\backslash ,$.

The pure strategy best response relations are:

:$b\_X(y)\; =$

\begin{cases}

1, & \mbox{if }y \in \left [0,1/2 \right ) \\

0\text{ or }1, & \mbox{if }y = 1/2 \\

0, & \mbox{if } y \in \left (1/2,1 \right ]

\end{cases}

:$b\_Y(x)\; =\; x\backslash ,$

$b\_X(y)\backslash ,$ and $b\_Y(x)\backslash ,$ 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\; =\; \backslash mathbb\{E\}\; [H(x,y)]$ as a linear combination of the first and second moments of the probability distributions of X and Y:

: $v\; =\; \backslash mu\_\{X2\}\; -\; 2\backslash mu\_\{X1\}\; \backslash mu\_\{Y1\}\; +\; \backslash mu\_\{Y2\}\backslash ,$

(where $\backslash mu\_\{XN\}\; =\; \backslash mathbb\{E\}\; [x^N]$ and similarly for Y).

The constraints on $\backslash mu\_\{X1\}\backslash ,$ and $\backslash mu\_\{X2\}$ (with similar constraints for y,) are given by Hausdorff as:

: $$

\begin{align}

\mu_{X1} \ge \mu_{X2} \\

\mu_{X1}^2 \le \mu_{X2}

\end{align}

\qquad

\begin{align}

\mu_{Y1} \ge \mu_{Y2} \\

\mu_{Y1}^2 \le \mu_{Y2}

\end{align}

Each pair of constraints defines a compact convex subset in the plane. Since $v\backslash ,$ 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

: $\backslash mu\_\{i1\}\; =\; \backslash mu\_\{i2\}\; \backslash text\{\; or\; \}\; \backslash mu\_\{i1\}^2\; =\; \backslash 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 $\backslash mu\_\{i1\}\; =\; \backslash mu\_\{i2\}\backslash ,$, it will lie on the whole line, so that both 0 and 1 are a best response. $b\_Y(\backslash mu\_\{X1\},\backslash mu\_\{X2\})\backslash ,$ simply gives the pure strategy $y\; =\; \backslash mu\_\{X1\}\backslash ,$, so $b\_Y\backslash ,$ will never give both 0 and 1.

However $b\_x\backslash ,$ gives both 0 and 1 when y = 1/2.

A Nash equilibrium exists when:

: $(\backslash mu\_\{X1\}*,\; \backslash mu\_\{X2\}*,\; \backslash mu\_\{Y1\}*,\; \backslash mu\_\{Y2\}*)\; =\; (1/2,\; 1/2,\; 1/2,\; 1/4)\backslash ,$

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.

Consider a zero-sum 2-player game between players X and Y, with $C\_X\; =\; C\_Y\; =\; \backslash left\; [0,1\; \backslash right\; ]$. Denote elements of $C\_X\backslash ,$ and $C\_Y\backslash ,$ as $x\backslash ,$ and $y\backslash ,$ respectively. Define the utility functions $H(x,y)\; =\; u\_x(x,y)\; =\; -u\_y(x,y)\backslash ,$ where

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

This game has no pure strategy Nash equilibrium. It can be shownIrving 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. that a unique mixed strategy Nash equilibrium exists with the following pair of cumulative distribution functions:

: $F^*(x)\; =\; \backslash frac\{4\}\{\backslash pi\}\; \backslash arctan\{\backslash sqrt\{x\}\}\; \backslash qquad\; G^*(y)\; =\; \backslash frac\{4\}\{\backslash pi\}\; \backslash arctan\{\backslash sqrt\{y\}\}.$

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

: $f^*(x)\; =\; \backslash frac\{2\}\{\backslash pi\; \backslash sqrt\{x\}\; (1+x)\}\; \backslash qquad\; g^*(y)\; =\; \backslash frac\{2\}\{\backslash pi\; \backslash sqrt\{y\}\; (1+y)\}.$

The value of the game is $4/\backslash pi$.

Consider a zero-sum 2-player game between players X and Y, with $C\_X\; =\; C\_Y\; =\; \backslash left\; [0,1\; \backslash right\; ]$. Denote elements of $C\_X\backslash ,$ and $C\_Y\backslash ,$ as $x\backslash ,$ and $y\backslash ,$ respectively. Define the utility functions $H(x,y)\; =\; u\_x(x,y)\; =\; -u\_y(x,y)\backslash ,$ where

:$H(x,y)=\backslash sum\_\{n=0\}^\backslash infty\; \backslash frac\{1\}\{2^n\}\backslash left(2x^n-\backslash left\; (\backslash left(1-\backslash frac\{x\}\{3\}\; \backslash right\; )^n-\backslash left\; (\backslash frac\{x\}\{3\}\backslash right)^n\; \backslash right\; )\; \backslash right\; )\; \backslash left(2y^n\; -\; \backslash left\; (\backslash left(1-\backslash frac\{y\}\{3\}\; \backslash right\; )^n-\backslash left\; (\backslash frac\{y\}\{3\}\backslash right)^n\; \backslash right\; )\; \backslash 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.Gross, O. (1952). "A rational payoff characterization of the Cantor distribution." Technical

Report D-1349, The RAND Corporation.

• 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. {{ISBN|0-691-07935-8}}.

• Graph continuous

Category:Game theory game classes