Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games (Q868531)

The autors study the problem of extreme Nash equilibria in bimatrix games and in their special generalization to \(n\)-person games, called polymatrix games . The first obtained result says that such games can be expressed as parametric linear 0-1 programs. Next this is used to construct the \(E\chi\)-MIP algorithm for the complete enumeration of the extreme equilibria in bimatrix and polymatrix games. This algorithm is numeracally illustrated for 3-person polymatrix games of size \(m\times m\times m\) with \(m\) up to 13. Also, it is compared with an another EEE algorithm of Audet in computational results on randomly generated bimatrix games for sizes \(n\times n\) for \(n\) up to 14.