Complexity of Constant Player Potential Game

Speaker: 

Time: 

Friday, 30 November 2018, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

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.