Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 04, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Antonis Thomas (University of Edinburgh)
We consider the complexity of w-PNE-GG, the problem of computing pure Nash equilibria in graphical games parameterized by the treewidth w of the underlying graph. It is well-known that the problem of computing such equilibria is NP-hard in general, but solvable in polynomial time when restricted to games of bounded treewidth. We prove that w-PNE-GG is W-hard and thus a fixed-parameter algorithm is unlikely.
Furthermore, we describe a dynamic programming algorithm for w-PNE-GG. In contrast to the previous algorithms that rely on reductions to other problems, our algorithm treats directly the problem at hand. We show that w-PNE-GG is fixed-parameter tractable when the strategy sets have bounded cardinality.
Automatic MiSe System Software Version 1.4803M | admin login