Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games

P.J.J. Herings, A.H. van den Elzen

Research output: Working paperDiscussion paperOther research output

237 Downloads (Pure)

Abstract

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. The tracing procedure plays an important role in the definition of risk-dominance for Nash equilibria. 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 strategies. By employing lexicographic pivoting techniques it can be shown that for the entire class of non-cooperative N-person games the path converges to an approximate Nash equilibrium, even when the starting point or the game is degenerate. The outcome of the algorithm is shown to be arbitrarily close to the beliefs proposed by the tracing procedure. Therefore, the algorithm does not compute just any Nash equilibrium, but one with a sound gametheoretic underpinning. 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.
Original languageEnglish
Place of PublicationTilburg
PublisherMicroeconomics
Number of pages28
Volume1998-04
Publication statusPublished - 1998

Publication series

NameCentER Discussion Paper
Volume1998-04

Fingerprint

Nash equilibrium
Homotopy
Geometry
Equilibrium selection
Risk dominance

Keywords

  • Computation of equilibria
  • Non-cooperative game theory
  • Tracing procedure

Cite this

Herings, P. J. J., & van den Elzen, A. H. (1998). Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games. (CentER Discussion Paper; Vol. 1998-04). Tilburg: Microeconomics.
Herings, P.J.J. ; van den Elzen, A.H. / Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games. Tilburg : Microeconomics, 1998. (CentER Discussion Paper).
@techreport{f30f7bfb49754851ac390e78d8cb288c,
title = "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games",
abstract = "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. The tracing procedure plays an important role in the definition of risk-dominance for Nash equilibria. 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 strategies. By employing lexicographic pivoting techniques it can be shown that for the entire class of non-cooperative N-person games the path converges to an approximate Nash equilibrium, even when the starting point or the game is degenerate. The outcome of the algorithm is shown to be arbitrarily close to the beliefs proposed by the tracing procedure. Therefore, the algorithm does not compute just any Nash equilibrium, but one with a sound gametheoretic underpinning. 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.",
keywords = "Computation of equilibria, Non-cooperative game theory, Tracing procedure",
author = "P.J.J. Herings and {van den Elzen}, A.H.",
note = "Pagination: 28",
year = "1998",
language = "English",
volume = "1998-04",
series = "CentER Discussion Paper",
publisher = "Microeconomics",
type = "WorkingPaper",
institution = "Microeconomics",

}

Herings, PJJ & van den Elzen, AH 1998 'Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games' CentER Discussion Paper, vol. 1998-04, Microeconomics, Tilburg.

Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games. / Herings, P.J.J.; van den Elzen, A.H.

Tilburg : Microeconomics, 1998. (CentER Discussion Paper; Vol. 1998-04).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games

AU - Herings, P.J.J.

AU - van den Elzen, A.H.

N1 - Pagination: 28

PY - 1998

Y1 - 1998

N2 - 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. The tracing procedure plays an important role in the definition of risk-dominance for Nash equilibria. 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 strategies. By employing lexicographic pivoting techniques it can be shown that for the entire class of non-cooperative N-person games the path converges to an approximate Nash equilibrium, even when the starting point or the game is degenerate. The outcome of the algorithm is shown to be arbitrarily close to the beliefs proposed by the tracing procedure. Therefore, the algorithm does not compute just any Nash equilibrium, but one with a sound gametheoretic underpinning. 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.

AB - 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. The tracing procedure plays an important role in the definition of risk-dominance for Nash equilibria. 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 strategies. By employing lexicographic pivoting techniques it can be shown that for the entire class of non-cooperative N-person games the path converges to an approximate Nash equilibrium, even when the starting point or the game is degenerate. The outcome of the algorithm is shown to be arbitrarily close to the beliefs proposed by the tracing procedure. Therefore, the algorithm does not compute just any Nash equilibrium, but one with a sound gametheoretic underpinning. 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.

KW - Computation of equilibria

KW - Non-cooperative game theory

KW - Tracing procedure

M3 - Discussion paper

VL - 1998-04

T3 - CentER Discussion Paper

BT - Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games

PB - Microeconomics

CY - Tilburg

ER -

Herings PJJ, van den Elzen AH. Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games. Tilburg: Microeconomics. 1998. (CentER Discussion Paper).