Solving Zero-Sum Games and the Minimax Theorem

In this part we will look a special class of zero sum games. (1)

remind:

  • There are 2 players.
  • where the sum of the players payoffs is zero:
U1(a1,a2) + u2 (a1,a2) = 0
  • exampes: Matching Pennies, Rock-Paper-Scisssors
  • “Zero” is not critical; generalized to “constant-sum” games:

U1(a1,a2) + u2 (a1,a2) = k

We can say that zero is not a particular privileged.

matching pennies                                Rock-Paper-Scissors
\     H       T                                         \       R       P         S
H   1,-1    -1,1                                      R     0,0  -1,1    1,-1
T  -1,1     1,-1                                     P     1,-1   0,0    -1,1
P     -1,1   1,-1    0,0

looking carefully, we can say something else about them…

Minimax Theorem

This theorem says if we can look at each of the players, in turn, and reason about what they might do in equilibrium.

So, in particular, let’s look at what it says about player 1. We says that player 1’s strategy, S1, if in
equilibrium, must be the results of doing this optimization on the part of player 1.

S1 = argmax s1’ ϵ S1 mins2 ϵ S2  [ u1(S’1, S2) ]

Player 1 (S1) says to itself, well, I care about my payoff, my utility (u1). And I want to find an S1 that maximizes my utility, that argmax part. Knowing that my opponent will do everything they can to minimize (min) my utility. This is where we’re using the zero, zero sum property of the game. That makes a lot of sense.

Similarly we can look at player 2 (S2):

S2 = argmin s2’ ϵ S2 mins1 ϵ S1  [ u1(S1, S’2) ]

Player 2 says well. I care about my pay off, buy my pay off is minus the pay off of my opponent. And so therefore, what I want to do is to find the argument that will minimize that payoff to the opponent, knowing that the opponent will do everything they can to maximize it.

So the equilibrium strategy is the max min of this value, or the min max of this valueu

u1(s1,s2) = max min  u1 (S1,S2) = min max u1 (S1,S2)

So far, this is called the min max theorem. It can be viewd as describing the equilibrium.

Pictorically: Matching Pennies

The game is played between two players, Player A and Player B. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match (both heads or both tails) Player A keeps both pennies, so wins one from Player B (+1 for A, -1 for B). If the pennies do not match (one heads and one tails) Player B keeps both pennies, so receives one from Player A (-1 for A, +1 for B). This is an example of a zero-sum game, where one player’s gain is exactly equal to the other player’s loss. (2)

And now we look at this three dimensional surface which is all the payoffs to the first agent and therefore minus the payoffs for the second agent given any strategy they might pick.

In the middle (randomize half) of the picture we can find a zone that contains a particullar point, it’s called saddle point. It has a special property where neither player has incentive to deviate.

from Game Theory 101:

Soccer Penalty Kicks

How reason about this game

  • How does the kicker maximize his minimum?

maxS1  minS2[ S1(L)S2(L)*0.6 + S1(L)S2(R)*0.8 + S1(R)S2(L)* 0.9 + S1(R)S2(R)*0.7 ]

  • How does the golie minimize the kicker’s maximum?

Omiting the maximization part for now. Let’s subtitute S2(R) by 1-S2(L)

minS2[ S1(L)S2(L)*0.6 + S1(L)S2(R)*0.8 + S1(R)S2(L)* 0.9 + S1(R)S2(R)*0.7 ]

=>  minS2 [ S1(L)S2(L)*0.6 + S1(L) (1 – S2(L))*0.8 + (1 – S1(L))S2(L)* 0.9 + (1 – S1(L)) (1 – S2(L))*0.7]

FOC:   0.2 – S1(L)*0.4 = 0

so :

S1(L) = ½ ,   S1(R) =  1 – S1(L) = ½

  • These two strategies coincide in an equilibrium
  • This can be verified for arbitrary 2×2 games.

.

(1) from Minimax Theorem, Matthew Jackson and oav Shoham. Game Theory. Stanford University.

(2) Matching pennies from the Wikipedia.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: