Presentation is loading. Please wait.

Presentation is loading. Please wait.

ゲーム理論 第13回 協力ゲーム (1) – コアの理論

Similar presentations


Presentation on theme: "ゲーム理論 第13回 協力ゲーム (1) – コアの理論"— Presentation transcript:

1 ゲーム理論 第13回 協力ゲーム (1) – コアの理論
ゲーム理論 第13回 協力ゲーム (1) – コアの理論 佐賀大学大学院 工学系研究科 知能情報システム学専攻 上田 俊

2 アウトライン 提携形ゲーム 特性関数 利得ベクトルと解概念 コア ブロッキング提携とコア コアの存在条件 コアの精緻化 不満 最小コア,仁

3 協力ゲーム プレイヤー間で拘束力のある合意が可能な場合のプレイヤーの振る舞いに関する理論
プレイヤーがどのような協力関係 (提携) を形成するかという問題 (提携構造形成問題) 提携内で得られた利益 (利得) をどのように配分するかという問題 (提携形ゲームの解概念)

4 ベンチャー企業ゲーム 大学生のA君,B君,C君は卒業後にベンチャー企業を作ろうとしている:
A君とC君なら,15万円.B君とC君なら,10万円. 3人で起業すると,総額24万円の日収になる. さて,誰と一緒に起業して,どのように利益を分配するのがいいだろうか?

5 提携形ゲーム 提携形ゲーム (coalitional game): 𝑁, 𝑣 𝑁= 𝐴, 𝐵, 𝐶 , 𝑣 の例
𝑁= 1,⋯,𝑛 : プレイヤーの集合 𝑆⊆𝑁: 提携 (coalition) 𝑣: 2 𝑁 →ℝ: 特性関数.𝑣 𝑆 は提携 𝑆 のメンバーが協力して得る利得を表す. 𝑁= 𝐴, 𝐵, 𝐶 , 𝑣 の例 𝑣 𝐴 =6, 𝑣 𝐵 =4, 𝑣 𝐶 =2, 𝑣 𝐴𝐵 =20, 𝑣 𝐴𝐶 =15, 𝑣 𝐵𝐶 =10, 𝑣 𝐴𝐵𝐶 =24.

6 優加法性 特性関数 𝑣 が優加法的 (super-additive) であるとは,任意の2つの提携 𝑆,𝑇 𝑠.𝑡. 𝑆∩𝑇=∅ に対して,𝑣 𝑆∪𝑇 ≥𝑣 𝑆 +𝑣 𝑇 が成り立つことである. 特性関数が優加法的である場合,全体提携 (grand coalition) 𝑁 の利得が最も大きくなる. 以下の議論では,特性関数が優加法的であることを仮定し,如何に 𝑣 𝑁 をプレイヤー間で分割するかを考える.

7 戦略的同等性とゲームの正規化 ゲーム 𝑁,𝑣 と 𝑁,𝑣′ が戦略的同等であるとは,正数 𝛼 と実数 𝛽 1 ,⋯, 𝛽 𝑛 が存在して,任意の提携 𝑆 に対して, 𝑣 ′ 𝑆 =𝛼𝑣 𝑆 + 𝑖∈𝑆 𝛽 𝑖 が成り立つことである. 0-正規化: ゲーム 𝑁,𝑣 に対して, 𝑣 ′ 𝑖 =0, 𝑖=1, ⋯,𝑛 を満たす戦略的同等なゲーム 𝑁, 𝑣′ が存在し, 0-正規化ゲームという.

8 利得ベクトルと配分 プレイヤー 𝑖 の利得を 𝑥 𝑖 とし,𝑥= 𝑥 1 ,⋯ 𝑥 𝑛 を利得ベクトル (payoff vector) という. 𝑥 𝑆 = 𝑖∈𝑆 𝑥 𝑖 と書く. 配分 (imputation): 以下の条件を満たす利得ベクトル (の集合) 個人合理性: 𝑥 𝑖 ≥𝑣 𝑖 , 𝑖=1,⋯𝑛 全体合理性: 𝑥 𝑁 =𝑣 𝑁 最も基本的な解概念 (solution concept)

9 基本三角形 高さが 𝑣 𝑁 の 正三角形 各辺への垂線の 長さが分配に対応 三角形の 内側が配分の集合になる. A 𝑣 𝐴𝐵𝐶 𝑥 𝐶 𝑥
高さが 𝑣 𝑁 の 正三角形 各辺への垂線の 長さが分配に対応 𝑣 𝐴𝐵𝐶 三角形の 内側が配分の集合になる. 𝑥 𝐶 𝑥 𝑥 𝐵 𝑥 𝐴 B C

10 解概念 提携形ゲームから利得ベクトルへのマッピング 解が利得ベクトルの集合となるもの 解が一意に定まるもの コア (core)
最小コア 仁 (nucleolus) 核 (kernel) 安定集合 解が一意に定まるもの シャプレイ値 (Shapley value)

11 アウトライン 提携形ゲーム 特性関数 利得ベクトルと解概念 コア ブロッキング提携とコア コアの存在条件 コアの精緻化 不満 最小コア,仁

12 ブロッキング提携とコア 以下の条件を満たすとき,提携 𝑆 は利得ベクトル 𝑥 をブロックするという: 𝑥 𝑆 <𝑣 𝑆
コア: 以下の条件を満たす利得ベクトルの集合 提携合理性: 𝑥 𝑆 ≥𝑣 𝑆 , ∀𝑆⊆𝑁 全体合理性: 𝑥 𝑁 =𝑣 𝑁 配分をブロックする提携がない ⇒ 全体提携から逸脱する誘因をもつ提携がない 安定な配分の集合

13 コアの例 (1/3) 𝑥= 𝑥 𝐴 , 𝑥 𝐵 , 𝑥 𝐶 = 10, 8, 6 を考える. 𝑥 はコアに含まれない.
𝑣 𝐴 =6, 𝑣 𝐵 =4, 𝑣 𝐶 =2, 𝑣 𝐴𝐵 =20, 𝑣 𝐴𝐶 =15, 𝑣 𝐵𝐶 =10, 𝑣 𝐴𝐵𝐶 =24. 𝑥= 𝑥 𝐴 , 𝑥 𝐵 , 𝑥 𝐶 = 10, 8, 6 を考える. 𝑣 𝑁 − 𝑣 𝐴 +𝑣 𝐵 +𝑣 𝐶 =12 を平等に3等分し,個人で得られる利得に加算している. いかにも大丈夫そうな利得の分け方だが…? 𝑥 はコアに含まれない. 提携 𝐴, 𝐵 がブロックする. 𝑥 𝐴𝐵 =18<𝑣 𝐴𝐵 =20 このままでは,AとBは全体提携から逸脱してしまう.

14 コアの例 (2/3) 𝑥′= 11, 9, 4 を考える. 𝑥′ はコアに含まれる.
𝑣 𝐴 =6, 𝑣 𝐵 =4, 𝑣 𝐶 =2, 𝑣 𝐴𝐵 =20, 𝑣 𝐴𝐶 =15, 𝑣 𝐵𝐶 =10, 𝑣 𝐴𝐵𝐶 =24. 𝑥′= 11, 9, 4 を考える. AとBに与える利得が足りなかったので,Cから1ずつ取り上げる. 𝑥′ はコアに含まれる. どの提携も 𝑥′ をブロックしない. 全体合理性を満たしている. このゲームを0-正規化し,基本三角形でコアの領域がどのように表示されるかみてみよう.

15 非空なコア 𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. A
𝑥 𝐶 ≤𝑣 𝐴𝐵𝐶 −𝑣 𝐴𝐵 =2 𝑥 𝐴 ≤8 𝑥 𝐵 ≤5 𝑥′= 5, 5, 2 𝑥= 4, 4, 4 v(A) = 6, v(B) = 4, v(C) = 2 v(AB) = 20, v(AC) = 15, v(BC) = 10 v(ABC) = 24 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = 10, v(AC) = 7, v(BC) = 4 v(ABC) = 12 a, b1, b2, b3 ① 6a+b1=0 (from v(A)) ② 4a+b2=0 (from v(B)) ③ 2a+b3=0 (from v(C)) ④ 20a+b1+b2=10 (from v(AB)) ⑤ 15a+b1+b3=7 (from v(AC)) ⑥ 10a+b2+b3=4 (from v(BC)) ⑦ 24a+b1+b2+b3=12 (from v(ABC)) ①より, b1 = -6a ②より, b2 = -4a ④より, 20a -6a -4a = 10 10a = 10 a = 1 ⇒ b1 = -6, b2 = -4, b3 = -2 ということは... x’=(5, 5, 2)? B C

16 コアの例 (3/3) 𝑣 𝐴𝐵𝐶 =22 と全体提携の利得が2だけ少なくなったゲームを考える. このゲームのコアは空である.
𝑣 𝐴 =6, 𝑣 𝐵 =4, 𝑣 𝐶 =2, 𝑣 𝐴𝐵 =20, 𝑣 𝐴𝐶 =15, 𝑣 𝐵𝐶 =10, 𝑣 𝐴𝐵𝐶 =22. 𝑣 𝐴𝐵𝐶 =22 と全体提携の利得が2だけ少なくなったゲームを考える. このゲームは優加法的なままである. このゲームのコアは空である. どんな配分にも,それをブロックする提携が少なくともひとつ存在する. 分配する利得が足りなくなると,コアが空になってしまう. 同様に0-正規化し,基本三角形で確認!

17 空なコア 𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =10. A
𝑥 𝐶 ≤0 𝑥 𝐵 ≤3 𝑥 𝐴 ≤6 v(A) = 6, v(B) = 4, v(C) = 2 v(AB) = 20, v(AC) = 15, v(BC) = 10 v(ABC) = 22 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = ?, v(AC) = ?, v(BC) = ? v(ABC) = ? a, b1, b2, b3 ① 6a+b1=0 (from v(A)) ② 4a+b2=0 (from v(B)) ③ 2a+b3=0 (from v(C)) ④ 20a+b1+b2=v(AB) (from v(AB)) ⑤ 15a+b1+b3=v(AC) (from v(AC)) ⑥ 10a+b2+b3=v(BC) (from v(BC)) ⑦ 22a+b1+b2+b3=v(ABC) (from v(ABC)) b1 = -6a, b2 = -4a, b3= -2a v(ABC) = 10a v(BC) = 4a v(AC) = 7a v(AB) = 10a B C

18 コアの存在条件 凸ゲーム: 任意の提携 𝑆, 𝑇 に対して,𝑣 𝑆 +𝑣 𝑇 ≤𝑣 𝑆∪𝑇 +𝑣 𝑆∩𝑇 が成立するゲーム.ただし,𝑆∩𝑇=∅ の場合,𝑣 ∅ =0 とする. 定理 凸ゲームのコアは非空である. 定理 コアが非空であるための必要十分条件は,次の線形計画問題 min 𝑥 𝑁 𝑠.𝑡. 𝑥 S ≥𝑣 𝑆 , ∀𝑆⊂𝑁 の最小値 𝑧 ∗ が 𝑧 ∗ ≤𝑣 𝑁 を満たすことである.

19 アウトライン 提携形ゲーム 特性関数 利得ベクトルと解概念 コア ブロッキング提携とコア コアの存在条件 コアの精緻化 不満 最小コア,仁

20 不満 利得ベクトル 𝑥 に対して提携 𝑆 が持つ不満 (excess) を 𝑒 𝑆, 𝑥 =𝑣 𝑆 −𝑥 𝑆 とする.
𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. 利得ベクトル 𝑥 に対して提携 𝑆 が持つ不満 (excess) を 𝑒 𝑆, 𝑥 =𝑣 𝑆 −𝑥 𝑆 とする. 正の不満を持つとき,その提携はその利得ベクトルをブロックする. コアに属する利得ベクトルでは,不満は0か負の値になっている. 𝑥= 4,4,4 に対して, 提携 𝐴,𝐶 は,𝑒 𝐴𝐶, 𝑥 =10−8=2 の不満を持つ. 提携 𝐵,𝐶 は,𝑒 𝐵𝐶, 𝑥 =4−8=−4 の不満を持つ.

21 𝜀-コアと最小コア コアの提携合理性条件を,不満を使って緩和する. 𝜀-コア:以下の条件を満たす利得ベクトルの集合
𝑒 𝑆,𝑥 ≤𝜀, ∀𝑆⊆𝑁 𝑥 𝑁 =𝑣 𝑁 最小コア: 非空な𝜀-コアの中で,𝜀 が最小のもの コアが非空である場合,𝜀 は負の値になり得る. 𝜀-コアや最小コアでは,個人合理性も緩和されていることに注意. 全体合理性だけを満たす利得ベクトルを準配分 (preimputation) と呼ぶ.

22 𝜀=1コア 𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =10. A 𝑥 𝐶 ≤1 𝑥 𝐵 ≤4 𝜀=1 𝑥 𝐴 ≤7 𝜀=1 𝑥′= 5, 4, 1 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = 10, v(AC) = 7, v(BC) = 4 v(ABC) = 10 εコアを調べる... ε=1の場合, xa + xb + xc = 10 xa >= -1, xb >= -1, xc >= -1 10 – xa – xb <= 1 9 <= xa + xb 9 <= (10 - xc) xc <= 1 7 – xa – xc <= 1 6 <= xa + xc 6 <= (10 - xb) xb <= 4 4 – xb – xc <= 1 3 <= (10 - xa) xa <= 7 x = (10, 8, 4) -> 0-正規化 -> (4, 4, 2) x = (5, 4, 1)? 𝜀=1 B C

23 安定性 vs. 公平性 コアは安定な解概念であると言われている. コアでは,プレイヤー間の分配のバランスをそこまで最適化していない.
𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. コアは安定な解概念であると言われている. 全体提携から逸脱する誘因をもつ提携が存在しない,“安定な”解 (の集合) コアでは,プレイヤー間の分配のバランスをそこまで最適化していない. 公平な解にはなっていない可能性がある. 例えば,𝑥= 5, 5, 2 はBとCがもらい過ぎ? 提携 𝐴,𝐵 と 𝐴,𝐶 の不満は 0 対して,提携 𝐵,𝐶 の不満は -3

24 非空なコア (再掲) 𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. A 𝑥 𝐶 ≤𝑣 𝐴𝐵𝐶 −𝑣 𝐴𝐵 =2 𝑥 𝐴 ≤8 𝑥 𝐵 ≤5 Aへの分配を多くして, より公平な配分にしたい. 𝑥= 5, 5, 2 v(A) = 6, v(B) = 4, v(C) = 2 v(AB) = 20, v(AC) = 15, v(BC) = 10 v(ABC) = 24 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = 10, v(AC) = 7, v(BC) = 4 v(ABC) = 12 a, b1, b2, b3 ① 6a+b1=0 (from v(A)) ② 4a+b2=0 (from v(B)) ③ 2a+b3=0 (from v(C)) ④ 20a+b1+b2=10 (from v(AB)) ⑤ 15a+b1+b3=7 (from v(AC)) ⑥ 10a+b2+b3=4 (from v(BC)) ⑦ 24a+b1+b2+b3=12 (from v(ABC)) ①より, b1 = -6a ②より, b2 = -4a ④より, 20a -6a -4a = 10 10a = 10 a = 1 ⇒ b1 = -6, b2 = -4, b3 = -2 ということは... x’=(5, 5, 2)? B C

25 不満ベクトル 𝜃 𝑥 = 𝑒 𝑆 1 ,𝑥 ,𝑒 𝑆 2 ,𝑥 ,⋯,𝑒 𝑆 𝐾 ,𝑥 , 𝐾= 2 𝑛 −1
𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. 𝜃 𝑥 = 𝑒 𝑆 1 ,𝑥 ,𝑒 𝑆 2 ,𝑥 ,⋯,𝑒 𝑆 𝐾 ,𝑥 , 𝐾= 2 𝑛 −1 ただし,𝑒 𝑆 1 ,𝑥 ≥𝑒 𝑆 2 ,𝑥 ≥⋯≥𝑒 𝑆 𝐾 ,𝑥 𝑥= 5, 5, 2 の不満ベクトルは以下の通り: 𝜃 𝑥 = 0,0,0,−2,−3,−5, −5 利得ベクトル 𝑥, 𝑦 に対して,𝑦 が 𝑥 よりも受容的 (acceptable) であるとは,𝜃 𝑦 が 𝜃 𝑥 よりも辞書式順序の意味で小さい (𝜃 𝑦 < 𝐿 𝜃 𝑥 と書く) ときをいう. 𝑦= 7,4,1 の不満ベクトルと比較してみる: 𝜃 𝑦 = 0, −1, −1, −1, −1, −4, −7 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = 10, v(AC) = 7, v(BC) = 4 v(ABC) = 12 e(A, x) = -5, e(B, x) = -5, e(C, x) = -2 e(AB, x) = 0, e(AC, x) = 0, e(BC, x) = -3 e(ABC, x) = 0 e(A, x) = -7, e(B, x) = -4, e(C, x) = -1 e(AB, x) = -1, e(AC, x) = -1, e(BC, x) = -1

26 仁 仁: 以下の条件を満たす配分の集合 性質: 𝑥∈𝑋 𝜃 𝑥 ≤ 𝐿 𝜃 𝑦 , ∀𝑦∈𝑋 ただし,𝑋 は配分の集合
𝑥∈𝑋 𝜃 𝑥 ≤ 𝐿 𝜃 𝑦 , ∀𝑦∈𝑋 ただし,𝑋 は配分の集合 性質: 必ず存在し,最小コアに含まれる. 線形計画問題を繰り返し解くことで求めることができる. 最大不満を最小化,その次に大きい不満を最小化… 計算量は絶望的 あまり,情報学分野では扱われない.

27 まとめ 特性関数 仁 (⊆ 最小コア) コア 基本三角形
𝑣 𝐴 =0 𝑣 𝐵 =0, 𝑣 𝐶 =0, 𝑣 𝐴𝐵 =10, 𝑣 𝐴𝐶 =7, 𝑣 𝐵𝐶 =4, 𝑣 𝐴𝐵𝐶 =12. A 𝑥 𝐶 ≤𝑣 𝐴𝐵𝐶 −𝑣 𝐴𝐵 =2 特性関数 仁 (⊆ 最小コア) 𝑥 𝐴 ≤8 𝑥 𝐵 ≤5 𝑦= 7, 4, 1 コア 𝑥= 5, 5, 2 基本三角形 v(A) = 6, v(B) = 4, v(C) = 2 v(AB) = 20, v(AC) = 15, v(BC) = 10 v(ABC) = 24 v(A) = 0, v(B) = 0, v(C) = 0 v(AB) = 10, v(AC) = 7, v(BC) = 4 v(ABC) = 12 a, b1, b2, b3 ① 6a+b1=0 (from v(A)) ② 4a+b2=0 (from v(B)) ③ 2a+b3=0 (from v(C)) ④ 20a+b1+b2=10 (from v(AB)) ⑤ 15a+b1+b3=7 (from v(AC)) ⑥ 10a+b2+b3=4 (from v(BC)) ⑦ 24a+b1+b2+b3=12 (from v(ABC)) ①より, b1 = -6a ②より, b2 = -4a ④より, 20a -6a -4a = 10 10a = 10 a = 1 ⇒ b1 = -6, b2 = -4, b3 = -2 ということは... x’=(5, 5, 2)? B C

28 成績評価について 小レポート 1, 2, 3, 4, 6, 7, 9, 10, 11, 12: 各2点 = 合計20点 中間レポート 40点
小レポート 1, 2, 3, 4, 6, 7, 9, 10, 11, 12: 各2点 = 合計20点 中間レポート 40点 期末レポート 50点 2/6 (木) 23:59 JST 時点で60点未満の学生には 2/7 (金) 中に LiveCampus or で連絡 2/14 (金) 23:59 JST が全レポートの締切


Download ppt "ゲーム理論 第13回 協力ゲーム (1) – コアの理論"

Similar presentations


Ads by Google