# Iterated Best Response to find Pure Nash Equilibria

The context of this question is Game Theory.

I've been trying to apply a simplified (?) version of the Iterated Best Response (IBR) technique to find Pure Nash Equilibria (PNE) in games generated by GAMUT.

In each iteration, a random player changes his action to the best action that is the best response to the other players their action. This is repeated untill a PNE is reached.

I found that the algorithm found PNE in Congestion Games very fast.

I was wondering if there are games that are certain to have PNE but in which the technique described above will not work/be slow (e.g. because the algorithm will cycle)?

The reason of the question: I'm trying to apply metaheuristic techniques to find PNE but I'm uncertain if this is interesting because of IBR.

• What kind of games are you working on? For finite normal-form games (and looking for mixed or pure equilibria) there's actually a quite beautiful algorithm that relies on a famous geometric 'structure theorem' that tells you what the set of all Nash equilibria of all games with a given player/action set looks like, and uses that structure to construct a dynamical system that converges to the equilibria of the game of interest. You might find it interesting depending upon your background. Jul 14, 2016 at 22:21
• At the time I posted this question, I was exploring the computational complexity of computing Pure Nash Equilibria and state-of-the-art algorithms to find them. This resulted in an article I wrote on applying metaheuristic techniques to compute (approximate) PNE in (normal form games) which is being published soon. I'm interested in any game that has interesting computational complexity for finding equilibria. That being said, in the past few months, I gained insight and am now able to answer my own question. Jul 14, 2016 at 22:39
• Neat. On the off-chance you haven't stumbled across it yet, you should check this out, you might find it interesting: faculty-gsb.stanford.edu/wilson/PDF/Game%20Theory/… Jul 15, 2016 at 7:34
• Very interesting indeed Jul 15, 2016 at 8:41

However, this game doesn't have a pure strategy equilibrium. To rectify this just 'purify' it though: consider a game whose pure strategies correspond to probability distributions over the two actions $\{Heads, Tails\}$. In this case, the best reply to any non-equilibrium strategy is to play a degenerate distribution, hence starting from any non-equilibrium strategy best-response dynamics never converge!