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?