Game with a hierarchy structure

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