Tata Institute of Fundamental Research
Complexity of Constant Player Potential Game
STCS Student Seminar
Speaker:
Vidya Sagar Sharma
Organiser:
Prerona Chatterjee
Date:
Friday, 30 Nov 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Vidya Sagar Sharma |
| Organiser: | Prerona Chatterjee |
| Date: | Friday, 30 Nov 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.