Abstract | ||
---|---|---|
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports that are small and balanced, and employ a backtracking procedure to efficiently explore these supports. Making use of a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art - the Lemke-Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan-Wilson for n-player games. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.geb.2006.03.015 | Games and Economic Behavior |
Keywords | Field | DocType |
normal-form game,2-player game,nash equilibrium,sample nash equilibrium,lemke-howson algorithm,player game,simple search method,n-player game,algorithms,computer science,simplicial subdivision,normal form game | Combinatorial game theory,Mathematical optimization,Epsilon-equilibrium,Computer science,Best response,Repeated game,Equilibrium selection,Game theory,Nash equilibrium,Bayesian game | Conference |
Volume | Issue | ISSN |
63 | 2 | 0899-8256 |
ISBN | Citations | PageRank |
0-262-51183-5 | 95 | 7.66 |
References | Authors | |
12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ryan Porter | 1 | 238 | 21.45 |
Eugene Nudelman | 2 | 503 | 30.09 |
Yoav Shoham | 3 | 5530 | 764.00 |