Solution Set 14 – Mixed Strategy Equilibrium

1. (Guess the average)

Let k* be the largest number to which any player's strategy assigns positive probability in a mixed strategy equilibrium and assume that player i's strategy does so. We now argue as follows.

• In order for player i's strategy to be optimal his payoff from the pure strategy k* must be equal to his equilibrium payoff.
• In any equilibrium player i's expected payoff is positive, since for any strategies of the other players he has a pure strategy that for some realization of the other players' strategies is at least as close to 2/3 of the average number as any other player's number.
• In any realization of the strategies in which player i chooses k*, some other player also chooses k*, since by the previous two points player i's payoff is positive in this case, so that no other player's number is closer to 2/3 of the average number than k*. (Note that all the other numbers cannot be less than 2/3 of the average number.)
• In any realization of the strategies in which player i chooses k* ³ 1, he can increase his payoff by choosing k* - 1, since by making this change he becomes the outright winner rather than tying with at least one other player.

The remaining possibility is that k* = 1: every player uses the pure strategy in which he announces the number 1.

2. (Investment race)

The set of actions of each player i is A_i = [0,1]. The payoff function of player i is

u_i(a₁,a₂) =

	-ai	if ai < aj
	1/2 - ai	if ai = aj
	1 - ai	if ai > aj,

where j Î {1,2} \ {i}.

We can represent a mixed strategy of a player i in this game by a probability distribution function F _i on the interval [0, 1], with the interpretation that F _i(v) is the probability that player i chooses an action in the interval [0, v]. Define the support of F _i to be the set of points v for which F _i(v + e) - F _i(v - e) > 0 for all e > 0, and define v to be an atom of F _i if F _i(v) > lim_e®0+F _i(v - e). Suppose that (F ₁*, F ₂*) is a mixed strategy Nash equilibrium of the game and let S_i* be the support of F *_i for i = 1, 2.

Step 1. S*₁ Ç(0,1]= S*₂Ç(0,1].

Proof. If not then there is an open interval, say (v, w), to which F *_i assigns positive probability while F *_j assigns zero probability (for some i, j). But then i can increase his payoff by transferring probability to smaller values within the interval (since this does not affect the probability that he wins or loses, but increases his payoff in both cases).

Step 2. If v is an atom of F *_i then it is not an atom of F *_j and for some e > 0 the set S*_j contains no point in (v - e, v).

Proof. If v is an atom of F *_i then for some e > 0, no action in (v - e,v] is optimal for player j since by moving any probability mass in F _i* that is in this interval to either v + d for some small d > 0 (if v < 1) or 0 (if v = 1), player j increases his payoff.

Step 3. If v > 0 then v is not an atom of F *_i for i = 1, 2.

Proof. If v > 0 is an atom of F *_i then, using Step 2, player i can increase his payoff by transferring the probability attached to the atom to a smaller point in the interval (v - e, v).

Step 4. S_i* = [0, M] for some M > 0 for i = 1, 2.

Proof. Suppose that v Ï S_i* and let w* = inf{w: w Î S_i* and w ³ v} > v. By Step 1 we have w* Î S*_j, and hence, given that w* is not an atom of F _i* by Step 3, we require j's payoff at w* to be no less than his payoff at v. Hence w* = v. By Step 2 at most one distribution has an atom at 0, so M > 0.

Step 5. S*_i = [0,1] and F *_i(v) = v for v Î [0,1] and i = 1, 2.

Proof. By Steps 2 and 3 each equilibrium distribution is atomless, except possibly at 0, where at most one distribution, say F *_i, has an atom. The payoff of j at v > 0 is F _i*(v) - v, where i ¹ j. Thus the constancy of i's payoff on [0,M] and F *_j(0) = 0 requires that F *_j(v) = v, which implies that M = 1. The constancy of j's payoff then implies that F _i*(v) = v.

We conclude that the game has a unique mixed strategy equilibrium, in which each player's probability distribution is uniform on [0,1].

3. (Guessing right)

In the game each player has K actions; u₁(k, k) = 1 for each k Î {1, ..., K} and u₁(k, l) = 0 if k ¹ l. The strategy pair ((1/K, ..., 1/K), (1/K, ..., 1/K)) is the unique mixed strategy equilibrium, with an expected payoff to player 1 of 1/K. To see this, let (p*, q*) be a mixed strategy equilibrium. If p*_k > 0 then the optimality of the action k for player 1 implies that q*_k is maximal among all the q_l*, so that in particular q*_k > 0, which implies that p*_k is minimal among all the p*_l, so that p_k* £ 1/K. Hence p*_k = 1/K for all k; similarly q_k = 1/K for all k.

4. (Air strike)

The payoffs of player 1 are given by the matrix

	0	v1	v1
	v2	0	v2
	v3	v3	0

Let (p*, q*) be a mixed strategy equilibrium.

Step 1. If p_i* = 0 then q_i* = 0 (otherwise q* is not a best response to p*); but if q_i* = 0 and i £ 2 then p_i+1 = 0 (since player i can achieve v_i by choosing i). Thus if for i £ 2 target i is not attacked then target i+1 is not attacked either.

Step 2. p* ¹ (1,0,0): it is not the case that only target 1 is attacked.

Step 3. The remaining possibilities are that only targets 1 and 2 are attacked or all three targets are attacked.

• If only targets 1 and 2 are attacked the requirement that the players be indifferent between the strategies that they use with positive probability implies that p* = (v₂/(v₁ + v₂), v₁/(v₁ + v₂), 0) and q* = (v₁/(v₁ + v₂), v₂/(v₁ + v₂), 0). Thus the expected payoff of Army A is v₁v₂/(v₁ + v₂). Hence this is an equilibrium if v₃ £ v₁v₂/(v₁ + v₂).
• If all three targets are attacked and defended with positive probability then the indifference conditions imply that the probabilities of attack are in the proportions v₂v₃ : v₁v₃ : v₁v₂ and the probabilities of defense are in the proportions z - 2v₂v₃ : z - 2v₃v₁ : z - 2v₁v₂ where z = v₁v₂ + v₂v₃ + v₃v₁. For an equilibrium we need these three proportions to be nonnegative, which is equivalent to z - 2v₁v₂ ³ 0, or v₃ ³ v₁v₂/(v₁ + v₂).
• Arnaud noted the following equilibria that I had overlooked during the precept. When v₃ = v₁v₂/(v₁ + v₂), A’s indifference conditions above imply that q₃*=0. In this case defending the third base need not be a best reply for B (i.e. B’s indifference conditions are less restrictive than the above) and any (p*,q*) where q* is as in above and p* satisfies the following is a mixed strategy NE: p₂* v₂=p₁* v₁, p₂* v₂£p₃* v₃. When v₃ = v₁v₂/(v₁ + v₂), in particular the above equilibrium satisfies these conditions among many others.

6. (Example of correlated equilibrium)

a. The pure strategy equilibria are (B, L, A), (T, R, A), (B, L, C), and (T, R, C).

b. A correlated equilibrium with the outcome described is given by: W = {x, y}, p(x) = p(y) = 1/2; P₁ = P₂ = {{x}, {y}}, P₃ = W; s₁({x}) = T, s₁({y}) = B; s₂({x}) = L, s₂({y}) = R; s₃(W) = B. (The P's should be in a calligraphic font.) Note that player 3 knows that (T,L) and (B,R) will occur with equal probabilities, so that if she deviates to A or C she obtains 3/2 < 2.

c. If player 3 were to have the same information as players 1 and 2 then the outcome would be one of those predicted by the notion of Nash equilibrium, in all of which she obtains a payoff of zero.