Premium
Computing Normal Form Perfect Equilibria for Extensive Two‐Person Games
Author(s) -
Von Stengel Bernhard,
Van Den Elzen Antoon,
Talman Dolf
Publication year - 2002
Publication title -
econometrica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 16.7
H-Index - 199
eISSN - 1468-0262
pISSN - 0012-9682
DOI - 10.1111/1468-0262.00300
Subject(s) - sequence (biology) , extensive form game , mathematics , path (computing) , game tree , sequential equilibrium , tree (set theory) , mathematical optimization , algorithm , mathematical economics , computer science , sequential game , combinatorics , game theory , equilibrium selection , repeated game , genetics , programming language , biology
This paper presents an algorithm for computing an equilibrium of an extensive two‐person game with perfect recall. The method is computationally efficient by virtue of using the sequence form, whose size is proportional to the size of the game tree. The equilibrium is traced on a piecewise linear path in the sequence form strategy space from an arbitrary starting vector. If the starting vector represents a pair of completely mixed strategies, then the equilibrium is normal form perfect. Computational experiments compare the sequence form and the reduced normal form, and show that only the sequence form is tractable for larger games.