normal-form-games.rst

Normal Form Games

Motivating example: Coordination Game

Game theory is the study of interactive decision making. One example of this is the following situation:

Two friends must decide what movie to watch at the cinema. Alice would like to watch a sport movie and Bob would like to watch a comedy. Importantly, they would both rather spend their evening together than apart.

To quantify this mathematically, numeric values are associated to the 4 possible outcomes:

1. Alice watches a sport movie, Bob watches a comedy: Alice receives a utility of 1 and Bob a utility of 1.
2. Alice watches a comedy, Bob watches a sport movie: Alice receives a utility of 0 and Bob a utility of 0.
3. Alice and Bob both watch a sport movie: Alice receives a utility of 3 and Bob a utility of 2.
4. Alice and Bob both watch a comedy: Alice receives a utility of 2 and Bob a utility of 3.

This particular example will be represented using two matrices.

A will represent the utilities of Alice:

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

B will represent the utilities of Bob

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

Alice is referred to as the row player and Bob as the column player:

• The row player chooses which row of the matrices the player will gain their utilities.
• The column player chooses which column of the matrices the player will gain their utilities.

This representation of the strategic interaction between Alice and Bob is called a Normal Form Game <definition-of-normal-form-game>

Definition of Normal Form Game

An N play normal form game consists of:

• A finite set of N players.
• Action set for the players: {𝒜₁, 𝒜₂, …𝒜_N}
• Payoff functions for the players: u_i : 𝒜₁ × 𝒜₂… × 𝒜_N → ℝ

Question

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

1. What is the finite set of players?
2. What are the action sets?
3. What are the payoff functions?

Answer

1. The two players are Alice and Bob (N = 2).
2. The action sets are: 𝒜₁ = 𝒜₂ = {Sport, Comedy}

3. The payoff functions are given by the matrices A, B where the first row or column corresponds to Sport and the second row or column corresponds to Comedy.

   
   u₁(𝒶₁, 𝒶₂) = A_{𝒶1, 𝒶2}  u₂(𝒶₁, 𝒶₂) = B_{𝒶1, 𝒶2}
   

   where 𝒶₁ ∈ 𝒜₁ and 𝒶₂ ∈ 𝒜₂.

Definition of a Zero Sum Game

A two player normal form game with payoff matrices A, B is called zero sum if and only if:

A =  − B

Question

Is the Coordination game <motivating-example-coordination-game> zero sum?

Answer

A ≠  − B so the Coordination game is not Zero sum.

Examples of other Normal Form Games

Prisoners Dilemma

Assume two thieves have been caught by the police and separated for questioning. If both thieves cooperate and do not divulge any information they will each get a short sentence (with a utility value of 3). If one defects they are offered a deal (utility value of 5) while the other thief will get a long sentence (utility value of 0). If they both defect they both get a medium length sentence (utility value of 1).

Question

For the Prisoners Dilemma

1. What is the finite set of players?
2. What are the action sets?
3. What are the payoff functions?
4. Is the game zero sum?

Answer

1. The two players are the two thiefs (N = 2).
2. The action sets are: 𝒜₁ = 𝒜₂ = {Cooperate, Defect}

3. The payoff functions are given by the matrices A, B where the first row or column corresponds to Cooperate and the second row or column corresponds to Defect.

   
   $$\begin{aligned} A = \begin{pmatrix} 3 & 0\\ 5 & 1 \end{pmatrix} \qquad B = \begin{pmatrix} 3 & 5\\ 0 & 1 \end{pmatrix} \end{aligned}$$
   

   
   u₁(𝒶₁, 𝒶₂) = A_{𝒶1, 𝒶2}  u₂(𝒶₁, 𝒶₂) = B_{𝒶1, 𝒶2}
   

   where 𝒶₁ ∈ 𝒜₁ and 𝒶₂ ∈ 𝒜₂.

4. The game is not Zero sum as A ≠  − B.

Hawk Dove Game

Suppose two birds of prey must share a limited resource. The birds can act like a hawk or a dove. Hawks always act aggressively over the resource to the point of exterminating another hawk (both hawks get a utility value of 0) and/or take a majority of the resource from a dove (the hawk gets a utility value of 3 and the dove a utility value of 1). Two doves can share the resource (both getting a utility value of 2).

Question

For the Hawk Dove Game

1. What is the finite set of players?
2. What are the action sets?
3. What are the payoff functions?
4. Is the game zero sum?

Answer

1. The two players are two birds N = 2.
2. The action sets are: 𝒜₁ = 𝒜₂ = {Hawk, Dove}

3. The payoff functions are given by the matrices A, B where the first row or column corresponds to Hawk and the second row or column corresponds to Dove.

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

   
   u₁(𝒶₁, 𝒶₂) = A_{𝒶1, 𝒶2}  u₂(𝒶₁, 𝒶₂) = B_{𝒶1, 𝒶2}
   

   where 𝒶₁ ∈ 𝒜₁ and 𝒶₂ ∈ 𝒜₂.

4. The game is not Zero sum as A ≠  − B.

Pigs

Consider two pigs. One dominant pig and one subservient pig. These pigs share a pen. There is a lever in the pen that delivers food but if either pig pushes the lever it will take them a little while to get to the food.

• If the dominant pig pushes the lever, the subservient pig has some time to eat most of the food before being pushed out of the way. The dominant pig gets a utility value of 2 and the subservient pig gets a utility value of 3.
• If the subservient pig pushes the lever, the dominant pig will eat all the food. The dominant pig gets a utility value of 6 and the subservient pig gets a utility value of -1.
• If both pigs push the lever, the subservient pig will a small amount of the food. The dominant pig gets a utility value of 4 and the subservient pig gets a utility value of 2.
• If both pigs do not push the lever they both get a utility value of 0.

Question

For the Pigs Game

1. What is the finite set of players?
2. What are the action sets?
3. What are the payoff functions?
4. Is the game zero sum?

Answer

1. The two players are dominant and a subservient pig N = 2.
2. The action sets are: 𝒜₁ = 𝒜₂ = {Push, Do not push}

3. The payoff functions are given by the matrices A, B where the first row or column corresponds to Push and the second row or column corresponds to Do not push.

   
   $$\begin{aligned} A = \begin{pmatrix} 4 & 2\\ 6 & 0 \end{pmatrix} \qquad B = \begin{pmatrix} 2 & 3\\ -1 & 0 \end{pmatrix} \end{aligned}$$
   

   
   u₁(𝒶₁, 𝒶₂) = A_{𝒶1, 𝒶2}  u₂(𝒶₁, 𝒶₂) = B_{𝒶1, 𝒶2}
   

   where 𝒶₁ ∈ 𝒜₁ and 𝒶₂ ∈ 𝒜₂.

4. The game is not Zero sum as A ≠  − B.

Matching Pennies

Consider two players who can choose to display a coin either Heads facing up or Tails facing up. If both players show the same face then player 1 wins, if not then player 2 wins. Winning corresponds to a numeric value of 1 and losing a numeric value of -1.

Question

For the Matching Pennies game:

1. What is the finite set of players?
2. What are the action sets?
3. What are the payoff functions?
4. Is the game zero sum?

Answer

1. There are two players N = 2.
2. The action sets are: 𝒜₁ = 𝒜₂ = {Heads, Tails}

3. The payoff functions are given by the matrices A, B where the first row or column corresponds to Heads and the second row or column corresponds to Tails.

   
   $$\begin{aligned} A = \begin{pmatrix} 1 & -1\\ -1 & 1 \end{pmatrix} \qquad B = \begin{pmatrix} -1 & 1\\ 1 & -1 \end{pmatrix} \end{aligned}$$
   

   
   u₁(𝒶₁, 𝒶₂) = A_{𝒶1, 𝒶2}  u₂(𝒶₁, 𝒶₂) = B_{𝒶1, 𝒶2}
   

   where 𝒶₁ ∈ 𝒜₁ and 𝒶₂ ∈ 𝒜₂.

4. The game is Zero sum as A =  − B.

Using Nashpy

See how-to-create-a-normal-form-game for guidance of how to use Nashpy to create a Normal form game.