Computing a quasi-perfect equilibrium of a two-player game

Peter Bro Miltersen; Troels Bjerre Sørensen

doi:10.1007/s00199-009-0440-6

Computing a quasi-perfect equilibrium of a two-player game

Peter Bro Miltersen, Troels Bjerre Sørensen

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

Abstract

Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.

Originalsprog	Engelsk
Tidsskrift	Economic Theory
Vol/bind	42
Nummer	1
Sider (fra-til)	175-192
Antal sider	18
ISSN	0938-2259
DOI	https://doi.org/10.1007/s00199-009-0440-6
Status	Udgivet - 2010

Adgang til dokumentet

10.1007/s00199-009-0440-6

Citationsformater

@article{7a02c4c0263b11dcbee902004c4f4f50,

title = "Computing a quasi-perfect equilibrium of a two-player game",

abstract = "Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.",

keywords = "Equilibrium computation, quasi-perfect equilibrium",

author = "Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

note = "From the issue entitled {"}Symposium on Computation of Nash Equilibria in Finite Games{"} ",

year = "2010",

doi = "10.1007/s00199-009-0440-6",

language = "English",

volume = "42",

pages = "175--192",

journal = "Economic Theory",

issn = "0938-2259",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Computing a quasi-perfect equilibrium of a two-player game

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - From the issue entitled "Symposium on Computation of Nash Equilibria in Finite Games"

PY - 2010

Y1 - 2010

N2 - Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.

AB - Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.

KW - Equilibrium computation

KW - quasi-perfect equilibrium

U2 - 10.1007/s00199-009-0440-6

DO - 10.1007/s00199-009-0440-6

M3 - Journal article

SN - 0938-2259

VL - 42

SP - 175

EP - 192

JO - Economic Theory

JF - Economic Theory

IS - 1

ER -

Computing a quasi-perfect equilibrium of a two-player game

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater