Sequential Games V

Final look at sequential games

Today we will take one last look at solving sequential games. Before we do that though let’s solve the example at the end of the previous blog.

Shirk

Let p represent the probability that your boss writes you up and 1-p be the probability that your boss does not write you up. The probability distribution would be -10p + 40(1-p) = 20.

-10p + 40 – 40p = 20 =>

-50p = -20 =>

p = -20/-50 = 2/5

1-p = 3/5

So you will choose to shirk if the probability of your boss writing you up is less than 2/5. Or you will choose to shirt if the probability of your boss not writing you up is greater than 3/5. Of course you would never shirk to begin with and always work hard right?

In most of our examples we have looked at sequential games that involved two players. In the following example there will be four participants. In particular, Yogurtland is looking to establish a shop in a new market. However, three potential competitors (Mickey’s Yogurt, Yum Yum Yogurt, and Big Kahuna) are also debating whether to enter the market or not.

yogurt1

The payoffs are organized from top to bottom representing Yogurtland, Yum Yum, Mickey’s, and Big Kahuna respectively. We can solve this game using backwards induction. Let’s start with the options for Big Kahuna.

Scenarios for Big Kahuna (a lot):

Enter, Enter, Enter, Enter = 0

Enter, Enter, Enter, No = 1

Enter, Enter, No, Enter = 3

Enter, Enter, No, No = 1

Enter, No, Enter, Enter = 3

Enter, No, Enter, No = 2

Enter, No, No, Enter = 3

Enter, No, No, No = 4 

No, No, Enter, Enter = 4

 

No, No, Enter, No = 4

No, No, No, Enter = 3

No, No, No, No = 0

No, Enter, Enter, Enter = 2

No, Enter, Enter, No = 4

No, Enter, No, Enter = 3

No, Enter, No, No = 1

yogurt 2

The preferences of Big Kahuna have been highlighted in red based on the payouts from each outcome. I also placed in bold the preferred actions of Big Kahuna above. Now let’s look at Mickey’s. Since Mickey’s assumes Big Kahuna will make optimal decisions, Mickey’s options are the following:

Enter, Enter, Enter, No = 3

Enter, Enter, No, Enter  = 1

Enter, No, Enter, Enter = 2

Enter, No, No, No = 1

No, No, Enter, Enter = 1

No, No, Enter, No = 1

No, No, No, Enter = 2

No, Enter, Enter, No = 1

No, Enter, No, Enter = 0

yogurt 3

Using backwards induction, Mickey’s optimal choices will be in blue. Let’s continue the process by identifying Yum Yum’s options.

Scenarios for Yum Yum:

Enter, Enter, Enter, No = 2

Enter, No, Enter, Enter = 3

No, No, No, Enter = 1

No, Enter, Enter, No = 3

yogurt 4

Yum Yum’s optimal choices are now highlighted in green. As you can see, the options for yogurt shops becomes less as we use backwards induction. This leaves Yogurtland with a decision to make, enter or do not enter the market.

Their scenarios are:

Enter, No, Enter, Enter = 2

No, Enter, Enter, No = 2

yogurt 5

Based on Yogurtland’s options, the company is indifferent between entering the market or not entering the market since their payoffs will be the same. So the solution to this game is (2,3,2,3) and (2,3,1,4) or (Enter, No, Enter, Enter) and (No, Enter, Enter, No).

Sequential Games IV

To be or not to be?

Last time we looked at the dilemma of Charlie Brown attempting to kick a football and Lucy pulling the football away from him (to this day he still tries). In this scenario I modified the game tree to where only Charlie knows his payoffs but not Lucy’s. I introduced probability distribution into the game to determine the probability of Charlie choosing to kick the football based on the potential payoffs. Let’s apply probability distribution to other instances of sequential games.

A great example comes from the humanities. One of William Shakespeare’s most famous plays was Hamlet. In Hamlet, the title character seeks revenge against his uncle King Claudius who, according to the ghost of Hamlet’s father, murdered Hamlet’s father and took the throne for himself. We can represent a sequential game as follows:

Hamlet 1

Hamlet has the choice of either living or killing himself (to be or not to be). If he chooses to kill himself (not to be) then he will receive a payoff of -50 since he will be unable to avenge his father’s killer. Now if he chooses “to be” then Claudius can either let Hamlet live or kill him.

If Hamlet is allowed to live he will receive a payoff of 200 since he will avenge his father’s death by killing Claudius. However, if Claudius kills Hamlet then Hamlet’s payoff is -100 since he was unable to avenge his father and he was killed by his father’s killer (double negative).

Since we do not know the payoffs of Claudius, we can only determine the potential outcome through probability distribution. First let p represent the probability that Claudius kills Hamlet and 1-p be the probability that Claudius does not kill Hamlet. The probability distribution of this game would be:

-100p + 200(1-p) = -50 =>

-100p + 200 – 200p = -50 =>

-300p = -250 =>

p = 5/6

1-p = 1/6

So Hamlet will choose “to be” if the probability of Claudius killing Hamlet is less than 5/6 or if the probability of Claudius letting Hamlet live is greater than 1/6. Of course, things don’t look good for Hamlet in this situation. More than likely Claudius would want to kill Hamlet. But we cannot make that assumption since we do not know Claudius’s payouts.

Try to solve the following game below. In this scenario, you are currently at work and have a tendency to shirk (neglect your job) instead of doing your job (untrue of course). Now if you decide to shirk your boss would either write you up or not (more than likely write you up). Solve for p, 1-p, and explain the probability of you choosing to shirk. Shirk

 

Solving Sequential Games III

Why does Charlie always kick?

Today we are going to analyze one of the greatest and puzzling dilemmas in cartoon animation history. Why does Charlie Brown always attempt to kick the football that Lucy is holding for him? In every instance she always pulls the ball away from him and he ends up going airborne from missing the ball. Let’s see if we can understand Charlie’s reasoning in a sequential game.

First we will represent the game in the following game tree:

Charlie 1

In this game Charlie has the option of either kicking the football or not. If he chooses not to kick the football then his payout will be 5 utils (happiness) while Lucy’s will be 0 (no bumps and bruises for Charlie). Now if Charlie chooses to kick the ball then he is at the mercy of Lucy. If Lucy allows Charlie to kick the ball then the payouts will be 15 for Charlie and 5 for Lucy. If Lucy pulls the football then Charlie’s payout is -5 since he will miss the kick and go flying into the air. Lucy will achieve a payout of 10 utils since she enjoys watching Charlie suffer (never liked Lucy).

Let’s solve this game under the assumption of complete rationality:

Charlie 2

The rational choice for Lucy is to not allow Charlie to kick since 10 > 5. Charlie should assume that Lucy is a rational decision maker and will opt to not allow him to kick. As such, Charlie should just walk away knowing that he did not give Lucy the satisfaction of missing the kick. But we know this is not the case as time and time again Charlie attempts to kick the football.

It’s possible to assume that Charlie always makes an irrational decision while Lucy always makes the rational choice. Lucy may know that Charlie is irrational hence her reason for always offering Charlie the opportunity to kick the ball. But what if we didn’t factor in Lucy payouts? Let’s assume Charlie does not know Lucy’s payouts and only knows his own as shown below.

Charlie 3

How would Charlie choose now? Let’s solve this using a probability distribution similar to  mixed strategies. Let p be the probability that Lucy doesn’t allow Charlie to kick and 1-p be the probability that Lucy allows Charlie to kick. The equation would appear as follows:

-5p + 15(1-p) = 5

Now let’s solve for p and 1-p:

-5p + 15(1-p) = 5 =>

-5p + 15 – 15p = 5 =>

-20p = -10 =>

p = -10/-20 or 1/2

1-p = 1 – 1/2 = 1/2

The way to interpret this is Charlie will choose to kick the ball as long as the probability of Lucy not allowing him to kick is less than 1/2. Or we can say Charlie will choose to kick the ball as long as the probability of Lucy letting him kick is greater than 1/2. So Charlie is still looking at a 50/50 split.

Based on Charlie’s history though we can only assume that he makes irrational decisions while Lucy always makes the rational choice. For some reason the desire for Charlie to kick that ball beats out all of the future body aches and pains. Poor Charlie.

 

Solving Sequential Games II

Where to set up shop?

In my previous blog I introduced the extensive form of games that are used in illustrating sequential games (order matters). These games are solved using backwards induction. Today we are going to analyze a scenario of where a restaurant should open up shop taking into consideration a competitor looking to open shop as well.

Pieology and Blaze Pizza are competing for world domination. It’s hard to miss these locations in town as they are popping up everywhere. Due to their long term strategy for aggressive expansion, Pieology is looking to open a location at a new shopping center. However, Blaze Pizza wants to capture market share in the new shopping center as well. The owners of the shopping center are willing to give Pieology first choice for the exact location (first-mover advantage). Which location should Pieology choose?

Sequential Pie

Observe the game tree above. Pielogy has the option of either choosing the West, South, or East side of the shopping center. Once Pieology makes there choice of location, Blaze Pizza will come in and establish a new location based on Pieology’s choice. Using backwards induction we can solve for the optimal choice for Pieology to maximize profit. If Pieology chooses West, Blaze Pizza can select either West, South, or East. Blaze Pizza will prefer to set up a location at the East side of the shopping center since 3 (East) > 2 (South) > 1(West).

Sequential Pie 2

Now let’s assume Pieology chooses to build the new location on the South side of the shopping center. Blaze Pizza will evaluate their potential profits based on the possible locations. Blaze Pizza’s preference is to build a new location on the East side of the shopping center due to 3 (East) > 2 (West) > 1 (South).

Sequential Pie 3

Similar analysis can be used to determine Blaze Pizza’s optimal choice if Pieology chooses the East side of the shopping center. Based on the possible profits, Blaze Pizza will select the West side of the shopping center since 3 (West) > 2 (South) > 1 (East).

Sequential Pie 4

Based on backwards induction what would be the optimal choice for Pieology?

If Pielogy chooses West: (West, East) = (4,3)

If Pieology chooses South: (South, East) = (3,3)

If Pieology chooses East: (East, West) = (5,3)

As you can see Pieology will always have higher profits than Blaze Pizza due to their first-mover advantage. However, their is an optimal location for Pieology. Based on the payouts (profits), Pieology will choose to establish their new location on the East side of the shopping center since 5 (East) > 4 (West) > 3 (South).

Sequential Pie 5

To optimize profits for both businesses, it is best that they establish locations furthest from each other at the new shopping center. We will continue to look at sequential games in the next blog which will include more examples as we continue to solve these types of games. I look forward to your feedback in the comments below.

Introduction to Sequential Games

Overview of solving sequential games in extensive form

We are going to switch gears and analyze sequential games. The format will be different but the principles of game theory that we reviewed will be the same. I am going to introduce the concept of backward induction to solve these type of games. Similar to simultaneous games, the sequential games will be complete and with perfect information.

Let’s look at the following example in extensive form:

Sequential 1

 

 

 

 

 

 

 

 

 

Going forward I will illustrate extensive form games in a game tree as shown above. In this example we have two siblings, one age 4 and the other age 2. On the table there is a plate with only two cookies remaining. Player 1 represents the older sibling and chooses an action a¹ from his or her set of options A¹. In this game the older sibling has the actions of “share” or “take”. Player 2 represents the younger sibling and observes the action of the older brother and then chooses an action a² (“share” or “take”) from his or her set of options A².

So if the older sibling chooses “take” then the payoff will be two cookies for the older sibling and none for the younger sibling (how cruel). If the older sibling chooses the option of “share”, then the younger sibling can choose either “take” or “share.” Now we can introduce the concept of backwards induction. We basically look at the options of the younger sibling first and work our way backwards.

Before we start, it is important to remember that players will look for the optimal choice based on their sets of options (similar to the simultaneous games we analyzed). So the younger sibling has the option of choosing the action “share” or “take”. If the younger sibling chooses “share” then both siblings will end up with one cookie. If the younger sibling chooses “take” then the younger sibling gets two cookies and the older sibling gets nothing. Since we are assuming rational players, the younger sibling will choose “take” since 2 > 1.

Sequential 2

Knowing that the younger sibling will choose “take” the optimal choice for the older sibling is to choose “take” since 2 > 0. So this game ends where the older sibling will approach the table and grab both cookies since it is assumed the younger sibling would do the same thing given the opportunity. It appears that both siblings do not understand the concept of sharing and equality. Although a simple example, this game represents the basics of backward induction and solving sequential games with complete information.

Going forward we will look at larger games with more players, actions, and options. I look forward to your feedback in the comments below and feel free to follow me on Twitter and connect via LinkedIn or Facebook or both.

 

Mixed Strategy Nash Equilibrium IV

Additional problem solving

We will focus on solving more games that involve pure strategy Nash Equilibrium and mixed strategy Nash Equilibrium. It is important that we understand how to solve these games as it lays the foundation for further topics in game theory. This is especially the case if you are interested in advancing your studies. In these problems the goal is to identify the Nash Equilibrium and not necessarily the payoffs.

Let’s start with Problem #1:

q 1-q
1\2 Red Blue
p Red 1,4 2,3
1-p Blue 3,2 1,4

Player 1 chooses Blue when Player 2 chooses Red.

Player 1 chooses Red when Player 2 chooses Blue.

Player 2 chooses Red when Player 1 chooses Red.

Player 2 chooses Blue when Player 1 chooses Blue.

There is no pure strategy Nash Equilibrium in this game. However, let’s see if a mixed strategy Nash Equilibrium exists. Similar to previous examples, we need to solve for p, 1-p, q, and 1-q to determine the mixed strategies.

For Player 1:

4p + 2(1-p) = 3p + 4(1-p)

=> 4p + 2 – 2p = 3p + 4 – 4p

=> 2p + 2 = 4 – p

=> 3p = 2

=> p = 2/3, 1-p = (1 – 2/3) = 1/3

For Player 2:

1q + 2(1-q) = 3q + 1(1-q)

=> q + 2 -2q = 3q +1 – q

=> 2 – q = 2q + 1

=> 1 = 3q

=> q = 1/3, 1-q = (1 – 1/3) = 2/3

Summary: Pure strategy Nash Equilibrium does not exist. Mixed strategy for Player 1 (Red = 2/3, Blue = 1/3) and Player 2 (Red = 1/3, Blue = 2/3)

Problem #2

q 1-q
1\2 Left Right
p Up 5,6 4,1
1-p Down 3,2 5,3

Player 1 chooses Up when Player 2 chooses Left.

Player 1 chooses Down when Player 2 chooses Right.

Player 2 chooses Left when Player 1 chooses Up.

Player 2 chooses Right when Player 1 chooses Down.

The pure strategy Nash Equilibrium for this game is (Up, Left) and (Down, Right). Now let’s determine if a mixed strategy Nash Equilibrium exists.

For Player 1:

6p + 2(1-p)  = 1p + 3(1-p)

=> 6p + 2  – 2p = p + 3 – 3p

=> 4p + 2 = 3 – 2p

=> 6p = 1

=> p = 1/6,  1-p = (1 – 1/6) = 5/6

For Player 2:

5q + 4(1-q) = 3q + 5(1-q)

=> 5q + 4 – 4q = 3q + 5 – 5q

=> q + 4 = 5 – 2q

=> 3q = 1

=> q = 1/3, 1-q = (1-1/3) = 2/3

Summary: In this game we have both pure strategy Nash Equilibrium and a mixed strategy Nash equilibrium. Pure strategies are (Up, Left) and (Down, Right). Mixed strategies are Player 1 (Up = 1/6, Down = 5/6) and Player 2 (Left = 1/3, Right = 2/3).

Problem #3:

q 1-q
1\2 Yellow Green
p Yellow 5,4 2,4
1-p Green 1,4 3,3

Player 1 chooses Yellow when Player 2 chooses Yellow.

Player 1 chooses Green when Player 2 chooses Green.

Player 2 is indifferent between Yellow and Green when Player 1 chooses Yellow.

Player 2 chooses Yellow when Player 1 chooses Green.

There is only one pure strategy Nash Equilibrium in this game (Yellow, Yellow). Now for the mixed strategy Nash equilibrium:

For Player 1:

4p + 4(1-p) = 4p + 3(1-p)

=> 4p + 4 – 4p = 4p + 3 – 3p

=> 4 = 3 +p

=> p = 1, 1-p = (1 – 1) = 0

What does it mean for p = 1? Remember in a probability distribution the sum of the probabilities must equal 100%. This means there is no mixed strategy Nash Equilibrium for Player 1. So Player 1’s optimal choice is to always choose the pure strategy of Red.

For Player 2:

5q + 2(1-q) = 1q + 3(1-q)

=> 5q + 2 – 2q = q + 3 – 3q

=> 3q + 2 = 3 – 2q

=> 5q = 1

=> q = 1/5, 1-q = (1 – 1/5) = 4/5

Summary: The pure strategy Nash Equilibrium is (Yellow,Yellow). Even though Player 1 does not have a mixed strategy Nash Equilibrium, Player 2’s mixed strategy is (Yellow = 1/5, Green = 4/5)

For additional practice I recommend you look for available problems online. Feel free to leave comments or feedback below.

 

Mixed Strategy Nash Equilibrium III

Is a mixed strategy optimal?

So far we have solved and analyzed games with only a mixed strategy Nash Equilibrium. Today we will analyze a scenario where both mixed and pure strategies exist. On occasion my wife and I are too lazy to cook and choose to go out to dinner. However, this is where the fun really begins. Like other couples, sometimes we don’t always agree on where to eat and have our own preferences.

This can be represented in the following game:

Me\Wife Mexican BBQ
Mexican 2,3 0,0
BBQ 0,0 3,2

On this night, I prefer to eat BBQ (love tri tip) over my wife’s preference of Mexican food. As you can see in this game, I would rather eat Mexican food over eating alone and my wife would rather have BBQ over eating alone. Eating alone represents a payoff of 0. In this game we have two pure strategy Nash Equilibrium represented as (Mexican, Mexican) and (BBQ, BBQ).

As we have seen in the past few blogs a mixed strategy Nash Equilibrium exists as well. Let’s solve for this equilibrium.

q 1-q
Me\Wife Mexican BBQ
p Mexican 2,3 0,0
1-p BBQ 0,0 3,2

Using the information above we will first solve for p and 1-p:

3(p) + 0(1-p) = 0(p) + 2(1-p)

=> 3p = 2 – 2p

=> 5p = 2

=> p = 2/5 and 1-p = 3/5

Now let’s solve for q and 1-q:

2(q) + 0(1-q) = 0(q) + 3(1-q)

=> 2q = 3 – 3q

=> 5q = 3

=> q = 3/5 and 1-q = 2/5

Here is an update of the game matrix with the mixed strategies.

q = 3/5 1-q = 2/5
Me\Wife Mexican BBQ
p = 2/5 Mexican 2,3 0,0
1-p = 3/5 BBQ 0,0 3,2

With the probabilities of each strategy being chosen solved, let’s determine the payouts for both my wife and I choosing a mixed strategy. We first need to determine the probability of us choosing:

(Mexican, Mexican) = (p)(q) = (2/5)(3/5) = 6/25

(Mexican, BBQ) = (p)(1-q) = (2/5)(2/5) = 4/25

(BBQ, Mexican) = (1-p)(q) = (3/5)(3/5) = 9/25

(BBQ, BBQ) = (1-p)(1-q) = (3/5)(2/5) = 6/25

Next we need to take summation of each individual player’s pure strategy payoff multiplied by the corresponding probability in that quadrant.

My payoff: (2)(6/25) + (0)(9/25) + (0)(4/25) + (3)(6/25) = 1.2

Wife’s payoff: (3)(6/25) + (0)(9/25) + (0)(4/25) + (2)(6/25) = 1.2

For this game my payoffs are (3, 2, and 1.2) for (BBQ, Mexican, and Mixed) and my wife’s are (3, 2, and 1.2) for (Mexican, BBQ, and Mixed). Looking at these payoffs, is a mixed strategy Nash Equilibrium optimal? We clearly don’t want to eat dinner alone (payoff of 0) and we run the risk of this occurring if we choose a mixed strategy. In addition, even though I favor BBQ over Mexican food, Mexican food with my wife is a better payoff than choosing a mix.

I can summarize my preferences as BBQ > Mexican > Mixed (3 > 2 > 1.2). Since we assume rational decisions, my wife will approach this game similarly. Her preferences are Mexican > BBQ > Mixed (3 > 2 > 1.2). It is not optimal for us to choose a mixed strategy. Plus, why would you want to choose a mixed strategy on your wife or husband in the first place? Are you trying to trick/confuse him or her? Sometimes it is best to concede to your spouse’s preference for the night and he or she will return the favor another night.