Fictitious play

Fictitious play is a very simple iterative procedure for finding a Nash equilibrium of a game. Before stating an open problem of interest, let me give a quick summary of how it works (or, you can read the Wikipedia page for a more careful description). It's an iterative process that if it converges, must converge to a Nash equilibrium, but unfortunately it doesn't always converge. However it always works for 2-player zero-sum games, more on that below.

Assume you have a 2-player game. To begin with, each player chooses a single pure strategy. Then, both players construct sequences of strategies according to the following rule: At each step, a player considers the sequence chosen by the other player, he supposes that the other player will randomize uniformly over that sequence, and he chooses a best response to that mixed strategy. (So, a player's sequence is treated as a multiset of strategies, one of which is selected uniformly at random.) Technically, we should explain how to choose a best response in the event of a tie (2 equally good responses) - there are various options, but I won't discuss them. Anyway, the chosen best-response is added to a player's sequence, and that's how the sequences get extended.

I have recently been pestering various people with the following question: What is the complexity of the following problem:

input: a bimatrix game. For each player, an initial pure strategy.

question: does FP converge when those initial strategies are chosen at the start?

Additional question: If it converges, give the NE that it converges to.

(and just to be clear, this is not the same thing as asking about the complexity of FP itself.)

I recently read one of the early papers on the topic, namely: Robinson, J. (1951) "An Iterative Method of Solving a Game", Annals of Mathematics 54, 296-301. It is a beautiful paper, just 6 pages; I would recommend anyone to read it. It proves the result mentioned above, that for any zero-sum game, the payoffs obtained by the players do indeed converge to the value of the game. (The convergence rate that is implicitly obtained is very slow - maybe it can be improved?) Note, that is not the same thing as showing that the players play the correct strategies after any given number of iterations - a new paper in SAGT (Felix Brandt, Felix Fischer and Paul Harrenstein "On the Rate of Convergence of Fictitious Play") indicates it may take arbitrarily long to find the right strategies, depending on the payoff values.

Another nice question follows up on a paper by Vince Conitzer "Approximation guarantees for fictitious play" (Allerton 09). This paper studies the quality of approximate equilibria obtained by FP, in a scenario where the number of iterations is less than the number of pure strategies per player. But, if it's applied to a n×n game, and allowed to run for more than n iterations, for all we know it may actually do better than the best currently-known polynomial-time approximation algorithms (that obtain round about 1/3-approximation, if all payoffs are in [0,1].) Although, I will pessimistically guess that some troublesome games that haven't yet been identified, have it obtaining just a 1/2-approximation.