Namespaces
Variants
Actions

Difference between revisions of "Game with a hierarchy structure"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A model of a conflict situation with a fixed sequence of moves and interchange of information between the players. The main object of investigation in the theory of games with a hierarchy structure is the problem of finding the largest guaranteed result and an optimal strategy for a selected player. Suppose that players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432701.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432702.png" />, respectively, tend to an increase in the pay-off functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432703.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432704.png" /> (cf. [[Gain function|Gain function]]), continuous on the product of two compacta <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432705.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432706.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432707.png" />. The following different types of games can be formulated according to the character of the information and the order of moves.
+
<!--
 +
g0432701.png
 +
$#A+1 = 215 n = 0
 +
$#C+1 = 215 : ~/encyclopedia/old_files/data/G043/G.0403270 Game with a hierarchy structure
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g0432709.png" />. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327010.png" /> chooses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327011.png" /> and communicates his choice to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327012.png" />. Let
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<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/g/g043/g043270/g04327013.png" /></td> </tr></table>
+
A model of a conflict situation with a fixed sequence of moves and interchange of information between the players. The main object of investigation in the theory of games with a hierarchy structure is the problem of finding the largest guaranteed result and an optimal strategy for a selected player. Suppose that players  $  \textrm{ I } $
 +
and  $  \textrm{ II } $,
 +
respectively, tend to an increase in the pay-off functions  $  f _ {1} ( x _ {1} , x _ {2} ) $
 +
and  $  f _ {2} ( x _ {1} , x _ {2} ) $(
 +
cf. [[Gain function|Gain function]]), continuous on the product of two compacta  $  X _ {1} , X _ {2} $;  
 +
$  x _ {1} \in X _ {1} $,
 +
$  x _ {2} \in X _ {2} $.  
 +
The following different types of games can be formulated according to the character of the information and the order of moves.
  
be the set of optimal choices of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327014.png" />. Then the largest guaranteed result for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327015.png" /> is
+
The game  $  \Gamma _ {1} $.  
 +
Player  $  \textrm{ I } $
 +
chooses  $  x _ {1} \in X _ {1} $
 +
and communicates his choice to player $  \textrm{ II } $.  
 +
Let
  
<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/g/g043/g043270/g04327016.png" /></td> </tr></table>
+
$$
 +
P ( x _ {1} )  = \
 +
\left \{ {x _ {2} } : {
 +
f _ {2} ( x _ {1} , x _ {2} ) =
 +
\max _ {y \in X _ {2} } \
 +
f _ {2} ( x _ {1} , y) } \right \}
 +
$$
  
The game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327018.png" />. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327019.png" /> expects to have and indeed will have information on the choices of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327020.png" />; he communicates his strategy, that is, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327022.png" /> — the set of all mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327023.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327024.png" />, to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327025.png" />. The largest guaranteed result for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327026.png" /> is
+
be the set of optimal choices of player $  \textrm{ II } $.  
 +
Then the largest guaranteed result for player $  \textrm{ 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/g/g043/g043270/g04327027.png" /></td> </tr></table>
+
$$
 +
G _ {1}  = \
 +
\sup _ {x _ {1} \in X _ {1} } \
 +
\min _ {x _ {2} \in P ( x _ {1} ) } \
 +
f _ {1} ( x _ {1} , x _ {2} ).
 +
$$
  
where the set of optimal choices of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327028.png" /> is
+
The game  $  \Gamma _ {2} $.
 +
Player  $  \textrm{ I } $
 +
expects to have and indeed will have information on the choices of player  $  \textrm{ II } $;
 +
he communicates his strategy, that is, a function  $  \widetilde{x}  _ {1} = x _ {1} ( x _ {2} ) $,
 +
where $  \widetilde{x}  _ {1} \in \widetilde{X}  _ {1} $—
 +
the set of all mappings from  $  X _ {2} $
 +
to  $  X _ {1} $,
 +
to player $  \textrm{ II } $.  
 +
The largest guaranteed result for player  $  \textrm{ 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/g/g043/g043270/g04327029.png" /></td> </tr></table>
+
$$
 +
G _ {2}  = \
 +
\sup _ {\widetilde{x}  _ {1} \in \widetilde{X}  _ {1} } \
 +
\inf _ {x _ {2} \in P _ {2} ( \widetilde{x}  _ {1} ) } \
 +
f _ {1} ( \widetilde{x}  _ {1} , x _ {2} ),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327030.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327031.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327032.png" /> is achieved.
+
where the set of optimal choices of player  $  \textrm{ II } $
 +
is
  
The game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327034.png" />. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327035.png" /> expects to have and indeed will have information on the choices of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327036.png" /> in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327038.png" /> — the set of all mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327039.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327040.png" />; he communicates to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327041.png" /> his strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327043.png" /> — the set of mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327044.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327045.png" />. The largest guaranteed result of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327046.png" /> is
+
$$
 +
P _ {2} ( \widetilde{x}  _ {1} )  = \
 +
\left \{ {x _ {2} } : {
 +
f _ {2} ( \widetilde{x}  _ {1} , x _ {2} ) =
 +
\sup _ {y \in X _ {2} } \
 +
f _ {2} ( x _ {1} ( y), y) -
 +
\delta ( \widetilde{x}  _ {1} ) } \right \}
 +
,
 +
$$
  
<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/g/g043/g043270/g04327047.png" /></td> </tr></table>
+
where  $  \delta ( \widetilde{x}  _ {1} ) \geq  0 $,
 +
and  $  \delta ( \widetilde{x}  _ {1} ) = 0 $
 +
if and only if  $  \max _ {y \in X _ {2}  }  f _ {2} ( x _ {1} ( y)  y) $
 +
is achieved.
 +
 
 +
The game  $  \Gamma _ {3} $.
 +
Player  $  \textrm{ I } $
 +
expects to have and indeed will have information on the choices of player  $  \textrm{ II } $
 +
in the form  $  \widetilde{x}  _ {2} = x _ {2} ( x _ {1} ) $,
 +
where  $  \widetilde{x}  _ {2} \in \widetilde{X}  _ {2} $—
 +
the set of all mappings from  $  X _ {1} $
 +
to  $  X _ {2} $;  
 +
he communicates to player  $  \textrm{ II } $
 +
his strategy  $  {\widetilde{x}  tilde } _ {1} = x _ {1} ( \widetilde{x}  _ {2} ) $,
 +
where  $  {\widetilde{x}  tilde } _ {1} \in {\widetilde{X}  tilde } _ {1} $—
 +
the set of mappings from  $  \widetilde{X}  _ {2} $
 +
to  $  X _ {1} $.
 +
The largest guaranteed result of player  $  \textrm{ I } $
 +
is
 +
 
 +
$$
 +
G _ {3}  = \
 +
\sup _
 +
{\begin{array}{c}
 +
{} \\
 +
{\widetilde{x}  tilde } _ {1} \in {\widetilde{X}  tilde } _ {1}
 +
\end{array}
 +
} \
 +
\inf _
 +
{\begin{array}{c}
 +
{} \\
 +
\widetilde{x}  _ {2} \in P _ {3} ( \widetilde{x}  tilde _ {1} )
 +
\end{array}
 +
} \
 +
f _ {1} ( {\widetilde{x}  tilde } _ {1} , \widetilde{x}  _ {2} ),
 +
$$
  
 
where
 
where
  
<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/g/g043/g043270/g04327048.png" /></td> </tr></table>
+
$$
 +
P _ {3} ( {\widetilde{x}  tilde } _ {1} )  = \
 +
\left \{ {\widetilde{x}  _ {2} } : {
 +
f _ {2} ( {\widetilde{x}  tilde } _ {1} , \widetilde{x}  _ {2} )  = \
 +
\sup _ {\begin{array}{c}
 +
{} \\
 +
y \in \widetilde{X}  _ {2}
 +
\end{array}
 +
} \
 +
f _ {2} ( x _ {1} ( y), y) -
 +
\delta ( {\widetilde{x}  tilde } _ {1} ) } \right \}
 +
,
 +
$$
 +
 
 +
$  \delta ( {\widetilde{x}  tilde } _ {1} ) \geq  0 $,
 +
where now  $  \delta ( {\widetilde{x}  tilde } _ {1} ) = 0 $
 +
if and only if  $  \max _ {y \in \widetilde{X}  _ {2}  }  f _ {2} ( x _ {1} ( y), y) $
 +
is achieved.
 +
 
 +
A relation between the results in these games determines for player  $  \textrm{ I } $
 +
knowledge of the information concerning the actions of player II: $  G _ {1} \leq  G _ {3} \leq  G _ {2} $.
 +
Using the scheme indicated in the construction of the strategies of the players, games with arbitrarily deep recursion can be formulated. The following assertion holds: in the games  $  \Gamma _ {2m} $,
 +
$  m > 1 $,
 +
the largest guaranteed result for player  $  \textrm{ I } $
 +
is  $  G _ {2} $;  
 +
in the games  $  \Gamma _ {2m + 1 }  $,
 +
$  m > 1 $,
 +
the largest guaranteed result is  $  G _ {3} $.
 +
The problem of determining  $  G _ {1} $
 +
is related to a class of problems of minimax type with related restrictions.
 +
 
 +
Methods have been developed for solving  $  \Gamma _ {1} $
 +
using penalty functions, necessary optimality conditions and approximation to the original game by games with unique responses for player  $  \textrm{ II } $.
 +
Complete solutions are known for special classes of games: games with close interests, bimatrix games, bilinear games, etc. The problem of determining  $  G _ {1} $
 +
is not well-posed relative to changes in the function  $  f _ {2} ( x _ {1} , x _ {2} ) $
 +
in the uniform metric and of the sets  $  X _ {1} $
 +
and  $  X _ {2} $
 +
in the Hausdorff metric. A general method has been proposed for regularizing the solution of the game  $  \Gamma _ {1} $;
 +
regularization of the problem relative to the pay-off function of  $  \textrm{ II } $
 +
is effected at the expense of introducing an artificial inaccuracy in the determination of  $  \max _ {x _ {2}  \in X _ {2} }  f _ {2} ( x _ {1} , x _ {2} ) $.
 +
The determination of the magnitude  $  G _ {2} $
 +
reduces to the solution of a set of problems in [[Mathematical programming|mathematical programming]].
 +
 
 +
Suppose that for arbitrary  $  \epsilon > 0 $
 +
the following functions, sets and numbers are defined:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327049.png" />, where now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327050.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327051.png" /> is achieved.
+
$$
 +
f _ {2} ( x _ {1}  ^ {H} ( x _ {2} ), x _ {2} )  = \
 +
\min _ {x _ {1} \in X _ {1} } \
 +
f _ {2} ( x _ {1} , x _ {2} ),
 +
$$
  
A relation between the results in these games determines for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327052.png" /> knowledge of the information concerning the actions of player II: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327053.png" />. Using the scheme indicated in the construction of the strategies of the players, games with arbitrarily deep recursion can be formulated. The following assertion holds: in the games <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327055.png" />, the largest guaranteed result for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327056.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327057.png" />; in the games <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327058.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327059.png" />, the largest guaranteed result is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327060.png" />. The problem of determining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327061.png" /> is related to a class of problems of minimax type with related restrictions.
+
$$
 +
L _ {2}  = \max _ {x _ {2} \in X _ {2} }  f _ {2} ( x _ {1}  ^ {H} ( x _ {2} ), x _ {2} )  =  \max _ {x _ {2} \in X _ {2} }  \min _ {x _ {1} \in X _ {1} }  f _ {2} ( x _ {1} , x _ {2} ),
 +
$$
  
Methods have been developed for solving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327062.png" /> using penalty functions, necessary optimality conditions and approximation to the original game by games with unique responses for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327063.png" />. Complete solutions are known for special classes of games: games with close interests, bimatrix games, bilinear games, etc. The problem of determining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327064.png" /> is not well-posed relative to changes in the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327065.png" /> in the uniform metric and of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327067.png" /> in the Hausdorff metric. A general method has been proposed for regularizing the solution of the game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327068.png" />; regularization of the problem relative to the pay-off function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327069.png" /> is effected at the expense of introducing an artificial inaccuracy in the determination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327070.png" />. The determination of the magnitude <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327071.png" /> reduces to the solution of a set of problems in [[Mathematical programming|mathematical programming]].
+
$$
 +
E _ {2}  = \{ x _ {2} \in X _ {2} : f _ {2} ( x _ {1}  ^ {H} ( x _ {2} ), x _ {2} ) = L _ {2} \} ,
 +
$$
  
Suppose that for arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327072.png" /> the following functions, sets and numbers are defined:
+
$$
 +
= \left \{
 +
\begin{array}{ll}
 +
\sup _ {( x _ {1} , x _ {2} ) \in D }  f _ {1} ( x _ {1} , x _ {2} )  & \textrm{ if }  D \neq \emptyset ,  \\
 +
- \infty  & \textrm{ if }  D = \emptyset , \\
 +
\end{array}
  
<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/g/g043/g043270/g04327073.png" /></td> </tr></table>
+
\right .$$
  
<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/g/g043/g043270/g04327074.png" /></td> </tr></table>
+
$$
 +
f _ {1} ( x _ {1}  ^  \epsilon  , x _ {2}  ^  \epsilon  )  \geq  K - \epsilon
 +
,\  ( x _ {1}  ^  \epsilon  , x _ {2}  ^  \epsilon  ) \in D \neq \emptyset ,
 +
$$
  
<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/g/g043/g043270/g04327075.png" /></td> </tr></table>
+
$$
 +
= \inf _ {x _ {2} \in E _ {2} }
 +
\sup _ {x _ {1} \in X _ {1} }  f _ {1} ( x _ {1} , x _ {2} ),
 +
$$
  
<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/g/g043/g043270/g04327076.png" /></td> </tr></table>
+
$$
 +
= \{ ( x _ {1} , x _ {2} ): f _ {2} ( x _ {1} , x _ {2} ) > L _ {2} \} ,
 +
$$
  
<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/g/g043/g043270/g04327077.png" /></td> </tr></table>
+
$$
 +
f _ {1} ( x _ {1} ^ {a \epsilon } ( x _ {2} ), x _ {2} )  \geq  \sup _ {x _ {1} \in X _ {1} } \
 +
f _ {1} ( x _ {1} , x _ {2} ) - \epsilon .
 +
$$
  
<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/g/g043/g043270/g04327078.png" /></td> </tr></table>
+
Under the conditions stated,  $  G _ {2} = \max ( K, M) $
 +
and the strategy
  
<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/g/g043/g043270/g04327079.png" /></td> </tr></table>
+
$$
 +
\widetilde{x}  {} _ {1}  ^  \epsilon  = \
 +
\left \{
  
<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/g/g043/g043270/g04327080.png" /></td> </tr></table>
+
\begin{array}{lll}
 +
x _ {1}  ^  \epsilon  & \textrm{ if }  x _ {2} = x _ {2}  ^  \epsilon  ,  &K > M,  \\
 +
x _ {1} ^ {a \epsilon } ( x _ {2} )  & \textrm{ if }  x _ {2} \in E _ {2} ,  &K \leq  M,  \\
 +
x _ {1}  ^ {H} ( x _ {2} )  & \textrm{ otherwise } ,  &{}  \\
 +
\end{array}
  
Under the conditions stated, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327081.png" /> and the strategy
+
\right .$$
  
<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/g/g043/g043270/g04327082.png" /></td> </tr></table>
+
guarantees that player  $  \textrm{ I } $
 +
receives  $  \max ( K, M) - \epsilon $
 +
for sufficiently small  $  \epsilon $.  
 +
As is clear from the definitions, an optimal strategy consists of a certain number of stages, the last playing the part of a strategy by punishment.
  
guarantees that player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327083.png" /> receives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327084.png" /> for sufficiently small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327085.png" />. As is clear from the definitions, an optimal strategy consists of a certain number of stages, the last playing the part of a strategy by punishment.
+
If  $  L _ {2} < f _ {2} ( x _ {1} , x _ {2} ) $
 +
and if  $  f _ {2} ( x _ {1} , x _ {2} ) $
 +
has no local maxima with value  $  L _ {2} $
 +
on  $  X _ {1} \times X _ {2} $,  
 +
then  $  K \geq  M $
 +
and an optimal strategy has the simple form:
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327086.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327087.png" /> has no local maxima with value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327088.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327089.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327090.png" /> and an optimal strategy has the simple form:
+
$$
 +
\widetilde{x}  {} _ {1}  ^  \epsilon  = \
 +
\left \{
  
<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/g/g043/g043270/g04327091.png" /></td> </tr></table>
+
\begin{array}{ll}
 +
x _ {1}  ^  \epsilon  & \textrm{ if }  x _ {2} = x _ {2}  ^  \epsilon  ,  \\
 +
x _ {1}  ^ {H} ( x _ {2} )  & \textrm{ if }  x _ {2} \neq x _ {2}  ^  \epsilon  . \\
 +
\end{array}
  
A solution can be found in a similar way for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327092.png" />; it also reduces to the solution of a sequence of problems in mathematical programming.
+
\right .$$
  
When side payments for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327093.png" /> are introduced into a game with a hierarchy structure as functions of the choices of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327094.png" />, the expression for the largest guaranteed result for player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327095.png" /> is significantly simplified. In the game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327096.png" />, where
+
A solution can be found in a similar way for $  \Gamma _ {3} $;
 +
it also reduces to the solution of a sequence of problems in mathematical programming.
  
<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/g/g043/g043270/g04327097.png" /></td> </tr></table>
+
When side payments for player  $  \textrm{ I } $
 +
are introduced into a game with a hierarchy structure as functions of the choices of player  $  \textrm{ II } $,
 +
the expression for the largest guaranteed result for player  $  \textrm{ I } $
 +
is significantly simplified. In the game  $  \Gamma _ {2} $,
 +
where
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327098.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g04327099.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270100.png" />, and player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270101.png" /> chooses strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270102.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270103.png" />, the determination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270104.png" /> reduces to the solution of a problem in mathematical programming:
+
$$
 +
w _ {1}  = \
 +
f _ {1} ( x _ {1} , x _ {2} ) - z,\ \
 +
w _ {2}  = \
 +
f _ {2} ( x _ {1} , x _ {2} ) + z,
 +
$$
  
<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/g/g043/g043270/g043270105.png" /></td> </tr></table>
+
$  x _ {1} \in X _ {1} $,
 +
$  x _ {2} \in X _ {2} $,
 +
$  0 \leq  z \leq  z  ^ {0} $,
 +
and player  $  \textrm{ I } $
 +
chooses strategies  $  x _ {1} ( x _ {2} ) $,
 +
$  z( x _ {2} ) $,
 +
the determination of  $  G _ {2} $
 +
reduces to the solution of a problem in mathematical programming:
  
<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/g/g043/g043270/g043270106.png" /></td> </tr></table>
+
$$
 +
G _ {2}  = \
 +
\max _ {x _ {1} , x _ {2} } \
 +
\min  [ f _ {1} ( x _ {1} , x _ {2} ),\
 +
f _ {1} ( x _ {1} , x _ {2} ) +
 +
f _ {2} ( x _ {1} , x _ {2} ) - L _ {2} ],
 +
$$
  
In general, the application of arbitrarily small side payments <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270107.png" /> in games with a hierarchy structure allows player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270108.png" /> to achieve the largest possible guaranteed result, reckoning on the generosity of his partner.
+
$$
 +
f _ {2} ( x _ {1} , x _ {2} )  \geq  L _ {2} - z  ^ {0} .
 +
$$
  
The games formulated can be generalized to the case of step-by-step receipt and use of information in a dynamical way. In the case where the states of the players are described by differential or difference equations there arises an extensive class of problems connected with the diversity of the forms of the players' information on the state and trend as a physical process as well as a process of making a decision. Generalizations of the games <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270110.png" /> are considered to the case of prohibited situations, that is, the presence of joint restrictions on the players' choices.
+
In general, the application of arbitrarily small side payments  $  z ( x _ {2} ) $
 +
in games with a hierarchy structure allows player  $  \textrm{ I } $
 +
to achieve the largest possible guaranteed result, reckoning on the generosity of his partner.
  
The formulations mentioned relate to the case where player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270111.png" /> has complete information on the pay-off function and the set of his choices. If player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270112.png" /> knows that the continuous pay-off function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270113.png" /> satisfies the inequalities
+
The games formulated can be generalized to the case of step-by-step receipt and use of information in a dynamical way. In the case where the states of the players are described by differential or difference equations there arises an extensive class of problems connected with the diversity of the forms of the players' information on the state and trend as a physical process as well as a process of making a decision. Generalizations of the games  $  \Gamma _ {1} $
 +
and $  \Gamma _ {2} $
 +
are considered to the case of prohibited situations, that is, the presence of joint restrictions on the players' choices.
  
<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/g/g043/g043270/g043270114.png" /></td> </tr></table>
+
The formulations mentioned relate to the case where player  $  \textrm{ I } $
 +
has complete information on the pay-off function and the set of his choices. If player  $  \textrm{ I } $
 +
knows that the continuous pay-off function of  $  \textrm{ II } $
 +
satisfies the inequalities
  
for known continuous functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270115.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270116.png" />, then the largest guaranteed result in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270117.png" /> is defined by maximizing conditions for a function of a single variable.
+
$$
 +
f _ {2}  ^ {-} ( x _ {1} , x _ {2} )  \leq  \
 +
f _ {2} ( x _ {1} , x _ {2} )  \leq  \
 +
f _ {2}  ^ {+} ( x _ {1} , x _ {2} )
 +
$$
  
A more general version of the case where player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270118.png" /> has incomplete information of the interests of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270119.png" /> is as follows. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270120.png" /> knows the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270121.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270122.png" />, and knows that the true pay-off function satisfies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270123.png" /> for some unknown value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270124.png" />. With such information, the solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270125.png" /> for finite sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270126.png" /> reduces to maximizing functions of several variables; for infinite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270127.png" /> the problem is more complicated. The presence of indefinite factors in the formulation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270128.png" /> does not lead to a significant complication of the problem, since this case reduces to that of a case without indefiniteness. In the indefinite case of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270129.png" />, a number of problems are considered, where the concept of a players' strategy is extended at the expense of the hypothesis that player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270130.png" /> communicates his effectiveness criterion to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270131.png" />, that is, some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270132.png" />, so that the final choice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270133.png" /> can be performed by obtaining information about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270134.png" /> and the effectiveness criterion of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270135.png" />. If player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270136.png" /> is cautious in the case, that is, he holds to the principle of the largest guaranteed result, and player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270137.png" /> communicates to him the parametrized strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270138.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270139.png" />, then it can be shown that the largest guaranteed result of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270140.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270141.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270142.png" /> is the largest guaranteed result of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270143.png" /> in the game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270144.png" /> for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270145.png" />. A similar result holds without assuming that player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270146.png" /> is cautious, if player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270147.png" /> knows a parametric family of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270148.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270149.png" />, one of which is the true one.
+
for known continuous functions $  f _ {2}  ^ {-} ( x _ {1} , x _ {2} ) $
 +
and $  f _ {2}  ^ {+} ( x _ {1} , x _ {2} ) $,  
 +
then the largest guaranteed result in  $  \Gamma _ {2} $
 +
is defined by maximizing conditions for a function of a single variable.
  
Close to the problem just discussed is that of finding the largest guaranteed result of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270150.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270151.png" /> in the presence of a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270152.png" /> in the pay-off functions of the players characterizing environmental uncertainty, where player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270153.png" /> is informed by his choice of the concrete value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270154.png" /> and player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270155.png" /> is not informed.
+
A more general version of the case where player  $  \textrm{ I } $
 +
has incomplete information of the interests of player $  \textrm{ II } $
 +
is as follows. Player  $  \textrm{ I } $
 +
knows the function  $  f _ {2} ( x _ {1} , x _ {2} , \alpha ) $,
 +
$  \alpha \in A $,
 +
and knows that the true pay-off function satisfies  $  f _ {2} ( x _ {1} , x _ {2} ) = f _ {2} ( x _ {1} , x _ {2} , \alpha _ {0} ) $
 +
for some unknown value  $  \alpha = \alpha _ {0} $.  
 +
With such information, the solution of  $  \Gamma _ {2} $
 +
for finite sets  $  A $
 +
reduces to maximizing functions of several variables; for infinite  $  A $
 +
the problem is more complicated. The presence of indefinite factors in the formulation of  $  \Gamma _ {1} $
 +
does not lead to a significant complication of the problem, since this case reduces to that of a case without indefiniteness. In the indefinite case of  $  \Gamma _ {2} $,
 +
a number of problems are considered, where the concept of a players' strategy is extended at the expense of the hypothesis that player  $  \textrm{ I } $
 +
communicates his effectiveness criterion to player  $  \textrm{ II } $,  
 +
that is, some  $  \widehat{a}  \in A $,
 +
so that the final choice  $  x _ {1} $
 +
can be performed by obtaining information about  $  x _ {2} $
 +
and the effectiveness criterion of player $  \textrm{ II } $.  
 +
If player  $  \textrm{ II } $
 +
is cautious in the case, that is, he holds to the principle of the largest guaranteed result, and player  $  \textrm{ I } $
 +
communicates to him the parametrized strategy  $  x _ {1 \alpha }  ( x _ {2} , \widehat{a}  ) $,
 +
$  \alpha \in A $,
 +
then it can be shown that the largest guaranteed result of player  $  \textrm{ I } $
 +
is  $  G _ {2} = \inf _ {\alpha \in A }  G _ {2 \alpha }  $,
 +
where  $  G _ {2 \alpha }  $
 +
is the largest guaranteed result of player  $  \textrm{ I } $
 +
in the game  $  \Gamma _ {2} $
 +
for a given  $  \alpha \in A $.  
 +
A similar result holds without assuming that player  $  \textrm{ II } $
 +
is cautious, if player $  \textrm{ I } $
 +
knows a parametric family of sets  $  X _ {2} ( \alpha ) $,
 +
$  \alpha \in A $,
 +
one of which is the true one.
  
In the case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270156.png" /> is repeated indefinitely, the extent to which player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270157.png" /> is informed about the interests and possibilities of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270158.png" /> can be increased because of the information contained in the responses of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270159.png" /> to the action of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270160.png" />. Procedures are accordingly constructed that allow player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270161.png" />, starting with some play, to obtain a result arbitrarily close to the result guaranteed to him by complete information. Such results are also obtained in a game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270162.png" /> with indefiniteness. If the moments when player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270163.png" /> obtains information on the indeterminate factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270164.png" /> are not fixed, then player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270165.png" /> can obtain in the remaining repetitions a result that is arbitrarily close to that guaranteed to him by complete information, under weaker assumptions on the pay-off functions of the participants. Moreover, player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270166.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270167.png" /> can obtain a similar result simply by observing the values of his own pay-off function.
+
Close to the problem just discussed is that of finding the largest guaranteed result of player  $  \textrm{ I } $
 +
in  $  \Gamma _ {2} $
 +
in the presence of a parameter  $  \alpha $
 +
in the pay-off functions of the players characterizing environmental uncertainty, where player  $  \textrm{ II } $
 +
is informed by his choice of the concrete value of  $  \alpha $
 +
and player  $  \textrm{ I } $
 +
is not informed.
 +
 
 +
In the case where $  \Gamma _ {2} $
 +
is repeated indefinitely, the extent to which player $  \textrm{ I } $
 +
is informed about the interests and possibilities of player $  \textrm{ II } $
 +
can be increased because of the information contained in the responses of player $  \textrm{ II } $
 +
to the action of player $  \textrm{ I } $.  
 +
Procedures are accordingly constructed that allow player $  \textrm{ I } $,  
 +
starting with some play, to obtain a result arbitrarily close to the result guaranteed to him by complete information. Such results are also obtained in a game $  \Gamma _ {1} $
 +
with indefiniteness. If the moments when player $  \textrm{ I } $
 +
obtains information on the indeterminate factors $  \alpha $
 +
are not fixed, then player $  \textrm{ I } $
 +
can obtain in the remaining repetitions a result that is arbitrarily close to that guaranteed to him by complete information, under weaker assumptions on the pay-off functions of the participants. Moreover, player $  \textrm{ I } $
 +
in $  \Gamma _ {1} $
 +
can obtain a similar result simply by observing the values of his own pay-off function.
  
 
The formulations of the games under consideration carry over naturally to the case of many persons whose interactions, in the sense of priority of action and transfer of information, have a hierarchy structure. In analyzing these games it is necessary to stipulate a rule of interaction of the players on the same level. Thus, when three-person games are considered, where the pay-off functions of the players have the form
 
The formulations of the games under consideration carry over naturally to the case of many persons whose interactions, in the sense of priority of action and transfer of information, have a hierarchy structure. In analyzing these games it is necessary to stipulate a rule of interaction of the players on the same level. Thus, when three-person games are considered, where the pay-off functions of the players have 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/g/g043/g043270/g043270168.png" /></td> </tr></table>
+
$$
 +
w _ {1}  = f _ {1} ( x _ {1} , x _ {2} , x _ {3} ),
 +
$$
  
<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/g/g043/g043270/g043270169.png" /></td> </tr></table>
+
$$
 +
w _ {2}  = f _ {2} ( x _ {1} , x _ {2} , x _ {3} ),\ \
 +
w _ {3}  = f _ {3} ( x _ {1} , x _ {2} , x _ {3} ),
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270170.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270171.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270172.png" />, then in order to describe the largest guaranteed result of a chosen player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270173.png" /> who has priority of action, it is necessary to make concrete his information on the behaviour of the players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270174.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270175.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270176.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270177.png" /> form a rigid [[Coalition|coalition]] to the knowledge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270178.png" />, that is, they formulate coalition criteria and determine their choices together, this case is equivalent to the previous two-person games as far as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270179.png" /> is concerned. Clear results have been obtained also in the case where the players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270180.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270181.png" /> either are in a coalition known to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270182.png" /> or act as individuals if they can then obtain a better result than is given by coalition; in this case neither player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270183.png" /> nor player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270184.png" /> has independent information on the moves of the other, and the order of these moves is given by player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270185.png" />. Games having a  "fan"  structure have been analyzed in detail: a distinguished player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270186.png" /> (who controls the centre) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270187.png" /> other players on the next level in the hierarchy (the producers of the output) tend to an increase in the pay-off functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270188.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270189.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270190.png" />, respectively, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270191.png" /> is the choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270192.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270193.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270194.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270195.png" /> is the set of choices of the players on the lower level of the hierarchy, who act moreover, independently, and the player with index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270196.png" /> deals with the choice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270197.png" />. All sets are assumed to be compact and the functions to be continuous. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270198.png" /> expects information (and will have it) on the choices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270199.png" /> and informs every player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270200.png" /> of the corresponding strategy function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270201.png" /> defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270202.png" /> with values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270203.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270204.png" />-person games with a hierarchy structure, expressions have been obtained for the largest guaranteed result of the distinguished player under various extensions of his class of strategies, at the expense of transmitting to the players on lower levels information on the actions of their colleagues, as well of of introducing actions of their colleagues and elements of bluff. As with games for two persons, the possibility of side payments to the distinguished player simplifies the determination of his guaranteed result considerably.
+
$  x _ {1} \in X _ {1} $,  
 +
$  x _ {2} \in X _ {2} $,  
 +
$  x _ {3} \in X _ {3} $,  
 +
then in order to describe the largest guaranteed result of a chosen player $  \textrm{ I } $
 +
who has priority of action, it is necessary to make concrete his information on the behaviour of the players $  \textrm{ II } $
 +
and $  \textrm{ III } $.  
 +
If $  \textrm{ II } $
 +
and $  \textrm{ III } $
 +
form a rigid [[Coalition|coalition]] to the knowledge of $  \textrm{ I } $,  
 +
that is, they formulate coalition criteria and determine their choices together, this case is equivalent to the previous two-person games as far as $  \textrm{ I } $
 +
is concerned. Clear results have been obtained also in the case where the players $  \textrm{ II } $
 +
and $  \textrm{ III } $
 +
either are in a coalition known to player $  \textrm{ I } $
 +
or act as individuals if they can then obtain a better result than is given by coalition; in this case neither player $  \textrm{ II } $
 +
nor player $  \textrm{ III } $
 +
has independent information on the moves of the other, and the order of these moves is given by player $  \textrm{ I } $.  
 +
Games having a  "fan"  structure have been analyzed in detail: a distinguished player $  \Pi _ {0} $(
 +
who controls the centre) and $  n $
 +
other players on the next level in the hierarchy (the producers of the output) tend to an increase in the pay-off functions $  f _ {0} ( x _ {0} , x) $
 +
and $  f _ {i} ( x _ {0}  ^ {i} , x _ {i} ) $,  
 +
$  i = 1 \dots n $,  
 +
respectively, where $  x _ {0} = \{ x _ {0}  ^ {1} \dots x _ {0}  ^ {n} \} $
 +
is the choice of $  \Pi _ {0} $,  
 +
$  x _ {0} \in X _ {0} $,  
 +
$  x _ {0}  ^ {i} \in X _ {0}  ^ {i} $,  
 +
and $  x = \{ x _ {1} \dots x _ {n} \} $
 +
is the set of choices of the players on the lower level of the hierarchy, who act moreover, independently, and the player with index $  i $
 +
deals with the choice $  x _ {i} \in X _ {i} $.  
 +
All sets are assumed to be compact and the functions to be continuous. Player $  \Pi _ {0} $
 +
expects information (and will have it) on the choices $  x _ {i} \in X _ {i} $
 +
and informs every player $  i $
 +
of the corresponding strategy function $  \widetilde{x}  {} _ {0}  ^ {i} = x _ {0}  ^ {i} ( x _ {i} ) $
 +
defined on $  X _ {i} $
 +
with values in $  X _ {0}  ^ {i} $.  
 +
For $  n $-
 +
person games with a hierarchy structure, expressions have been obtained for the largest guaranteed result of the distinguished player under various extensions of his class of strategies, at the expense of transmitting to the players on lower levels information on the actions of their colleagues, as well of of introducing actions of their colleagues and elements of bluff. As with games for two persons, the possibility of side payments to the distinguished player simplifies the determination of his guaranteed result considerably.
  
Using games with a hierarchy structure, a natural interpretation has been obtained of the various mechanisms of centralized control of active economic subsystems. The game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270205.png" /> describes the process of centralized control by means of prices; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270206.png" /> models the policy of penalties and encouragement via stimulation of production; and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270207.png" /> models the process of resource distribution as a function of the industrial methods of using these resources.
+
Using games with a hierarchy structure, a natural interpretation has been obtained of the various mechanisms of centralized control of active economic subsystems. The game $  \Gamma _ {1} $
 +
describes the process of centralized control by means of prices; $  \Gamma _ {2} $
 +
models the policy of penalties and encouragement via stimulation of production; and $  \Gamma _ {3} $
 +
models the process of resource distribution as a function of the industrial methods of using these resources.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  Yu.B. Germeier,  "Non-antagonistic games" , Reidel  (1986)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  Yu.B. Germeier,  "Non-antagonistic games" , Reidel  (1986)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
Game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270208.png" /> is often referred to as a Stackelberg game. In the formulation given, player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270209.png" /> is the leader who conveys his decision to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270210.png" />, the follower, who makes his decision afterwards. See [[#References|[a1]]], Chapt. IV. In the economic literature, game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270211.png" /> is said to have an incentive structure. Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270212.png" />, the leader again, does not announce his action, but instead his strategy to player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270213.png" />. The decision of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270214.png" /> then also determines the action (i.e. decision) of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270215.png" />; player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270216.png" />'s decision is substituted into player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270217.png" />'s strategy, which results in player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043270/g043270218.png" />'s decision [[#References|[a2]]].
+
Game $  \Gamma _ {1} $
 +
is often referred to as a Stackelberg game. In the formulation given, player $  \textrm{ I } $
 +
is the leader who conveys his decision to player $  \textrm{ II } $,  
 +
the follower, who makes his decision afterwards. See [[#References|[a1]]], Chapt. IV. In the economic literature, game $  \Gamma _ {2} $
 +
is said to have an incentive structure. Player $  \textrm{ I } $,  
 +
the leader again, does not announce his action, but instead his strategy to player $  \textrm{ II } $.  
 +
The decision of player $  \textrm{ II } $
 +
then also determines the action (i.e. decision) of player $  \textrm{ I } $;  
 +
player $  \textrm{ II } $'
 +
s decision is substituted into player $  \textrm{ I } $'
 +
s strategy, which results in player $  \textrm{ I } $'
 +
s decision [[#References|[a2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Basar,  G.J. Olsder,  "Dynamic noncooperative game theory" , Acad. Press  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.B. Luk,  Y.C. Ho,  G.J. Olsder,  "A control-theoretical view on incentives"  ''Automatica'' , '''18'''  (1982)  pp. 167–179</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Basar,  G.J. Olsder,  "Dynamic noncooperative game theory" , Acad. Press  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.B. Luk,  Y.C. Ho,  G.J. Olsder,  "A control-theoretical view on incentives"  ''Automatica'' , '''18'''  (1982)  pp. 167–179</TD></TR></table>

Latest revision as of 19:41, 5 June 2020


A model of a conflict situation with a fixed sequence of moves and interchange of information between the players. The main object of investigation in the theory of games with a hierarchy structure is the problem of finding the largest guaranteed result and an optimal strategy for a selected player. Suppose that players $ \textrm{ I } $ and $ \textrm{ II } $, respectively, tend to an increase in the pay-off functions $ f _ {1} ( x _ {1} , x _ {2} ) $ and $ f _ {2} ( x _ {1} , x _ {2} ) $( cf. Gain function), continuous on the product of two compacta $ X _ {1} , X _ {2} $; $ x _ {1} \in X _ {1} $, $ x _ {2} \in X _ {2} $. The following different types of games can be formulated according to the character of the information and the order of moves.

The game $ \Gamma _ {1} $. Player $ \textrm{ I } $ chooses $ x _ {1} \in X _ {1} $ and communicates his choice to player $ \textrm{ II } $. Let

$$ P ( x _ {1} ) = \ \left \{ {x _ {2} } : { f _ {2} ( x _ {1} , x _ {2} ) = \max _ {y \in X _ {2} } \ f _ {2} ( x _ {1} , y) } \right \} $$

be the set of optimal choices of player $ \textrm{ II } $. Then the largest guaranteed result for player $ \textrm{ I } $ is

$$ G _ {1} = \ \sup _ {x _ {1} \in X _ {1} } \ \min _ {x _ {2} \in P ( x _ {1} ) } \ f _ {1} ( x _ {1} , x _ {2} ). $$

The game $ \Gamma _ {2} $. Player $ \textrm{ I } $ expects to have and indeed will have information on the choices of player $ \textrm{ II } $; he communicates his strategy, that is, a function $ \widetilde{x} _ {1} = x _ {1} ( x _ {2} ) $, where $ \widetilde{x} _ {1} \in \widetilde{X} _ {1} $— the set of all mappings from $ X _ {2} $ to $ X _ {1} $, to player $ \textrm{ II } $. The largest guaranteed result for player $ \textrm{ I } $ is

$$ G _ {2} = \ \sup _ {\widetilde{x} _ {1} \in \widetilde{X} _ {1} } \ \inf _ {x _ {2} \in P _ {2} ( \widetilde{x} _ {1} ) } \ f _ {1} ( \widetilde{x} _ {1} , x _ {2} ), $$

where the set of optimal choices of player $ \textrm{ II } $ is

$$ P _ {2} ( \widetilde{x} _ {1} ) = \ \left \{ {x _ {2} } : { f _ {2} ( \widetilde{x} _ {1} , x _ {2} ) = \sup _ {y \in X _ {2} } \ f _ {2} ( x _ {1} ( y), y) - \delta ( \widetilde{x} _ {1} ) } \right \} , $$

where $ \delta ( \widetilde{x} _ {1} ) \geq 0 $, and $ \delta ( \widetilde{x} _ {1} ) = 0 $ if and only if $ \max _ {y \in X _ {2} } f _ {2} ( x _ {1} ( y) y) $ is achieved.

The game $ \Gamma _ {3} $. Player $ \textrm{ I } $ expects to have and indeed will have information on the choices of player $ \textrm{ II } $ in the form $ \widetilde{x} _ {2} = x _ {2} ( x _ {1} ) $, where $ \widetilde{x} _ {2} \in \widetilde{X} _ {2} $— the set of all mappings from $ X _ {1} $ to $ X _ {2} $; he communicates to player $ \textrm{ II } $ his strategy $ {\widetilde{x} tilde } _ {1} = x _ {1} ( \widetilde{x} _ {2} ) $, where $ {\widetilde{x} tilde } _ {1} \in {\widetilde{X} tilde } _ {1} $— the set of mappings from $ \widetilde{X} _ {2} $ to $ X _ {1} $. The largest guaranteed result of player $ \textrm{ I } $ is

$$ G _ {3} = \ \sup _ {\begin{array}{c} {} \\ {\widetilde{x} tilde } _ {1} \in {\widetilde{X} tilde } _ {1} \end{array} } \ \inf _ {\begin{array}{c} {} \\ \widetilde{x} _ {2} \in P _ {3} ( \widetilde{x} tilde _ {1} ) \end{array} } \ f _ {1} ( {\widetilde{x} tilde } _ {1} , \widetilde{x} _ {2} ), $$

where

$$ P _ {3} ( {\widetilde{x} tilde } _ {1} ) = \ \left \{ {\widetilde{x} _ {2} } : { f _ {2} ( {\widetilde{x} tilde } _ {1} , \widetilde{x} _ {2} ) = \ \sup _ {\begin{array}{c} {} \\ y \in \widetilde{X} _ {2} \end{array} } \ f _ {2} ( x _ {1} ( y), y) - \delta ( {\widetilde{x} tilde } _ {1} ) } \right \} , $$

$ \delta ( {\widetilde{x} tilde } _ {1} ) \geq 0 $, where now $ \delta ( {\widetilde{x} tilde } _ {1} ) = 0 $ if and only if $ \max _ {y \in \widetilde{X} _ {2} } f _ {2} ( x _ {1} ( y), y) $ is achieved.

A relation between the results in these games determines for player $ \textrm{ I } $ knowledge of the information concerning the actions of player II: $ G _ {1} \leq G _ {3} \leq G _ {2} $. Using the scheme indicated in the construction of the strategies of the players, games with arbitrarily deep recursion can be formulated. The following assertion holds: in the games $ \Gamma _ {2m} $, $ m > 1 $, the largest guaranteed result for player $ \textrm{ I } $ is $ G _ {2} $; in the games $ \Gamma _ {2m + 1 } $, $ m > 1 $, the largest guaranteed result is $ G _ {3} $. The problem of determining $ G _ {1} $ is related to a class of problems of minimax type with related restrictions.

Methods have been developed for solving $ \Gamma _ {1} $ using penalty functions, necessary optimality conditions and approximation to the original game by games with unique responses for player $ \textrm{ II } $. Complete solutions are known for special classes of games: games with close interests, bimatrix games, bilinear games, etc. The problem of determining $ G _ {1} $ is not well-posed relative to changes in the function $ f _ {2} ( x _ {1} , x _ {2} ) $ in the uniform metric and of the sets $ X _ {1} $ and $ X _ {2} $ in the Hausdorff metric. A general method has been proposed for regularizing the solution of the game $ \Gamma _ {1} $; regularization of the problem relative to the pay-off function of $ \textrm{ II } $ is effected at the expense of introducing an artificial inaccuracy in the determination of $ \max _ {x _ {2} \in X _ {2} } f _ {2} ( x _ {1} , x _ {2} ) $. The determination of the magnitude $ G _ {2} $ reduces to the solution of a set of problems in mathematical programming.

Suppose that for arbitrary $ \epsilon > 0 $ the following functions, sets and numbers are defined:

$$ f _ {2} ( x _ {1} ^ {H} ( x _ {2} ), x _ {2} ) = \ \min _ {x _ {1} \in X _ {1} } \ f _ {2} ( x _ {1} , x _ {2} ), $$

$$ L _ {2} = \max _ {x _ {2} \in X _ {2} } f _ {2} ( x _ {1} ^ {H} ( x _ {2} ), x _ {2} ) = \max _ {x _ {2} \in X _ {2} } \min _ {x _ {1} \in X _ {1} } f _ {2} ( x _ {1} , x _ {2} ), $$

$$ E _ {2} = \{ x _ {2} \in X _ {2} : f _ {2} ( x _ {1} ^ {H} ( x _ {2} ), x _ {2} ) = L _ {2} \} , $$

$$ K = \left \{ \begin{array}{ll} \sup _ {( x _ {1} , x _ {2} ) \in D } f _ {1} ( x _ {1} , x _ {2} ) & \textrm{ if } D \neq \emptyset , \\ - \infty & \textrm{ if } D = \emptyset , \\ \end{array} \right .$$

$$ f _ {1} ( x _ {1} ^ \epsilon , x _ {2} ^ \epsilon ) \geq K - \epsilon ,\ ( x _ {1} ^ \epsilon , x _ {2} ^ \epsilon ) \in D \neq \emptyset , $$

$$ M = \inf _ {x _ {2} \in E _ {2} } \sup _ {x _ {1} \in X _ {1} } f _ {1} ( x _ {1} , x _ {2} ), $$

$$ D = \{ ( x _ {1} , x _ {2} ): f _ {2} ( x _ {1} , x _ {2} ) > L _ {2} \} , $$

$$ f _ {1} ( x _ {1} ^ {a \epsilon } ( x _ {2} ), x _ {2} ) \geq \sup _ {x _ {1} \in X _ {1} } \ f _ {1} ( x _ {1} , x _ {2} ) - \epsilon . $$

Under the conditions stated, $ G _ {2} = \max ( K, M) $ and the strategy

$$ \widetilde{x} {} _ {1} ^ \epsilon = \ \left \{ \begin{array}{lll} x _ {1} ^ \epsilon & \textrm{ if } x _ {2} = x _ {2} ^ \epsilon , &K > M, \\ x _ {1} ^ {a \epsilon } ( x _ {2} ) & \textrm{ if } x _ {2} \in E _ {2} , &K \leq M, \\ x _ {1} ^ {H} ( x _ {2} ) & \textrm{ otherwise } , &{} \\ \end{array} \right .$$

guarantees that player $ \textrm{ I } $ receives $ \max ( K, M) - \epsilon $ for sufficiently small $ \epsilon $. As is clear from the definitions, an optimal strategy consists of a certain number of stages, the last playing the part of a strategy by punishment.

If $ L _ {2} < f _ {2} ( x _ {1} , x _ {2} ) $ and if $ f _ {2} ( x _ {1} , x _ {2} ) $ has no local maxima with value $ L _ {2} $ on $ X _ {1} \times X _ {2} $, then $ K \geq M $ and an optimal strategy has the simple form:

$$ \widetilde{x} {} _ {1} ^ \epsilon = \ \left \{ \begin{array}{ll} x _ {1} ^ \epsilon & \textrm{ if } x _ {2} = x _ {2} ^ \epsilon , \\ x _ {1} ^ {H} ( x _ {2} ) & \textrm{ if } x _ {2} \neq x _ {2} ^ \epsilon . \\ \end{array} \right .$$

A solution can be found in a similar way for $ \Gamma _ {3} $; it also reduces to the solution of a sequence of problems in mathematical programming.

When side payments for player $ \textrm{ I } $ are introduced into a game with a hierarchy structure as functions of the choices of player $ \textrm{ II } $, the expression for the largest guaranteed result for player $ \textrm{ I } $ is significantly simplified. In the game $ \Gamma _ {2} $, where

$$ w _ {1} = \ f _ {1} ( x _ {1} , x _ {2} ) - z,\ \ w _ {2} = \ f _ {2} ( x _ {1} , x _ {2} ) + z, $$

$ x _ {1} \in X _ {1} $, $ x _ {2} \in X _ {2} $, $ 0 \leq z \leq z ^ {0} $, and player $ \textrm{ I } $ chooses strategies $ x _ {1} ( x _ {2} ) $, $ z( x _ {2} ) $, the determination of $ G _ {2} $ reduces to the solution of a problem in mathematical programming:

$$ G _ {2} = \ \max _ {x _ {1} , x _ {2} } \ \min [ f _ {1} ( x _ {1} , x _ {2} ),\ f _ {1} ( x _ {1} , x _ {2} ) + f _ {2} ( x _ {1} , x _ {2} ) - L _ {2} ], $$

$$ f _ {2} ( x _ {1} , x _ {2} ) \geq L _ {2} - z ^ {0} . $$

In general, the application of arbitrarily small side payments $ z ( x _ {2} ) $ in games with a hierarchy structure allows player $ \textrm{ I } $ to achieve the largest possible guaranteed result, reckoning on the generosity of his partner.

The games formulated can be generalized to the case of step-by-step receipt and use of information in a dynamical way. In the case where the states of the players are described by differential or difference equations there arises an extensive class of problems connected with the diversity of the forms of the players' information on the state and trend as a physical process as well as a process of making a decision. Generalizations of the games $ \Gamma _ {1} $ and $ \Gamma _ {2} $ are considered to the case of prohibited situations, that is, the presence of joint restrictions on the players' choices.

The formulations mentioned relate to the case where player $ \textrm{ I } $ has complete information on the pay-off function and the set of his choices. If player $ \textrm{ I } $ knows that the continuous pay-off function of $ \textrm{ II } $ satisfies the inequalities

$$ f _ {2} ^ {-} ( x _ {1} , x _ {2} ) \leq \ f _ {2} ( x _ {1} , x _ {2} ) \leq \ f _ {2} ^ {+} ( x _ {1} , x _ {2} ) $$

for known continuous functions $ f _ {2} ^ {-} ( x _ {1} , x _ {2} ) $ and $ f _ {2} ^ {+} ( x _ {1} , x _ {2} ) $, then the largest guaranteed result in $ \Gamma _ {2} $ is defined by maximizing conditions for a function of a single variable.

A more general version of the case where player $ \textrm{ I } $ has incomplete information of the interests of player $ \textrm{ II } $ is as follows. Player $ \textrm{ I } $ knows the function $ f _ {2} ( x _ {1} , x _ {2} , \alpha ) $, $ \alpha \in A $, and knows that the true pay-off function satisfies $ f _ {2} ( x _ {1} , x _ {2} ) = f _ {2} ( x _ {1} , x _ {2} , \alpha _ {0} ) $ for some unknown value $ \alpha = \alpha _ {0} $. With such information, the solution of $ \Gamma _ {2} $ for finite sets $ A $ reduces to maximizing functions of several variables; for infinite $ A $ the problem is more complicated. The presence of indefinite factors in the formulation of $ \Gamma _ {1} $ does not lead to a significant complication of the problem, since this case reduces to that of a case without indefiniteness. In the indefinite case of $ \Gamma _ {2} $, a number of problems are considered, where the concept of a players' strategy is extended at the expense of the hypothesis that player $ \textrm{ I } $ communicates his effectiveness criterion to player $ \textrm{ II } $, that is, some $ \widehat{a} \in A $, so that the final choice $ x _ {1} $ can be performed by obtaining information about $ x _ {2} $ and the effectiveness criterion of player $ \textrm{ II } $. If player $ \textrm{ II } $ is cautious in the case, that is, he holds to the principle of the largest guaranteed result, and player $ \textrm{ I } $ communicates to him the parametrized strategy $ x _ {1 \alpha } ( x _ {2} , \widehat{a} ) $, $ \alpha \in A $, then it can be shown that the largest guaranteed result of player $ \textrm{ I } $ is $ G _ {2} = \inf _ {\alpha \in A } G _ {2 \alpha } $, where $ G _ {2 \alpha } $ is the largest guaranteed result of player $ \textrm{ I } $ in the game $ \Gamma _ {2} $ for a given $ \alpha \in A $. A similar result holds without assuming that player $ \textrm{ II } $ is cautious, if player $ \textrm{ I } $ knows a parametric family of sets $ X _ {2} ( \alpha ) $, $ \alpha \in A $, one of which is the true one.

Close to the problem just discussed is that of finding the largest guaranteed result of player $ \textrm{ I } $ in $ \Gamma _ {2} $ in the presence of a parameter $ \alpha $ in the pay-off functions of the players characterizing environmental uncertainty, where player $ \textrm{ II } $ is informed by his choice of the concrete value of $ \alpha $ and player $ \textrm{ I } $ is not informed.

In the case where $ \Gamma _ {2} $ is repeated indefinitely, the extent to which player $ \textrm{ I } $ is informed about the interests and possibilities of player $ \textrm{ II } $ can be increased because of the information contained in the responses of player $ \textrm{ II } $ to the action of player $ \textrm{ I } $. Procedures are accordingly constructed that allow player $ \textrm{ I } $, starting with some play, to obtain a result arbitrarily close to the result guaranteed to him by complete information. Such results are also obtained in a game $ \Gamma _ {1} $ with indefiniteness. If the moments when player $ \textrm{ I } $ obtains information on the indeterminate factors $ \alpha $ are not fixed, then player $ \textrm{ I } $ can obtain in the remaining repetitions a result that is arbitrarily close to that guaranteed to him by complete information, under weaker assumptions on the pay-off functions of the participants. Moreover, player $ \textrm{ I } $ in $ \Gamma _ {1} $ can obtain a similar result simply by observing the values of his own pay-off function.

The formulations of the games under consideration carry over naturally to the case of many persons whose interactions, in the sense of priority of action and transfer of information, have a hierarchy structure. In analyzing these games it is necessary to stipulate a rule of interaction of the players on the same level. Thus, when three-person games are considered, where the pay-off functions of the players have the form

$$ w _ {1} = f _ {1} ( x _ {1} , x _ {2} , x _ {3} ), $$

$$ w _ {2} = f _ {2} ( x _ {1} , x _ {2} , x _ {3} ),\ \ w _ {3} = f _ {3} ( x _ {1} , x _ {2} , x _ {3} ), $$

$ x _ {1} \in X _ {1} $, $ x _ {2} \in X _ {2} $, $ x _ {3} \in X _ {3} $, then in order to describe the largest guaranteed result of a chosen player $ \textrm{ I } $ who has priority of action, it is necessary to make concrete his information on the behaviour of the players $ \textrm{ II } $ and $ \textrm{ III } $. If $ \textrm{ II } $ and $ \textrm{ III } $ form a rigid coalition to the knowledge of $ \textrm{ I } $, that is, they formulate coalition criteria and determine their choices together, this case is equivalent to the previous two-person games as far as $ \textrm{ I } $ is concerned. Clear results have been obtained also in the case where the players $ \textrm{ II } $ and $ \textrm{ III } $ either are in a coalition known to player $ \textrm{ I } $ or act as individuals if they can then obtain a better result than is given by coalition; in this case neither player $ \textrm{ II } $ nor player $ \textrm{ III } $ has independent information on the moves of the other, and the order of these moves is given by player $ \textrm{ I } $. Games having a "fan" structure have been analyzed in detail: a distinguished player $ \Pi _ {0} $( who controls the centre) and $ n $ other players on the next level in the hierarchy (the producers of the output) tend to an increase in the pay-off functions $ f _ {0} ( x _ {0} , x) $ and $ f _ {i} ( x _ {0} ^ {i} , x _ {i} ) $, $ i = 1 \dots n $, respectively, where $ x _ {0} = \{ x _ {0} ^ {1} \dots x _ {0} ^ {n} \} $ is the choice of $ \Pi _ {0} $, $ x _ {0} \in X _ {0} $, $ x _ {0} ^ {i} \in X _ {0} ^ {i} $, and $ x = \{ x _ {1} \dots x _ {n} \} $ is the set of choices of the players on the lower level of the hierarchy, who act moreover, independently, and the player with index $ i $ deals with the choice $ x _ {i} \in X _ {i} $. All sets are assumed to be compact and the functions to be continuous. Player $ \Pi _ {0} $ expects information (and will have it) on the choices $ x _ {i} \in X _ {i} $ and informs every player $ i $ of the corresponding strategy function $ \widetilde{x} {} _ {0} ^ {i} = x _ {0} ^ {i} ( x _ {i} ) $ defined on $ X _ {i} $ with values in $ X _ {0} ^ {i} $. For $ n $- person games with a hierarchy structure, expressions have been obtained for the largest guaranteed result of the distinguished player under various extensions of his class of strategies, at the expense of transmitting to the players on lower levels information on the actions of their colleagues, as well of of introducing actions of their colleagues and elements of bluff. As with games for two persons, the possibility of side payments to the distinguished player simplifies the determination of his guaranteed result considerably.

Using games with a hierarchy structure, a natural interpretation has been obtained of the various mechanisms of centralized control of active economic subsystems. The game $ \Gamma _ {1} $ describes the process of centralized control by means of prices; $ \Gamma _ {2} $ models the policy of penalties and encouragement via stimulation of production; and $ \Gamma _ {3} $ models the process of resource distribution as a function of the industrial methods of using these resources.

References

[1] Yu.B. Germeier, "Non-antagonistic games" , Reidel (1986) (Translated from Russian)

Comments

Game $ \Gamma _ {1} $ is often referred to as a Stackelberg game. In the formulation given, player $ \textrm{ I } $ is the leader who conveys his decision to player $ \textrm{ II } $, the follower, who makes his decision afterwards. See [a1], Chapt. IV. In the economic literature, game $ \Gamma _ {2} $ is said to have an incentive structure. Player $ \textrm{ I } $, the leader again, does not announce his action, but instead his strategy to player $ \textrm{ II } $. The decision of player $ \textrm{ II } $ then also determines the action (i.e. decision) of player $ \textrm{ I } $; player $ \textrm{ II } $' s decision is substituted into player $ \textrm{ I } $' s strategy, which results in player $ \textrm{ I } $' s decision [a2].

References

[a1] T. Basar, G.J. Olsder, "Dynamic noncooperative game theory" , Acad. Press (1982)
[a2] P.B. Luk, Y.C. Ho, G.J. Olsder, "A control-theoretical view on incentives" Automatica , 18 (1982) pp. 167–179
How to Cite This Entry:
Game with a hierarchy structure. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Game_with_a_hierarchy_structure&oldid=47035
This article was adapted from an original article by I.A. Vatel'F.I. Ereshko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article