• Non ci sono risultati.

Game Theory: lecture on March 20, 2018

N/A
N/A
Protected

Academic year: 2021

Condividi "Game Theory: lecture on March 20, 2018"

Copied!
18
0
0

Testo completo

(1)

Game Theory: lecture on March 20, 2018

Chiara Mocenni

Course on Game Theory

(2)

Le funzioni di payoff

In a game with two players we use the payoff functions calculated by means of the payoff matrices of each player.

Let A ∈ R m

1

×m

2

and B ∈ R m

1

×m

2

be the payoff matrices of players

1 and 2, respectively. We have 4 cases: both players choose pure

strategies, one chooses a pure and the other a mixed strategy, both

choose mixed strategies.

(3)

Both players choose pure strategies

If player 1 chooses pure strategy i and player 2 pure strategy j , the payoff obtained by player 1 is:

a i ,j and the payoff obtained by player 2 is:

b i ,j

(4)

One player chooses pure and the other mixed strategy

Player 1 chooses pure strategy i (then x i = 1 and all the other elements of vector x are null) and player 2 chooses the mixed strategy y . The payoff obtained by player 1 is:

u 1i =

m

2

X

j =1

a ij y j

while if player 2 chooses pure strategy j (then y j = 1 and all the other elements of vector y are null) and player 1 the mixed strategy x the payoff obtained by player 2 is:

u 2j =

m

1

X

i =1

b ij x i

(5)

Both players choose mixed strategies

Let x and y the mixed strategies of player 1 and 2, respectively.

Player 1 in average earns:

π 1 (x , y ) = x T Ay while player 2 in average earns:

π 2 (x , y ) = x T B T y

(6)

Games with two players and two strategies

In a game with two players and two strategies the payoffs of the two players are represented by the two matrices:

A =

 a 1 b 1

c 1 d 1



, B =

 a 2 b 2

c 2 d 2

 . and by the bi-matrix:

G 2

s1 s2

s1 (a 1 , a 2 ) (b 1 , c 2 ) G 1

s2 (c 1 , b 2 ) (d 1 , d 2 )

(7)

The payoff functions of games with two strategies and two players

The payoff functions obtained by the matrices A and B, using vectors

x = [x 1 1 − x 1 ] T and y = [y 1 1 − y 1 ] T , are:

π 1 (x , y ) = x 1 [(a 1 − c 1 + d 1 − b 1 )y 1 + b 1 − d 1 ] + (c 1 − d 1 )y 1 + d 1

π 2 (x , y ) = y 1 [(a 2 − c 2 + d 2 − b 2 )x 1 + b 2 − d 2 ] + (c 2 − d 2 )x 1 + d 2

(8)

The Nash equilibria in games with two players and two strategies

Calculating the derivatives

∂π 1

∂x 1 e ∂π 2

∂y 1

and letting them equal to 0, we obtain the following solutions:

x 1 = (d 2 − b 2 )

(d 2 − b 2 ) + (a 2 − c 2 ) , x 2 = (a 2 − c 2 ) (d 2 − b 2 ) + (a 2 − c 2 ) y 1 = (d 1 − b 1 )

(d 1 − b 1 ) + (a 1 − c 1 ) , y 2 = (a 1 − c 1 ) (d 1 − b 1 ) + (a 1 − c 1 )

(1)

(9)

Feasibility of pure and mixed Nash equilibria

Nash equilibria are feasible if they belong to the simplex ∆ of dimension 2 and may represent a mixed equilibrium of the game, if any.

The pure equilibria can be directly calculated by the bi-matrix.

(10)

Classification of games with two players and two strategies

Sometimes it is convenient to classify the games with two players and two strategies in:

Uncoordinated games

Coordinated games

Contributive games

(11)

Uncoordinated games (1/2)

In these games pure Nash equilibria do not exist. This happens in the following case:

G 2

s1 s2

s1 (a 1 , a 2 ) ← (b 1 , c 2 )

G 1 ↓ ↑

s2 (c 1 , b 2 ) → (d 1 , d 2 )

where we have that c 1 > a 1 , b 1 > d 1 , a 2 > c 2 and d 2 > b 2 .

(12)

Uncoordinated games (3/2)

In the following case we have the same situation:

G 2

s1 s2

s1 (a 1 , a 2 ) → (b 1 , c 2 )

G 1 ↑ ↓

s2 (c 1 , b 2 ) ← (d 1 , d 2 ) where a 1 > c 1 , d 1 > b 1 , c 2 > a 2 and b 2 > d 2 .

From the Nash Theorem we know that at least one mixed

equilibrium exists, then we can conclude that it corresponds to the

one found by solving equations (1). Indeed, we don’t have any

pure equilibrium.

(13)

Coordinated games

In coordinated games 2 pure Nash equilibria exist. These equilibria correspond to the strategy profiles (1, 1) and (2, 2). The two players, under the hypothesis that they have the same available strategies, are coordinated because they choose the same strategy.

G 2

s1 s2

s1 (a 1 , a 2 ) ← (b 1 , c 2 )

G 1 ↑ ↓

s2 (c 1 , b 2 ) → (d 1 , d 2 )

We have that a 1 > c 1 , d 1 > b 1 , a 2 > c 2 and d 2 > b 2 .

(14)

Contributive games

In contributed games 2 pure Nash equilibria exist. These equilibria are defined by the strategy profiles (1, 2) and (2, 1). The term

”contributive“ depends on the fact that at the equilibrium each player contributes to maximize the payoff of the opponent.

G 2

s1 s2

s1 (a 1 , a 2 ) → (b 1 , c 2 )

G 1 ↓ ↑

s2 (c 1 , b 2 ) ← (d 1 , d 2 )

We have that c 1 > a 1 , b 1 > d 1 , c 2 > a 2 e b 2 > d 2 .

(15)

Mixed Nash equilibria of a game with two players and three strategies

We show how to calculate the mixed Nash equilibrium of the ROCK-SCISSOR-PAPER game.

Notice that this game does not have any pure equilibrium. A fundamental theorem of game theory helps us to solve the problem of finding all feasible Nash equilibria of a game. John Nash

demonstrated that in any game at least one Nash equilibrium exists in the space of mixed strategies.

The payoff matrices of the R-S-P game are the following:

A = B =

0 −1 1

1 0 −1

−1 1 0

(16)

The payoff functions

Let the vectors x and y be:

x =

x 1

x 2

1 − x 1 − x 2

 , y =

y 1

y 2

1 − y 1 − y 2

 The payoff functions become:

π 1 (x , y ) = x T Ay = (−3y 2 + 1)x 1 + (3y 1 − 1)x 2 − y 1 + y 2

π 2 (x , y ) = x T B T y = (−3x 2 + 1)y 1 + (3x 1 − 1)y 2 − x 1 + x 2

(17)

Maximizing the payoff functions (1/2)

Calculate the derivatives...

 

 

 

 

∂π 1

∂x 1

= −3y 2 + 1

∂π 1

∂x 2 = 3y 1 − 1 ,

 

 

 

 

∂π 2

∂y 1

= −3x 2 + 1

∂π 2

∂y 2 = 3x 1 − 1

(18)

Maximizing the payoff functions (2/2)

...and set them equal to 0:

 

 

 

 

∂π 1

∂x 1 = −3y 2 + 1 = 0

∂π 1

∂x 2

= 3y 1 − 1 = 0

=⇒

 

 

 

 

 

 

 

 

y 1 = 1 3 y 2 = 1 3

y 3 = 1 − y 1 − y 2 = 1 3

 

 

 

 

∂π 2

∂y 1 = −3x 2 + 1 = 0

∂π 2

∂y 2 = 3x 1 − 1 = 0

=⇒

 

 

 

 

 

 

 

 

x 1 = 1 3 x 2 = 1 3

x 3 = 1 − x 1 − x 2 = 1

3

Riferimenti

Documenti correlati

The rules also specify that the set of coins that may be turned over depends only on the position of the rightmost coin turned over and not otherwise on the position of the other

in which both the expected payoffs and actual payoff division are proportional to the voting weights. In this paper we wish to explore the connections between constant sum

Games on graphs Written by Group 13 Revised by 3.. PART II: Repeated and Evolutionary Games

Likewise, if your accomplice confesses while you remain silent, he will go free (freedom) while you do the time (4 years in jail). • If you both confess I get two convictions, but

The best reply of player 1 associates for each strategy of player 2 the set of strategies that player 1 must adopt to maximize his payoff... Actually, considering that columns

Assuming the equivalence of the payoff functions of the pure strategies is equivalent to assume that the payoff bi-matrix of the second player is the transpose of the payoff matrix

Infinite population of equal individuals (players or replicators) Each individual exhibits a certain phenotype (= it is.. preprogrammed to play a

The characteristic function of a TU Game may be obtained starting from the strategic or normal form of the game, taking into account the different possible total payoffs of a