research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleEfficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
Bibtex cite IDRACTI-RU1-2007-38
Booktitle 34th International Colloquium on Automata, Languages and Programming (ICALP'07), track A
Year published 2007
Month July
Pages 595-606
Publisher Springer - Verlag Berlin Heidelberg 2007
Organization ICALP 2007
Location Wrocław - Poland
Keywords Bimatrix Games,Well Supported Approximate Equilibria.
In this work we study the tractability of well supported approximate Nash Equilibria (SuppNE in short) in bimatrix games. In view of the apparent intractability of constructing Nash Equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is of great importance. We initially prove that SuppNE are immune to the addition of arbitrary real vectors to the rows (columns) of the row (column) player˘s payoff matrix. Consequently we propose a polynomial time algorithm (based on linear programming) that constructs a 0.5−SuppNE for arbitrary win lose games. We then parameterize our technique for win lose games, in order to apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique leads to a weaker ö−SuppNE for win lose games, where ö = √5−1 2 is the golden ratio. Nevertheless, this parameterized technique extends nicely to a technique for arbitrary [0, 1]−bimatrix games, which assures a 0.658−SuppNE in polynomial time. To our knowledge, these are the first polynomial time algorithms providing å−SuppNE of normalized or win lose bimatrix games, for some nontrivial constant å ∈ [0, 1), bounded away from 1.
Kontogiannis, Spyros
Spirakis, Paul
ICALP2007.pdf (main file)
Publication ID92