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:Article
Entered by:
TitlePerformance evaluation of a descent algorithm for bi-matrix games
Bibtex cite IDRACTI-RU1-2008-36
Journal 4th International Workshop on Internet and Network Economics
Year published 2008
Month September
Pages 222-230
Note (WINE '08)
In this paper we present an implementation and performance evaluation of a descent algorithm that was proposed in \citetsaspi for the computation of approximate Nash equilibria of non-cooperative bi-matrix games. This algorithm, which achieves the best polynomially computable \epsilon-approximate equilibria till now, is applied here to several problem instances designed so as to avoid the existence of easy solutions. Its performance is analyzed in terms of quality of approximation and speed of convergence. The results demonstrate significantly better performance than the theoretical worst case bounds, both for the quality of approximation and for the speed of convergence. This motivates further investigation into the intrinsic characteristics of descent algorithms applied to bi-matrix games. We discuss these issues and provide some insights about possible variations and extensions of the algorithmic concept that could lead to further understanding of the complexity of computing equilibria. We also prove here a new significantly better bound on the number of loops required for convergence of the descent algorithm.
Tsaknakis, Haralampos
Spirakis, Paul
Kanoulas, Dimitrios
Performance evaluation_descent algorithm.pdf (main file)
Publication ID484