Enumeration of all extreme equilibria of bimatrix games -- Web of Science 5.0

Easy Search Results--Full Record

Article 4 of 40

Explanation

Enumeration of all extreme equilibria of bimatrix games
Audet C, Hansen P, Jaumard B, Savard G
SIAM JOURNAL ON SCIENTIFIC COMPUTING 23 (1): 323-338 JUN 27 2001

Document type: Article

Language: English

Cited References: 24

Times Cited: 0

Abstract:
The set of equilibrium points of a bimatrix game is the union of polytopes that are not necessarily disjoint. Knowledge of the vertices of these polytopes ( extreme equilibria) is sufficient to identify all equilibria. We present an algorithm that enumerates all extreme equilibria by exploiting complementary slackness optimality conditions of two pairs of parameterized linear programming problems. The algorithm is applied to randomly generated problems of size up to 29 x 29 when both dimensions are equal, and up to 700 x 5 when the second dimension is fixed. The number of extreme equilibria grows exponentially with problem size but remains moderate for the instances considered. Therefore, the results could be useful for further study of refinements of Nash equilibria.

Author Keywords:
bimatrix game, extreme equilibrium, implicit enumeration, two-person nonzero-sum game

Addresses:
Audet C, Ecole Polytech, Dept Math & Genie Ind, CP 6079,Succursale Ctr Ville, Montreal, PQ H3C 3A7, Canada
Ecole Polytech, Dept Math & Genie Ind, Montreal, PQ H3C 3A7, Canada
Rice Univ, Houston, TX 77251 USA
Ecole Hautes Etud Commerciales, Montreal, PQ H3T 2A7, Canada
GERAD, Montreal, PQ H3T 2A7, Canada
GERAD, Dept Math & Genie Ind, Montreal, PQ H3C 3A7, Canada

Publisher:
SIAM PUBLICATIONS, PHILADELPHIA

IDS Number:
451NG

ISSN:
1064-8275

Article 4 of 40

Acceptable Use Policy