Efficient algorithmic methods for Nash equilibria computation

From LRDE

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } dimensions.