Numerical Tracking of the Tracing Procedure for Non-cooperative N-person games

P. J. J. Herings and Antoon van den Eizen - Tilburg University

Harsanyi and Selten (1988) have proposed a theory of equilibrium selection that selects a unique Nash equilibrium for any non-cooperative $ N $-person game. The heart of their theory is given by the tracing procedure, a mathematical construction that adjusts arbitrary prior beliefs into equilibrium beliefs. Although the term "procedure" suggests a numerical approach, the tracing procedure itself is a non-constructive method. In this paper we propose a homotopy algorithm that generates a path of beliefs that always converges to a Nash equilibrium and, generically in the space of all non-cooperative N-person games, is shown to be arbitrarily close to the beliefs proposed by the tracing procedure. Like other homotopy algorithms, it is easily implemented on a computer. To show our results we apply methods from the theory of simplicial algorithms and algebraic geometry. Clearly, our algorithm can be seen as an algorithm to compute Nash equilibria. When compared to other algorithms to compute Nash equilibria, an advantage of our algorithm is that it computes a Nash equilibrium that has a sound game-theoretic underpinning. It is also shown that when the prior beliefs are non-degenerate, then our algorithm finds a perfect Nash equilibrium.

Scheduled for Session 3.7 Computation And Economic Theory - II