Pure Nash Equilibria in Graphical Games and Treewidth
OPEN ACCESS
Loading...
Author / Producer
Date
2015-03
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be ππ-complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is π[1]-Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in πβ(πΌπ€) time, where πΌ is the cardinality of the largest strategy set and π€ is the treewidth of the input graph (and πβ hides polynomial factors). This proves that PNE-GG is in πΉππ for the combined parameter (πΌ,π€). Moreover, we prove that there is no algorithm that solves PNE-GG in πβ((πΌβπ)π€) time for any π>0, unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that πΌβ₯3; we show that for πΌ=2 the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of π(logπ) treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
71 (3)
Pages / Article No.
581 - 604
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Nash equilibria; Graphical games; Parameterized complexity; Treewidth
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.