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
TitleWell Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach
Bibtex cite IDRACTI-RU1-2008-70
Year published 2008
Month September
Publisher Springer Science+Business Media
Keywords Bimatrix games ∑ Well supported approximate Nash equilibria
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 an important challenge. In this work we study the tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short). Roughly speaking, while the typical notion of approximate NE demands that each player gets a payoff at least an additive term less than the best possible payoff, in a SuppNE each player is assumed to adopt with positive probability only approximate pure best responses to the opponentĘs strategy. As a first step, we demonstrate the existence of SuppNE with small supports and at the same time good quality. This is a simple corollary of AlthöferĘs Approximation Lemma, and implies a subexponential time algorithm for constructing SuppNE of arbitrary (constant) precision. We then propose algorithms for constructing SuppNE in win lose and normalized bimatrix games (i.e., whose payoff matrices take values from 0, 1 and [0, 1] respectively). Our methodology for attacking the problem is based on the solvability of zero sum bimatrix games (via its connection to linear programming) and provides a 0.5-SuppNE for win lose games and a 0.667-SuppNE for normalized games. To our knowledge, this paper provides the first polynomial time algorithms constructing å-SuppNE for normalized or win lose bimatrix games, for any nontrivial constant 0 ≤å <1, bounded away from 1.
Kontogiannis, Spyros
Spirakis, Paul
KS08_AlgorithmicaVersion.pdf (main file)
Publication ID531