Computing Nash equilibria by iterated polymatrix approximation

✍ Scribed by Srihari Govindan; Robert Wilson

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 249 KB
• Volume: 28
• Category: Article
• ISSN: 0165-1889
• DOI: 10.1016/s0165-1889(03)00108-8

✦ Synopsis

This article develops a new algorithm for computing Nash equilibria of N -player games. The algorithm approximates a game by a sequence of polymatrix games in which the players interact bilaterally. We provide su cient conditions for local convergence to an equilibrium and report computational experience. The algorithm convergences globally and rapidly on test problems, although in theory it is not failsafe because it can stall on a set of codimension 1. But it can stall only at an approximate equilibrium with index +1, thus allowing a switch to the global Newton method, which is slower but can fail only on a set of codimension 2. Thus, the algorithm can be used to obtain a fast start for the more reliable global Newton method.