What about sequential games?
In a sequential game, players enter in the game at different moments: A first player starts the game with an initial decision, and a player may play at several moments in the game, she may reconsider and change the action plan she has set at the beginning of the game.
The information available to a given player may depend on the possibility of other players playing before her (information maybe imperfect)
In order to analyze such a game we must be able to represent exactly the sequence of players’ decisions in the game and the information available to each player at the moment where she is making a decision.
We use a game tree to fully represent such games (generalization of the concept of a decision tree). This is called the extensive form of a game.
The extensive form is s a game tree where
- An initial node (a circle) represents the choice of the player starting the game
- Successive decision nodes (disks) represent the choices of the following players in the game order
- Vertices connect previous nodes to the successive ones, representing all potential sequence of decisions that can happen during the game, given the potential choices available to each player at each step where she has to make a decision
- Final nodes are connected to the payoffs vector of the players, given the sequence of choices before this final node and the corresponding outcome of the game
A simple example with two players:
:
Question: The player 2 makes decision at two nodes in the game tree, Why?
The difference between these nodes is the strategy choice of player 1 that precedes them.
Indeed, this means that the player 2 can answer two questions:
- What shall I do if player 1 chooses A?
- What shall I do if player 1 chooses B?
Which indicates that in this game player 2 will observe the choice of Player 1 before making her decision. This is a perfect information game.
If this observation was not possible, the information of player 2 would be imperfect.
How can we represent such a situation?
If 2 cannot observe the choice of 1, she cannot choose a strategy after A, and another after B.
In fact, when she makes her choice, she will not know if she is at node 2A or 2B.
She cannot distinguish these nodes on the game tree: they belong to the same information set for this player, and we represent this information set by connecting these two nodes in order to indicate that they belong to the same set.
Player 2 can only make one choice (
or
) and this decision will apply whatever is the choice of Player 1.
We can now give a general definition of a strategy:
Strategy: Each strategy of each player must include a choice by this player in each of her information sets
If the player must make decisions in two different information sets in the game, each strategy must include two elements:
- The decision in the first information set
- The decision in the second information set
In our example with perfect information, the player 2 has two information sets and each strategy must indicate a choice in 2A, for example
, and a choice in 2B, for example
:
, and
- In the imperfect information version: , for example and , since there is only one information set.
The concept of NE is valid for any type of non-cooperative game, but now a strategy of a player could include decisions in different steps in the game. The outcomes are at the end of the game and each corresponds to a specific sequence of decisions by all players in all steps of the game.
If at least one player prefers another outcome than the one we consider, it cannot be a NE.
If Bonnie speaks before Clyde...
When the Sheriff Clint is interrogating Bonnie and Clyde, it could happen that Bonnie speaks first but the Sheriff should make sure that Clyde cannot observe Bonnie’s choice (and vice versa).
We would have a sequence in the choices, but without any informational impact on the decisions:
Now, we have information on the sequence of decisions during the game, and we can take it into account in our analysis, because the players’s decisions would depend on their knowledge of this sequence if they are rational.
Consequently, we must take into account the possibility for a player to choose or change her strategy when it is exactly her turn to play, giving the information she has on previous decisions.
This idea is behind the Subgame Perfect Nash Equilibrium (SPNE) concept proposed by [Selten, 1975].
Sommaire
(c) Murat Yildizoglu, 2021-
(c) Murat Yildizoglu, 2021-