School of Technology and Computer Science Seminars

Complexity of Constant Player Potential Game

by Vidya Sagar Sharma (STCS, TIFR)

Friday, November 30, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.
Organised by Prerona Chatterjee