On Perfect Nash Equilibria of Polymatrix Games. (29th September 2014)

• Record Type: Journal Article
• Authors: Belhaiza, Slim
• Other Names: Briec Walter Academic Editor.
• Is Part Of: Game theory. Volume 2014(2014)
• Publication Date: 2014-09-29
• Subjects: Game theory -- Periodicals; Game theory; Periodicals; 519.3
• DOI: 10.1155/2014/937070
• Languages: English
• ISSNs: 2314-6559

Abstract

Abstract : When confronted with multiple Nash equilibria, decision makers have to refine their choices. Among all known Nash equilibrium refinements, the perfectness concept is probably the most famous one. It is known that weakly dominated strategies of two-player games cannot be part of a perfect equilibrium. In general, this undominance property however does not extend ton -player games (E. E. C. van Damme, 1983). In this paper we show that polymatrix games, which form a particular class ofn -player games, verify the undominance property. Consequently, we prove that every perfect equilibrium of a polymatrix game is undominated and that every undominated equilibrium of a polymatrix game is perfect. This result is used to set a new characterization of perfect Nash equilibria for polymatrix games. We also prove that the set of perfect Nash equilibria of a polymatrix game is a finite union of convex polytopes. In addition, we introduce a linear programming formulation to identify perfect equilibria for polymatrix games. These results are illustrated on two small game applications. Computational experiments on randomly generated polymatrix games with different size and density are provided.