2-player 0-sum imperfect information games

rps   mmx   lp   nash   cfr  

rock paper scissors

  • play with a classmate

  • is your strategy equiprobabe ?

    • yes: why ?

    • no: what is your strategy ? how did you model your opponent ?

rps payoff matrix
two players: row, column

payoffs for row         column's strategies
                              r     p    s
                        r     0    -1    1
row's strategies        p     1     0   -1
                        s    -1     1    0

minimax

  • minimax value: the minimum, over all player/opponent strategy pairs, of the maximum the opponent can score

  • for 2-player 0-sum games (so op't score \+ player score = 0)

    • if each player plays a fixed strategy for the whole game, minimax value is easily computed

  • e.g. assume row plays equiprobable: rps each 1/3

  • assume col plays rps resp. probs y1 y2 y3

  • then expected row payoff 1/3(y2-y3) + 1/3(y1-y3) + 1/3(y2-y1) = 0

  • so row's minimax value is at least 0 (some other row strategy might do better)

  • but, by symmetry (payoff matrix is symmetric), col's expected value is 0 by playing equiprobable

  • so, for this game, row's minimax value is 0, and can be achieved by playing equiprobable

2p 0sum minimax via linear programming

- assume col knows row's strategy
- then, for this row-strat, some pure col strategy is best for col
- so row wants to pick a mixed strategy that maximizes
  the minimum score row gets, over all pure col strats
- so row wants to pick x1 x2 x3 to maximize
      min x2 - x3, (row payoff against col strat r)
          x3 - x1, ("   "      "       "   "     p)
          x1 - x2  ("   "      "       "   "     s)
- so row wants to solve the LP
                max z  st
             z <=        x2 - x3
             z <= -x1       + x3
             z <=  x1  - x2
                   x1  + x2 + x3 = 1
             x1,x2,c3 >= 0
- similarly, col wants to solve an LP that turns out to be the dual of the above
- notice that the above LP has a feasible solution and z is bounded
- so the duality theorem of LP tells us that each problem has the same solution
- we have already seen that (1/3 1/3 1/3) is the primal solution

nash equilibrium

  • wiki

  • for 2-player 0-sum games, the above LP result implies that the minimax solution (assuming each player has a fixed mixed strategy for the whole game) is the only Nash equilibrium

  • prisoner's dilemma

    • if player's trust each other, they can cooperate and do better than the minimax value

    • but this combination of strategies is not a Nash equilibrium

  • sufficient conditions

counterfactual regret