Speaker: Peter Miltersen University of Aarhus
Time: 2008-12-15 16:00-2008-12-15 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!
Abstract:
Borgs et al recently showed that approximating the minmax value of a multiplayer game in strategic form is NP-hard. We illlustrate the importance of their result by observing that this implies NP-hardness of deciding whether a given Pure Strategy Nash Equilibrium of a game in strategic form is trembling hand perfect. Tightening the result of Borgs et al., we observe that approximating the value with a precision epsilon log n digits (for any constant > 0) is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits can be done in quasi-polynomial time. We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k = 2 and there are only two possible rational payffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated with any polynomial number of digits of accuracy in time n^(O(k)). On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-Clique requires time n^(Omega(k)) then so does minmax value computation. Joint work with Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen and Troels Bjerre Soerensen.
Joint work with Shankar Bhamidi and Guy Bresler.
Short Bio:
Peter Bro Miltersen is associate professor at the computer science department at Aarhus University, Denmark, and principal investigator of the Center for Algorithmic Game Theory, funded by the Carlsberg Foundation. His main research interests are computational complexity theory and computational and algorithmic game theory.
