Well supported approximate equilibria in bimatrix games

DOI10.1007/s00453-008-9227-6zbMath1200.91012OpenAlexW2107285505MaRDI QIDQ973002

Spyros C. Kontogiannis, Paul G. Spirakis

Publication date: 28 May 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9227-6

zbMATH Keywords

bimatrix gameswell supported approximate Nash equilibria

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) Approximation methods and heuristics in mathematical programming (90C59) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (16)

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Approximate well-supported Nash equilibria below two-thirds ⋮ On the approximation performance of fictitious play in finite games ⋮ A note on anti-Nash equilibrium for bimatrix game ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Distributed Methods for Computing Approximate Equilibria ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ On mutual concavity and strategically-zero-sum bimatrix games ⋮ On the communication complexity of approximate Nash equilibria ⋮ Distributed methods for computing approximate equilibria ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ Lipschitz continuity and approximate equilibria ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Building a completely positive factorization ⋮ The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem

Cites Work

• Games of fixed rank: a hierarchy of bimatrix games
• New complexity results about Nash equilibria
• A note on approximate Nash equilibria
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• New algorithms for approximate Nash equilibria in bimatrix games
• Nash and correlated equilibria: Some complexity considerations
• On sparse approximations to randomized strategies and convex combinations
• On the complexity of the parity argument and other inefficient proofs of existence
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Non-cooperative games
• Reducibility among equilibrium problems
• The complexity of computing a Nash equilibrium
• Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach
• An Optimization Approach for Approximate Nash Equilibria
• Algorithms, games, and the internet
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• Equilibrium Points of Bimatrix Games
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
• Algorithms – ESA 2005
• Hard-to-Solve Bimatrix Games

This page was built for publication: Well supported approximate equilibria in bimatrix games