Groupe d’études et de recherche en analyse des décisions

G-2006-10

A New Sequence Form Approach for the Enumeration and Refinement of all Extreme Nash Equilibria for Extensive Form Games

, et

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).

, 20 pages

Ce cahier a été révisé en janvier 2007