#Both authors contributed equally to this research.
1. Introduction
The Berge equilibrium (BE) is a solution concept in game theory introduced in [1] and formally defined in [2] . It was extended to mixed strategies (MBE) in [3] . The Berge equilibrium represents a strategy that is mutually cooperative. In other words, at a Berge equilibrium player i cannot gain a better payoff if any other player changes his strategy unilaterally. In effect, an MBE represents the situation where every
players choose the best joint mixed strategy for the remaining player. In this paper, we apply the concept of an MBE to finite extensive form games, where players make decisions sequentially. We consider here finite n-person extensive form games both with complete information and incomplete information. In a complete information game, each player is aware of the actions of the other players. In imperfect information games, however, players are not aware of the actions that other players choose.
The paper is organized as follows. In Section 2, we give the needed notation and definitions. In Section 3, we study the existence of an MBE in extensive form games. In Section 4, we give examples, and then give conclusions in Section 5.
2. Preliminaries
We use here a notation similar to that of [4] . An extensive form game G is written as
, where N is the set of the players, H is the set of histories, P is a function assigning a player to each non-terminal history, and I represents an information set.
Each history h is a sequence of actions
. In this paper, we assume that all the sequences of actions are finite. Hence the game is finite. Each history
ends with a terminal node which gives the utility value for each of the n-players. Each non-terminal node belongs to an information set
for a player i such that
. The set of all information sets for player i is
. If each information set has only one node, then the game is a perfect information game. In an imperfect information game, two or more nodes belong to some information set. If two or more nodes belong to the same information set, then they are connected with a dotted line. The idea is that if an information set includes only one decision node, then a player knows the actions that led to that node so the game is a perfect information game. An example of a 2-person extensive form game is show in Figure 1. In this game, player 1 makes a decision
or
. Next, player 2 makes a decision. After that, either the game is finished or player 1 makes a decision with imperfect information. The label above a node
means information set j for player i.
Each game in extensive form can be represented as a game in normal form [5] . The set of pure strategies
for each player i is the Cartesian product over the actions player i has at each of his information sets. A mixed strategy
for a player i is a probability distribution over his set of pure strategies. The set of all mixed strategies for player i is
. The support of a
Figure 1. Example of a two-person extensive form game.
mixed strategy for player i is
A pure strategy for player i is a special case of the mixed strategy where a player chooses exactly one action at each of his information sets.
Similarly, a mixed strategy for all players other than player i is a probability distribution
over the set of the Cartesian product of all the pure strategies for all players other than player i. Hence
, where
is the that product of the probabilities that each player other than player i chooses the strategy
. The set of all mixed strategies for all players other than player i is
. The support of a mixed strategy for all players other than player i is
.
The following identities were derived in [3] . Player i’s expected payoff for strategy
for player i and strategy
for the remaining players is
(1)
Player i’s expected payoff for strategy
for player i and strategy
for the remaining players is
(2)
Player i’s expected payoff for strategy
for player i and strategy
for the remaining players is
(3)
We now define the NE.
Definition 1. A strategy
is an NE if and only if
(4)
In an NE, no player can increase his expected payoff by changing his strategy unilaterally. We can similarly define an MBE.
Definition 2. A strategy
is an MBE if and only if
(5)
In an MBE all players other than player i cannot increase the expected payoff for player i by changing their strategies. Hence no player can increase other player’s expected payoff by changing his strategy unilaterally.
Next, the subgame perfect Nash equilibrium (SPNE) is an important concept in extensive games since it always exists. An SPNE can be obtained using backward induction. The following definition of a subgame is from [4] .
Definition 3. An extensive form subgame is a sequence of actions
after a history
such that
.
We extend the concept of the SPNE to a subgame perfect MBE (SPMBE). We prove that one exists for every 2-person game. However, we show that one may not exist for
.
Definition 4. A strategy
is an SPNE if and only if for every nonterminal history
with
, then
(6)
An SPNE, is an NE for some subgame. Furthermore, no player can increase his expected payoff by changing his strategy unilaterally at any information node and history h such that
.
We now give the definition of an SPMBE. Note the difference in history as opposed to Definition 4.
Definition 5. A strategy
is an SPMBE if and only if for every non-terminal history
with
, then
(7)
Thus an SPMBE is a subgame concept where a strategy is an MBE for some subgame. Furthermore, players other than player i cannot increase player i’s expected payoff by unilaterally changing their strategies at any information node with a non-terminal history h for which
.
3. MBE Existence in Extensive Form Games
We now consider the existence of an MBE in an extensive form game. The following theorem from [5] is used.
Theorem 1. Every game in extensive form has a subgame perfect NE.
Next we define a 2-person game
in extensive form. Each player has the same set of actions as he has in the game G. However, the two players payoffs are swapped.
Definition 6. The game
is a 2-person game where each player has the same actions as in the game G. The payoffs for player 1 in G are the payoffs for player 2 in
and vice versa.
Lemma 2. Let G be a 2-person normal form game. Then any NE for the game
is an MBE for G.
Proof. Let
be an NE for
. Then,
(8)
and
(9)
Thus
is an MBE by Definition 5 to complete the proof. □
The following remark follows immediately from Theorem 1 and Lemma 2.
Remark. Every 2-person game G has an SPMBE. Hence every 2-person game in extensive form has an MBE.
Proof. Let G be a 2-person game and
is the game with the swapped payoffs for the two players. By Theorem 1,
always has an SPNE
for some subgame in
. Therefore by Lemma 2,
is an MBE for the same subgame in G. Hence the game G has an SPMBE. Moreover, by Definition 5 an SPMBE is an MBE for the game G, and the proof is complete. □
In the following lemma, we give necessary and sufficient conditions for the existence on an MBE.
Lemma 3. A strategy
is an MBE for G if and only if
when
(10)
Proof. Let
be an MBE for G. Suppose that there exists a strategy
such that
and
. Hence by Equation (3)
. Therefore, by Definition 5 the strategy
is not an MBE to yield a contradiction.
Conversely, suppose
is a strategy such that if
(11)
then
. Hence
(12)
Thus
is an MBE by Definition 5 to complete the proof. □
We now use a counterexample to prove that an MBE may not exist in n-person extensive form games with
.
Theorem 4. An MBE may not exist when
.
Proof. The proof of this theorem is by a counterexample. Consider the following example of Figure 2. We claim that there is not an MBE for this game. Suppose there exists an MBE
for the game. Let
be the strategy of player 1. Note that from Figure 2
(13)
Moreover,
is an MBE. Hence players 2 and 3 choose with positive probabilities their pure strategies that give player 2 a payoff 1. Hence player 2 would only choose strategy
. However, whenever player 2 wants to maximize player 1’s payoff there exists a pure strategy for player 3 such that for some pure strategy for player 1 in
(14)
Figure 2. Three-person game with no MBE.
Any strategy chosen by player 3 can only maximize either player 1’s or player 2’s expected payoff, but not both. Hence
cannot be an MBE by Lemma 3 to yield a contradiction. □
4. Examples
In this section we give two examples. In the first example we consider a 3-person game with imperfect information. We show that the game does not have an MBE. If we consider the same game with perfect information, then it has an MBE. However, the game does not have an SPMBE even with perfect information.
Example 1:
We now show an example of an imperfect information game. Consider the 3-person game shown in Figure 3. The game shown in Table 1 is the normal form representation for the game in Figure 3. However, it was proven in [3] that an MBE does not exist for this game. We now consider the same game but with perfect information as shown in Figure 4. An interesting result is that the game has multiple MBEs in the case of perfect information.
The strategies for player 1 are simply
and
. However, player 2 has 4 pure strategies and player 3 has 16 pure strategies, as shown in Table 2 and Table 3 respectively.
Figure 3. Three-person game with imperfect information.
Figure 4. Three-person game with perfect information.
Table 1. Normal form representation.
For this game, player 3 has 16 different strategies as shown in Table 3. For example strategy 1 means that if player 1 chooses
, and player 2 chooses
, then player 3 chooses
. If player 1 chooses
, and player 2 chooses
, then player 3 chooses
. If player 1 chooses
, and player 2 chooses
, then player 3 chooses
. If player 1 chooses
, and player 2 chooses
, then player 3 chooses
.
One BE for this game is that player 1 chooses
, player 2 chooses
and player 3 chooses strategy
. Note that for this BE, player 3 gets a payoff 0. However, players 1 and 2 cannot increase player 3’s payoff regardless of their strategies. Moreover, they want to maximize the expected payoff for each other. Hence the strategy is an MBE.
Note that even with perfect information, the game does not have an SPMBE. Using backward induction, regardless of whether player 3 chooses
or
, then player 1 alone can increase player 3’s expected payoff. However that would result in reducing player 2’s expected payoff. A symmetric result holds for player 1 if player 2 increases player 3’s payoff. Hence the game cannot have an SPMBE. The next remark follows immediately.
Remark. An MBE for the game G is not necessarily an SPMBE.
Example 2:
We now give an example of a 2-person Bayesian game. Bayesian games with different types have been considered in literature; e.g., see [5] . In this example, we consider a 2-person game in extensive form. Each player has two strategies cooperate (C) and defect (D). We assume that there is a probability distribution over the types of player 1. The first type is an altruistic type. This type wants to maximize player 2’s expected payoff. The second type chooses the strategy Tit-for-Tat of [6] . The second type will cooperate with player 2 only if player 2 chooses to cooperate with player 1. The third type is selfish and wants to maximize his own expected payoff. In this example, let the probability of each type be
,
and
. The game is an imperfect information game. We assume that the game is repeated and not a one-stage game. At each stage, player 1 can be from any type and player 2 only knows the probability distribution over the types. Player 2 next chooses his action. Then player 1 chooses his action without knowing what action player 2 chose. The payoffs for each are shown in Figure 5.
The normal form representation of the game in Figure 5 is shown in Table 4.
Note that for
an NE for the game would be
. Hence player 2 would always defect. In the case that
, an NE would be
. However, when
, then an NE for the game is
. In all three cases, player 2 is selfish and concerned with his own payoff. Hence he would rather defect unless there is a high probability for the Tit-for-Tat type where player 2 can maximize his expected payoff by cooperating if the game is repeated.
5. Conclusion
The MBE is a solution concept in game theory that represents mutual cooperation
Figure 5. Two-person Bayesian game in extensive form.
Table 4. Two-person Bayesian game in normal form.
among players and extends the BE to mixed strategies. In this paper, we extended extensive form games to include players acting altruistically. In particular, we applied the concept of an MBE to finite n-person games in extensive form. We showed how an MBE always exists for 2-person games. However, we showed that an MBE may not exist in an n-person extensive form games with
. We extended the definition of the subgame perfect equilibrium to include the case of the MBE. Moreover we proved that an SPMBE may not exist for
.
Acknowledgements
This research is funded by the U.S. Department of Education GAANN Fellowship, reward no. P200A130164.