Potential Games

GAMES AND ECONOMIC BEHAVIOR 14, 124–143 (1996) ARTICLE NO. 0044 Potential Games Dov Monderer⁄ Faculty of Industrial Engineering and Management, The Technion, Haifa 32000, Israel and Lloyd S. Shapley Department of Economics and Department of Mathematics, University of California, Los Angeles, California 90024 Received January 19, 1994 We define and discuss several notions of potential functions for games in strategic form. We characterize games that have a potential function, and we present a variety of applica- tions. Journal of Economic Literature Classification Numbers: C72, C73. © 1996 Academic Press, Inc. 1. INTRODUCTION Consider a symmetric oligopoly Cournot competition with linear cost func- tions ci .qi / D cqi , 1 • i • n. The inverse demand function, F.Q/, Q > 0, is a positive function (no monotonicity, continuity, or differentiability assumptions on F are needed). The profit function of Firm i is defined on RnCC as 5i .q1; q2; : : : ; qn/ D F.Q/qi ¡ cqi ; where Q DPnjD1 qj . Define a function P: RnCC ¡! R: P.q1; q2; : : : ; qn/ D q1q2 ¢ ¢ ¢ qn.F.Q/¡ c/: For every Firm i , and for every q¡i 2 Rn¡1CC , 5i .qi ; q¡i /¡5i .xi ; q¡i / > 0; iff P.qi ; q¡i /¡ P.xi ; q¡i / > 0; 8qi ; xi 2 RCC: (1.1) ⁄ First version: December 1988. Financial support from the Fund for the Promotion of Research at the Technion is gratefully acknowledged by the first author. E-mail: dov@techunix.technion.ac.il. 124 0899-8256/96 $18.00 Copyright © 1996 by Academic Press, Inc. All rights of reproduction in any form reserved. POTENTIAL GAMES 125 A function P satisfying (1.1) is called an ordinal potential, and a game that pos- sesses an ordinal potential is called an ordinal potential game. Clearly, the pure- strategy equilibrium set of the Cournot game coincides with the pure-strategy equilibrium set of the game in which every firm’s profit is given by P . A condition stronger than (1.1) is required if we are interested in mixed strategies. Consider a quasi-Cournot competition1 with a linear inverse demand function F.Q/ D a ¡ bQ, a; b > 0, and arbitrary differentiable cost functions ci .qi /, 1 • i • n. Define a function P⁄..q1; q2; : : : ; qn// as P⁄..q1; q2; : : : ; qn// D a nX jD1 qj ¡ b nX jD1 q2j ¡ b X 1•i< j•n qi qj ¡ nX jD1 cj .qj /: (1.2) It can be verified that For every Firm i , and for every q¡i 2 Rn¡1C , 5i .qi ; q¡i /¡5i .xi ; q¡i / D P⁄.qi ; q¡i /¡ P⁄.xi ; q¡i /; 8qi ; xi 2 RC: .1:3/ A function P⁄ satisfying (1.3) will be called a potential function.2;3 The equal- ities (1.3) imply that the mixed-strategy equilibrium set of the quasi-Cournot game coincides with the mixed-strategy equilibrium set of the game obtained by replacing every payoff function by P⁄. In particular, firms that are jointly trying to maximize the potential function P⁄ (or the ordinal potential P) end up in an equilibrium.4 We will prove that there exists at most one potential function (up to an additive constant). This raises the natural question about the economic content (or interpretation) of P⁄: What do the firms try to jointly maximize? 1 Negative prices are possible in this game, though the prices in any nondegenerate equilibrium will be positive. 2 In physics, P⁄ is a potential function for .51;52; : : : ;5n/ if @5i @qi D @P ⁄ @qi for every 1 • i • n. If the profits functions are continuously differentiable then this condition is equivalent to (1.3). 3 Slade (1993) proved the existence of a function P⁄ satisfying (1.3) for the quasi-Cournot game. She called this function a fictitious objective function. 4 Every q⁄ that maximizes P⁄ is a pure-strategy equilibrium, but there may be pure-strategy equi- librium profiles that are just “local” maximum points, and there may be mixed-strategy equilibrium profiles as well. Therefore, the argmax set of the potential can be used as a refinement tool for potential games (this issue is discussed in Section 5). Neyman (1991) showed that if the potential function is concave and continuously differentiable, then every mixed-strategy equilibrium profile is pure and must maximize the potential function. Neyman’s result is related by Shin and Williamson (1994) to the concept of “simple equilibrium outcome” in Bayesian games. 126 MONDERER AND SHAPLEY We do not have an answer to this question. However, it is clear that the mere existence of a potential function helps us (and the players) to better analyze the game.5 In this paper we will prove various properties of potential games, and we will provide simple methods for detecting them and for computing their potential functions. To our knowledge, the first to use potential functions for games in strategic form was Rosenthal (1973). Rosenthal defined the class of congestion games and proved, by explicitly constructing a potential function, that every game in this class possesses a pure-strategy equilibrium. The class of congestion games is, on the one hand, narrow, but on the other hand, very important for economics. Any game where a collection of homogeneous agents have to choose from a finite set of alternatives, and where the payoff of a player depends on the number of players choosing each alternative, is a congestion game. We will show that the class of congestion games coincides (up to an isomorphism) with the class of finite potential games. Recently, much attention has been devoted to several notions of “myopic” learning processes. We show that for generic finite games, the existence of an ordinal potential is equivalent to the convergence to equilibrium of the learning process defined by the one-sided better reply dynamic. The new learning liter- ature raised a new interest in the Fictitious Play process in games in strategic form defined by Brown (1951). It was studied for zero-sum games by Robinson (1951) and for non-zero-sum games by Miyasawa (1961), Shapley (1964), De- schamps (1973), and lately by Krishna (1991), Milgrom and Roberts (1991), Sela (1992), Fudenberg and Kreps (1993), Jordan (1993), Hofbauer (1994), Krishna and Sjo¨stro¨m (1994), Fudenberg and Levine (1994), Monderer et al. (1994), and others. In Monderer and Shapley (1996) we prove that the Fictitious Play process converges to the equilibrium set in a class of games that contains the finite (weighted) potential games. Milchtaich (1996) analyzed classes of games related to congestion games. His work, as well as that of Blume (1993), indicates that ordinal potential games are naturally related to the evolutionary learning as well (see e.g., Crawford, 1991; Kandori and Rob, 1992; Young, 1993; Roth and Erev, 1995; and the references listed therein). As the potential function is uniquely defined up to an additive constant, the argmax set of the potential function does not depend on a particular potential function. Thus, for potential games this argmax set refines the equilibrium set, at least technically. We show that this refinement concept accurately predicts the experimental results obtained by Van Huyck et al. (1990). We do not attempt to provide any explanation to this prediction power obtained (perhaps as a coinci- 5 A similar problem is discussed by Bergstrom and Varian (1985). POTENTIAL GAMES 127 dence) in this case.6 A possible way of explaining this can be found in Blume (1993). Blume discusses various stochastic strategy revision processes for play- ers who have direct interaction only with small part of the population. He proves for the log-linear strategy revision process that the strategies of the players in a symmetric potential game converge to the argmax set of the potential.7 Hart and Mas-Colell (1989) have applied potential theory to cooperative games. Except for the fact that we are all using potential theory our works are not connected. Nevertheless, we will show in the last section that combining our work with Hart and Mas-Colell’s yields a surprising application to value theory.8 The paper is organized as follows: In Section 2 we give the basic definitions and provide several useful characterizations of finite potential and finite ordinal potential games. An equivalence theorem between potential games and conges- tion games is given in Section 3. In Section 4 we discuss and characterize infinite potential games. Section 5 is devoted to a discussion of the experimental results of Van Huyck et al. In Section 6 we show an application of our theory to the strategic approach to cooperative games. 2. POTENTIAL GAMES Let 0.u1; u2; : : : ; un/ be a game in strategic form with a finite number of players. The set of players is N D f1; 2; : : : ; ng, the set of strategies of Player i is Y i , and the payoff function of Player i is ui : Y ! R, where Y D Y 1 £ Y 2 £ ¢ ¢ ¢ £ Y n is the set of strategy profiles, and R denotes the set of real numbers. When no confusion may arise we denote 0.u1; u2; : : : ; un/ by 0. For S µ N , ¡S denotes the complementary set of S, and Y S denotes the Cartesian product £i2SY i . For singleton sets fig, Y¡fig is denoted by Y¡i . A function P: Y ! R is an ordinal potential for 0, if for every i 2 N and for every y¡i 2 Y¡i ui .y¡i ; x/¡ ui .y¡i ; z/ > 0 iff P.y¡i ; x/¡ P.y¡i ; z/ > 0 for every x; z 2 Y i . (2.1) 0 is called an ordinal potential game if it admits an ordinal potential. Letw D .wi /i2N be a vector of positive numbers which will be called weights. A function P: Y ! R is a w-potential for 0 if for every i 2 N and for every y¡i 2 Y¡i ui .y¡i ; x/¡ ui .y¡i ; z/ D wi ¡P.y¡i ; x/¡ P.y¡i ; z/¢ for every x; z 2 Y i . (2.2) 0 is called a w-potential game if it admits a w-potential. 6 Crawford (1991) gave an evolutionary interpretation of these experiments’ results. 7 This argmax set is assumed to be a singleton. 8 Another application to cooperative games is discussed by Qin (1992). 128 MONDERER AND SHAPLEY When we are not interested in particular weights w, we simply say that P is a weighted potential and that 0 is a weighted potential game.9 A function P: Y ! R is an exact potential (or, in short, a potential) for 0 if it is aw-potential for 0 withwi D 1 for every i 2 N . 0 is called an exact potential game (or, in short, a potential game) if it admits a potential. For example, the matrix P is a potential for the Prisoner’s Dilemma game G described below: G D µ .1; 1/ .9; 0/ .0; 9/ .6; 6/ ¶ ; P D µ 4 3 3 0 ¶ : The next lemma characterizes the equilibrium set of ordinal potential games. Its obvious proof will be omitted. LEMMA 2.1. Let P be an ordinal potential function for 0.u1; u2; : : : ; un/. Then the equilibrium set of 0.u1; u2; : : : ; un/ coincides with the equilibrium set of 0.P; P; : : : ; P/. That is, y 2 Y is an equilibrium point for 0 if and only if for every i 2 N P.y/ ‚ P.y¡i ; x/ for every x 2 Y i . Consequently, If P admits a maximal value10 in Y , then 0 possesses a (pure- strategy) equilibrium. COROLLARY 2.2. Every finite ordinal potential game possesses a pure-strategy equilibrium. A path in Y is a sequence ° D .y0; y1; : : :/ such that for every k ‚ 1 there exists a unique player, say Player i , such that yk D .y¡ik¡1; x/ for some x 6D yik¡1 in Y i . y0 is called the initial point of ° , and if ° is finite, then its last element is called the terminal point of ° . ° D .y0; y1; : : :/ is an improvement path with respect to 0 if for all k ‚ 1 ui .yk/ > ui .yk¡1/, where i is the unique deviator at step k. Hence, an improvement path is a path generated by myopic players. 0 has the finite improvement property (FIP) if every improvement path is finite. LEMMA 2.3. Every finite ordinal potential game has the FIP. Proof. For every improvement path ° D .y0; y1; y2; : : :/ we have by (2.1) P.y0/ < P.y1/ < P.y2/ < ¢ ¢ ¢ : As Y is a finite set, the sequence ° must be finite. 9 Using Blume’s (1993) terminology we can give an equivalent definition: 0 is a weighted potential game if and only if there exists a payoff function which is strongly best-response equivalent to each of the players’ payoff functions. Sela (1992) proved that if the two-person game .A; B/ does not have weakly dominated strategies, then it has a weighted potential if and only if it is better-response equivalent in mixed strategies (see Monderer and Shapley (1996) for the precise definition) to a game of the form .P; P/. This result can be easily generalized to n-person games. 10 See footnote 4. POTENTIAL GAMES 129 It is obvious that for finite games with the FIP, and in particular for finite ordinal potential games, every maximal improvement path must terminate in an equilibrium point. That is, the myopic learning process based on the one-sided better reply dynamic converges to the equilibrium set. However we have obtained a stronger learning result11: THEOREM 2.4 (Monderer and Shapley, 1996). Every finite weighted poten- tial game has the Fictitious Play property. It is interesting to note that having the FIP is not equivalent to having an ordinal potential. A counterexample is the game G1 described below. The rows in G1 are labeled by a and b, and the columns are labeled by c and d. G1 D µ .1; 0/ .2; 0/ .2; 0/ .0; 1/ ¶ : The game G1 has the FIP, but any ordinal potential P for G1 must satisfy the following impossible sequence of relations: P.a; c/ < P.b; c/ < P.b; d/ < P.a; d/ D P.a; c/: A function P: Y ! R is a generalized ordinal potential for 0 if for every i 2 N and for every y¡i 2 Y¡i , and for every x; z 2 Y i , ui .y¡i ; x/¡ ui .y¡i ; z/ > 0 implies that P.y¡i ; x/¡ P.y¡i ; z/ > 0: .2:3/ LEMMA 2.5. Let 0 be a finite game. Then, 0 has the FIP if and only if 0 has a generalized ordinal potential. Proof. Let 0 be a game with the FIP. Define a binary relation “>” on Y as follows: x > y iff x 6D y and there exists a finite improvement path ° with an initial point y and a terminal point x . The finite improvement property implies that “>” is a transitive relation. Let Z µ Y . We say that Z is represented if there exists Q: Z ! R such that for every x; y 2 Z , x > y implies that Q.x/ > Q.y/. Let Z be a maximal represented subset of Y . We proceed to prove that Z D Y . Suppose x 62 Z . If x > z for every z 2 Z , we extend Q to Z [ fxg by defining Q.x/ D 1 C maxz2Z Q.z/, thus contradicting the maximality of Z . If z > x for every z 2 Z , we extend Q to Z [ fxg by defining Q.x/ D minz2Z Q.z/¡ 1, contradicting again the maximality of Z . Otherwise we extend Q and contradict the maximality of Z by defining Q.x/ D .a C b//2, 11 Several notions of acyclicity are discussed in the recent learning literature. Most of them (unlike the FIP) are related to the best-response dynamic. See, e.g., Young (1993). Other results relating the fictitious play property with various types of improvement paths can be found in Monderer and Sela (1992). 130 MONDERER AND SHAPLEY where a D maxfQ.z/ : z 2 Z ; x > zg, and b D minfQ.z/ : z 2 Z ; z > xg. Hence Y is represented.12 COROLLARY 2.6. Let 0 be a finite game with the FIP. Suppose in addition that for every i 2 N and for every y¡i 2 Y¡i ui .y¡i ; x/ 6D ui .y¡i ; z/ for every x 6D z 2 Y i . Then 0 has an ordinal potential. Proof. Observe that the condition on0 implies that every generalized ordinal potential for 0 is an ordinal potential for 0. Hence, the proof follows from Lemma 2.5. Ordinal potential games have many ordinal potentials. For exact potential games we have: LEMMA 2.7. Let P1 and P2 be potentials for the game 0. Then there exists a constant c such that P1.y/¡ P2.y/ D c for every y 2 Y : Proof. Fix z 2 Y . For all y 2 Y define H.y/ D nX iD1 £ ui .ai¡1/¡ ui .ai / ⁄ ; where a0 D y and for every 1 • i • n, ai D .a¡ii¡1; zi /. If P stands for either P1 or P2, then by (2.1), H.y/ D P.y/¡ P.z/ for every y 2 Y . Therefore P1.y/¡ P2.y/ D c for every y 2 Y : The next results characterize exact potential games in a way that resembles the standard approach to potential functions in physics. For a finite path ° D .y0; y1; : : : ; yN / and for a vector v D .v1; v2; : : : ; vn/ of functions vi : Y ! R, we define I .°; v/ D nX kD1 £ vik .yk/¡ vik .yk¡1 ⁄ ; where ik is the unique deviator at step k (i.e., yikk 6D yikk¡1). 12 A constructive and more elegant proof of this result is given in Milchtaich (1996); he showed that the function P that assigns to each y 2 Y the number of strategy profiles that are connected to y by an improvement path that terminates in y is a generalized ordinal potential for 0. POTENTIAL GAMES 131 The path ° D .y0; y1; : : : ; yN / is closed if y0 D yN . It is a simple closed path if in addition yl 6D yk for every 0 • l 6D k • N¡1. The length of a simple closed path is defined to be the number of distinct vertices in it. That is, the length of ° D .y0; y1; : : : ; yN / is N . THEOREM 2.8. Let 0 be a game in strategic form, as described at the begin- ning of this section. Then the following claims are equivalent: (1) 0 is a potential game. (2) I .°; u/ D 0 for every finite closed paths ° . (3) I .°; u/ D 0 for every finite simple closed paths ° . (4) I .°; u/ D 0 for every finite simple closed paths ° of length 4. The proof of Theorem 2.8 is given in Appendix A. A typical simple closed path, ° , of length 4 is described below. In this path, i and j are the active players, a 2 Y¡fi; jg is a fixed strategy profile of the other players, xi ; yi 2 Y i , and xj ; yj 2 Y j , ° D A ¡ˆ¡¡¡ D??y x?? B ¡¡¡¡! C ; where A D .xi ; xj ; a/, B D .yi ; xj ; a/, C D .yi ; yj ; a/, and D D .xi ; yj ; a/. COROLLARY 2.9. 0 is a potential game if and only if for every i; j 2 N , for every a 2 Y¡fi; jg, and for every xi ; yi 2 Y i and xj ; yj 2 Y j , ui .B/¡ ui .A/C u j .C/¡ u j .B/C ui .D/¡ ui .C/C u j .A/¡ u j .D/ D 0; where the points A; B;C , and D are described above. We end this section with an important remark concerning the mixed extension of finite games. LEMMA 2.10. Let 0 be a finite game. Then 0 is a w-potential game if and only if the mixed extension of 0 is a w-potential game. Proof. For i 2 N let 1i be the set of mixed strategies of Player i and let U i be the payoff function of player i in the mixed extension of 0. That is, U i . f / D U i . f 1; f 2; : : : ; f n/ D X y2Y ui .y1; y2; : : : ; yn/ f 1.y1/ f 2.y2/ : : : f n.yn/; 8 f 2 1, where 1 D £i2N1i . Obviously, if NP: 1! R is a w-potential function for the mixed extension of 0, then its restriction to Y yields a w-potential for 0. As for 132 MONDERER AND SHAPLEY the converse, suppose P is a w-potential for 0, then it can be easily verified that NP is a potential for the mixed extension of 0, where NP. f 1; f 2; : : : ; f n/ D X y2Y P.y1; y2; : : : ; yn/ f 1.y1/ f 2.y2/ : : : f n.yn/: .2:4/ An example to an ordinal potential game whose mixed extension is not an ordinal potential game is given in Sela (1992). 3. CONGESTION GAMES Congestion games were defined by Rosenthal (1973). They are derived from congestion models that have been extensively discussed in the literature (see e.g., Garcia and Zangwill, 1981). Consider an illustrative example: A c1.1/;c1.2/¡¡¡¡¡! B c3.1/;c3.2/ ??y ??yc2.1/;c2.2/ D ¡¡¡¡¡! c4.1/;c4.2/ C In the congestion model described above, Driver a has to go from point A to point C and Driver b has to go from point B to point D. AB is called road segment 1, BC is called road segment 2; : : : etc. cj .1/ denotes the payoff (e.g., the negative of the cost) for a single user of road segment j . cj .2/ denotes the payoff for each user of road segment j if both drivers use road segment j . The drivers are therefore engaged in a game (the associated congestion game, CG) whose strategic form is given below (The rows are labeled by f1; 2g and f3; 4g, and the columns are labeled by f1; 3g and f2; 4g: CG D µ .c1.2/C c2.1/; c1.2/C c3.1// .c2.2/C c1.1/; c2.2/C c4.1// .c3.2/C c4.1/; c3.2/C c1.1// .c4.2/C c3.1/; c4.2/C c2.1// ¶ : By Corollary 2.9 the congestion game CG admits a potential. In particular (and with no restrictions on the payoff cj .i/) it has a (pure-strategy) equilibrium. For completeness we attach below a potent