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.

Yes, there are many such games. Generally, one of the appeals of supermodular games (see, for example, here) is that the set of pure-strategy Nash equilibria has a formal order structure to it, and moreover, iterated best response dynamics are guaranteed to converge to an equilibrium. This is very much not guaranteed for arbitrary games.

Keep These Mind gave an example of when best-reply dynamics do not converge:

![enter image description here](

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!