%0 Journal Article
%T On Perfect Nash Equilibria of Polymatrix Games
%A Slim Belhaiza
%J Game Theory
%D 2014
%R 10.1155/2014/937070
%X 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 to -player games (E. E. C. van Damme, 1983). In this paper we show that polymatrix games, which form a particular class of -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. 1. Introduction Interest for game theoretic applications has been growing in engineering, management and political sciences. A polymatrix game is a confrontation of players in a normal and noncooperative context. Polymatrix games form a particular class of -player games. A polymatrix game with players is such that player ¡¯s payoff relative to player ¡¯s decisions is independent from the remaining players¡¯ choices. Considering as the set of all players, each player controls a finite set of pure strategies with . We define . 1.1. Literature Review The Nash equilibrium concept [1] has often been presented as the most desirable solution for games. Authors like Avis and Fukuda [2] and Audet et al. [3, 4] presented computational methods to enumerate all Nash extreme points for two-player games. Some other authors like Daskalakis et al. [5] and Hazan and Krauthgamer [6] have recently studied the Nash equilibrium computation complexity problem, also for two-player games. Etessami and Yannakakis [7] studied the complexity of computing approximated Nash equilibria for three or more players finite games. Some pioneering results on polymatrix games are to be mentioned. The complementary pivoting method was used by Yanovskaya [8] to compute polymatrix game equilibria. Howson [9], Eaves [10], and Howson and Rosenthal [11] also adopted the same approach. Quintas [12] showed that the set of Nash
%U http://www.hindawi.com/journals/gt/2014/937070/