# Degenerate game

separable game, polynomial-like game

A non-cooperative game of $n$ persons in which the pay-off function $K _ {i} ( x _ {1} \dots x _ {n} )$ of each player $i$ is degenerate, i.e. has the form

$$\sum _ {j _ {1} \dots j _ {n} } a _ {j _ {1} \dots j _ {n} } ^ {( i) } r _ {j _ {1} } ^ {( i) } ( x _ {1} ) \dots r _ {j _ {n} } ^ {( i) } ( x _ {n} ),$$

where $r _ {j _ {k} } ^ {(} i) ( x _ {k} )$, $1 \leq j _ {k} \leq n ^ {(} k)$, are functions defined on the set of pure strategies $X _ {k}$ of player $k$, $k = 1 \dots n$. In the case of two-person zero-sum degenerate games on the unit square the pay-off function $K( x, y)$ of player I is

$$\sum _ {i = 1 } ^ { m } \sum _ {j = 1 } ^ { n } a _ {ij} r _ {i} ( x) s _ {j} ( y).$$

Such a game is reduced to a finite two-person zero-sum convex game $\langle R, S, K\rangle$, where $R$ is the convex set spanned by the $m$- dimensional curve $r _ {i} = r _ {i} ( x)$, $0 \leq x \leq 1$, $i = 1 \dots m$, in $m$- dimensional space, while $S$ is the convex set spanned by the curve $s _ {j} = s _ {j} ( y)$, $0 \leq y \leq 1$, $j = 1 \dots n$, in $n$- dimensional space; the pay-off function $K( r, s)$ has the form

$$\sum _ {i = 1 } ^ { m } \sum _ {j = 1 } ^ { n } a _ {ij} r _ {i} s _ {j} ,\ \ r \in R,\ s \in S.$$

In particular, if $r _ {i} ( x) = x ^ {i}$ and $s _ {j} ( y) = y ^ {j}$, the degenerate game is called a polynomial game. In any two-person zero-sum degenerate game on the unit square player I has an optimal mixed strategy whose support consists of at most $m$ points and if the game is polynomial — of at most $m/2$ points (in computing the number of points the weight assigned to a terminal point is $1/2$). In a similar manner, player II has an optimal mixed strategy whose support consists of at most $n$ points, and in the case of a polynomial game — of at most $n/2$ points.

#### References

 [1] M. Dresher, S. Karlin, L.S. Shapley, "Polynomial games" , Contributions to the theory of games I , Ann. Math. Studies , 24 , Princeton Univ. Press (1950) pp. 161–180 [2] D. Gale, O. Gross, "A note on polynomial and separable games" Pacific J. Math. , 8 : 4 (1958) pp. 735–741
How to Cite This Entry:
Degenerate game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Degenerate_game&oldid=46610
This article was adapted from an original article by G.N. Dyubin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article