extensive-form-games.rst

Extensive Form Games

Motivating example: A modification of the Coordination Game

Consider the Coordination game <motivating-example-coordination-game> with the modification that Alice and Bob have more information available to them: Alice decides where they are going and then lets Bob know before Bob makes their own choice.

This can be represented pictorially as follows:

Definition of an Extensive Form Game

An extensive form game consists of:

• A finite set of players 𝒩.
• A tree: G = (V, E, x⁰) where: V is the set of vertices, E the set of edges and x⁰ ∈ V is the root of the tree.
• (V_i)_{i ∈ 𝒩} is a partition of the set of vertices that are not leaves.
• O is the set of possible game outcomes.
• u is a function mapping every leaf of G to an element of O.

Question

For the modified coordination game <motivating-example-modified-coordination-game>:

1. What is the finite set of players 𝒩?
2. What the elements G = (V, E, x⁰)?
3. What is the partition (V_i)_{i ∈ 𝒩}?
4. What is the set of possible game outcomes O?
5. What is the mapping u from every leaf of G to an element of O?

Answer

1. The set 𝒩 has two players: Alice and Bob.

2. The tree is given by:

   
   V = {A, B₁, B₂, O₁, O₂, O₃, O₄}
   

   
   E = {(A, B₁), (A, B₂), (B₁, O₁), (B₁, O₂), (B₂, O₃), (B₂, O₄)}
   

   
   x⁰ = A
   

3. The partition of of non leaf vertices is given by:

   
   V_Alice = {A₁}  V_Bob = {B₁, B₂}
   

4. The set of possible game ouctomes O = {(3, 2), (1, 1), (0, 0), (2, 3)}.
5. The mapping u is given by:

u(O₁) = (3, 2)  u(O₂) = (1, 1)  u(O₃) = (0, 0)  u(O₄) = (2, 3)

Imperfect information

The modified coordination game described here <motivating-example-modified-coordination-game> differs from the example given in the normal for game chapter <motivating-example-coordination-game> in that Bob knows what action is chosen by Alice.

To represent imperfect information we can partition the vertices of a game tree to indicate which vertices have the same information.

This can be represented pictorially as follows:

This indicates that Bob makes a decision at both nodes in {B₁, B₂} without knowing at which of the two vertices they are. The set {B₁, B₂} is called an information set.

Definition of an information set

Given a game in extensive form: (𝒩, G, (V_i)_{i ∈ 𝒩}, O, u) the set of information sets v_i of player i ∈ 𝒩 is a partition of V_i. Each element of v_i denotes a set of nodes at which a player is unable to distinguish when choosing an action.

This implies that:

• Every information set contains vertices for a single player.
• All vertices in an information set must have the same number of successors (with the same action labels).

Question

For the following games with 𝒩 = {Alice, Bob}, assume that decision nodes A_i are Alice's and B_i are Bob's. Obtain all information sets:

1. 
2. 
3. 
4. 
5. 

Answer

1. :math:v_{text{Alice}}={{A}} v_Bob = {{B₁}, {B₂}}
2. :math:v_{text{Alice}}={{A}} v_Bob = {{B₁, B₂}}
3. :math:v_{text{Alice}}={{A_1}, {A_2}} v_Bob = {{B₁}, {B₂}}
4. :math:v_{text{Alice}}={{A_1}, {A_2}} v_Bob = {{B₁, B₂}}
5. This game has incoherent information sets: the two vertices B₁ and B₂ have different actions.

Definition of a strategy in an extensive form game

A strategy for a player in an extensive form is a collection of probability distribution over the action set of each information set.

Equivalence of Extensive and Normal Form Games

A game in extensive form can be mapped to a game in normal form by enumerating all possible strategies that indicate single actions at each information set. This set of possible strategies corresponds to the actions in the normal form game.

These strategies can be thought of as vectors in the space of the cross product of the sets of actions available at every information set. For player i ∈ 𝒩 with information sets v_i = ((v_i)₁, (v_i)₂, …, (v_i)_n) a strategy s = (s₁, s₂, …, s_n indicates what action to take at each information set. So s₂ will prescribe which action to take at all vertices contained in (v_i)₂.

As an example consider the modified coordination game <motivating-example-modified-coordination-game>. The full enumeration of strategies that indicate single actions for Alice is:

𝒜₁ = {(Sports), (Comedy)}

The full enumeration of strategies that indicate single actions for Bob is:

𝒜₂ = {(Sports, Sports), (Sports, Comedy), (Comedy, Sports), (Comedy, Comedy)}

So (Sports, Comedy) indicates to choose Sports at B₁ and Comedy at B₂.

Using this enumeration the payoff functions can be given by the matrices A, B:

$$\begin{aligned} A = \begin{pmatrix} 3 & 3 & 1 & 1\\\ 0 & 2 & 0 & 2\\\ \end{pmatrix} \end{aligned}$$

$$\begin{aligned} B = \begin{pmatrix} 2 & 2 & 1 & 1\\\ 0 & 3 & 0 & 3\\\ \end{pmatrix} \end{aligned}$$

Question

Obtain the Normal Form Game representation corresponding to

Answer

The full enumeration of strategies that indicate single actions for Alice is:

𝒜₁ = {(Sports), (Comedy)}

The full enumeration of strategies that indicate single actions for Bob is:

𝒜₂ = {(Sports), (Comedy)}

This is because there is a single information set for Bob.

Using this enumeration the payoff functions can be given by the matrices A, B:

$$\begin{aligned} A = \begin{pmatrix} 3 & 1\\\ 0 & 2\\\ \end{pmatrix} \end{aligned}$$

$$\begin{aligned} B = \begin{pmatrix} 2 & 1\\\ 0 & 3\\\ \end{pmatrix} \end{aligned}$$

Using Nashpy

See how-to-use-support-enumeration for guidance of how to use Nashpy to use support enumeration to find Nash equilibria once a Normal Form game representation has been obtained.