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