View source for Degenerate game

<!--
d0307801.png
$#A+1 = 32 n = 0
$#C+1 = 32 : ~/encyclopedia/old_files/data/D030/D.0300780 Degenerate game,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''separable game, polynomial-like game''

A [[Non-cooperative game|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|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D. Gale,   O. Gross,   "A note on polynomial and separable games"  ''Pacific J. Math.'' , '''8''' :  4  (1958)  pp. 735–741</TD></TR></table>