Efficient algorithmic methods for Nash equilibria computation

Authors

Antoine Leblanc

Type

techreport

Year

2007

Number

0745

Keywords

Nash equilibria TOP algorithms

Abstract

One of the remaining problems with Nash equilibria is the lack of efficiency of best known algorithms. In general case their worst complexity is $O(4^{n})$. Those algorithms are usually old, and aren't likely to be improved. This study focuses first on main algorithms and methods and explains their advantages and their weaknesses. It then introduces a new algorithm developed at the LRDE based on a geometrical approach: a TOP computing method in $d$ dimensions.