Game Theory

 

 

I. Introduction and Nash Equilibria

 

 

Def. Game Theory: The logical analysis of situations of conflict and cooperation

 

Def. Game:

1)      at least two players (individuals, companies, nations, animals, …)

2)      each player has a number of possible strategies, which they may choose to follow

3)      the strategies chosen by each player determine the outcome of the game

4)      associated to each possible outcome of the game is a collection of numerical payoffs, one to each player (each payoff represents the value of the outcome to the player)

 

  • Game Theory is the study of how players should rationally play games
  • Each player has some control over the outcomes, since their choices will influence it.
  • Games are not restricted to the normal ones, such as chess or poker (although both are great examples) they extend to

1)      Companies pursuing corporate strategies

2)      Political candidates trying to win an election

3)      Nations maneuvering in the international arena

4)      Auctions (of which there are several types)

5)      Matrix games (pure, mixed)

[Str, p 3]

Example: Prisoner’s Dilemma Game [Ali, p 42]

Strategy

Silent

Confess

Silent

(-1,-1)

(-10, 0)

Confess

(0,-10)

(-5, -5)

 

Where Player 1 has the vertical choices and Player 2, has the horizontal choices. This game is easy to see the payoff’s value to the player, since it represents the number of years they will stay in prison. The situation is that two suspects were captured and are now being questioned, separately, about the crime that they are suspected to have committed. Each one can either stay silent or confess.

 

Suppose it happens that       

P1       P2

 

P1  P2

(Silent, Silent)

then the outcomes will be

(-1, -1)

 

This is how we read such tables.

 

What should P1 do, if he knows P2 will confess?

            If he’s silent, then his payoff is -10.

            If he confesses, then his payoff is -5.

So… P1 should confess to receive the best payoff.

 

What should P1 do, if he knows P2 will stay silent?

            If he’s silent, then his payoff is -1.

            If he confesses, then his payoff is 0.

So… P1 should confess to receive the best payoff.

 

So no matter what P2 does is is always better for P1 to confess, this is called a strictly dominate strategy for Player 1.

 

What should P2 do, if he knows P1 will confess?

            If he’s silent, then his payoff is -10.

            If he confesses, then his payoff is -5.

What should P2 do, if he knows P1 will stay silent?

            If he’s silent, then his payoff is -1.

            If he confesses, then his payoff is 0.

 

Hence, P2 has a strictly dominate strategy of confessing.

 

So, both players will always confess to obtain the best outcome for themselves. Hence, the solution to the game is (-5,-5) or (confess, confess), which we found by looking at each player’s strictly dominant strategy.

 

Example. [Ali, p 40]

 

In this example Player 1 will be US Air (vertical choices), and Player 2 American Airlines (horizontal choices). What is the solution to the following game?

 

Fare

$500

$200

$500

(50, 100)

(-100, 200)

$200

(-150, -200)

(-10, -10)

 

Where the choice of action of the players is to set the fare on a round-trip flight from JFK to LAX, and the payoffs are there profits in the millions.

 

Using the method in the previous example we try to find the solution by finding each player’s strictly dominant strategy.

 

What should US Air set its fare to if American Airlines chooses $500?

            If they set it to $500, then there profit will be $50 M.

            If they set it to $200, then there profit will be $150 M.

What should US Air set its fare to if American Airlines chooses $200?

            If they set it to $500, then there profit will be -$100 M.

            If they set it to $200, then there profit will be -$10 M.

Hence, US Air’s strictly dominant strategy is to set it’s fare to $200.

 

 

What should American Airlines set its fare to if US Air chooses $500?

            If they set it to $500, then there profit will be $100 M.

            If they set it to $200, then there profit will be $200 M.

What should American Airlines set its fare to if US Air chooses $200?

            If they set it to $500, then there profit will be -$200 M.

            If they set it to $200, then there profit will be -$10 M.

So we see that American Airlines’ strictly dominant strategy is also to set the fare at $200.

 

Thus, both airlines will set their fares to $200, a similar analysis was carried out in court to prove that there was price fixing among airlines and in October 1994 some airlines settled for $40 M.

 

Def. These strategy pairs are called Nash Equilibriums, which are strategies where, given what the other player is doing, it’s optimal for a player to play the Nash Equilibrium.

 

Problem Set 1 : Find the Nash Equilibrium of

 

Strategy

L

C

R

T

(1,0)

(1,3)

(3,0)

M

(0,2)

(0,1)

(3,0)

B

(0,2)

(2,4)

(5,3)

 

 

Both methods we used to solve this game are equivalent and are called the method of iterated elimination of strictly dominant strategies. (see section VII for a discussion of the solution)

 

Question? Does every game have a unique Nash Equilibrium?

 

 

Question?  Does every matrix game (the games we have been talking about) have a Nash Equilibrium?

 

End of Problem Set 1

 

 

Def. A Zero-Sum Game is a matrix game where each of the possible payoffs sums to 0.

 

Example of a Zero-Sum Game

           

Strategy

D

E

F

A

(-1,1)

(0,0)

(2,-2)

B

(3,-3)

(1,-1)

(1,-1)

C

(0,0)

(1,-1)

(2,-2)

 

Def. A Saddle Point of a zero-sum game is the position in which the payoffs for player 1 are maximal in a column and minimal in a row.

 

Notice that in the Example game there is a saddle point at the position (B, E), one can check that a Zero-Sum game has a NE at a position if and only if that position is a saddle point.

 

Problem Set 2 : Find the NE of this game, by find its saddle point(s).

 

These are the payoffs for Player 1.

 

-4

0

3

4

-6

1

2

3

-3

0

-1

-2

 

End of Problem Set 2

 

 

References and Further Reading:

1.C. D. Aliprantis, and S. K. Chakrabarti, Games and Decision Making, Oxford    

   University Press, New York, 2000.

2. P. Straffin, Game Theory and Strategy, The Mathematical Association of America, DC,

   1993.