0
$\begingroup$

I have an exercise which I can't solve.

Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial time algorithm to decide if such a game has a pure Nash equilibrium.

The idea seems pretty obvious, every vertex of the tree and corresponding neighbouring vertices represent a "mini" game which can be represent in normal form with size at most $2^4$. This "mini" game can decided efficiently in polynomial time.

The problem is we have $n$ such a neighbouring areas (as a number of players), therefore we need somehow iteratively going over every area and decide where we have equilibrium and if not going back to the previous neighbouring areas change actions and check the existence. On the worst case it is going to take $2^{4n}$.

But how to decide it in polynomial time?

Improve this question
$\endgroup$
3
  • $\begingroup$ Quick question, will dynamic programming solve it? Say you have solved the problem for two subtrees $T_1$ and $T_2$, with $v$ the vertex connecting $T_1$ and $T_2$, can you solve it for the subtree $T_v$ which consists of $v$ and $T_1$ and $T_2$? $\endgroup$
    – Pål GD
    Jun 4 '13 at 21:34
  • $\begingroup$ @PålGD, it seems so, but solving for $T_v$ might require additional perturbation for $T_1$ and $T_2$, but in this case space complexity becomes exponential. $\endgroup$
    – com
    Jun 5 '13 at 5:39
  • $\begingroup$ The space complexity cannot exceed the time complexity, so if space complexity really becomes exponential, then time complexity is as well and the trick doesn't work. What do you mean "might require additional perturbation"? Can you not store all necessary information in the roots of $T_1$ and $T_2$ in, say, constant space? I.e., something like at most $2^{2^4}$ bits? $\endgroup$
    – Pål GD
    Jun 5 '13 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.