Game Theory: lecture of April 2, 2019

Game Theory: lecture of April 2, 2019

Chiara Mocenni

Course on Game Theory

Symmetric Games with two players (1/2)

A game is symmetric when the two players obtain the same payoff under the same conditions.

A symmetric game involves two players with the same number of strategies and the payoff function of any strategy is

independent on the location of the player that is playing at a given time.

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 of the first player, that is: B = A^T.

Symmetric Games with two players (2/2)

With K = {1, 2, ..., k} we indicate the set of pure strategies With x ∈ ∆ e y ∈ ∆ we indicate the mixed strategies of the first and the second player, where

∆ = {x ∈ R₊^k :P

i ∈Kx_i = 1}, while Θ = ∆².

The set of best reply β(z) is calculated with respect to one strategy z ∈ ∆ and it is the same for both players:

β(z) = {x ∈ ∆ : π(x , z) ≥ π(y , z) ∀y ∈ ∆}.

Symmetric Nash Equilibria

A couple of strategies (x , y ) ∈ Θ = ∆² (strategy profile) is a Nash equilibrium, (x , y ) ∈ Θ^NE, is and only if x ∈ β(y ) and y ∈ β(x ). If x = y , the equilibrium (x , y ) is said symmetric.

The subset of strategies x ∈ ∆ that are in equilibrium with themselves is:

∆^NE = {x ∈ ∆ : (x , x ) ∈ Θ^NE}

The Nash equilibria of a symmetric game can be asymmetric, but each symmetric game has at least one symmetric Nash equilibrium.

Theorem

For each finite symmetric game with two players,, ∆^NE 6= ∅.

Classification of 2x2 symmetric games

In this section we analyze games where players have only two pure strategies available. Let be the generic payoff matrix of a 2 × 2 symmetric game:

A =

 a₁₁ a₁₂ a21 a22



Subtracting a21 from the first column and a12 from the second, we have:

A⁰ =

 a11− a₂₁ 0 0 a₂₂− a₁₂



In this way we obtain a symmetric matrix and then a symmetric game, with payoff matrix:

A⁰=

 a1 0 0 a₂



Where a₁ = a₁₁− a₂₁ and a₂ = a₂₂− a₁₂.

Graphical representation

The obtained matrix is identified by one point a = (a1, a2) ∈ R². This point will belong to one of the orthants of this cartesian plane, allowing us to identify the category to which the game corresponds.

Calculus of symmetric Nash equilibria

If x ∈ ∆^NE (x is a symmetric Nash equilibrium), then x ∈ β(x ). In other words:

π(x , x ) ≥ π(y , x ) ∀y ∈ ∆, or

x^TAx ≥ y^TAx ∀y ∈ ∆.

We can rewrite the equation in terms of sums:

k

X

i =1

x_i[Ax ]_i ≥

k

X

i =1

y_i[Ax ]_i ∀y ∈ ∆, (1) where [Ax ]_i indicates l’i -th component of vector Ax .

Theorem for pure equilibria

Theorem

Let x be a pure strategy (x = e^h). If [Ax ]_h≥ [Ax]_i ∀i 6= h, then x ∈ ∆^NE.

Proof.

Let M = [Ax ]_h. We have that:

k

X

i =1

x_i[Ax ]_i = x_h[Ax ]_h= M, and

k

X

i =1

y_i[Ax ]_i = y_h[Ax ]_h+

k

X

i =1,i 6=h

y_i[Ax ]_i = y_hM +

k

X

i =1,i 6=h

y_i[Ax ]_i.

... cont

Since M ≥ [Ax ]_i ∀i 6= h, then:

k

X

i =1,i 6=h

y_i[Ax ]_i ≤

k

X

i =1,i 6=h

y_iM = (1 − y_h)M.

Therfore:

Pk

i =1xi[Ax ]i = M, e Pk

i =1yi[Ax ]i ≤ M.

From this it follows that

k

X

i =1

x_i[Ax ]_i ≥

k

X

i =1

y_i[Ax ]_i ∀y ∈ ∆.

Theorem for the mixed equilibria

Theorem

Let x be a strategy belonging to int∆, that is it is a mixed strategy such that x_i > 0 ∀i . If [Ax ]_i = [Ax ]_j ∀i , j, then x ∈ ∆^NE. Proof.

Let M = [Ax ]_i ∀i . Then:

k

X

i =1

x_i[Ax ]_i =

k

X

i =1

x_iM = M

k

X

i =1

x_i = M · 1 = M, and

k

X

i =1

y_i[Ax ]_i =

k

X

i =1

y_iM = M

k

X

i =1

y_i = M · 1 = M.

... cont

Then, equation (1) holds always in non strict form, that is:

k

X

i =1

x_i[Ax ]_i =

k

X

i =1

y_i[Ax ]_i ∀y ∈ ∆.

This means that x is a symmetric Nash equilibrium. Moreover, this equilibrium is non strict.

Theorem for pure/mixed equilibria

Theorem

Let x be a mixed strategy with only one null component (x_h= 0, x_i > 0 ∀i 6= h). If [Ax ]_i = [Ax ]_j ∀i 6= h, j 6= h, and [Ax ]_i ≥ [Ax]_h ∀i 6= h then x ∈ ∆^NE.

Proof. Let M = [Ax ]_i ∀i 6= h. Then:

k

X

i =1

xi[Ax ]i =

k

X

i =1

xiM = M

k

X

i =1

xi = M · 1 = M, and

k

X

i =1

yi[Ax ]i =

k

X

i =1,i 6=h

yiM + yh[Ax ]h= M

k

X

i =1,i 6=h

yi + yh[Ax ]h=

= M(1 − y_h) + y_h[Ax ]_h.

... cont

In the second equation we have used the fact that

k

X

i =1

y_i = 1 ⇒

k

X

i =1,i 6=h

y_i = 1 − y_h. By assumption, we have that M ≥ [Ax ]_h. It follows that:

M ≥ [Ax]_h ⇒

y_hM ≥ y_h[Ax ]_h ⇒

yhM + M − M ≥ y_h[Ax ]h ⇒

M − M(1 − y_h) ≥ y_h[Ax ]_h ⇒ M ≥ M(1 − y_h) + y_h[Ax ]_h ⇒

k

X

i =1

xi[Ax ]i ≥

k

X

i =1

yi[Ax ]i ∀y ∈ ∆.

Since x satisfy eq. (1) for each y , then x is a symmetric Nash eq.