Namespaces
Variants
Actions

Difference between revisions of "Degenerate game"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
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''
 
''separable game, polynomial-like game''
  
A [[Non-cooperative game|non-cooperative game]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307801.png" /> persons in which the pay-off function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307802.png" /> of each player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307803.png" /> is degenerate, i.e. has the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307804.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307805.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307806.png" />, are functions defined on the set of pure strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307807.png" /> of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307808.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d0307809.png" />. In the case of two-person zero-sum degenerate games on the unit square the pay-off function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078010.png" /> of player I is
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078011.png" /></td> </tr></table>
+
$$
 +
\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]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078013.png" /> is the convex set spanned by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078014.png" />-dimensional curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078017.png" />, in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078018.png" />-dimensional space, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078019.png" /> is the convex set spanned by the curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078022.png" />, in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078023.png" />-dimensional space; the pay-off function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078024.png" /> has the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078025.png" /></td> </tr></table>
+
$$
 +
\sum _ {i = 1 } ^ { m }
 +
\sum _ {j = 1 } ^ { n }
 +
a _ {ij} r _ {i} s _ {j} ,\ \
 +
r \in R,\  s \in S.
 +
$$
  
In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078027.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078028.png" /> points and if the game is polynomial — of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078029.png" /> points (in computing the number of points the weight assigned to a terminal point is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078030.png" />). In a similar manner, player II has an optimal mixed strategy whose support consists of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078031.png" /> points, and in the case of a polynomial game — of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030780/d03078032.png" /> points.
+
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====
 
====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>
 
<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>

Latest revision as of 17:32, 5 June 2020


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