Game Theory: Lecture of March 26, 2019

Game Theory: Lecture of March 26, 2019

Chiara Mocenni

MSc in Game Theory

In game theory we consider a set of n alternatives available to take a given decision. Formally, we use a vector x of n components (x ∈ R

). In particular, the i -th component x

will be the only equal 1 if we decided to adopt the strategy labeled by the number i . This vector identifies univocally the decision we have taken.

Specifically:

x

=

 1 if the adopted strategy is the i -th

0 if the adopted strategy is not the i -th (1)

We can think to a profit, usually named payoff, as a function

π(x ) : R

−→ R that associates to each choice vector x a real

number that quantifies the reward that the individual is obtaining

from that choice.

In game theory the choices of the various participants are independent one from the other and are driven by the willing of each subject to maximize his own payoff. The individuals are called players.

In the simplest case the game is played by two players.

Let be x ∈ R

the vector indicating the choice of the first player in a set of n strategies, while y ∈ R

will indicate the choice of the second participant, who has m options available. The payoff functions are the following:

π

(x , y ) : R

× R

−→ R payoff of player 1

π

(x , y ) : R

× R

−→ R payoff of player 2

Each player is aimed at maximizing his own payoff taking into

account the choices of the opponent. The decisions of the two

players are independent, communicated at the same time, then

there is no time for hesitation or collusion. The mechanism is like

the public auctions. Sealed-bid auctions in which bidders place

their bid in a sealed envelope and simultaneously hand them to the

auctioneer. The envelopes are opened and the individual with the

highest bid wins, getting the bigger payoff (paying the amount bid

for the real first-price auctions).

Game theory is a tool supporting people to take decisions. It is robust and take advantage by many theorems and results. All these results are based on the assumption that the payoff functions are all known. Actually, to identify correctly a payoff function is a hard job: it is like to quantify the happyness that someone has when doing something!

In the decision theory we can define the payoff functions by means

of estimates of the information cost or by assessing the utility

functions during appropriate interviews to the decision maker.

The payoff of players 1 and 2 are determined by the couple of strategies (i , j ), where i is the strategy of player 1 and j the one adopted by player 2. We indicate with a

the payoff that player 1 earns if he uses strategy i while his opponent is using strategy j . b

indicates the payoff of player 2: again, b

is the payoff the he gets when he is choosing j and his opponent (player 1) chooses i . It follows that we have introduced two payoff matrices

A, B ∈ R

, such that A = {a

} and B = {b

}.

We can use the above matrices to introduce the payoff functions:

π

(x , y ) = x

Ay π

(x , y ) = x

By

Indeed, when x and y are vectors defined as above, then x

Ay and

x

By identify the elements a

of matrix A and b

of matrix B,

assuming the x

and y

are the only components of x and y equal 1.

In game theory we can introduce the best reply . These are functions that support the decision mechanism. 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. We indicate with β

(j ) and β

(i ) the best reply of players. For example:

A =





1 3 0 2 0 4 5 9 3



 =⇒







β

(1) = {3}

β

(2) = {3}

β

(3) = {2}

Actually, considering that columns indicate the strategies of player

2, we fix the column relative to the strategy j ; then we look for the

maximum element along this column. The best reply will be the

strategy i (row) where is placed the maximum element.

One more exemple:

A =





3 6 2

3 6 1

5 1 0



 =⇒







β

(1) = {3}

β

(2) = {1, 2}

β

(3) = {1}

In this case, if player 2 adopts strategy j = 2, then player 1 is

indifferent when using strategies i = 1 and i = 2, since they

guarantee the same payoff. The best reply function of player 2 is

similar to the one above, except that we have to exchange rows

(strategies of player 1) with columns (strategies of player 2).

Let’s consider the following game:

A =





3 6 20

3 6 1

5 1 0



 =⇒







β

(1) = {3}

β

(2) = {1, 2}

β

(3) = {1}

B =





4 8 2

1 1 10

3 5 5



 =⇒







β

(1) = {2}

β

(2) = {3}

β

(3) = {2, 3}

Selfishness of players could bring them to take a decision that is non optimal for the game. The idea to overcome this problem is to look for a compromise, that is take a decision that is good for both players. We must reach some equilibrium between the two parts.

Mathematically, we can define an equilibrium in the following way:

(i

, j

) is an equilibrium ⇐⇒

 i

∈ β

(j

)

j

∈ β

(i

) (2)

Thsi idea has been formalized by the Nobel prize Nobel J.F.Nash

who gave the name to the Nash equilibrium.

Studying the best reply functions introduced above, we obtain that (i

, j

) = (1, 2). Indeed

i

= 1 ∈ β

(j

= 2) = {1, 2}

and

j

= 2 ∈ β

(i

= 1) = {2}.

If player 2 could be sure that his opponent will choose i = 1, then

he will choose j = 2, thus earning the maximum payoff available

reachable when i = 1. Similarly, player 1, knowing that player 2 will

choose j = 2, will be able to choose i = 1 and i = 2, because both

strategies will ensure a maximum payoff. If players will be allowed

to change strategy unilaterally from i = 1 and j = 2, they will not

have reason for doing so. For this reason we talk of equilibrium.

The Nash equilibrium we have found previously is non strict,

indeed player 1 has two options to maximize his payoff with

respect to the choice j = 2. When there is no ambiguity we can

talk of strict equilibrium. Anyway, there is no guarantee that,

given a game, only one Nash equilibrium exists. They may be more

than one, or even no one, although we will see that one Nash

equilibrium always exists in the set of mixed strategies (not yet

introduced here).

There is also another method to find Nash equilibrium, namely the bi-matrix method:

player 2

strat. 1 strat. 2

strat. 1 (5, 2) ← (1, 1)

player 1 ↑ ↓

strat. 2 (1, 7) ← (2, 3)

When we find a strategy with only pointing in arrows, then this is

a strict Nash equilibrium. In this case we have that the number of

arrows corresponds to the maximum number of available arrows (2

for games with 2 participants). In this particular case strategy

(1, 1) is a strict Nash equilibrium.

Another example:

player 2

strat. 1 strat. 2

strat. 1 (4, 20) ← (3, 15)

player 1 l ↑

strat. 2 (4, 7) → (2, 13) The double sided arrow indicates that player 1 is indifferent

between choosing his strategy when the opponent chooses strategy

1 (he will earn the same payoff in any case). We see that the

couple of strategies (1, 1) is a Nash equilibrium because it has 2

pointing in arrows, but in this case it is non strict, indeed there is

also one pointing out arrow.

Let’s define I = {1, 2, ...n} the set of players, where n is a positive integer number and S

= {1, 2, ...m

} the set of pure strategies for each player i ∈ I , where m

≥ 2. Player i is characterized by a vector x

∈ R

such that:

x

=

 1 if strategy adopted by player i is j

0 if strategy adopted by player i is not j . (3)

The set of vectors {x

, x

, . . . , x

} is named strategy profile.

For each strategy profile and each player i ∈ I , let’s

π

(x

, x

, . . . , x

) ∈ R the payoff associated to player i. In game theory, the payoff of one player is a function that incorporates the value of its outcome for the choices of all the other players involved in the game.

In the particular case of a game played by two players, the payoff

functions , π

(x

, x

) and π

(x

, x

), can be represented by two

matrices A and B like R

; notice that in this case we used x

instead of x , and x

instead of y .

A mixed strategy for player i is a probability distribution in the set of its m

pure strategies. Formally:

x

= Probability for which player i will use strategy j (4) Following this definition we can interpret a pure strategy as a particular case of mixed strategy. Saying that player i uses the pure strategy j ” is equivalent to say that “player i uses strategy j with 100% of probability”, that “player i uses strategy j 100% of the times”.

An example of mixed strategy is the following:

x

= 

0.4, 0.1, 0, 0.5  , (5)

where player i has m

= 4 strategies available.

Since x

( j = 1, 2, ..., m

) represent probabilities, then vector x

∈ R

belongs to the simplex ∆

in the m

-space:

∆

=







x

∈ R

:

mi

X

j =1

x

= 1







. (6)

Figura: Il simplesso ∆

con m = 3.

Figura: Geometric representation of the simplex for m = 3.

Simplex ∆

of player i has dimension m

− 1.

The vertices of ∆

are the versors of the m

-space, indicated by e

= (1, 0, ..., 0), e

= (0, 1, ..., 0), up to e

= (0, 0, ..., 1).

Each vertex e

represents the mixed strategy i who assigns probability 1 to the j -th pure strategy. If player i uses pure strategy j , then x

= e

.

The simplex of mixed strategies ∆

is a convex hull of the vertices, and each x

∈ ∆

is a convex combination of the versors, said pure strategies e

:

x

=

mi

X

j =1

x

e

. (7)

The interior of ∆

is defined as:

int(∆

) = {x

∈ ∆

: x

> 0 ∀j} (8) The mixed strategies of this subset are called internal or fully mixed and they associate positive probabilities to all pure strategies of the players.

The set of not internal strategies of ∆

is called boundary of

∆

, defined as:

bd (∆

) = {x

∈ ∆

: x

∈ int(∆ /

)} (9) The boundary of ∆

is the set of strategies x

for which at least one strategy j is played with null probability, i.e.

∃j ∈ {1, . . . , m

} : x

= 0

A mixed strategy profile X = {x

, x

, ..., x

} is a point in the space of mixed strategies of the game:

Θ = ×

∆

. (10)

Θ is the product of n simple units ∆

, where each of them is a set (m

− 1)-dimensional for each player i ∈ I , the set is a

(m − n)-dimensional polyhedron in R

, where

m = m

+ m

+ ... + m

is the total number of pure strategies of the game. A strategy profile X is said internal if each component x

is internal. The subset of such profiles is defined as:

int(Θ) = ×

int(∆

). (11)

Similarly, the boundary of Θ, bd (Θ), is the set of non internal

profiles x ∈ Θ.

Introducing the mixed strategies implies a revision of the concept of payoff. Indeed, since mixed strategies are probability

distributions, then the payoff is the expected value of the payoffs that can be earned by means of pure strategies. This is true for each game with n players.

Let’s analyze the simple case of 2 players. Let A ∈ R

be the payoff matrix of player 1. Suppose that player 1 decides to use the pure strategy i , while player 2 plays the mixed strategy x

. In average, player 1 will get the following quantity:

u

=

m2

X

j =1

a

x

,

which is the sum of payoffs a

weighted by the probabilities x

.

If player 1 opts for the mixed strategy x

, he will earn in average:

m1

X

i =1

x

u

=

m1

X

i =1 m2

X

j =1

x

a

x

,

which represents the sum of the average payoffs u

weighted by the probabilities x

. The double sum allows to rewrite the payoff in the matricial form:

m1

X

i =1 m2

X

j =1

x

a

x

= x

Ax

,

making the previous equation in line with the definition of payoff given for the pure strategies:

π

(x

, x

) = x

Ax

. (12) Similarly, the payoff of the second player is

π

(x

, x

) = x

Bx

.

Let’s now consider the games with two strategis. The payoffs are represented by the following matrices:

A =

 a

b

c

d



, B =

 a

c

b

d

 . and the corresponding bi-matrix is:

G 2

s1 s2

s1 (a

, a

) (b

, c

) G 1

s2 (c

, b

) (d

, d

)

Consider the payoff functions obtained by matrices A and B, and using as vectors x = [x

1 − x

]

and y = [y

1 − y

]

:

π

(x , y ) = x

[(a

− c

+ d

− b

)y

+ b

− d

] + (c

− d

)y

+ d

π

(x , y ) = y

[(a

− c

+ d

− b

)x

+ b

− d

] + (c

− d

)x

+ d

(13) Calculating the derivatives

1

and

1

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

x

= (d

− b

)

(d

− b

) + (a

− c

) , x

= (a

− c

) (d

− b

) + (a

− c

) y

= (d

− b

)

(d

− b

) + (a

− c

) , y

= (a

− c

) (d

− b

) + (a

− c

)

(14)

These solutions are valid if they belong to the simplex ∆ of dimension 2 and possibly represent the mixed equilibrium of the game.

The pure equilibria can be obtained by means of the bi-matrix

method.