Aarhus University Seal / Aarhus Universitets segl

Fast algorithms for finding proper strategies in game trees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

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. ed. / Shang-Teng Huang. Society for Industrial and Applied Mathematics, 2008. p. 874-883.

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Miltersen, PB & Sørensen, TB 2008, Fast algorithms for finding proper strategies in game trees. in S-T Huang (ed.), Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 874-883, Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08, San Francisco, United States, 20/01/2008.

APA

Miltersen, P. B., & Sørensen, T. B. (2008). Fast algorithms for finding proper strategies in game trees. In S-T. Huang (Ed.), Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 874-883). Society for Industrial and Applied Mathematics.

CBE

Miltersen PB, Sørensen TB. 2008. Fast algorithms for finding proper strategies in game trees. Huang S-T, editor. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 874-883.

MLA

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

Vancouver

Miltersen PB, Sørensen TB. Fast algorithms for finding proper strategies in game trees. In Huang S-T, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2008. p. 874-883

Author

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

Bibtex

@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 = "null ; Conference date: 20-01-2008 Through 22-01-2008",

}

RIS

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

Y2 - 20 January 2008 through 22 January 2008

ER -