TU Berlin

Talk 29.06.2011

isti-logo

Page Content

to Navigation

Parameterized Two-Player Nash Equilibrium

Danny Hermelin (Max-Planck-Institut für Informatik)
We study the problem of computing Nash equilibria in a two-player normal form game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. These cases occur in the previously studied settings of sparse games and unbalanced games as well as in the newly considered case of locally bounded treewidth games that generalizes both these two cases.

date
speaker
location
language
29.06.2011 14:15
Danny Hermelin

FR 6510
english


Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe