Esercizi di "Game Theory"

GAME THEORY

MERCOLEDÌ

• T. Ø. 2
• T. 1. 3.
• 10:15 - 12:15

MARTEDÌ

• N. Ø. 3
• prof office
• 16:15 - 18:15

GIOVEDÌ

• B. 2. 1 A-M
• B. Ø. N-Z
• 16:15 - 18:15

B

• 14:15 - 16:15
• B. 2. 1
• 16:15 - 18:15

VENERDÌ

• S. Ø. 5
• 15:15 - 18:15

1. INTRODUCTORY EXAMPLES

Exercise 2

• 2 PLAYERS
• FINITE
• COMPLETE INFORMATION
• NO CHANCE MOVE

• NO DOMINATED STRATEGIES ELIMINATION
• NO BACKWARD INDUCTION

I II deviate not

• deviate (-1,-1) (1,10)
• not (10,1) (-10,-10)

deviate not crash NO NEED: -2

deviate not crash NEEDED: +1

not deviate not crash: +10

not deviate crash: -10

COORDINATION is NEEDED

Exercise 3

1. 1) DECISION THEORY

• 2 PLAYERS
• FINITE
• PERFECT INFORMATION

(a)

X = { HOME ALONE, BACH TOGETHER, BACH ALONE,

 STRN. TOGETHER, STRN. ALONE, HOME TOGETHER }

u(X) = [-10 , +1.0 , +2 , +5 , -5]

GO to BACH: 10

GO to STRAWINSKI: 5

NOT GO: 0

(iii)

• 2 PLAYERS
• FINITE
• COMPLETE INFORMATION
• NO CHANCE MOVE

GAME

NO ELIMINATION OF DOMINATED STRATEGIES

NO BACKWARD INDUCTION

(10,10) (-2,-5) (-5,-2) (5,5)

Exercise 6

Whatever I offer, player II accepts my offer → I offer him 1 €.

ELIMINATION OF DOMINATED STRATEGY: II will always accept!

BACKWARD INDUCTION: I know that II will always accept!

• 2 PLAYERS
• FINITE
• PERFECT INFORMATION
• NO CHANCE MOVE

2. GAMES IN EXTENSIVE FORM

Ex. 8

1) Father offers Alice 2 identical objects.

• 2 players
• finite
• no chance move
• perfect information

INDIFFERENCE IN BACKWARD INDUCTION!

WEAKLY DOMINATED STRATEGIES ELIMINATION: LEADS TO THE SAME INDIFFERENCE

2) FATHER OFFERS ALICE 1 object:

INDIFFERENCE IN BACKWARD INDUCTION!

Ex. 19

Can remove {1,2,3,4,5,6,7}

• 2 players
• finite
• perfect information
• no change move
• zero-sum game
• win/loose, no tie
• normal play rule

P P N N N N N N N N P P

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

P positions = {m ∈ ℕ / m mod 7 = 0} = ^₀, m.zero = m ∈ ℕ

→ 31 chips = initial position ⇒ It is a N position ⇒ Player I wins and Player II loses;

A winning strategy is 31 ➞ 28 ... {27,26,25,24,8,22} ⇒ 24 ➞ {20,19,18,17,16,15,14} ➞ 7 ➞ 0

P N N N N P N P

{13,12,11,10,8} ➞ {1,2,3,4,5,6} ➞ ⁰ ➞ win!

N P P N I P

Ex. 21

Nim game :

• 2 players
• finite, perfect information
• zero-sum game
• normal play rule
• no change move

Finite position: (8,5,13,2)

1) It is a N-position :

8 = 1000 _₊ᴺ

5 = 0101 _₊ᴺ

13 = 1101 _₊ᴺ

2 = 0010 =

0010 = ² ≠ _θ ⇒ (x\xcZx.zhBhcomBouton) It is a N-position.

2) The only possible winning strategy is to bring to (8,5,13,0), which is a P-position (xZ.xcBx.khxBouton).

Ex. 22

Rules: n coins ; you can turn over one coin and, if you want, another coin to the left

Initial position : T H T T H T T H T H T H T H

1 2 3 4 5 6 7 8 9 10 11 12 13

i) This is (?)_NIM ➞ ...

1. 2
2. 5
3. 9
4. 12

Ex. 23 (B)

B =

3 2 1 0

0 1 2 0

1 0 2 1

3 1 2 2

2 players

zero-sum

Dominated strategies:

No elimination

Maxmin and Cominvetive values:

v_I^e = max {0, 0, 0, 1} = 1

v_II^e = min {3, 2, 2, 2} = 2

There are no equilibria in pure strategies.

I can't say nothing about MIXED strategies (except that there exists at least one equilibrium).

Ex. 33:

A =

6 0 5 3

1 5 8 4

2 players

fruit

zero-sum game

Strictly dominated strategies:

(6 0 3)

(1 5 4)

Cominvetive values of the players:

(6 0 5 3) 0

(1 5 8 4) 1

No equilibria in pure strategies.

I can reduce the matrix to:

(6 0 3)

(1 5 4)

If I play r_i with positive probability both rows (ρ ∈ (0,1) ) An optimal strategy for player II is, and that

6q_I + 0q₂ + 3 (1-q_I-q₂) = q₁ + 5q₂ + 4 (1-q_I-q₂)

(9q₁ q₂, 1-q_I-q₂) 3q_I+q₂ =

3q_I-3q₂ +3 = -3q_I + 9q₂ + 4

6q_I - 4q₂ + 1 = 0 (C).

5. GAMES IN STRATEGIC FORM

Ex. 43

confess not confess confess (-5,-5) (0,-7) not confess (-7,0) (-1,-1)

This is a 2 players, finite, with complete information, no chance move, non-zero-sum, (non-cooperative) game. Let's try elimination of dominated (strictly) strategies. We obtained Nech Equilibria in pure strategies:

(-5,-5) (0,-7) (-7,0) (-1,-1)

(1,0),(1,0) is the strategy profile which provides a Nash Equilibrium. Looking for correlated equilibria:

• x + y + z + t = 1
• x = y
• 2x = y
• x+2y+z+t=1
• x>-y/2
• y=-z/2
• Since (1,0),(1,0) is a N.E. profile

x = 0 | x+z=1 ( x 0) t >= 0 | x >= 0 (0 0) z >= 0 | t >= 0 y = 0 |

is a C.E.

Ex. 44

(5,4) (1,6) (0,3) (5,1) (15,3) (3,2) (1,0) (4,3) (2,5) (4,0) (1,5) (2,1)

Nash Equilibria in pure strategies are: ( (0,4,0),(4,0,0,0) ) ( (0,0,1),(0,0,2,0) )

Ex. 48

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

Nash Equilibrium in pure strategies is: ((0,1),(0,1))

let's see if

(¹/₃,¹/₃,¹/₃) ∈ BR₁(^y/₃) :

if a = z :

y = (9,4,-9,0) ; Let's suppose x ∈ BR₁(^y/₃) ⇒ {2q+(1-9) = bq+(1)(1-9) ⇒

{2q+(1-4) = 2q+(1-9) ⇒

q = 2/b ⇒ b = 2/q ; q = 2/b = 1 ; (b ≥ 2 or b ≤ 1) (b ≥ 2) ∩ (b > 0)

So in the case (^{z - b}/_{b z z}) ∩ (b z z) :

^{(x, 1 - 2/b y y}/₃) is ∈ N.E.

if a > 2 : y = (-3, 0, 1, 0) ; If x ∈ BR₁(y) ⇒ {1 = -1

1 = 1 FALSE

if a < 2 :

y = (1, 0, 0) ; If x ∈ BR₁(y) ⇒ b = -2

b = 2

So in the case (a < 2) ∩ (b = z) :

(x, (1, 0, 0, 1)) is ∈ N.E.

3. b = 1 :

^{(x, 0, 0)}/_{(0, 0, 0)}

 y 0

^{x = 1 :}

2 1 -2

1 9 2

2 1 0

{@^{2x ≥ x}/_{3x ≥ 2x}

ok ⇒ θ ≥ 0

ok ⇒ θ ≥ 0

^{x = 3 :}

2y + z ≥ 2y + z

24 + 2 ≥ 14 - z

^{surge 0}

z = -2y 4

if y ≤ y

y = -z

2y ≥ 0

^{j = 1 :}

1 1 1

1 3 θ

1 0 1

2 1 2

{@ 3x ≥ x +y ⇒ 2x ≠ y

3x ≥ x +2y

2x ≥ 2y

{@ ^{j = 2 :}

z ≥ 0

z ≥ 2z

z ≥ 0

j = θ ≥ 0

^{j = 3 :}

0 2 0

0 2 0

A C E is :

^{x, 0, 0}/_{0 0 0} with x ≥ y

-Ex. 62.

1. The N.E. in pure strategies are :

   if (a ≥ z) : ((1, 0, 0), (1, 0, 0)) with outcome (2, 2)

   if (b ≤ 6) : ((0, 1, 0), (0, 1, 0)) with outcome (5, 6)

2.  ^{x = (}/₄

   4, 4, z)

BR_a(x) :

     ^{E_R(1, y₁) = 2}/₁ = 4

     ^{2 + b}/₄ = 3

 E_x(x, y₂) = 2 ¹/₄ = 4/4 =⇒ 3 = 2

        5 = 5 ⇒ 1

 E_x(x, y₃) = 1/4 + 5/2 = θ b + 4/0

y (x, 0 (0, 9 - 1, 4)

  0, y y y = 2

   ²/6 + 4/4 · b + θ -4

        ^{1. 1-9 + 3 - 4 + 5 (1-9) z}/_{9 + b/4 + b/4}

+ 3/2 + 9 + 2f_q