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.
Sure, there are such games. Consider a matrix game that only has a mixed-strategy equilibrium (e.g., matching pennies). Extend it by a choice that always yields a worse outcome, unless everybody chooses it, when it will give the highest payoff. This is then a (the only) pure-strategy equilibrium. However, your IBR version will never reach it (unless it starts super-close). Indeed, it will cycle.