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
References
[1]
J. F. Nash, “Equilibrium points in -person games,” Proceedings of the National Academy of Sciences of the United States of America, vol. 36, pp. 48–49, 1950.
[2]
D. Avis and K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,” Discrete & Computational Geometry, vol. 8, no. 1, pp. 295–313, 1992.
[3]
C. Audet, P. Hansen, B. Jaumard, and G. Savard, “Enumeration of all extreme equilibria of bimatrix games,” SIAM Journal on Scientific Computing, vol. 23, no. 1, pp. 323–338, 2001.
[4]
C. Audet, S. Belhaiza, and P. Hansen, “Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games,” Journal of Optimization Theory and Applications, vol. 129, no. 3, pp. 349–372, 2006.
[5]
C. Daskalakis, P. Goldberg, and C. Papadimitriou, “The complexity of computing a Nash equilibrium,” SIAM Journal on Computing, vol. 39, no. 1, pp. 195–259, 2009.
[6]
E. Hazan and R. Krauthgamer, “How hard is it to approximate the best Nash equilibrium?” SIAM Journal on Computing, vol. 40, no. 1, pp. 79–91, 2011.
[7]
K. Etessami and M. Yannakakis, “On the complexity of Nash equilibria and other fixed points,” SIAM Journal on Computing, vol. 39, no. 6, pp. 2531–2597, 2010.
[8]
E. B. Yanovskaya, “Equilibrium points in polymatrix games,” Latvian Mathematical Collection, vol. 8, pp. 381–384, 1968.
[9]
J. T. Howson, “Equilibria of polymatrix games,” Management Science, vol. 18, pp. 312–318, 1972.
[10]
B. C. Eaves, “Polymatrix games with joint constraints,” SIAM Journal on Applied Mathematics, vol. 24, pp. 418–423, 1973.
[11]
J. T. Howson and R. W. Rosenthal, “Bayesian equilibria of finite two-person games with incomplete information,” Management Science, vol. 21, no. 3, pp. 313–315, 1974.
[12]
L. G. Quintas, “A note on polymatrix games,” International Journal of Game Theory, vol. 18, no. 3, pp. 261–272, 1989.
[13]
D. A. Miller and S. W. Zucker, “Copositive-plus Lemke algorithm solves polymatrix games,” Operations Research Letters, vol. 10, no. 5, pp. 285–290, 1991.
[14]
C. E. Lemke, “Bimatrix equilibrium points and mathematical programming,” Management Science, vol. 11, pp. 681–689, 1965.
[15]
R. Wilson, “Computing equilibria of -person games,” SIAM Journal on Applied Mathematics, vol. 21, pp. 80–87, 1971.
[16]
C. E. Lemke and J. T. Howson, “Equilibrium points of bimatrix games,” SIAM Journal on Applied Mathematics, vol. 12, pp. 413–423, 1964.
[17]
S. Govindan and R. Wilson, “Computing Nash equilibria by iterated polymatrix approximation,” Journal of Economic Dynamics & Control, vol. 28, no. 7, pp. 1229–1241, 2004.
[18]
C. H. Papadimitriou and T. Roughgarden, “Computing correlated equilibria in multi-player games,” Journal of the ACM, vol. 55, no. 3, article 14, 2008.
[19]
R. Selten, “Reexamination of the perfectness concept for equilibrium points in extensive games,” International Journal of Game Theory, vol. 4, no. 1, pp. 25–55, 1975.
[20]
R. B. Myerson, Game Theory: Analysis of Conict, Harvard University Press, Cambridge, Mass, USA, 1997.
[21]
I. Topolyan, “Existence of perfect equilibria: a direct proof,” Economic Theory, vol. 53, no. 3, pp. 697–705, 2013.
[22]
P. E. M. Borm, M. J. M. Jansen, J. A. M. Potters, and S. J. Tijs, “On the structure of the set of perfect equilibria in bimatrix games,” Operations-Research-Spektrum, vol. 15, no. 1, pp. 17–20, 1993.
[23]
J.-F. Laslier and K. van der Straeten, “Electoral competition under imperfect information,” Economic Theory, vol. 24, no. 2, pp. 419–446, 2004.
[24]
T. Watanabe and T. Yamato, “A choice of auction format in seller cheating: a signaling game analysis,” Economic Theory, vol. 36, no. 1, pp. 57–80, 2008.
[25]
P. B. Miltersen and T. B. S？rensen, “Computing a quasi-perfect equilibrium of a two-player game,” Economic Theory, vol. 42, no. 1, pp. 175–192, 2010.
[26]
S. Belhaiza, C. Audet, and P. Hansen, “A note on bimatrix game maximal Selten subsets,” Arabian Journal of Mathematics, vol. 3, no. 3, pp. 299–311, 2014.
[27]
E. E. C. van Damme, Refinements of the Nash Equilibrium Concept, Springer, Berlin, Germany, 1983.
[28]
C. Audet, S. Belhaiza, and P. Hansen, “A new sequence form approach for the enumeration and refinement of all extreme Nash equilibria for extensive form games,” International Game Theory Review, vol. 11, no. 4, pp. 437–451, 2009.
[29]
G. Fandel and J. Trockel, “Avoiding non-optimal management decisions by applying a three-person inspection game,” European Journal of Operational Research, vol. 226, no. 1, pp. 85–93, 2013.
[30]
G. B. Dantzig, “Maximization of a linear function of variables subject to linear inequalities,” in Activity Analysis of Production and Allocation, T. C. Koopmans, Ed., chapter 21, pp. 359–373, John Wiley & Sons, New York, NY, USA, 1951.
