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

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

## Charles Audet, Slim Belhaiza et Pierre Hansen

In previous work, bimatrix games were expressed as parametric linear mixed 0-1 programs and the ${\rm E}_\chi$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