Continuous game

A continuous game is a mathematical generalization, used in game theory. 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,{\mathbf {C}},{\mathbf {U}})$ where

P={1,2,3,\ldots ,n}

is the set of

n\,

players,

{\mathbf {C}}=(C_{1},C_{2},\ldots ,C_{n})

where each

C_{i}\,

is a compact metric space corresponding to the

i\,

th player's set of pure strategies,

{\mathbf {U}}=(u_{1},u_{2},\ldots ,u_{n})

where

u_{i}:{\mathbf {C}}\to \mathbb{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 of

b_{i}(\sigma _{{-i}})\,

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

{\mathbf {b}}({\boldsymbol {\sigma }})=b_{1}(\sigma _{{-1}})\times b_{2}(\sigma _{{-2}})\times \cdots \times b_{n}(\sigma _{{-n}})

A strategy profile ${\boldsymbol {\sigma }}*$ is a Nash equilibrium if and only if ${\boldsymbol {\sigma }}*\in {\mathbf {b}}({\boldsymbol {\sigma }}*)$ The existence of a Nash equilibrium for any continuous game with continuous utility functions can been 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}:{\mathbf {C}}\to \mathbb{R}$ can be expressed in the sum-of-products form:

u_{i}({\mathbf {s}})=\sum _{{k_{1}=1}}^{{m_{1}}}\ldots \sum _{{k_{n}=1}}^{{m_{n}}}a_{{i\,,\,k_{1}\ldots k_{n}}}f_{1}(s_{1})\ldots f_{n}(s_{n})

, where

{\mathbf {s}}\in {\mathbf {C}}

s_{i}\in C_{i}

a_{{i\,,\,k_{1}\ldots k_{n}}}\in \mathbb{R}

, and the functions

f_{{i\,,\,k}}:C_{i}\to \mathbb{R}

are continuous.

A polynomial game is a separable game where each $C_{i}\,$ is a compact interval on $\mathbb{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)\,$ where

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

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\,

$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={\mathbb {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}}={\mathbb {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{aligned}\mu _{{X1}}\geq \mu _{{X2}}\\\mu _{{X1}}^{2}\leq \mu _{{X2}}\end{aligned}}\qquad {\begin{aligned}\mu _{{Y1}}\geq \mu _{{Y2}}\\\mu _{{Y1}}^{2}\leq \mu _{{Y2}}\end{aligned}}

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}}*,\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 pay-off function

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^[3] that a unique mixed strategy Nash equilibrium exists with the following pair of probability density functions:

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

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

Requiring a Cantor distribution

H(x,y)=\sum _{{n=0}}^{\infty }{\frac {1}{2^{n}}}\left(2x^{n}-\left(\left(1-{\frac {x}{3}}\right)^{n}-\left({\frac {x}{3}}\right)^{n}\right)\right)\left(2y^{n}-\left(\left(1-{\frac {y}{3}}\right)^{n}-\left({\frac {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]

References

↑ 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.
↑ 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. http://arxiv.org/abs/0707.3462
↑ Glicksberg, I. & Gross, O. (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.
↑ Gross, O. (1952). "A rational payoff characterization of the Cantor distribution." Technical Report D-1349, The RAND Corporation.

This article is issued from Wikipedia - version of the 10/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Continuous game

Formal definition

Separable games

Examples

Separable games

A polynomial game

Non-Separable Games

A rational pay-off function

Requiring a Cantor distribution

Further reading

See also

References