03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

(1,1)

(1,2)

(2,1)

(2,2)

(1,1)

Two-Finger Morra Game

Two players simultaneously raise both hands with one or two fingers extended on each hand. Left hand is for “number shown,” right hand for “number guessed.” The guess is about how many fingers the other player is going to show―with his left hand, of course.

0 0 0 0 0 0 0 0 -3 3 4 0 -4 0 0 -4 0 3 4 -3

(1,2)

(2,1)

(2,2)

(1,1) 0 (1,1) 0 2 (1,2) -2 -3 (2,1) 3 (2,2) 0 2

(1,2) -2 -3 0

(2,1) 3

(2,2)

Mixed Strategies in Normal and Sequential Form Games

1

The South Pacific Example (World War II) Japan

E

2 E US -2 0 0

W

0

1 -1

W

0

You have to choose one of the two routes, E or W, every day. How would you play?

Mixed Strategies in Normal and Sequential Form Games

2

The South Pacific Example with Different Payoffs

The original game

Japan

E

2 E US -2 0 5

W

0

US W E -2

Japan E W 2 0 0 0 -1 1 0

1 -1

W

0

Regardless of the solution to the original game what would you do, as the US player, if your payoffs were altered as above? (Say, they can bring considerably more supplies using E rather than W.) Would you go E more often than before, less often or with the same frequency?

Mixed Strategies in Normal and Sequential Form Games

3

How to calculate payoffs to a probabilistic mix of Row’s E and W against, for instance, Column’s E?

Japan

E 2 E W 0 0 0 W 0 -1 1

US

-2

p E

uUS (

,E)=?

1-p W

Mixed Strategies in Normal and Sequential Form Games 4

Japan

E

2

W

0 0 0 1 -1

p E

p (E, E)

E

uUS (

,E)=

1-p W

uUS (

1-p (W, E)

)=

US W

-2 0

here we need expected utility theory

= p uUS (E, E) + (1-p) uUS (W, E) = p?(-2) + (1-p)?0 = -2p

Thus with mixed strategies we have to switch from ordinal utility assumption (preference theory) to cardinal utility assumption (expected utility theory)

p E

For notational convenience instead of

1-p W

I will write pE ? (1-p)W

? stands for a “lottery”

Mixed Strategies in Normal and Sequential Form Games

5

Japan E W 2 E 0 0 0 W 0 -1 1 -2

A Few Examples

US

uUS (0.7E ? 0.3W, E) = 0.7 uUS (E, E) + 0.3 uUS (W, E) = 0.7?(-2) + 0.3?0 = -1.4

Row’s strategy (recall the general notation rules in game theory) Column’s strategy

uJ (0.6E ? 0.4W, W) = 0.6 uJ (E, W) + 0.4 uJ (W, W) = 0.6?0 + 0.4?1 = 0.4 uUS (W, 0.7E ? 0.3W) = 0.7 uUS (W, E) + 0.3 uUS (W, W) = 0.7?0 + 0.3?(-1) = -0.3 uJ (0.2E ? 0.8W, 0.3E ? 0.7W) = 0.2 uJ (E, 0.3E ? 0.7W ) + 0.8 uJ (W, 0.3E ? 0.7W) = 0.2?0.3 uJ (E, E) + 0.2?0.7 uJ (E, W) + 0.8?0.3 uJ (W, E) + 0.8?0.7 uJ (W, W) = 0.06?2 + 0.14?0 + 0.24?0 + 0.56?1 = 0.68

Mixed Strategies in Normal and Sequential Form Games

6

q

1-q

E

2 p E 1-p W 0 pE?(1-p)W 2p -2 0 0

W

0

qE?(1-q)W

p?2 + (1-p)?0

-2q 1

-1 1-p

q-1

p?0 + (1-p)?1

Just like we were looking for Nash equilibria in pure strategies we now need to do the same with mixed strategies. The difference here is that since we have infinitely many mixed strategies we can no longer draw a payoff table with rows representing choices of the Row player. Note that when 2p > 1-p, or equivalently when p > 1/3, the best response of Column is his pure strategy E since mixing in W will only lower his payoff.

By the same token, when 2p < 1-p, that is p < 1/3, the best response of Column is his pure strategy W.

Finally, when p = 1/3 then all possible strategies of Column give him the same payoff—all are best response strategies.

Mixed Strategies in Normal and Sequential Form Games 7

Game with pure strategies only

Japan E W 2 US 0 0 0 W 0 -1 1

A way to think about the same game with mixed strategies

Japan 1 1 US 1/3 0 1/3 0

E -2

qE?(1-q)W

best response of Column to Row’s choice of strategy “p” W ? q=0

E ? q=1

E ? p=1

1/3E?2/3W ? q=1/3

best response of Row to Column’s choice of strategy “q”

pE?(1-p)W

1/3E?2/3W ? p=1/3

Nash equilibrium: each is the best response to the other

2 1 2 ? ?1 ? E ? W, E ? W ? 3 3 3 ? ?3

W ? p=0

Mixed Strategies in Normal and Sequential Form Games 8

The South Pacific Example with Different Payoffs

The original game

Japan E W

E

Japan

W

2 0 0 0 1 -1

2

E US W -2 0 5

0

US

E W

-2 0

1

1

-1

What would be Row’s equilibrium strategy if his payoffs were altered as above? (Say, they can bring considerably more supplies using E rather than W.) Would you go E more often than before, less often or with the same frequency? THE SAME: since his strategy depends only on the other player’s payoffs and they are the same in both games.

Mixed Strategies in Normal and Sequential Form Games 9

THEOREM

1 2 n Denote p1s1 ? p 2s1 ? ...... ? p n s1 ? s 2 m q1s1 ? q 2s 2 ? ...... ? q ms 2 ? s* 2

s1 2

p1

……

sm 2

……

s1 1

If two proper mixes (s, s* )

……

are in Nash equilibrium then

m u 2 (s1 , s) = ... = u 2 (s 2 , s) and 2 1 n u1 (s1 , s* ) = ... = u1 (s1 , s* ).

pn

Proper mix ? does not reduce to a pure strategy

n s1

……

Idea behind the proof: If, for example, a was greater than a*, then Column would have no reason to play s2m at all and since he plays it in equilibrium it must be that a = a*.

1 n p1s1 ? .... ? p n s1

a

……

a*

……

Mixed Strategies in Normal and Sequential Form Games

10

Battle of the Sexes Example

G

1 G 2 0 0

T

0

2 1

T

0

Identify all Nash equilibria in this game.

Mixed Strategies in Normal and Sequential Form Games

11

G

T

qG?(1-q)T

1

G 2 0 T 0 pG?(1-p)T p 1 0

0

2q 2 1-q 2-2p

The value of p for which the payoffs to Column are the same: p = 2-2p or p = 2/3 The value of q for which the payoffs to Row are the same: 2q = 1-q or q = 1/3

Mixed Strategies in Normal and Sequential Form Games

12

Game with pure strategies only

A way to think about the same game with mixed strategies

1 1/3 0

G 1

T 0 0 2 1 0 1 2/3

G 2

0 T 0

qG?(1-q)T

best response of Column to Row’s choice of strategy “p” W ? q=0

G ? q=1

G ? p=1

1/3G?2/3T ? q=1/3

best response of Row to Column’s choice of strategy “q”

2/3G?1/3T ? p=2/3

pG?(1-p)T

Nash equilibria: (G, G), (T, T) and ( ? T, ? T )

T?

p=0

Mixed Strategies in Normal and Sequential Form Games 13

Competition: Chicken / Hawk-Dove Game

H

0 H 0 3 3

D

1

2 2

D

1

Draw the best response diagram and identify all Nash equilibria on it.

Mixed Strategies in Normal and Sequential Form Games

14

Game with pure strategies only The value of p for which the payoffs to Column are the same: 3(1-p) = p + 2(1-p) or p = 1/2

1 3 3 D 1 2 2

H 0

D

H 0

The value of q for which the payoffs to Row are the same: 3(1-q) = q + 2(1-q) or q = 1/2

qH?(1-q)D

best response of Column to Row’s choice of strategy “p” D ? q=0

H ? q=1

1/2H?1/2D q=1/2

H ? p=1

best response of Row to Column’s choice of strategy “q”

pH?(1-p)D

1/2H?1/2D ? p=1/2

Nash equilibria: (H, D), (D, H) and ( ? D, ? D)

D?

p=0

Mixed Strategies in Normal and Sequential Form Games 15

A footnote: mixed strategies and iterated dominance

X 4 A 6 3 B 3 2 C 2 6 3 3 2 0 Y 5

Step 1:B is dominated by ? A ? ?C Step 2: X is dominated by Y Step 3: A is dominated by C (C,Y) is the solution through iterated dominance Next comes the second important idea of Nash.

Mixed Strategies in Normal and Sequential Form Games

16

THEOREM (Nash) Every game with finite number of strategies has at least one equilibrium.

Idea behind the proof

First a few concepts: A set is closed if it contains all its boundary points. For example, interval (0,1) is not a closed set since it does not contain its boundary points; interval [0,1] is a closed set. A set is convex if for any two points it contains it also contains all points from the interval connecting the two points.

non-convex sets

convex sets

A set is compact if it is both closed and bounded. A function from Re (real numbers) to Re is continuous if you can draw its graph without having to lift the pen off the paper. This of course is not a definition but an intuition behind it.

Mixed Strategies in Normal and Sequential Form Games 17

THEOREM (Brouwer) Take any nonempty, compact, convex set X in Ren. If a function f: X→X is continuous then there is a point x0 such that f(x0) = x0.

Example: Take X = [0,1] and consider any continuous function from [0,1] into [0, 1], that is f: [0,1]→[0,1]. We have three possible cases: (1) f(0) = 0, (2) f(1) = 1, and (3) f(0) ≠ 0 & f(1) ≠ 1. In (1) the fixed point is 0, in (2) the fixed point is 1, so the only nontrivial case to consider is case (3). .

f(x) 1 f(x) = x line

f(x0) = x0

0

x0 1

x

Mixed Strategies in Normal and Sequential Form Games

18

Japan

E -2

US

E 2 0 0 -1

W 0 1

THEOREM (Kakutani) Take any nonempty, compact , convex set X. Take any correspondence f: X→X that has a closed graph and such that for any x, f(x) is convex and nonempty then there is a point x0 such that x0 ?f(x0). How does it apply to games? Take any of the games we have solved for Nash equilibria in mixed strategies as an example, say the South Pacific game.

q=0 Consider Column’s best response function: BRC(p) = q, BRC: [0,1]→ [0,1] Consider Row’s best response function: BRR(q) = p, BRR: [0,1]→ [0,1]

W0

BR of Column to Row’s “p” BR of Row to Column’s “q” q=1 p=1 q=1/3

p=1/3 p=0

Now take the following transformation: f: (p, q) → (BRR(q), BRC(p))

1 1

q

0

1 1

BRC(p)

0

(?, ?)

p BRR(q)

(?,?)

0 0

Yellow circle is a fixed point of this correspondence. This point is (?,?), of course.

(?, ?)

Mixed Strategies in Normal and Sequential Form Games 19

In 2 x 2 game finding Nash equilibria is trivial. The problem begins with larger games. The source of the problem is that in larger games we don’t know which mixes go into Nash equilibrium. Let’s go back to the Two-Finger Morra game.

Mixed Strategies in Normal and Sequential Form Games

20

C1 0 R1 0 2 2

C2 -2

C3 3

C4 0

-3 0 0

0 -3

R2

-2 -3 0 0 0 0 3 4

R3

3 0 0 3 0 -4 -4 0

R4

0 -3 4 0

Mixed Strategies in Normal and Sequential Form Games

21

C1 0 p1 R1 0 2 p2 R2 -2 -3 p3 R3 0 2

C2 -2

C3 3

C4 0

-3 0 0

0 -3

0 0 0

3 4

3

0 p4 R4 0 p1R1? p2R2? p3R3 ? p4R4 2p2-3p3

0

3

0

-4

-4 0

-3 -2p1+3p4

4 3p1-4p4

0 -3p2+4p3

The idea: Find values of p1, p2, p3 and p4 that make all payoffs to the Column less or equal to zero, that is 2p2-3p3 ?0, -2p1+3p4 ?0, 3p1-4p4 ?0 and -3p2+4p3 ?0

Mixed Strategies in Normal and Sequential Form Games 22

Note that we can group the four inequalities into two sets with the same variables: (1) -2p1+3p4 ?0, 3p1-4p4 ?0 and (2) 2p2-3p3 ?0, -3p2+4p3 ?0. where p1, p2, p3 p4?0 since they are all probabilities. Let’s solve (1): -2p1+3p4 ?0 ? 3p4 ?2p1 ? p4 ?2/3p1 3p1-4p4 ?0 ? 3p1?4p4 ? 3/4p1?p4 which means that 3/4p1? p4 ?2/3p1 or 0.75p1? p4 ?0.67p1 But this cannot be satisfied by any values of p1 and p4 that are larger than 0. The only values of p1 and p4 that satisfy these inequalities are p1 = p4=0.

Mixed Strategies in Normal and Sequential Form Games

23

Let’s solve now (2): 2p2-3p3 ?0 and -3p2+4p3 ?0. But first note that since p1 = p4=0 and all four probabilities have to add up to 1, it must be that p2+ p3=1. So, in the two inequalities we can substitute for p3 , for instance, p3=1- p2. That way we get: 2p2-3(1-p2 )?0 which is 5p2-3 ?0, and -3p2+4(1-p2 )?0.which is 4-7p2?0 Solving the two inequalities we have: p2?3/5 or p2?0.6 and p2?4/7 or (approximately) p2?0.57. Putting the two inequalities together: 0.57?p2?0.6. (This implies that 0.4?p3?0.43.)

Mixed Strategies in Normal and Sequential Form Games

24

The set of all Nash equilibria in the Two-Finger Morra Game

q2 of the Column player

set of Nash equilibria 0.6

0.57

0 0.57 0.6

p2 of the Row player

Any pair of strategies ( p2R2?(1-p2)R3, q2C2?(1-q2)C3 ) where 0.56 ? p2,q2 ?0.6 is a Nash equilibrium. The set of all Nash equilibria is identified above as the set of all points (p2,q2) where 0.56 ? p2,q2 ?0.6

Mixed Strategies in Normal and Sequential Form Games

25

Back to sequential games. How would you play the following game?

0, 2

2 X

How about representing this game in a normal form?

X

Y 2 0 2 0 1 1

A

1

Y

2, 0

A

2, 0 B 2 Y 1, 1 X B 2 0

Mixed Strategies in Normal and Sequential Form Games

26

Looks familiar?

Subtract 2 from the payoffs of Row.

X 0 2 Y 0 0 0 B 0 -1 1

X 2

Y

A

0 0 B 2 1 2 1

A

-2

It is the South Pacific example. It is easier to solve games for mixed strategy Nash equilibria when a game is represented in normal form. We can always take a sequential game and represent it in normal form. What is, however, the relationship between Nash equilibria in a normal form game and the rollback equilibrium in the corresponding sequential game?

Mixed Strategies in Normal and Sequential Form Games

27

1, 2

2

X XW 2 XZ 2 1 2 YW 3 2 3 1 2 2 YZ 3

A 1

Y

2, 3

1, 3

A B

1

3

1 2

2

B

W

2

Z 2, 2

The rollback equilibrium in this game is (A, YW) There are three Nash equilibria: (A, YW), (A, YZ) and (B, XW) but only one of them is the rollback equilibrium.

Selten: the concept of subgame perfect equilibrium (the rollback equilibrium as we have called it before.)

Mixed Strategies in Normal and Sequential Form Games 28

相关文章:

更多相关标签:

- 09 Mixed strategies in theory and tennis
- Leadership with commitment to mixed strategies
- 10 Mixed strategies in baseball, dating and paying your taxes
- Evolution Strategies for Mixed-Integer Optimization of Optical Multilayer Systems
- Finding mixed strategies with small supports in extensive form games
- 2_Mixed_Strategies,_2009-03-03
- 2 Mixed Strategies
- 2_Mixed_Strategies,_2009-03-03(中文)
- mixed_strategies_handout
- 博弈论第二讲 Mixed Strategies
- 09 Mixed strategies in theory and tennis
- Asynchronous optimal mixed P2P satellite refueling strategies
- A computational study of search strategies for mixed integer programming
- Strategies for PHA production by mixed cultures and renewable waste materials
- 复旦微观经济学mixed and continuous strategies