G-2006-10
A New Sequence Form Approach for the Enumeration and Refinement of all Extreme Nash Equilibria for Extensive Form Games
Charles Audet, Slim Belhaiza, and Pierre Hansen
This paper presents two new results on the enumeration of all extreme equilibria of
the sequence form of a two person extensive game. The sequential form of an extensive
game is expressed, for the first time to our knowledge, as a parametric linear 0 − 1
program. Considering Ext(P) as the set of all of the sequential form extreme Nash
equilibria and Ext(Q) as the set of all the parametric linear 0 − 1 program extreme
points, we show that Ext(P) ⊆ Ext(Q). Using exact arithmetics classes, the algorithm
[3,1] is extended to enumerate all elements of Ext(Q). A small procedure is
then applied in order to obtain all elements of Ext(P).
Published February 2006 , 20 pages
This cahier was revised in January 2007