8
$\begingroup$

A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's payoff is $A_{ij}$ and player 2's payoff is $A_{ji}$. It is well known that the problem of computing a symmetric Nash Equillibrium in such a game is PPAD-complete (PPAD lies between P and NP but is probably intractable).

Wilson's Oddness Theorem states that there are an odd number of symmetric Nash Equilibria in such games. This gives rise to my question. Suppose we have found two equilibria of $A$. Given these, what is the computational complexity of computing one more?

Or, more generally - given $2k$ equilibria, what is the complexity of computing another?

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
3
$\begingroup$

In a two-by-two symmetric game, there are two possible symmetric equilibria in pure strategies. Suppose we know that these are both in fact equilibria. All this tells us is that $A_{11}>A_{21}$ and $A_{22}>A_{12}$.

Then there is exactly one additional equilibrium, determined by the equation $${p\over 1-p}={A_{22}-A_{12}\over A_{11}-A_{21}}$$ which means that $p$ can take any value at all between $0$ and $1$. So at least in this case, knowing two equilibria is of absolutely no help in finding the third. (And one can easily extend this example to $n$ by $n$ games.)

(The above assumes all $A_{ij}$ are distinct but you need something like this to apply Wilson's theorem in the first place.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is a reasonable clarifying point, but I don't know why the answer was accepted because I don't understand how this answers the question. You need to know the payoffs to compute another equilibrium, but in a complexity sense is it hard or easy? $\endgroup$
    – Noah Stein
    Commented Jun 19, 2013 at 14:39
  • $\begingroup$ Noah: The question as I understood it wasn't "Is it hard or easy", but "Is it any easier than it was before I knew about the first two equilibria?". $\endgroup$
    – Steven Landsburg
    Commented Jun 19, 2013 at 14:54
  • $\begingroup$ Steven: But in what sense has that been answered? I guess "Can you compute a third equilibrium without using the payoffs?" is one interpretation of the original question, but it does not seem to me like the most natural interpretation. What if (though it would shock me) you could write a linear system in an efficient way in terms of the payoffs and the two known equilibria and solve it to find a third equilibrium? This would certainly be easier than computing an equilibrium from scratch without the side information of the two known equilibria. $\endgroup$
    – Noah Stein
    Commented Jun 19, 2013 at 15:11
  • $\begingroup$ Noah: But in this case, the two equilibria give you no information beyond what can be extracted trivially from knowing the payoffs. (That is, all they give you is the two inequalities $A_{11}>A_{21}$ and $A_{22}>A_{12}$.) So if there were an efficient linear system as you envision, then it would follow that there's such a system using only the payoffs as input. Am I missing something? $\endgroup$
    – Steven Landsburg
    Commented Jun 19, 2013 at 16:01
  • $\begingroup$ Steven: But this observation is only for the $2\times 2$ case. If I understand correctly (which I didn't before), your suggestion for the $n\times n$ case is to consider a game with two symmetric pure strategy equilibria, so knowing these doesn't give any information that you couldn't easily compute from the payoffs. I don't see any obvious way to use two such equilibria to compute a third, but maybe there is a non-obvious one? Is it known to be hard to compute a third equilibrium in games with two pure equilibria? I agree that it seems like it should be, but can you, for example ... $\endgroup$
    – Noah Stein
    Commented Jun 19, 2013 at 16:42
1
$\begingroup$

Elaborating on Steven's answer, consider the Chicken game, that is the two-by-two symmetric game where each player can either cooperate (C) or defect (D). The payoff for mutual cooperation is $R$, the one for mutual defection is $P$, and, if one player cooperates and the other defects, then the cooperator gets $S$ and the defector gets $T$. Payoffs are subject to the conditions $T>R>S>P$.

This game has always two pure Nash equilibria, $(C,D)$ and $(D,C)$, independently of the exact values of the payoffs. But the other Nash equilibrium may be any mixed strategies depending on the particular payoffs. To see this observe that the extremal situation $T=R$ (resp. $S=P$) gives rise to the two degenerate equilibria $(C,C)$ (resp. $(D,D)$).

So, again, if you are given only two Nash equilibria, there is no way to know the third one. This suggests that the problem remains PPAD complete.

Improve this answer
$\endgroup$
1
$\begingroup$

Computational complexity of knowing if more than one equilibrium exists in NP-Hard (complete)

http://www.sciencedirect.com/science/article/pii/S0899825609001973

There we look at very simple two player games called imitation games and the proofs are prety simple. Further, the payoff matrix is a symmetric. So even in that special case, knowing if another equilibrium exists is NP-Hard.

Of course, if you have found one equilibrium, then finding another is not in the class of PPAD because that other one may not exist.

Now given two, it is still not clear to me that finding a third is PPAD. I don't know of a path following algorithm that does this.

Improve this answer
$\endgroup$

You must log in to answer this question.

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