1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jul 14, 2016 at 22:21
  • $\begingroup$ 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. $\endgroup$
    – Auberon
    Jul 14, 2016 at 22:39
  • $\begingroup$ 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/… $\endgroup$ Jul 15, 2016 at 7:34
  • $\begingroup$ Very interesting indeed $\endgroup$
    – Auberon
    Jul 15, 2016 at 8:41

2 Answers 2

1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .