Abstract: It is well known that multi-player potential game is PLS-complete.We show that constant player potential game is also PLS-complete.We also show that,there exist a constant-player potential game with some initial strategy such that it can take exponential time to reach Nash-equilibrium.We also give a polynomial time algorithm to get Nash-equilibrium in the network congestion game in the case of directed acyclic graph.
