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

G-2007-85

Perfect and Proper Refinements of All Extreme Nash Equilibria for Bimatrix Games

, et

In previous work, bimatrix games were expressed as parametric linear mixed 0-1 programs and the MIP algorithm was proposed to enumerate all their extreme Nash equilibria. In this paper, we use a maximal cliques enumeration algorithm to enumerate all Nash maximal subsets. We use a pair of linear programs in order to identify perfect extreme equilibria and enumerate all Selten maximal subsets. We also define a 0-1 mixed quadratic program in order to identify non-proper extreme equilibria.

, 24 pages