Group for Research in Decision Analysis

# 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 $\mbox{E}_\chi\mbox{MIP}$ [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).

, 20 pages

This cahier was revised in January 2007