Computer Science – Data Structures and Algorithms
Scientific paper
2008-11-20
Computer Science
Data Structures and Algorithms
15 pages, 18 figures. The source code of our implementation can be found at http://allievi.sssup.it/game/index.html
Scientific paper
We present an experimental investigation of the performance of the Lemke-Howson algorithm, which is the most widely used algorithm for the computation of a Nash equilibrium for bimatrix games. Lemke-Howson algorithm is based upon a simple pivoting strategy, which corresponds to following a path whose endpoint is a Nash equilibrium. We analyze both the basic Lemke-Howson algorithm and a heuristic modification of it, which we designed to cope with the effects of a 'bad' initial choice of the pivot. Our experimental findings show that, on uniformly random games, the heuristics achieves a linear running time, while the basic Lemke-Howson algorithm runs in time roughly proportional to a polynomial of degree seven. To conduct the experiments, we have developed our own implementation of Lemke-Howson algorithm, which turns out to be significantly faster than state-of-the-art software. This allowed us to run the algorithm on a much larger set of data, and on instances of much larger size, compared with previous work.
Codenotti Bruno
Pagan Marino
Rossi Stefano de
No associations
LandOfFree
An experimental analysis of Lemke-Howson algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An experimental analysis of Lemke-Howson algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An experimental analysis of Lemke-Howson algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-667579