Mixed Strategies

To introduce the idea of mixed strategies we will consider the Battle of the Disciplines at Lower State University.  The president of the school has received a gift for a new building.  He has asked the Dean of the Sciences, Al Einstein, and the Dean of the Performing Arts, Vaughn Karian, what sort of building to construct: a performance hall or a new lab building. The president has stipulated that the two must agree on the project or nothing will be built.

The payoff table for the Deans is

Which project will be built? To answer the question, begin by trying to find a solution to the game.

Are there dominant strategies? No.
Are there dominated strategies? No.
Is/are there Nash Equilibria?  The 'best responses' are

There are two Nash equilibria, but is either of them more likely to be the outcome of the game?

What strategies could be played by Al?  H, or L, or flip a coin? Using the coin to decide which strategy to play is called a mixed strategy.   Previously we worked only with pure strategies.  A pure strategy would be for Al to play Hall with no uncertainty.

Suppose Al plays Lab 2/3 of the time and Hall 1/3 of the time.  Vaughn plays Hall 2/3 of the time and Lab 1/3 of the time.  We can construct a 2-way table to represent the probability of the different outcomes.

Was anything gained by playing a mixed strategy? The last column corresponds to Vaughn's expected payoff from playing the mixed strategy against Al's pure strategies. The last row shows Al's expected payoffs from playing the mixed strategy against Vaughn's pure strategies. There is still no dominant strategy. 

It doesn't seem anything is gained from the mixed strategy, since the mixed strategy doesn't dominate either Hall or Lab for either player. But wait.   Does it make sense for Al to play a pure strategy against Vaughn's mixed strategy? If Al plays a pure strategy of Lab against Vaughn's mixed strategy then Al's expected payoff is 2/3 ( = 0x2/3 + 2x1/3 ); playing a pure strategy of Hall against Vaughn's mixed strategy is no better for Al, 2/3 (=1x2/3 + 0x1/3).  The symmetry of the  game tells us that we would reach a similar conclusion for Vaughn's use of a pure strategy against mixed play by Al. So, we conclude that there is a third Nash equilibrium: Both play a mixed strategy.

What is the expected value of Al's utility from playing the game when both of them use the proposed mixed strategy?

Al: (2/9)x1 + (1/9)x0 + (4/9)x0 + (2/9)x2 = 6/9

Similarly for Vaughn

Vaughn: (2/9)x2 + (1/9)x0 + (4/9)x0 + (2/9)x1 = 6/9

Redrawing the payoff table

These payoffs can be better for them than playing a pure strategy against an opponent's mixed strategy.  Given that neither of the pure strategy equilibria is a focal point of the game, the solution to the game is for both of them to play a mixed strategy.

Consider a second example.

To kill time while waiting to be contacted by extraterrestrials, Ursa Maigeur and Paul Ariss are playing the following normal form game:

There is no solution to this game in pure strategies. It is possible to find a Nash equilibrium in mixed strategies.  Suppose that Paul and Ursa both play Left with probability 1/2.  When they do this we can expand the payoff table as follows:

Paul would be indifferent between Left, Right and Mix in response to a play of Mix by Ursa.  The same is true for Ursa.  There is an intersection of their conjectures at {Mix, Mix}, so this is the Nash equilibrium.

Consider a third example.

A Day at the Mall: Nole's Soles and Grace's Laces

At the local mall there are two shoe stores, Nole's Soles and Grace's Laces.  Their strategies include the window displays to be used in their respective stores.  The decision is made simultaneously each Monday morning.  They then must live with their choice for the rest of the week.  The payoff matrix, or strategic form of the game, is shown below.  The numbers are hundreds of shoppers stopping in to examine the goods.

Suppose that for aesthetic reasons Grace will never use window displays  of type M1 or D.  Otherwise, the two store owners play strategies with the probabilities shown along the margins of the 2-way table shown below.  The probabilities in the cells are the joint probabilities resulting from the corresponding strategy pairs.

The expected payoffs when both managers are playing mixed strategies are

Before explaining the importance of these expected payoffs in the solution of the game we need a bit more background.

Definition: The support of a mixed strategy is the set of pure strategies used to construct the mixed strategy.

Implication: Grace's mixed strategy is a best response to Nole's play if and only if each of the pure strategies in its support is a best response to Nole's play. Since each pure strategy is a best response, any (probability) weighted average of them is also a best response. 

Look again at Nole's and Grace's original game again:

Their best response plays are

From which we can see that there is just one Nash equilibrium, shown by the shaded cell in the payoff matrix.

Consider a specific best response of Nole: b^N(D^G) = U, D. To a play of D by Grace, Nole's best response would be either U or D.  In fact, in response to a play of D by Grace, if Nole plays U with probability p and D with probability 1-p, then this weighted average is a best response to D^G since it beats playing a pure strategy of M: Note 3p + 3(1-p) > 2.

Can you see that whenever Grace plays M2, any probability weighted average of U, M, and D is as good as any pure strategy for Nole?  Can you explain why Grace will never construct a mixed strategy involving D? Pick some probabilities and demonstrate it for yourself.

So, we have shown that a mixed strategy can be a best response.  There must be a reason to construct such best response mixed strategies in order to make it worth the effort.  Indeed, there are three reasons to make the effort.

The Meaning of playing a mixed strategy.

Three Reasons to Play a Mixed Strategy

Reason 1. A pure strategy that is undominated by other pure strategies may be dominated by a mixed strategy.

Reason 2. Playing a mixed strategy can keep your opponent off balance.  The worst case payoff of a mixed strategy may be better than the worst case payoff of a pure strategy.

Reason 3. In a game without a pure strategy Nash equilibrium, a mixed strategy may result in a Nash equilibrium.

Rock-Paper-Scissors is a symmetric game with no Nash equilibrium, but in which a mixed strategy provides a useful approach.

Two methods for solving mixed strategies.

Another mixed strategy example.