A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games

P.J.J. Herings; R.J.A.P. Peeters

doi:10.1007/s10479-005-2265-4

A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games

P.J.J. Herings^*, R.J.A.P. Peeters

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

108 Downloads (Pure)

Abstract

In this paper we present an algorithm to compute all nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.

Original language	English
Pages (from-to)	349-368
Journal	Annals of Operations Research
Volume	137
DOIs	https://doi.org/10.1007/s10479-005-2265-4
Publication status	Published - 1 Jan 2005

Access to Document

10.1007/s10479-005-2265-4

Full TextFinal published version, 155 KBLicence: Taverne

1 Working paper

A globally convergent algorithm to compute all nash equilibria for n-person games
Herings, P. J. J. & Peeters, R. J. A. P., 1 Jan 2002, Maastricht: METEOR, Maastricht University School of Business and Economics, 23 p. (METEOR Research Memorandum; No. 053).
Research output: Working paper / Preprint › Working paper

Open Access
File

127 Downloads (Pure)

Cite this

@article{c08844dff79d4910980ef66e5dc7f508,

title = "A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games",

abstract = "In this paper we present an algorithm to compute all nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.",

author = "P.J.J. Herings and R.J.A.P. Peeters",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/s10479-005-2265-4",

language = "English",

volume = "137",

pages = "349--368",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer",

}

TY - JOUR

T1 - A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games

AU - Herings, P.J.J.

AU - Peeters, R.J.A.P.

PY - 2005/1/1

Y1 - 2005/1/1

N2 - In this paper we present an algorithm to compute all nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.

AB - In this paper we present an algorithm to compute all nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.

U2 - 10.1007/s10479-005-2265-4

DO - 10.1007/s10479-005-2265-4

M3 - Article

SN - 0254-5330

VL - 137

SP - 349

EP - 368

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -

A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games

Abstract

Access to Document

Research output

A globally convergent algorithm to compute all nash equilibria for n-person games

Cite this