Fast algorithms for finding proper strategies in game trees

Peter Bro Miltersen; Troels Bjerre Sørensen

Fast algorithms for finding proper strategies in game trees

Peter Bro Miltersen, Troels Bjerre Sørensen

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.

Originalsprog	Engelsk
Titel	Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Redaktører	Shang-Teng Huang
Antal sider	10
Forlag	Society for Industrial and Applied Mathematics
Publikationsdato	2008
Sider	874-883
ISBN (Trykt)	978-0-898716-47-4
Status	Udgivet - 2008
Begivenhed	Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08 - San Francisco, USA Varighed: 20 jan. 2008 → 22 jan. 2008 Konferencens nummer: 19

Konference

Konference	Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08
Nummer	19
Land/Område	USA
By	San Francisco
Periode	20/01/2008 → 22/01/2008

Citationsformater

@inproceedings{54451a50764811dcbee902004c4f4f50,

title = "Fast algorithms for finding proper strategies in game trees",

abstract = "We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.",

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

year = "2008",

language = "English",

isbn = "978-0-898716-47-4",

pages = "874--883",

editor = "Shang-Teng Huang",

booktitle = "Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics",

note = "Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08 ; Conference date: 20-01-2008 Through 22-01-2008",

}

Fast algorithms for finding proper strategies in game trees. / Miltersen, Peter Bro; Sørensen, Troels Bjerre.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. red. / Shang-Teng Huang. Society for Industrial and Applied Mathematics, 2008. s. 874-883.

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Fast algorithms for finding proper strategies in game trees

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 19

PY - 2008

Y1 - 2008

N2 - We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.

AB - We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.

M3 - Article in proceedings

SN - 978-0-898716-47-4

SP - 874

EP - 883

BT - Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Huang, Shang-Teng

PB - Society for Industrial and Applied Mathematics

T2 - Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08

Y2 - 20 January 2008 through 22 January 2008

ER -

Fast algorithms for finding proper strategies in game trees

Abstract

Konference

Fingeraftryk

Citationsformater