Generalization of games used in game theory
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
where
is the set of
players,
where each
is a compact set, in a metric space, corresponding to the
th player's set of pure strategies,
where
is the utility function of player ![{\displaystyle i\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8288705aba0c3da0eae22f3895f572ecc2ccdf8)
- We define
to be the set of Borel probability measures on
, giving us the mixed strategy space of player i.
- Define the strategy profile
where ![{\displaystyle \sigma _{i}\in \Delta _{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0050bdbda0d82e280a59376a2ba31db3ec287ba3)
Let
be a strategy profile of all players except for player
. As with discrete games, we can define a best response correspondence for player
,
.
is a relation from the set of all probability distributions over opponent player profiles to a set of player
's strategies, such that each element of
![{\displaystyle b_{i}(\sigma _{-i})\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66bcd4d5cea8e0d7444601c6018abd45ef668f9d)
is a best response to
. Define
.
A strategy profile
is a Nash equilibrium if and only if
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,
'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
can be expressed in the sum-of-products form:
, where
,
,
, and the functions
are continuous.
A polynomial game is a separable game where each
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
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
. Denote elements of
and
as
and
respectively. Define the utility functions
where
.
The pure strategy best response relations are:
![{\displaystyle 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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2a9e41248021569d55075ae9ad5c94aac90a01d)
![{\displaystyle b_{Y}(x)=x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fdfb7b5478dd6718eb6a86233270e3119a97172)
and
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,
as a linear combination of the first and second moments of the probability distributions of X and Y:
![{\displaystyle v=\mu _{X2}-2\mu _{X1}\mu _{Y1}+\mu _{Y2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa8851cc3bb96b8513004be7689049bfaeac04b4)
(where
and similarly for Y).
The constraints on
and
(with similar constraints for y,) are given by Hausdorff as:
![{\displaystyle {\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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7ff2c3d08e547df102d8c1e403e7ad6e2718c83)
Each pair of constraints defines a compact convex subset in the plane. Since
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
![{\displaystyle \mu _{i1}=\mu _{i2}{\text{ or ))\mu _{i1}^{2}=\mu _{i2))](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7e05e3807042e7f2f292e4ee027814295f22cf3)
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
, it will lie on the whole line, so that both 0 and 1 are a best response.
simply gives the pure strategy
, so
will never give both 0 and 1.
However
gives both 0 and 1 when y = 1/2.
A Nash equilibrium exists when:
![{\displaystyle (\mu _{X1}*,\mu _{X2}*,\mu _{Y1}*,\mu _{Y2}*)=(1/2,1/2,1/2,1/4)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28daef121c633726f38095373b1e0e79d1913ebf)
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
. Denote elements of
and
as
and
respectively. Define the utility functions
where
![{\displaystyle H(x,y)={\frac {(1+x)(1+y)(1-xy)}{(1+xy)^{2))}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5249155bba22f235a100aa3976a524a79b3116ee)
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:
![{\displaystyle f^{*}(x)={\frac {2}{\pi {\sqrt {x))(1+x)))\qquad g^{*}(y)={\frac {2}{\pi {\sqrt {y))(1+y))).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70e19956b9303d060528e25ae3fc79e5353a4b92)
The value of the game is
.
Requiring a Cantor distribution
Consider a zero-sum 2-player game between players X and Y, with
. Denote elements of
and
as
and
respectively. Define the utility functions
where
.
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]