Game theory is often described as a branch of applied mathematics and economics. Since its creation, it has been used in various domains, such as political science or studies on animal behavior. Nash equilibria (named from John Forbes Nash) are one of the main concepts it introduced. In 1950, Nash proved that for any finite game with any number of players there is an equilibrium, a strategy that prevents each player from deviating. In 1994 he received a Nobel Prize in Economics as a reward for his work.

One of the remaining problems with Nash equilibria is the lack of efficiency of best known algorithms. In general case their worst complexity is 4^n. Those algorithms are usually old (such as Lemke-Howson algorithm, which is forty years old), and aren't likely to be improved.

However, for random games, it is possible to find equilibria with small support size with high probability, allowing the use of polynomial time algorithms. Unfortunately, games of much interest do not behave as random games...

This study will focus on those algorithms and methods and will explain their advantages and their weakness. It will also introduce a new algorithm developed in LRDE, based on a geometrical approach.

• 0745.pdf