Parameterized two-player Nash equilibrium
From MaRDI portal
Publication:1949741
DOI10.1007/s00453-011-9609-zzbMath1272.68142arXiv1006.2063OpenAlexW2098199921MaRDI QIDQ1949741
Danny Hermelin, Stefan Kratsch, Magnus Wahlström, Chien-Chung Huang
Publication date: 16 May 2013
Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1006.2063
algorithmsNash equilibriumparameterized complexitytwo-player gamesgraph-theoretic toolsgraph-theoretic representation of a bimatrix game
2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
The Linear Complementarity Problems with a Few Variables per Constraint ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ Parameterized two-player Nash equilibrium ⋮ Confronting intractability via parameters ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
Cites Work
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Games of fixed rank: a hierarchy of bimatrix games
- A note on approximate Nash equilibria
- On problems without polynomial kernels
- New algorithms for approximate Nash equilibria in bimatrix games
- Nash and correlated equilibria: Some complexity considerations
- Parameterized two-player Nash equilibrium
- Tight lower bounds for certain parameterized NP-hard problems
- Reducibility among equilibrium problems
- Single Parameter FPT-Algorithms for Non-trivial Games
- Algorithms for Playing Games with Limited Randomness
- An Optimization Approach for Approximate Nash Equilibria
- Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses
- Subgraph Isomorphism in Planar Graphs and Related Problems
- On oblivious PTAS's for nash equilibrium
- Algorithms, games, and the internet
- A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
- Algorithmic Game Theory
- Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
- Algorithms – ESA 2005
