Simple search methods for finding a Nash equilibrium

• 成果类型: Article; Proceedings Paper
• 署名作者: Porter, Ryan; Nudelman, Eugene; Shoham, Yoav
• 署名单位: Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2006.03.015
• 发表日期: 2008
• 页码: 642-662
• 关键词: Nash equilibrium; computer science; algorithms

摘要

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. (C) 2006 Elsevier Inc. All rights reserved.