报告——有限博弈的半张量积方法2.pdf
报告——有限博弈的半张量积方法2.pdf
1nÏÝ ŒÜþÈÛÏ• 1 3ù ù: k • Æ ‰ Œ Ü þ È • { 3.2 ³ Æ ‰ STP• •{ o•U lichangxi@pku.edu.cn ®ŒÆ, óÆ 2023c08 14F, ¢ŒÆ ̇SN 1 ³Æ‰9ÙÄ 2 ³•§ 3 ³•§ 4 k•Æ‰ 5 Š’ ( 5Ÿ †) •þ˜m©) 2 / 36 1. ³Æ ‰ 9 Ù Ä 5Ÿ + Ÿo´³Æ‰? ³Æ‰•@´dRosenthal JÑ . Shapley <‰ Nõ?˜Ú õÚuÐ. ³Æ‰Š•˜aAÏ Æ‰kNõ`û 5Ÿ. AO´ §3üze¬Âñ BŸþï: ù˜A5, ¦§ É “à. §•Ïd3Nõ¢SXÚ ïÄ¥ A^: ~X, ÏZl¯K, >å ‰†> ›› . 3 / 36 + ³¼ê Definition 1.1 G = (N, QnS, C) • ˜ k • Æ ‰. |N| = n, |Si | = ki , i = 1, · · · , n, i=1 ki = k. G ¡•˜‡•³Æ‰(ordinal potential game), XJ• 3˜‡¼êP : S → R, ¡•³¼ê, ¦ éz‡i Úz ‡s−i ∈ S−i þ¤á: ci (xi , s−i ) − ci (yi , s−i ) > 0 ⇔ P(xi , s−i ) − P(yi , s−i ) > 0, ∀xi , yi ∈ Si . (1) 4 / 36 Definition 1.1(cont’d) G ¡•˜‡\ ³Æ‰(weighted potential game), X J•3˜| ê{wi > 0 | i = 1, · · · , n}, ¡• -, Ú˜ ‡¼êP : S → R, ¡•³¼ê,¼êP : S → R, ¡•³ ¼ê, ¦ éz‡i, z˜|xi , yi ∈ Si , Úz˜‡s−i ∈ S−i þ¤á: ci (xi , s−i ) − ci (yi , s−i ) = wi P(xi , s−i ) − P(yi , s−i ) . (2) G ¡•˜‡(X)³Æ‰(pure potential game), XJG ´ ˜‡\ ³Æ‰, …¤k -þ•1, =wi = 1, ∀i. 5 / 36 5¿, ·‚w,kXe%º'X: ³Æ‰ ⇒ \ ³Æ‰ ⇒ •³Æ‰. e¡´³Æ‰ ˜ ̇5Ÿ: Theorem 1.2 XJG ´³Æ‰, @o, P 3NN˜‡~ê ¿Âe•˜. †óƒ, XJP1 ÚP2 •G ü‡³¼ê, KP1 −P2 = c0 ∈ R. 6 / 36 Theorem 1.3 XJG ´³Æ‰, P ´G ³¼ê, s∗ •³¼ê :. @o, s∗ ´G ˜‡BŸþï:. £Š’¤ ˜‡4Œ e¡ íØ´w, . Corollary 1.4 XJG ´k•³Æ‰, d§•GéMBRA •#•ª/¤ü zƉ, KTüzƉÂñu˜‡BŸþï:. 7 / 36 Ù•, ÃØ´åƽ>|¥ ³¼êé4´Oþ•". e¡ ½nw« Ɖ¥³¼ê aq5Ÿ. §• ^5u ˜‡Æ‰´Ä´³Æ‰. 8 / 36 Theorem 1.5 ˜‡Æ‰G ´³Æ‰, …= éz˜éi, j ∈ N, ÀJ?Û ˜‡a ∈ S−{i,j} , ˜éxi , yi ∈ Si , Ú˜éxj , yj ∈ Sj , þk ci (B) − ci (A) + cj (C) − cj (B) +ci (D) − ci (C) + cj (A) − cj (D) = 0, (3) ùpA = (xi , xj , a), B = (yi , xj , a), C = (yi , yj , a), D = (xi , yj , a). A D B C ã 1: 4£´ [1] D. Monderer, L.S. Shapley, Potential Games, Games and Economic Behavior, Vol. 14, 124-143, 1996. 9 / 36 2. ³ • § !í (\ )³Æ‰¤÷v Ä •§, ¡³•§. 2.1 ˜ ‡ k • Æ ‰G ´ \ ³ Æ ‰, …= • 3(i) P(x1 , · · · , n); (ii) di (x1 , · · · , x̂i , · · · , xn ), i = 1, · · · , n, ùp.̂ L «vkT‘(=, di †xi Ã'); (iii) wi > 0, i = 1, · · · , n, ¦ ci (x1 , · · · , xn ) = wi P(x1 , · · · , xn ) +di (x1 , · · · , x̂i , · · · , xn ), i = 1, · · · , n. (4) P ¡•\ ³¼ê. 10 / 36 ò(4) L«••þ/ª, K Vic nnj=1 xj = wi VP nnj=1 xj + Vid nj6=i xj , n i = 1, · · · , n, (5) n−1 ùpVic , VP ∈ Rk ±9Vid ∈ Rk Ñ´1•þ, ´ƒA¼ê ( •þ. Ïd, u G ´Ä´³Æ‰Ò du(4) ´Ä•3ƒA P Údi . ù du(5) ´Ä•3)VP ÚVid . 11 / 36 ½Â Ψi := Iαi ⊗ 1ki ⊗ Iβi , i = 1, · · · , n, (6) ùp Q α1 = 1, αi = i−1 k, i≥2 Qnj=1 j βn = 1, βi = j=i+1 kj , i ≤ n − 1. @o(5) ÒŒ±L«¤ Vid ΨTi = Vic − wi V p , i = 1, · · · , n. (7) 12 / 36 l(7) )Ñ w1 V P = V1c − V1d ΨT1 . “\(7) Ù¦•§Œ w1 Vid ΨTi − wi V1d ΨT1 = w1 Vic − wi V1c , i = 2, 3, · · · , n. (8) ½Âü|•þXe: ξi := (Vid )T , i = 1, · · · , n, bi−1 := [w1 Vic − wi V1c ]T , i = 2, · · · , n. (9) K(8) ŒLˆ• Ψw ξ = b, (10) 13 / 36 ùp ξ = (ξ1T , · · · , ξnT )T , b = (bT1 , · · · , bTn−1 )T , … −w2 Ψ1 w1 Ψ2 0 ··· −w3 Ψ1 0 w1 Ψ3 · · · Ψw = .. . −wn Ψ1 0 0 ··· 0 0 . w1 Ψn (11) 14 / 36 nܱþ ?ØŒ•: Theorem 2.2 G = (N, S, C) • ˜ k • Æ ‰, |N| = n, |Si | = ki , i = 1, · · · , n. G ´˜‡±{wi > 0 | i = 1, · · · , n} • \ ³Æ‰, …= •§(10) k). ¿…, XJ)•3, K V Pw = 1 c V1 − ξ1T ΨT1 . w1 (12) 15 / 36 Remark 2.3 ¡(10) •³•§. wi = 1, i = 1, · · · , n, \ •³Æ‰. ·‚PÙXꕧ• ³Æ‰C Ψ := Ψw w=1T . n XJPw ÚP̃w ´ -•w ü‡(\ ƉG0 , §ò |G¼êU• c0i = ci , wi @o, Pw ÚP̃w Ñ´G0 )³. ½Â˜‡# i = 1, · · · , n. ³¼ê. Šâ½n1.2, P̃w − Pw = c0 ∈ R. 16 / 36 e¡• œÞ-} -ÙiZ. Example 3.2 •Äü< , 3: Ù. œÞ-} -Ù, |G„L1, L¥: 1: œÞ, 2: } L 1: œÞ-} -Ù |GÝ c\P c1 c2 11 12 13 0 −1 1 0 1 −1 21 1 −1 22 23 0 −1 0 1 31 −1 1 32 1 −1 33 0 0 G ´³Æ‰í? 17 / 36 Example 3.2(cont’d) N´Ž Ψ1 = δ3 [1, 2, 3, 1, 2, 3, 1, 2, 3]T Ψ2 = δ3 [1, 1, 1, 2, 2, 2, 3, 3, 3]T . u´k −1 0 0 1 0 0 0 −1 0 1 0 0 0 0 −1 1 0 0 −1 0 0 0 1 0 0 −1 0 0 1 0 Ψ = [−Ψ1 Ψ2 ] = 0 0 −1 0 1 0 −1 0 0 0 0 1 0 −1 0 0 0 1 0 0 −1 0 0 1 b = V2c − V1c = [0, 2, −2, −2, 0, 2, 2, −2, 0]T . 18 / 36 Example 3.2(cont’d) ØJu : rank(Ψ) = 5 rank[Ψ b] = 6, ³•§Ã). Ïd, œÞ-} -ÙØ´˜‡³Æ‰. 19 / 36 3. ³ • § ( †) Proposition Pk−i = kki , i = 1, · · · , n. u´k iT h T T T ξ0 := w1 1k−1 , w2 1k−2 , · · · , wn 1k−n ´(10) ƒA àg•§ ). =, Ψw ξ0 = 0. w rank(Ψ ) = n X k i=1 §'Ψw ê ki − 1 := rΨ , 1. 20 / 36 Theorem G ∈ G[n;k1 ,k2 ,··· ,kn ] . K±eA: d: (i) G •³Æ‰. (ii) rank[Ψ, b] = n X k i=1 ki − 1. (13) (iii) b ∈ Span Col(Ψ). (14) (iv) ?À i ∈ {1, 2, · · · , n}, b ∈ Span {Colj (Ψ)|j 6= i} . (15) 21 / 36 !ÏLA‡~f`²XÛA^³•§u Example 3.1 ³Æ‰. ˜‡k•Æ‰G, |N| = 3, |Si | = 2, |GÝ „L2. L 2: ~3.1 |GÝ c\p c1 c2 c3 111 a a a 112 b b c 121 b c b 122 d e e 211 c b b 212 221 222 e e f d e f e d f ·‚u é¡Æ‰ G ´Ä•³Æ‰? 22 / 36 Example 3.1(cont’d) |^(6) Œ (δ2 [1, 2, 1, 2])T ⊗ I2 T 0 0 0 1 0 0 0 1 0 0 0 1 0 0 ; 0 1 0 0 0 1 0 0 0 1 0 0 0 1 (16) (δ2 [1, 1, 2, 2])T ⊗ I2 T 0 1 0 0 0 0 0 1 0 1 0 0 0 0 ; 0 0 0 1 0 1 0 0 0 0 0 1 0 1 (17) (δ4 [1, 1, 2, 2, 3, 3, 4, 4])T T 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 = 0 0 0 0 1 1 0 0 . 0 0 0 0 0 0 1 1 (18) Ψ1 = 1 0 = 0 0 Ψ2 = 1 0 = 0 0 Ψ3 = 23 / 36 Example 3.1(cont’d) ÏdŒ −1 Ψ= 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 0 −1 0 0 0 −1 0 0 0 −1 0 0 0 −1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 . 24 / 36 Example 3.1(cont’d) e¡OŽ b1 = (V2c − V1c )T = [0, 0, c − b, e − d, b − c, d − e, 0, 0]T b2 = (V3c − V1c )T = [0, c − b, 0, e − d, b − c, 0, d − e, 0]T . u´ T b = [bT1 bT2 ] = [0, 0, β, β, −α, −β, 0, 0, 0, α, 0, β, −α, 0, −β, 0]T , 25 / 36 Example 3.1(cont’d) ùpα = c − b, β = e − d. ØJu b = (α + β)Col1 (Ψ) + βCol2 (Ψ) + βCol3 (Ψ) +(α + β)Col5 (Ψ) + βCol6 (Ψ) + βCol7 (Ψ) +(α + β)Col9 (Ψ) + βCol10 (Ψ) + βCol11 (Ψ). Šâ½n2.2 Œ•, þ•³Æ‰. |N| = 3 |Si | = 2, i = 1, 2 ž, é¡Æ‰ 26 / 36 Example 3.1(cont’d) e¡, •OŽ³¼ê, ·‚‰ÑäNëê. c = 2, d = −1, e = 1, f = −1. KØJŽÑ a = 1, b = 1, b1 = [V2c − V1c ]T = [0, 0, 1, 2, −1, −2, 0, 0]T b2 = [V3c − V1c ]T = [0, 1, 0, 2, −1, 0, −2, 0]T . )³•§(10), ?¦˜‡)ξ = [3, 2, 2, 0, 3, 2, 2, 0, 3, 2, 2, 0]T . KV1d = ξ1T = [3, 2, 2, 0]. |^(12) Œ 27 / 36 Example 3.1(cont’d) [2,2] VP = V1c − V1d Dr = [1, 1, 1, −1, 2, 1, 1, −1] − [3, 2, 2, 0]δ2 [1, 2, 1, 2] = [−2, −1, −1, −1, −1, −1, −1, −1]. • Œ ³¼ê P(x) = [−2, −1, −1, −1, −1, −1, −1, −1]x + c0 , ùpx = n3i=1 xi ∈ ∆8 . 28 / 36 4. k •Æ ‰ •þ˜m©) + •þ˜m( G[n;k1 ,··· ,kn ] G ∈ G: ci = Vic nnj=1 xj , i = 1, · · · , n. G ∼ (V1c , · · · , Vnc ) ∈ Rnk , k= n Y ki . i=1 29 / 36 + •þ˜m©) G[n;k1 ,··· ,kn ] = | Pp {z⊕ P: Potential H: Harmonic games z N } { Hp . }| ⊕ (19) games 30 / 36 + Non-Strategic N ci (xi , s−i ) − ci (yi , s−i ) = 0, xi , yi ∈ Si , s−i ∈ S−i . + Harmonic H H = P ⊥. [1] D. Cheng, On finite potential games, Automatica, Vol. 50, No. 7, 1793-1801, 2014 (Regular Paper). [2] D. Cheng, T. Liu, K. Zhang,H. Qi, On Decomposed Subspaces of Finite Games, IEEE Trans. Aut. Contr., 61(11), 3651-3656, 2016. 31 / 36 + {¤ Shapley [3]: N = 2, O(k4 ) ; Hofbauer 4]: N = 2, O(k3 ); Hino [5]: N = 2, O(k2 ); Cheng [1]: N = n, Potential Equation; Liu Zhu [6]: N = n, minimum order. Hino (2011): “It is not easy, however, to verify whether a given game is a potential game.” 32 / 36 + References [3] D. Monderer, L.S. Shapley, Potential Games Games and Economic Behavior, Vol. 14, 124-143, 1996. [4] J. Hofbauer, G. Sorger, A differential game approach to evolutionary equilibrium selection, Int. Game Theory Rev., 4, 17-31, 2002. [5] Y. Hino, An improved algorithm for detecting potential games, Int. J. Game Theory, 40, 199-205, 2011. [6] X. Liu, J. Zhu, On potential equation of finite games, Automatica, Vol. 68, 245-253, 2016. 33 / 36 + Ɖ››Øµe [7] Utility Design Potential Games Learning Design ã 2: Game Theoretic Approach [7] R. Gopalakrishnan, J.R. Marden, A. Wierman, An architectural view of game theoretic control, ACM SIGMETRICS, Vol. 38, No. 3, 31-36, 2010. 34 / 36 Š’ 1. •Ä˜šé¡ <Ɖ, |GÝ „L3. L 3: G |GVÝ P1 \P2 1 2 1 2 (1, 3) (2, 2) (3, 4) (4, 3) §´Ä•³Æ‰? XJ´, OŽƒA ³¼ê. 35 / 36 ! Q&A