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-2007-39
Booktitle 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2007)
Year published 2007
Month August
Pages 596-608
Location Cesky Krumlov--Czech Republic
We study the existence and tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short).We prove existence of "−SuppNE for any constant " 2 (0, 1), with only logarithmic support sizes for both players. Also we propose a polynomial–time construction of SuppNE, both for win lose and for arbitrary (normalized) bimatrix games. The quality of these SuppNE depends on the girth of the Nash Dynamics graph in the win lose game, or a (rounded–off) win lose image of the original normalized game. Our constructions are very successful in sparse win lose games (ie, having a constant number of (0, 1)−elements in the bimatrix) with large girth in the Nash Dynamics graph. The same holds also for normalized games whose win lose image is sparse with large girth. Finally we prove the simplicity of constructing SuppNE both in random normalized games and in random win lose games. In the former case we prove that the uniform full mix is an o(1)−SuppNE, while in the case of win lose games, we show that (with high probability) there is either a PNE or a 0.5-SuppNE with support sizes only 2.
Kontogiannis, Spyros
Spirakis, Paul
mfcs-paper020-main.pdf (main file)
Publication ID93