haihongyuan.com

海量文库 文档专家

海量文库 文档专家

发布时间：2014-01-02 09:00:42

Chapter 2

Normal Form Game and Nash Equilibrium: Mixed Strategy

1. The Advantage of Mixed Strategies

? reference to chapter 4 ? Consider the following Rock-PaperScissors game: Note that RPS is a

zero-sum game.

1. The Advantage of Mixed Strategies

R R P S

0, 0

1, -1 -1, 1

-1, 1

0, 0 1, -1

1, -1

-1, 1 0, 0

P

C

1. The Advantage of Mixed Strategies

? This game has no pure-strategy Nash equilibrium. Whatever pure strategy player 1 chooses, player 2 can beat him.

1. The Advantage of Mixed Strategies

? A natural solution for player 1 might be to randomize amongst his strategies.

1. The Advantage of Mixed Strategies

? Another example of a game without pure-strategy NE is matching pennies. ? As in RPS the opponent can exploit his knowledge of the other player's action.

1. The Advantage of Mixed Strategies

H H T

-1, 1

T

1, -1 -1, 1

1, -1

1. The Advantage of Mixed Strategies

? Fearing this what might the opponent do? One solution is to randomize and play a mixed strategy. ? Each player could play H with probability 0.5 and T with probability 0.5

1. The Advantage of Mixed Strategies

? Note that each player cannot be taken advantage of.

1. The Advantage of Mixed Strategies

? Definition of Mixed Strategy: ? Let G be a game with strategy spaces S1,S2,..,SI . A mixed strategy σi for player i is a probability distribution on Si.

1. The Advantage of Mixed Strategies

? Several notations are commonly used for describing mixed strategies.

? 1. Function (measure): σ1 (H) = 0.5 and σ1(T) = 0.5

1. The Advantage of Mixed Strategies

? 2. Vector: If the pure strategies are si1,..siNi write (σi (si1) ; …; σi (siNi)) ? e.g. (0.5, 0.5)

1. The Advantage of Mixed Strategies

? 3. 0.5H + 0.5T

2. Mixed Strategy Nash Equilibrium

? We write ui (σi ,σ-i ) for player i's expected payoff when he uses mixed strategy σi and all other players play as in σ-i

2. Mixed Strategy Nash Equilibrium

? Definition of Mixed Strategy NE: ? A mixed strategy NE of G is a mixed profile σ* such that:

? ui (σi* ,σ-i* ) ≥ ui (σi ,σ-i* ) for all i and allσi

2. Mixed Strategy Nash Equilibrium

? The strategy profile σ1 = σ2 = 0.5H + 0.5T is a NE of Matching Pennies.

2. Mixed Strategy Nash Equilibrium

? Because of symmetry it is sufficient to check that player 1 would not deviate. If he plays his mixed strategy he gets expected payoff 0. ? There is no incentive to deviate.

3. Find the mixed strategy NE

L U R

1, 1

0, 2

0, 4

2, 1

D

3. Find the mixed strategy NE

? It is easy to see that this game has no pure strategy Nash equilibria.

? Is there pure NE in this game? Please check it.

3. Find the mixed strategy NE

? For a mixed strategy Nash equilibrium to exist, player 1 has to be indifferent between strategies U, and D and player 2 has to be indifferent between L and R.

3. Find the mixed strategy NE

? Assume player 1 plays U with probability α and player 2 plays L with probability β .

3. Find the mixed strategy NE

? u1 (U; σ2* ) = u1 (D; σ2* ) ? Eg. β= 2(1-β)

? β=2/3

3. Find the mixed strategy NE

u2 (L; σ1* ) = u2 (R; σ1* )

E.g.. α+2(1-α)=4 α+(1-α) α=1/4

3. Find the mixed strategy NE

? Therefore, the mixed strategy NE is:

? σ1*=1/4U+3/4D, σ2*=2/3L+1/3R

3. Find the mixed strategy NE

? Recall the Battle of the Sexes experiments. ? It can be shown that the game has a mixed NE where each agent plays her favorite strategy with probability 2/3.

3. Find the mixed strategy NE II

? Finding mixed NE in 2 by 2 games is relatively easy. It becomes harder if players have more than two strategies.

3. Find the mixed strategy NE II

? In many cases it is useful to exploit iterated deletion in order to narrow down possible supports.

An Example

L U C R

1, 1 0, 2 0, 2

0, 2 5, 0 1, 1

0, 4 1, 6 2, 1

M D

3. Find the mixed strategy NE II

? Note that C for player 2 is strictly dominated by 1/2L + 1/2R. Thus we would think that C won't be used.

3. Find the mixed strategy NE II

? After we delete C , we note that M is dominated by 2/3D+ 1/3U. Using the above proposition we can conclude that the only Nash equilibria are the NE of the ? 2 by 2 game analyzed in the previous section.

3. Find the mixed strategy NE II

? Since that game had a unique mixed strategy equilibrium we can conclude that the only NE of the 3 by 3 game is σ1*= 1/4U + 3/4D

and σ2*= 2/3L + 1/3R.

4. Existence of Nash equilibrium

? (reference to chapter 4)

? NE Existence Theorem: Every finite strategic-form game has a mixedstrategy Nash equilibrium.

4. Existence of Nash equilibrium

? In the following we will go through a proofs of the Existence Theorem in a 2×2 games using elementary techniques.

4. Existence of Nash equilibrium

? Let us consider the simple 2 × 2 game which we discussed in the previous lecture on mixed Nash equilibrium.

L U

R

1, 1 0, 2

0, 4 2, 1

D

? We next draw the best-response curves of both players.

? Recall that player1's strategy can be represented by a single number α such that σ1 = αU +(1-α)D while player 2's strategy is σ2 = βL + (1-β)R.

? Let's find the best-response of player 2 to player 1 playing strategy α:

u2 ( L, ?U ? (1 ? ? ) D) ? 2 ? ? u2 ( R, ?U ? (1 ? ? ) D ) ? 1 ? 3?

? Therefore, player 2 will strictly prefer strategy L if 2-α> 1 + 3αwhich implies α < 1.

The best-response correspondence of player 2 is therefore:

? We can similarly find the bestresponse correspondence of player 1:

? We draw both best-response correspondences in a single graph:

? We immediately see, that both correspondences intersect in the single pointα = 1/4 and β= 2/3 which is therefore the unique (mixed) Nash equilibrium of the game.

? What's useful about this approach is that it generalizes to a proof that any two by two game has at least one Nash equilibrium.

? i.e. its two best response correspondences have to int

ersect in at least one point.