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
TitlePolynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games
Bibtex cite IDRACTI-RU1-2006-37
Booktitle 2nd international Workshop on Internet & Network Economics (WINE 2006)
Year published 2006
Month December
Pages 286-296
Location Patra, Greece
Note LNCS 4286
We focus on the problem of computing an -Nash equilibrium of a bimatrix game, when is an absolute constant. We present a simple algorithm for computing a 3 -Nash equilibrium for any bimatrix game in 4 strongly polynomial time and we next show how to extend this algorithm so as to obtain a (potentially stronger) parameterized approximation. Namely, we present an algorithm that computes a 2+ë -Nash equilibrium, 4 where ë is the minimum, among all Nash equilibria, expected payoff of either player. The suggested algorithm runs in time polynomial in the number of strategies available to the players.
Kontogiannis, Spyros
Panagopoulou, Panagiota
Spirakis, Paul
wine06.pdf (main file)
Publication ID91