On the complexity of constrained Nash equilibria in graphical games

DOI10.1016/j.tcs.2009.05.030zbMath1173.91324OpenAlexW2019713702MaRDI QIDQ837182

Gianluigi Greco, Francesco Scarcello

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.030

zbMATH Keywords

computational complexitygame theoryNash equilibriatreewidthgraphical games

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Other game-theoretic models (91A40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Pure Nash equilibria in graphical games and treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure and complexity of worst-case equilibria
• New complexity results about Nash equilibria
• Tree-size bounded alternation
• Nash and correlated equilibria: Some complexity considerations
• On the complexity of the parity argument and other inefficient proofs of existence
• A comparison of structural CSP decomposition methods
• Approximate equilibria and ball fusion
• Potential games
• The complexity of selecting maximal solutions
• A class of games possessing pure-strategy Nash equilibria
• Structure and complexity of extreme Nash equilibria
• Non-cooperative games
• Reducibility among equilibrium problems
• The complexity of computing a Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• On the Desirability of Acyclic Database Schemes
• On the Complexity of Nash Equilibria and Other Fixed Points
• The complexity of acyclic conjunctive queries
• The complexity of pure Nash equilibria
• Graph minors. II. Algorithmic aspects of tree-width
• The price of selfish routing
• Mathematical Foundations of Computer Science 2005
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• LATIN 2004: Theoretical Informatics
• Computing LOGCFL certificates