An Optimization Approach for Approximate Nash Equilibria

DOI10.1080/15427951.2008.10129172zbMath1194.91034OpenAlexW2122497197WikidataQ29029605 ScholiaQ29029605MaRDI QIDQ3574301

Haralampos Tsaknakis, Paul G. Spirakis

Publication date: 9 July 2010

Published in: Internet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/15427951.2008.10129172

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05)

Related Items (28)

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Computing equilibria: a computational complexity perspective ⋮ Approximate well-supported Nash equilibria below two-thirds ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ On the approximation performance of fictitious play in finite games ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ 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 ⋮ A Metaheuristic Approach to Compute Pure Nash Equilibria ⋮ On the performance of approximate equilibria in congestion games ⋮ Parameterized two-player Nash equilibrium ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ Distributed methods for computing approximate equilibria ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ Lipschitz continuity and approximate equilibria ⋮ Well supported approximate equilibria in bimatrix games ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximate Nash Equilibria for Multi-player Games ⋮ A note on approximate Nash equilibria ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Lipschitz Continuity and Approximate Equilibria ⋮ New algorithms for approximate Nash equilibria in bimatrix games ⋮ Unnamed Item ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

This page was built for publication: An Optimization Approach for Approximate Nash Equilibria