## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, April 04, 2013, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Antonis Thomas (University of Edinburgh)

## Pure Nash Equilibria and Treewidth

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[1]-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.

Information for students and suggested topics for student talks