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

  • Department of Computer Science
  • Teoretisk naturvidenskab
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.
Original languageEnglish
Title of host publicationProceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsShang-Teng Huang
Number of pages10
PublisherSociety for Industrial and Applied Mathematics
Publication year2008
Pages874-883
ISBN (print)978-0-898716-47-4
Publication statusPublished - 2008
EventAnnual ACM-SIAM Symposium on Discrete Algorithms. SODA '08 - San Francisco, United States
Duration: 20 Jan 200822 Jan 2008
Conference number: 19

Conference

ConferenceAnnual ACM-SIAM Symposium on Discrete Algorithms. SODA '08
Nummer19
LandUnited States
BySan Francisco
Periode20/01/200822/01/2008

See relations at Aarhus University Citationformats

ID: 6362577