报告——基于STP的势博弈理论.pdf
报告——基于STP的势博弈理论.pdf
Potential Game Theory Based on STP Lesson Two (1 1 ù) Lecturer: Jiandong Zhu (ÁïÅ) (School of Mathematical Sciences, Nanjing Normal University, Nanjing) H®“‰ŒÆêƉÆÆ Center of STP Theory and Its Applications July 17-24, 2021 LiaoCheng University, LiaoCheng, Shandong, P.R. China Outline 1 Introduction of game theory 2 Game Theory Based on STP 3 Potential game 4 Potential equations based on STP 5 Example: a congestion game 6 Conclusions 7 References 2 / 47 Modern game theory Modern game theory began with the idea of mixedstrategy equilibria in two-person zero-sum games and its proof by John von Neumann. His paper was followed by the 1944 book Theory of Games and Economic Behavior, co-written with Oskar Morgenstern. 3 / 47 Introduction, Definition of Game Definition 1. [1] A finite game is a triple G = (N , S, C), where (i) N = {1, 2, · · · , n} is the set of players; (ii) S = S1 × S2 × · · · × Sn , where each Si = {si1 , si2 , · · · , siki } is the strategy set of player i; (iii) C = {c1 , c2 , · · · , cn } is the set of payoff functions, where every ci : S → R is the payoff function of player i. The finite game defined above is called a normal form game in [2]. [1] Monderer D, Shapley LS (1996) Potential games. Games and Economic Behavior, 14, 124-143. [2] Sandholm WH, (2010) Decompositions and potentials for normal form games. Games and Economic Behavior, 70, 446-456. 4 / 47 Introduction, Definition of Game Let cµi1 i2 ···in = cµ (s1i1 , s2i2 , · · · , snin ) where 1 ≤ is ≤ ks and s = 1, 2, · · · , n. Then the finite game can be described by the arrays Cµ = {cµi1 i2 ···in | 1 ≤ is ≤ ks , s = 1, 2, · · · , n} (1) with µ = 1, 2, · · · , n. Given n and k1 , . . . , kn , the set of all finite games is a linear space with dimension d = nk1 k2 · · · kn . Particularly, for a 2-player game, the k1 × k2 matrices C1 = (c1ij ) and C2 = (c2ij ) are payoffs of players 1 and 2 respectively. Therefore, a 2-player finite game is also called a bi-matrix game, which is usually denoted by the simple notation G = (C1 , C2 ). 5 / 47 Introduction, Examples of Game The game of ’rock, paper, scissors’ with 2 players: A r r (0, 0) p (1, −1) s (−1, 1) 0 −1 1 0 −1 , C1 = 1 −1 1 0 B p (−1, 1) (0, 0) (1, −1) s (1, −1) (−1, 1) (0, 0) 0 1 −1 1 C2 = −1 0 1 −1 0 Question How can we describe a 3-player game in a matrix form? 6 / 47 Introduction, Examples of Game The game of ’rock, paper, scissors’ with 2 players: A r r (0, 0) p (1, −1) s (−1, 1) 0 −1 1 0 −1 , C1 = 1 −1 1 0 B p (−1, 1) (0, 0) (1, −1) s (1, −1) (−1, 1) (0, 0) 0 1 −1 1 C2 = −1 0 1 −1 0 Question How can we describe a 3-player game in a matrix form? 6 / 47 Introduction, Examples of Game The game of ’rock, paper, scissors’ with 2 players: A r r (0, 0) p (1, −1) s (−1, 1) 0 −1 1 0 −1 , C1 = 1 −1 1 0 B p (−1, 1) (0, 0) (1, −1) s (1, −1) (−1, 1) (0, 0) 0 1 −1 1 C2 = −1 0 1 −1 0 Question How can we describe a 3-player game in a matrix form? 6 / 47 Introduction, Examples of Game The game of ’palm up, palm down’ with 3 players: A B C uuu uud udu udd duu dud c1 0 1 1 −2 −2 1 c2 0 1 −2 1 1 −2 c3 0 −2 1 1 1 1 ddu ddd 1 0 1 0 −2 0 Payoff matrix is defined as 0 1 1 −2 −2 1 1 0 1 −2 1 0 . P = 0 1 −2 1 0 −2 1 1 1 1 −2 0 This description of finite games was proposed in [3]. [3] D. Cheng, On finite potential games, Automatica, 50, 1793-1801, 2014. 7 / 47 Introduction, Examples of Game The game of ’palm up, palm down’ with 3 players: A B C uuu uud udu udd duu dud c1 0 1 1 −2 −2 1 c2 0 1 −2 1 1 −2 c3 0 −2 1 1 1 1 ddu ddd 1 0 1 0 −2 0 Payoff matrix is defined as 0 1 1 −2 −2 1 1 0 1 −2 1 0 . P = 0 1 −2 1 0 −2 1 1 1 1 −2 0 This description of finite games was proposed in [3]. [3] D. Cheng, On finite potential games, Automatica, 50, 1793-1801, 2014. 7 / 47 Introduction, Examples of Game The game of ’palm up, palm down’ with 3 players: A B C uuu uud udu udd duu dud c1 0 1 1 −2 −2 1 c2 0 1 −2 1 1 −2 c3 0 −2 1 1 1 1 ddu ddd 1 0 1 0 −2 0 Payoff matrix is defined as 0 1 1 −2 −2 1 1 0 1 −2 1 0 . P = 0 1 −2 1 0 −2 1 1 1 1 −2 0 This description of finite games was proposed in [3]. [3] D. Cheng, On finite potential games, Automatica, 50, 1793-1801, 2014. 7 / 47 matrix forms of payoff matrices The game of ’palm up, palm down’ with 3 players: A B C uuu uud udu udd duu dud ddu ddd c1 0 1 1 −2 −2 1 1 0 c2 0 1 −2 1 1 −2 1 0 c3 0 −2 1 1 1 1 −2 0 Payoff matrix is defined as 0 1 1 −2 −2 1 1 0 1 −2 1 0 . P = 0 1 −2 1 0 −2 1 1 1 1 −2 0 The matrix form of payoff function: c1 (x1 , x2 , x3 ) = [0 1 1 − 2 − 2 1 1 0]x1 x2 x3 , where xi ∈ 1 0 0 , . 1 8 / 47 matrix forms of payoff matrices In general, each payoff function can be rewritten in the matrix form based on STP as follows: ci (x1 , x2 , · · · , xn ) = Vic x1 x2 · · · xn , where xj ∈ ∆kj , i, j = 1, 2, . . . , n. The payoff matrix is an n × k1 k2 · · · kn matrix: V1c Vc 2 P = .. . . Vnc Obviously, the dimension of the linear space composed of all n × k1 k2 · · · kn matrices is nk1 k2 · · · kn . 9 / 47 Introduction, Nash Equilibria A strategy profile s = (s1 , s2 , · · · , sn ) ∈ S is a Nash equilibrium (NE) if fi (si , s−i ) ≥ fi (xi , s−i ) ∀i, xi ∈ Si . Example: Prisoner’s Dilemma B s b s (−1, −1) (−10, 0) A b (0, −10) (−8, −8) s=silent; b=betray. Nash Equilibrium: (b,b). −1 −10 −1 0 C1 = , C2 = 0 −8 −10 −8 10 / 47 Introduction, Nash Equilibria Nash’s Existence Theorem If we allow mixed strategies, then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium. 11 / 47 Introduction, Nash Equilibria Nash’s Existence Theorem If we allow mixed strategies, then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium. B head A tail head tail (3, −3) (−2, 2) (−2, 2) (1, −1) If we are allowed to take a mixed strategy, we can take 13 head and 23 tail. Let P(A = head) = x and P(B = head) = y. Then we have c1 = 3·xy+1·(1−x)(1−y)−2·(1−x)y−2·x(1−y) = 8xy − 3x − 3y + 1; 12 / 47 The payoff function of A is c1 (x, y) = 8xy − 3x − 3y + 1. The Nash equilibrium is (x∗ , y∗ ) = ( 38 , 83 ) and 3 3 3 1 c1 (x, ) = 8x − 3x − 3 + 1 = − , 8 8 8 8 1 c2 (x, y∗ ) = , ∀ x. 8 2 1.5 1 0.5 0 −0.5 −1 −1.5 −2 −2.5 −3 0 0.5 1 0 0.2 0.4 0.6 0.8 1 c1 (x, y) = 8xy − 3x − 3y + 1. 13 / 47 Definition of Potential Game Question What kind of games have a Nash Equilibrium under pure strategies? Definition. (Monderer & Shapley, 1996) A finite game G = (N , S, C) is said to be potential if there exists a function p : S → R, called the potential function, such that ci (x, s−i ) − ci (y, s−i ) = p(x, s−i ) − p(y, , s−i ) for all x, y ∈ Si , s−i ∈ S −i i = 1, 2, · · · , n, where S −i = S1 × · · · × Si−1 × Si+1 × · · · × Sn . 14 / 47 Definition of Potential Game Question What kind of games have a Nash Equilibrium under pure strategies? Definition. (Monderer & Shapley, 1996) A finite game G = (N , S, C) is said to be potential if there exists a function p : S → R, called the potential function, such that ci (x, s−i ) − ci (y, s−i ) = p(x, s−i ) − p(y, , s−i ) for all x, y ∈ Si , s−i ∈ S −i i = 1, 2, · · · , n, where S −i = S1 × · · · × Si−1 × Si+1 × · · · × Sn . 14 / 47 potential games Theorem (Monderer & Shapley, 1996) Every finite potential game possesses a pure Nash equilibrium. Question (Monderer & Shapley, 1996) How can we test whether a finite game is potential? 15 / 47 Conservative vector field In vector calculus, a conservative vector field (potential field) is a gradient field of a scalar function called a potential function. A vector field is a conservative field if and only if the line integral is path independent. Gradient Theorem A conservative vector field c(x) = (c1 (x), . . . , cn (x))T satisfies Z c(x) · dx = p(B) − p(A), C where C is any path from point A to point B, and p(·) is the potential function. 16 / 47 Conservative vector field Gradient Theorem A conservative vector field c(x) = (c1 (x), c2 (x))T satisfies Z c1 (x)dx1 + c2 (x)dx2 = p(B) − p(A), C where C is a path form point A to point B, and p(·) is the potential function. The potential function p(x) is Z (x1 ,x2 ) p(x1 , x2 ) = c1 (x)dx1 + c2 (x)dx2 . (a,b) Let p1 and p2 be potentials for a conservative vector field. Then there exists a constant c such that p1 (x1 , x2 ) − p2 (x1 , x2 ) = c for every (x1 , x2 ). 17 / 47 Conservative vector field Vector field c(x) = T (c1 (x), c2 (x)) is a conservative field if and only if I c1 (x)dx1 + c2 (x)dx2 = 0 for every closed-loop. In particular, consider the above closed loop. If vector field c(x) = (c1 (x), c2 (x))T is conservative, then Z y1 Z y2 Z x1 Z x2 c1 (x)dx1 + c2 (x)dx2 + c1 (x)dx1 + c2 (x)dx2 = 0. x1 x2 y1 y2 18 / 47 Conservative vector field Vector field c(x) = T (c1 (x), c2 (x)) is a conservative field if and only if I c1 (x)dx1 + c2 (x)dx2 = 0 for every closed-loop. In particular, consider the above closed loop. If vector field c(x) = (c1 (x), c2 (x))T is conservative, then Z y1 Z y2 Z x1 Z x2 c1 (x)dx1 + c2 (x)dx2 + c1 (x)dx1 + c2 (x)dx2 = 0. x1 x2 y1 y2 18 / 47 potential games Definition (Monderer & Shapley, 1996) A path in S is a sequence γ = (y0 , y1 , . . . ) such that for every k ≥ 1 there exists a unique player, say Player i, such that yk = (y−i k−1 , x) for some i x 6= yk−1 in S. 19 / 47 potential games Definition (Monderer & Shapley, 1996) For a finite path γ = (y0 , y1 , . . . yN ) and for a vector c = (c1 , c2 , . . . , cn ) of payoff functions ci (x), the total payoff along γ is defined as N X I(γ, c) = [cik (yk ) − cik (yk−1 )], k=1 where ik is the unique deviator at step k. The total payoff is similar to the line integral along γ: Z c(x) · dx = γ N Z yk X k=1 cik (x)dxik . yk−1 20 / 47 potential games For the finite path γ = (y0 , y1 , y2 , y3 ) the total payoff is I(γ, c) = [c1 (y1 ) − c1 (y0 )] + [c3 (y2 ) − c3 (y1 )] + [c2 (y3 ) − c2 (y2 )], which is similar to the line integral Z Z y1 Z y2 Z y3 c(x) · dx = c1 (x)dx1 + c3 (x)dx3 + c2 (x)dx2 . γ y0 y1 y2 21 / 47 potential games Theorem (Monderer & Shapley, 1996) Let G be a finite game with payoff vector c. The following claims are equivalent: (1) G is a potential game; (2) I(γ, c) = 0 for every finite closed path γ; (3) I(γ, c) = 0 for every simple closed path γ of length 4. path4.pdf path4.pdf [c2 (B)−c2 (A)]+[c1 (C)−c1 (B)]+[c2 (D)−c2 (C)]+[c1 (A)−c1 (D)] = 0. 22 / 47 potential games Theorem (Monderer & Shapley, 1996) G = (N , S, C) is a potential game iff for every i, j ∈ N , for every a ∈ S −{i,j} , and for every xi , yi ∈ Si and xj , yj ∈ Sj , [cj (B)−cj (A)]+[ci (C)−ci (B)]+[cj (D)−cj (C)]+[ci (A)−ci (D)] = 0. It is called a four-cycle equation in (Sandholm 2010). Question: How many equations are needed to check? 23 / 47 potential games Question How many equations are needed to check for a finite game with n players and k strategies for each player? By (Monderer & Shapley, 1996), the number of equations corresponding to simple closed loops with length 4 is n(n − 1)kn (k − 1)2 2 n−2 2 2 Cn k Ck Ck = = O(n2 kn+2 ). 6 The theoretical minimum value of the number of equations is nkn − (kn + nkn−1 − 1) = (n − 1)kn − nkn−1 + 1 = O(nkn ). 24 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (2) Proof. (⇐) If (2) holds, then Up (x, s−p ) = V(x, s−p ) + Wp (s−p ) (3) Up (y, s−p ) = V(y, s−p ) + Wp (s−p ). (4) and From (3)−(4), it follows that Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ). Therefore, U is a potential game with the potential function V(x). 25 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (2) Proof. (⇐) If (2) holds, then Up (x, s−p ) = V(x, s−p ) + Wp (s−p ) (3) Up (y, s−p ) = V(y, s−p ) + Wp (s−p ). From (3)−(4), it follows that (4) and Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ). Therefore, U is a potential game with the potential function V(x). 25 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (2) Proof. (⇐) If (2) holds, then Up (x, s−p ) = V(x, s−p ) + Wp (s−p ) (3) Up (y, s−p ) = V(y, s−p ) + Wp (s−p ). From (3)−(4), it follows that (4) and Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ). Therefore, U is a potential game with the potential function V(x). 25 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (5) Proof. (⇒) Assume that U is a potential game with the potential function V(x), i.e., Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ) for any x, y ∈ Si and s−p ∈ S −p . So, Up (x, s−p ) − V(x, s−p ) = Up (y, s−p ) − V(y, s−p ). (6) Let Wp (s) = Up (s) − V(s). Then (6) implies that Wp (s) is independent of sp , which is rewritten as Wp (s−p ). Therefore, Up (s) = V(s) + Wp (s−p ). (7) 26 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (5) Proof. (⇒) Assume that U is a potential game with the potential function V(x), i.e., Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ) for any x, y ∈ Si and s−p ∈ S −p . So, Up (x, s−p ) − V(x, s−p ) = Up (y, s−p ) − V(y, s−p ). (6) Let Wp (s) = Up (s) − V(s). Then (6) implies that Wp (s) is independent of sp , which is rewritten as Wp (s−p ). Therefore, Up (s) = V(s) + Wp (s−p ). (7) 26 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (5) Proof. (⇒) Assume that U is a potential game with the potential function V(x), i.e., Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ) for any x, y ∈ Si and s−p ∈ S −p . So, Up (x, s−p ) − V(x, s−p ) = Up (y, s−p ) − V(y, s−p ). (6) Let Wp (s) = Up (s) − V(s). Then (6) implies that Wp (s) is independent of sp , which is rewritten as Wp (s−p ). Therefore, Up (s) = V(s) + Wp (s−p ). (7) 26 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (5) Proof. (⇒) Assume that U is a potential game with the potential function V(x), i.e., Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ) for any x, y ∈ Si and s−p ∈ S −p . So, Up (x, s−p ) − V(x, s−p ) = Up (y, s−p ) − V(y, s−p ). (6) Let Wp (s) = Up (s) − V(s). Then (6) implies that Wp (s) is independent of sp , which is rewritten as Wp (s−p ). Therefore, Up (s) = V(s) + Wp (s−p ). (7) 26 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N . (5) Proof. (⇒) Assume that U is a potential game with the potential function V(x), i.e., Up (x, s−p ) − Up (y, s−p ) = V(x, s−p ) − V(y, s−p ) for any x, y ∈ Si and s−p ∈ S −p . So, Up (x, s−p ) − V(x, s−p ) = Up (y, s−p ) − V(y, s−p ). (6) Let Wp (s) = Up (s) − V(s). Then (6) implies that Wp (s) is independent of sp , which is rewritten as Wp (s−p ). Therefore, Up (s) = V(s) + Wp (s−p ). (7) 26 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N , By using the matrix form based on STP, U is a potential game iff its payoff matrix U has the form U1 V ? U2 V ? .. = .. + .. . . . . Up V ? Let x ∈ ∆n1 , y ∈ ∆n2 and z ∈ ∆n3 . Then xz = (In1 ⊗ 1Tn2 ⊗ In3 )xyz. Proof. (In1 ⊗ 1Tn2 ⊗ In3 )(x ⊗ y ⊗ z) = x ⊗ 1 ⊗ z = xz. 27 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N , By using the matrix form based on STP, U is a potential game iff its payoff matrix U has the form U1 V ? U2 V ? .. = .. + .. . . . . Up V ? Let x ∈ ∆n1 , y ∈ ∆n2 and z ∈ ∆n3 . Then xz = (In1 ⊗ 1Tn2 ⊗ In3 )xyz. Proof. (In1 ⊗ 1Tn2 ⊗ In3 )(x ⊗ y ⊗ z) = x ⊗ 1 ⊗ z = xz. 27 / 47 potential games U is a potential game if and only if there is a potential function V and auxiliary functions Wp : S −p → R such that Up (s) = V(s) + Wp (s−p ) ∀ s ∈ S, ∀ p ∈ N , By using the matrix form based on STP, U is a potential game iff its payoff matrix U has the form U1 V ? U2 V ? .. = .. + .. . . . . Up V ? Let x ∈ ∆n1 , y ∈ ∆n2 and z ∈ ∆n3 . Then xz = (In1 ⊗ 1Tn2 ⊗ In3 )xyz. Proof. (In1 ⊗ 1Tn2 ⊗ In3 )(x ⊗ y ⊗ z) = x ⊗ 1 ⊗ z = xz. 27 / 47 potential games U is a potential game iff its payoff matrix U has the form V W1(1Tk ⊗Ikn−1) 0 0 V W2 (Ik ⊗1T ⊗I n−2) 0 0 k k U =..+ + +· · ·+ . .. .. .. . . . . T V 0 0 Wn (Ikn−1 ⊗1k ) Let X and Y be subspaces of a n-dimensional linear space. Then dim(X + Y) = dim(X ) + dim(Y) − dim(X ∩ Y). So the dimension of the linear space composed of potential games is kn + nkn−1 − 1. (Sandholm, Games Econ Behav, 2010; Monderer D, Shapley, Games Econ Behav, 1996) 28 / 47 potential games U is a potential game iff its payoff matrix U has the form V W1(1Tk ⊗Ikn−1) 0 0 V W2 (Ik ⊗1T ⊗I n−2) 0 0 k k U =..+ + +· · ·+ . .. .. .. . . . . T V 0 0 Wn (Ikn−1 ⊗1k ) Let X and Y be subspaces of a n-dimensional linear space. Then dim(X + Y) = dim(X ) + dim(Y) − dim(X ∩ Y). So the dimension of the linear space composed of potential games is kn + nkn−1 − 1. (Sandholm, Games Econ Behav, 2010; Monderer D, Shapley, Games Econ Behav, 1996) 28 / 47 potential games Theorem (Hino, Int J Game Theory 2011) G = (N , S, C) is a potential game iff for every i, j ∈ N , for every a ∈ S −{i,j} , and for every xi ∈ Si and xj ∈ Sj , [cj (B)−cj (A)]+[ci (C)−ci (B)]+[cj (D)−cj (C)]+[ci (A)−ci (D)] = 0, where A = (xi , xj , a), B = (xi + 1, xj , a), C = (xi + 1, xj + 1, a), and D = (xi , xj + 1, a). The number of four-cycle equations is Cn2 kn−2 Ck2 Ck2 = O(n2 kn+2 ). By (Hino, 2011), the number of equations is Cn2 kn−2 (k − 1)2 = O(n2 kn ). The minimum value is (n − 1)kn − nkn−1 + 1 = O(nkn ). [4] Y. Hino, An improved algorithm for detecting potential games, Int J Game Theory (2011) 40:199-205. 29 / 47 Potential equation A finite game U is a potential game iff there are exists row vectors V and Wi such that U1 V W1(1Tk ⊗Ikn−1) U2 V W2 (Ik ⊗1T ⊗I n−2) k k .. = .. + . .. . . . T Un V Wn (Ikn−1 ⊗1k ) or U1 V W1(1Tk ⊗Ikn−1) U2 − U1 0 W2 (Ik ⊗1T ⊗I n−2) − W1(1T ⊗I n−1) k k k k . = .. + .. .. . . . Un − U1 0 Wn (Ikn−1 ⊗1Tk ) − W1(1Tk ⊗Ikn−1) 30 / 47 Potential equation A finite game U is a potential game iff there are exists row vectors Wi such that U2 − U1 W2 (Ik ⊗1Tk ⊗Ikn−2) − W1(1Tk ⊗Ikn−1) .. .. = . . . T T Un − U1 Wn (Ikn−1 ⊗1k ) − W1(1k ⊗Ikn−1) or −1k ⊗Ikn−1 Ik ⊗1k ⊗Ikn−2 −1k ⊗I n−1 Ik2 ⊗1k ⊗Ikn−3 k .. ... . −1k ⊗Ikn−1 T (U2 −U1 ) .. ξ= . . (Un −U1 )T Ikn−1 ⊗1k The potential equation is dented by Ψξ = b, where Ψ is an (n−1)kn × nkn−1 matrix. 31 / 47 Potential equation Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if the potential equation Ψξ = b has a solution ξ. Lemma (Cheng, Automatica, 2014) Ψ1nkn−1 = 0; rankΨ = nkn−1 − 1. We only need to prove that the dimension of Ψξ = 0 is 1. Assume that Ψξ = 0, prove that ξ = a1nkn−1 for some a. Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if rank[Ψ, b] = nkn−1 − 1. 32 / 47 Potential equation Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if the potential equation Ψξ = b has a solution ξ. Lemma (Cheng, Automatica, 2014) Ψ1nkn−1 = 0; rankΨ = nkn−1 − 1. We only need to prove that the dimension of Ψξ = 0 is 1. Assume that Ψξ = 0, prove that ξ = a1nkn−1 for some a. Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if rank[Ψ, b] = nkn−1 − 1. 32 / 47 Potential equation Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if the potential equation Ψξ = b has a solution ξ. Lemma (Cheng, Automatica, 2014) Ψ1nkn−1 = 0; rankΨ = nkn−1 − 1. We only need to prove that the dimension of Ψξ = 0 is 1. Assume that Ψξ = 0, prove that ξ = a1nkn−1 for some a. Theorem (Cheng, Automatica, 2014) The game G = (N , S, C) is potential if and only if rank[Ψ, b] = nkn−1 − 1. 32 / 47 Potential equation Question What is the relationship between the four-cycle equation and the potential equation? For the case of n = 2, the potential equation is −1k1 ⊗Ik2 Ik1 ⊗1k2 ξ = b. Theorem The bi-matrix game G = (C1 , C2 ) is a potential game if and only if Bk1 (C2 − C1 )BTk2 = 0, (8) where Bk = [Ik−1 , −1k−1 ] [5] Xinyun Liu, Jiandong Zhu, On potential equations of finite games, Automatica, 68, 245-253, 2016. 33 / 47 Proof. Let Dk := [Ik−1 , 0] ∈ R(k−1)×k . Then it is easy to see that Bk DTk = Ik−1 , Dk δkk = Bk 1k = 0. (9) Construct two matrices E = [−δkk11 ⊗ Ik2 , BTk1 ⊗ δkk22 , BTk1 ⊗ BTk2 ]T ∈ Rk1 k2 ×k1 k2 F = [−1k1 ⊗ Ik2 , DTk1 ⊗ 1k2 , DTk1 ⊗ DTk2 ] ∈ Rk1 k2 ×k1 k2 . Then a straightforward calculation shows that −(δkk11 )T ⊗ Ik2 EF = Bk1 ⊗ (δkk22 )T [−1k1 ⊗ Ik2 , DTk1 ⊗ 1k2 , DTk1 ⊗ DTk2 ] Bk1 ⊗ Bk2 lcl Ik2 0 0 = Ik1 k2 0 = 0 Ik1 −1 0 0 I(k1 −1)(k2 −1) 34 / 47 Potential equation So the potential equation is equivalent to EΨξ = Eb. It is easy to check that −(δkk11 )T ⊗ Ik2 E[Ψ, b] = Bk1 ⊗ (δkk22 )T [−1k1 ⊗ Ik2 , Ik1 ⊗ 1k2 , b] Bk1 ⊗ Bk2 Ik2 −(δkk11 )T ⊗ 1k2 −((δkk11 )T ⊗ Ik2 )b = 0 B k1 (Bk1 ⊗ (δkk22 )T )b 0 0 (Bk1 ⊗ Bk2 )b Ik2 0 −1k2 −((δkk11 )T ⊗ Ik2 )b = 0 Ik1 −1 −1k1 −1 (Bk1 ⊗ (δkk22 )T )b .(10) 0 0 0 (Bk1 ⊗ Bk2 )b So the potential equation is solvable if and only if (Bk1 ⊗ Bk2 )b = 0, i.e., Bk1 (C2 − C1 )BTk2 = 0. (11) 35 / 47 Potential equation Corollary The bi-matrix game G = (C1 , C2 ) is a potential game if and only if rij − rik2 − rk1 j + rk1 k2 = 0 (12) for every i = 1, 2, · · · , k1 − 1 and j = 1, 2, · · · , k2 − 1, where (rij ) = C2 − C1 . rij − rik2 − rk1 j + rk1 k2 = c2 (i, j) − c1 (i, j) − c2 (i, k2 ) + c1 (i, k2 ) −c2 (k1 , j) + c1 (k1 , j) + c2 (k1 , k2 ) − c1 (k1 , k2 ) = [c1 (k1 , j) − c1 (i, j)] + [c2 (k1 , k2 ) − c2 (k1 , j)] +[c1 (i, k2 ) − c1 (k1 , k2 )] + [c2 (i, j) − c2 (i, k2 )] (13) So the condition in the theorem is just a set of four-cycle 36 / 47 equations. potential games Given the strategy set for bi-matrix games, the set of all the relative payoff matrices of potential bi-matrix games is a (k1 + k2 − 1)-dimensional subspace, which is isomorphic to P = {b ∈ Rk1k2 | (Bk1 ⊗Bk2 )b = 0}. (14) Lemma Consider a linear subspace of Rn as follows: X = {v ∈ Rn | Bv = 0}. (15) If B has a full row rank, then the orthogonal projection of u onto X is ProjX u = (In − BT (BBT )−1 B)u. (16) 37 / 47 potential games Now we consider the orthogonal projection onto the potential subspace. Theorem Consider a bi-matrix game G = (C1 , C2 ), where C1 , C2 ∈ Rk1 ×k2 . Denote the relative payoff matrix by R = (rij ) = C2−C1 and let Hk = Ik − 1k 1k 1Tk . Then ProjP Vr (R) = (Ik1k2 − Hk1 ⊗ Hk2 )Vr (R). (17) Proof. Let B̃ = Bk1 ⊗ Bk2 . By Lemma, we have ProjP Vr (R) = (Ik1 k2 − B̃T (B̃B̃T )−1 B̃)Vr (R) = (Ik1 k2 −BTk1 (Bk1 BTk1 )−1 Bk1 ⊗ BTk2 (Bk2 BTk2 )−1 Bk2 )Vr (R). 38 / 47 potential games A straightforward computation shows that = = = = BTk (Bk BTk )−1 Bk Ik−1 (Ik−1 + 1k−1 1Tk−1 )−1 [Ik−1 − 1k−1 ] T −1k−1 1 Ik−1 (I − 1k−1 1Tk−1 )[Ik−1 − 1k−1 ] k−1 T −1k−1 k Ik−1 − 1k 1k−1 1Tk−1 − 1k 1k−1 k−1 − 1k 1Tk−1 k 1 T Ik − 1k 1k = Hk . (18) k It follows that (17) holds. 2 39 / 47 potential games Theorem Consider a bi-matrix game G = (C1 , C2 ), where C1 , C2 ∈ Rk1 ×k2 . Let R = (rij ) = C2 − C1 . Then the following statements are equivalent: (i) G is a potential game; (ii) Hk1 RHk2 = 0, where Hk = Ik − 1k 1k 1Tk ; (iii) rij = ri−ave + rj−ave − rave for all i = 1, 2, · · · , k1 and j = 1, 2, · · · , k2 , where P2 P1 ri−ave = k12 kµ=1 riµ , rj−ave = k11 kλ=1 rλj , (19) P P k2 1 rave = k11k2 kλ=1 (20) µ=1 rλµ . 40 / 47 potential games Proof. Obviously, G is a potential game if and only if ProjP Vr (R) = Vr (R), where P is the potential subspace. Therefore, we have that G is potential if and only if (Hk1 ⊗ Hk2 )Vr (R) = 0, i.e. Hk RHk = 0. Moreover, a straightforward calculation shows that Hk RHk 1 1 1k1 1Tk1 )R(Ik2 − 1k2 1Tk2 ) k1 k2 1Tk1 R1k2 1 1 T T 1k1 1Tk2 . = R− 1k1 1k1 R− R1k2 1k2 + k1 k2 k1 k2 = (Ik1 − (21) From (19)-(21), the equivalence between (ii) and (iii) follows. 2 41 / 47 weighted network congestion games Consider an example of weighted network congestion games (WNCG) addressed in Lemma 1 of Fotakis, Kontogiannis, and Spirakis (2005). 42 / 47 A weighted congestion game With simple calculations, we get the relative payoff matrix R = w2 P2 − w1 P1 , where P1 and P2 are given as follows: c31 +c32 +c33 c11 +c12 +c33 c11 +c12 +c13 c11 +c12 +c13 c33 +c14 +c15 c33 +c34 +c35 c13 +c34 +c15 c13 +c14 +c15 P1= c14 +c16 +c17 c34 +c16 +c17 c34 +c36 +c37 c14 +c16 +c17 c18 +c19 +c1,10 c18 +c19 +c1,10 c18 +c19 +c1,10 c38 +c39 +c3,10 c31 +c32 +c33 c21 +c22 +c33 P2= c21 +c22 +c23 c21 +c22 +c23 c33 +c24 +c25 c33 +c34 +c35 c23 +c34 +c25 c23 +c24 +c25 c24 +c26 +c27 c34 +c26 +c27 c34 +c36 +c37 c24 +c26 +c27 c28 +c29 +c2,10 c28 +c29 +c2,10 . c28 +c29 +c2,10 c38 +c39 +c3,10 43 / 47 A weighted congestion game By the concept of weighted congestion game, the relative payoff matrix is R = w2 P2 − w1 P1 . So, the game is a potential game if and only if B4 RBT4 = 0, which is simplified as the following equations: w2 (c31 + c32 − c21 − c22 ) − w1 (c31 + c32 − c11 − c12 ) = 0, w2 (c33 − c23 ) − w1 (c33 − c13 ) = 0, w2 (c34 − c24 ) − w1 (c34 − c14 ) = 0, w2 (c35 − c25 ) − w1 (c35 − c15 ) = 0, w2 (c36 + c37 − c26 − c27 ) − w1 (c36 + c37 − c16 − c17 ) = 0, w2 (c38 + c39 + c3,10 − c28 − c29 − c2,10 ) −w1 (c38 + c39 + c3,10 − c18 − c19 − c1,10 ) = 0. 44 / 47 Conclusions 1. Based on the STP, a finite game can be expressed as a payoff matrix. 2. A finite potential game is just like a potential vector field (conservative field). 3. A finite game is a potential game if and only if its potential equation has a solution. 4. The minimum number of linear equations for verifying potential games can be obtained. 5. Based on STP, linear spaces of games and conges45 / 47 tion games can be considered. Conclusions 1. Based on the STP, a finite game can be expressed as a payoff matrix. 2. A finite potential game is just like a potential vector field (conservative field). 3. A finite game is a potential game if and only if its potential equation has a solution. 4. The minimum number of linear equations for verifying potential games can be obtained. 5. Based on STP, linear spaces of games and conges45 / 47 tion games can be considered. Conclusions 1. Based on the STP, a finite game can be expressed as a payoff matrix. 2. A finite potential game is just like a potential vector field (conservative field). 3. A finite game is a potential game if and only if its potential equation has a solution. 4. The minimum number of linear equations for verifying potential games can be obtained. 5. Based on STP, linear spaces of games and conges45 / 47 tion games can be considered. Conclusions 1. Based on the STP, a finite game can be expressed as a payoff matrix. 2. A finite potential game is just like a potential vector field (conservative field). 3. A finite game is a potential game if and only if its potential equation has a solution. 4. The minimum number of linear equations for verifying potential games can be obtained. 5. Based on STP, linear spaces of games and conges45 / 47 tion games can be considered. Conclusions 1. Based on the STP, a finite game can be expressed as a payoff matrix. 2. A finite potential game is just like a potential vector field (conservative field). 3. A finite game is a potential game if and only if its potential equation has a solution. 4. The minimum number of linear equations for verifying potential games can be obtained. 5. Based on STP, linear spaces of games and conges45 / 47 tion games can be considered. + References [1] Monderer D, Shapley LS, (1996) Potential games. Games and Economic Behavior, 14, 124-143. [2] Sandholm WH, (2010) Decompositions and potentials for normal form games. Games and Economic Behavior, 70, 446-456. [3] Y. Hino, (2011) An improved algorithm for detecting potential games, Int J Game Theory, 40, 199-205. [4] D. Cheng, (2014) On finite potential games, Automatica, 50, 1793-1801. [5] X. Liu, J. Zhu, (2016) On potential equations of finite games, Automatica, 68, 245-253. 46 / 47 Many Thanks for Your Attention! 47 / 47