. . 行列ゲームぜんだおず曽道智 Zeng, Dao-Zhi 東北大学 2015 年 4 月 28 日 1 / 15 行列ゲーム I 戦略形ゲーム (game in strategic form) 標準形ゲーム (game in normal form) 例 B社 A社新製品を販売現状維持新製品を販売現状維持 50%, 50% 30%, 70% 70%, 30% 50%, 50% 定義 G = (N, {Si }i∈N , { fi }i∈N ) N: プレイヤーの集合 Si : プレイヤー i の戦略の集合. ∏ fi : i∈N Si → R, プレイヤー i の利得関数. fi (s1 , · · · , si ) 以上の情報は共有知識 (common knowledge) 2 / 15 行列ゲーム II ゼロ和ゲーム, 定和ゲーム n ∑ fi (s1 , · · · , s n) = K i=1 (双) 行列ゲーム: 有限個の戦略、2 人の場合  ··· (a1n, b1n)  (a11 , b11 )  . .. ..  (ai j , bi j ) .  (a n1 , b n1 ) ··· (a nn, b nn) 囚人のジレンマ, prisoner’s dilemma 囚人 2 黙秘囚人 1 黙秘 5, 5 自白 6, −4      自白 −4, 6 −3, −3 3 / 15 行列ゲーム III 男女の争い battle of the sexes 女ボクシング男ボクシング 2, 1 バレエ −1, −1 バレエ −1, −1 1, 2 4 / 15 Nash 均衡 I プレイヤー i の戦略 si ∈ Si が他の n − 1 人のプレイヤーの戦略の組 s−i = (s1 , · · · , si−1 , si+1 , · · · , s n) に対する最適応答 (best response): fi (si , s−i ) = max fi (t i , s−i ) t i ∈Si 最適応答の全体 Bi (s−i ) Nash 均衡点 s∗ = (s∗1 , · · · , s∗n) ⇔ s∗i ∈ Bi (s∗−i ), ∀i 予想と最適戦略が整合的 (i) すべてのプレイヤーが他のプレイヤーの戦略に対する最適応答となる戦略を選択する (ii) すべてのプレイヤーが他のプレイヤーが選択する戦略を正しく推測するの条件が必要．特に (ii) は厳しい． 5 / 15 Nash 均衡 II 2 人ゼロ和ゲームの場合, 均衡点 = 鞍点 f (s1 , s∗2 ) ≤ f (s∗1 , s∗2 ) ≤ f (s∗1 , s2 ) 存在するも保障されない硬貨合わせゲーム (matching pennies) 兄表裏弟表 −1, 1 1, −1 裏 1, −1 −1, 1 ジャンケン唯一性も保障されない. どちらの均衡を予測する? C D C D A 100, 100 0, 0 A 9, 9 0, 8 B 0, 0 1, 1 B 8, 0 7, 7 6 / 15 Nash 均衡 III E A B C D 100, 100 0, 0 0, 0 0, 0 F G 0, 0 0, 0 0, 0 100, 100 99, 99 0, 0 0, 0 0, 0 H 0, 0 0, 0 0, 0 100, 100 7 / 15 支配戦略 I プレイヤー i の戦略 si が戦略 t i を支配する (dominate) とは、 fi (si , s−i ) > fi (t i , s−i ) が任意の s−i ∈ S−i に対して成り立つことである弱 (い) 支配: > ⇒ ≥ 囚人のジレンマの「自白」が「黙秘」を支配するすべてのプレイヤーに強支配戦略が存在すれば，その組は純粋戦略の範囲においてこのゲームのナッシュ均衡であり，それ以外にはナッシュ均衡は存在しないプレイヤーの戦略が他のすべての戦略を強（弱）支配する場合，強（弱）支配戦略 (dominant strategy) という．強支配される戦略の逐次消去強支配される戦略を除去し、残った戦略だけを用いる戦略形ゲームを考える L M R U 1, 0 1, 2 0, 1 D 0, 3 0, 1 2, 0 8 / 15 支配戦略 II 強支配される戦略を逐次消去する場合，最終的に残る戦略は除去する順番に依存しない．強支配される戦略の逐次消去により，唯１つの戦略の組が残ったとすれば，この戦略の組は純粋戦略の範囲においてこのゲームのナッシュ均衡であり，これ以外にはナッシュ均衡は存在しない．戦略の組が純粋戦略の範囲においてナッシュ均衡であれば，各戦略が強支配される戦略の逐次消去により消去されることはない．弱支配される戦略の逐次消去により，唯１つの戦略の組が残ったとすれば，この戦略の組は純粋戦略の範囲においてこのゲームのナッシュ均衡である．戦略の組 s = (s1 , · · · , s n) がパレート最適 (Pareto optimal) であるとは、 fi (t) > fi (s) となる戦略の組 t ∈ S が存在しないことである。均衡点は必ずしも Pareto optimal ではない 9 / 15 混合戦略 I 純戦略 (pure strategy) 混合戦略 (mixed strategy). 確率的に純戦略を利用 G = (N, {Si }i∈N , { fi }i∈N ) の混合拡大 (mixed extension) G∗ = (N, {Qi }i∈N , {Fi }i∈N ) Qi は Si 上の確率分布の全体である。その要素 qi がプレイヤー i の混合戦略 ∏ Fi : i∈N Qi → R, 期待利得関数 Fi (q1 , · · · , q n) = ∑ s1 ∈S1 ··· n ∑{∏ s n∈S n } q j (s j ) fi (s1 , · · · , s n) j=1 最適応答 Bi (q−i ) = {qi ∈ Qi |Fi (qi , q−i ) = max ri ∈Qi Fi (ri , q−i )} B(q) = B1 (q−1 ) × · · · × B n(q−n) 10 / 15 混合戦略 II 均衡点 q∗ ⇔ q∗ ∈ B(q∗ ) 不動点支配戦略, Pareto 最適も同様混合戦略による実現可能集合 (feasible set) U = {(F1 (q), · · · , F n(q))|q ∈ Q} が有界な閉集合 (compact) 図 2.2, 2.3: 囚人のジレンマ, 男女の争いゲームの実現可能集合 11 / 15 均衡点の存在 Nash 定理 n 人有限ゲーム G において、混合戦略の範囲で少なくとも 1 つの均衡点が存在するミニマックス定理ゼロ和 2 人ゲームにおいて max min F(q1 , q2 ) = min max F(q1 , q2 ) q1 ∈Q1 q2 ∈Q2 q2 ∈Q2 q1 ∈Q1 複数の均衡があるかも。リスク支配による選択 12 / 15 無限ゲーム I 人数が無限, 独占競争への発展戦略数が無限, 連続ゲーム利得関数の連続条件 Melvin Dresher 著 The Mathematics of Games of Stragegy: Theory and Application P.115 両プレーヤーの戦略空間 X = Y = [0, 1] Player 1 の利得関数 f (·, ·) と Player 2 の利得関数 g(·, ·)   0 for x = y    −1 for x = 1, y < 1; and x < y < 1 f (x, y) = − g(x, y) =     +1 for y = 1, x < 1; and y < x < 1. プレーヤー 1 の混合戦略 F(x) とプレーヤー 2 の純戦略 y の対戦によるプレーヤー 1 の利得は、 13 / 15 無限ゲーム II (i) y ∈ (0, 1) の場合に、 ∫ π(F, y) = 1 f (x, y)dF(x) x=0 ∫ y−0 = −1 ∫ 1−0 dF(x) + 1 0 ∫ dF(x) − 1 y+0 1 dF(x) 1−0 = −1 + 2F(1 − 0) − [F(y − 0) + F(y)] ≤ −1 + 2[F(1 − 0) − F(y − 0)]; (ii) y = 0 の場合に、 ∫ π(F, y) = +1 1−0 0+0 ∫ dF(x) − 1 1 dF(x) 1−0 = 2F(1 − 0) − 1 ≥ −1 + 2[F(1 − 0) − F(y − 0)] 14 / 15 無限ゲーム III (iii) y = 1 の場合に、 ∫ 1−0 π(F, y) = +1 ∫ 1 dF(x) − 1 dF 0 1−0 = 2F(1 − 0) − 1 ≥ −1 + 2[F(1 − 0) − F(y − 0)] よって、どんな F(x) とどんな ϵ ∈ (0, 1/2) に対して、 π(F, y0 ) ≤ −1 + ϵ を満たす y0 が存在する。 inf π(F, G) ≤ −1 + ϵ ⇒ sup inf π(F, G) ≤ −1 + ϵ. G G F 同様に、inf G sup F π(F, G) ≥ 1 − ϵ もあるので、 inf sup π(F, G) > sup inf π(F, G) G F F G が成立し混合戦略による均衡は存在しない 15 / 15