3
$\begingroup$

Suppose you and I are playing a two-player zero-sum game repeatedly. There is a payoff matrix $(A_{ij})$, and if I play action $i$ and you play action $j$ then I receive $A_{ij}$ and you receive $-A_{ij}$. I am not clever enough to compute my best strategy (my maximin strategy), but I can just manage to compute a best response to your mixed strategy, if you were to publicize it. Similarly you. We decide that at each turn (i.e., repetition of the game) we will just play a best response to our opponent's apparent strategy so far. To be more specific we each do the following:

  • Turn $1$: Play something. Who cares. It's only one turn.
  • Turn $n$: Play a best response assuming that the opponent will simply pick one of turns $1,\dots,n-1$ uniformly at random and replay that action.

This is an attractive rough and ready way to try to solve a two-player game when tackling the linear program head-on is difficult. But is it any good? That is, do our strategies converge to our respective maximin strategies? Williams's Compleat Strategyst says it works, but unfortunately it's not the sort of book that gives references.

For example, if we were playing rock-paper-scissors, the play might go as follows:

  • rock, rock (we both start arbitrarily)
  • paper, paper (paper is the best response to rock)
  • paper, paper (paper is the best response to 1/2 rock, 1/2 paper)
  • scissors, scissors (scissors is the best response to 1/3 rock, 2/3 paper)
  • etc.

Clearly play is always symmetric here and we always draw, but that is not important (and wouldn't be true if we started with different actions). The only thing I care about is whether our distribution of actions converges to 1/3 rock, 1/3 paper, 1/3 scissors (the optimal strategy), and how fast.

$\endgroup$
3
  • $\begingroup$ Can you give more details? What exactly is your definition of a game? What is a turn? What are the winning conditions? What is the pay-off? In its current state you can easily construct a 'game' in which this approach will fall flat. Simply let a given player lose if he follows your proposed strategy. $\endgroup$ Jan 2, 2017 at 11:38
  • 1
    $\begingroup$ @Stefan The game is an arbitrary zero-sum two-player game with an arbitrary payoff. The turns are repetitions of the game. We are trying to find our maximin strategies, i.e., the Nash equilibrium. I added some more words to try to make this clear. $\endgroup$ Jan 2, 2017 at 12:22
  • $\begingroup$ I see. Your kind of games look pretty different from the ones I had in mind. Thanks for your clarifications. $\endgroup$ Jan 2, 2017 at 13:13

1 Answer 1

1
$\begingroup$

The keywords I was looking for were "fictitious play" and "Brown--Robinson process". The short answer seems to be that it works, sometimes. For more information see https://en.wikipedia.org/wiki/Fictitious_play.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.