議会における政党のパワーをゲーム理論から見ると？

Size: px

Start display at page:

Download "議会における政党のパワーをゲーム理論から見ると？"

こうざぶろうしどり
7 years ago
Views:

1 マッチング 1 対 1 マッチング - 結婚ゲーム, 仕事の割り当て多対 1 マッチング - インターンの病院への割り当て, 内部進学者の学部への配属学科所属, 研究室所属

2 結婚ゲーム例男性,, 女性,, : > >, : > >, : > > : > >, : > >, : > > どのようなペアの集まり ( マッチング ) が安定か? µ = : > (, ) のペアでは, ともによくなる : > 安定ではない υ =,, ベストな相手とペアどのペアもよくならない安定である

3 結婚ゲーム ( 定式化 ) M = {m 1,, m p } 男性の集合 N = {w 1,, w q } 女性の集合仮定 : p = q (p q の場合は後述 ) 各 m i は W の上に選好順序 > mi をもつ各 w k は M の上に選好順序 > wk をもつ仮定 : 無差別はない結婚ゲーム : (M, W, {> mi } mi M, {> wk } wk W )

4 マッチング結婚ゲーム : (M, W, {> mi } mi M, {> wk } wk W ) マッチング µ : W M 全単射 w µ(w) m µ -1 (m) µ = w 1 w p µ(w 1 ) µ(w p )

5 安定なマッチング 2 つのマッチング µ = w 1 w k w p µ(w 1 ) µ(w k ) µ(w p ) = m i υ = w 1 w k υ -1 (m i ) w p υ(w 1 ) υ(w k ) m i υ(w p ) µ が υ を (w k, m i ) を通して支配する ( (w k, m i ) は υ をブロックする ) µ(w k ) = m i, m i > wk υ(w k ), w k > mi υ -1 (m i ) µ が υ を支配するあるペア (w k, m i ) が存在して µ が υ を (w k, m i ) を通して支配する

6 コア結婚ゲームのコア = {µ µ を支配するマッチングが存在しない } 一般のコア : 任意の提携 S M W に関して µ を支配するマッチングが存在しない結婚ゲームのコア : 任意のペア (w k, m i ), w k W, m i M に関して µ を支配するマッチングが存在しない結婚ゲームにおいて : 任意の提携 S M W に関して µ を支配するマッチングが存在しない,???

7 コア結婚ゲームのコア : 任意のペア (w k, m i ), w k W, m i M に関して µ を支配するマッチングが存在しない結婚ゲームにおいて : 任意の提携 S M W に関して µ を支配するマッチングが存在しない = : 明らか (S として (w k, m i ) をとればよい ) : µ, µ とする µ υ, S υ において, すべての i S が µ より好ましい相手とペア w k S W, m i S M をとると, υ は µ を (w k, m i ) に関して支 µ に矛盾

8 コアに属するマッチングを求めるアルゴリズム ( ゲールシャープレイのアルゴリズム ) 男性側女性側例男性,, 女性,, : > >, : > >, : > > : > >, : > >, : > >

9 コアに属するマッチングを求めるアルゴリズム ( ゲールシャープレイのアルゴリズム ) 例男性,, 女性,, : > >, : > >, : > > : > >, : > >, : > > 男性側女性側ゲールシャープレイのアルゴリズム安定なマッチング, ベスト : は > は > ブロックするペアなし

10 ゲールシャープレイのアルゴリズム第 1ステップ : すべての男性は最も好ましい女性にプロポーズ各女性は自分にプロポーズした男性のうち最も好ましい人をリストに残しあとは拒否拒否された男性がいなければ終了 : > >, : > >, : > > : > >, : > >, : > > 第 2ステップ : 拒否された男性は拒否された女性の次に好ましい女性にプロポーズ各女性は自分にプロポーズした男性をリストに入れ, その中で最も好ましい人を選びあとは拒否拒否された男性がいなければ終了第 3ステップ, 第 4ステップ,

11 ゲールシャープレイのアルゴリズム必ずマッチングに到達するもし, すべての女性に拒否し続けられた男性がいたとすると, 男女同数ゆえ, ペアを組めなかった女性が存在する彼女にプロポーズした男性存在しない矛盾アルゴリズムは有限回のステップで終了するあるステップで終了しなければ, 拒否された男性が存在次のステップで拒否された次に好ましい女性にプロポーズ女性の数は有限, すべての女性に拒否されることはない, 有限回のステップで終了

12 ゲールシャープレイのアルゴリズム到達したマッチングは安定である ( コアに属する ) 到達したマッチングを µ = w 1 w µ -1 (m) w p とし µ(w 1 ) µ(w) m µ(w p ) (w, m) が µ をブロックするとする m > w µ(w), w > m µ -1 (m) m > w µ(w) ゆえ,m は w にプロポーズしていない (*) m は µ -1 (m) とペアを作っている µ -1 (m) より好ましい女性からはすべて拒否されている w > m µ -1 (m) ゆえ w にこれまでにプロポーズしていたはずである (*) に矛盾

13 男性最適なマッチングと女性最適なマッチング男性,, 女性,, : > >, : > >, : > > : > >, : > >, : > > 男性側女性側女性側男性側

14 男性最適なマッチングと女性最適なマッチング男性,, 女性,, : > >, : > >, : > > : > >, : > >, : > > 男性側女性側 µ = 女性側男性側 υ = 男性 : : =, : >, : > µ のほうが良い女性 : : >, : =, : > υ のほうが良い

15 男性最適なマッチングと女性最適なマッチング安定なマッチング µ = w 1 µ -1 (m) w p が男性最適 ( 最悪 ) µ(w 1 ) m µ(w p ) 任意の安定なマッチング υ = w 1 υ -1 (m) w p に対して υ(w 1 ) m υ(w p ) m M µ -1 (m) υ -1 (m) µ -1 (m) > m υ -1 (m) (µ -1 (m) < m υ -1 (m) ) 安定なマッチング µ = w 1 w w p が女性最適 ( 最悪 ) µ(w 1 ) µ(w) µ(w p ) 任意の安定なマッチング υ = w 1 w w p に対して υ(w 1 ) υ(w) υ(w p ) w W µ(w) υ(w) µ(w) > w υ(w) (µ(w) < w υ(w) )

16 男性最適なマッチングと女性最適なマッチング男性側がプロポーズゲールシャープレイのアルゴリズム男性最適 ( 女性最悪 ) なマッチング女性側がプロポーズゲールシャープレイのアルゴリズム女性最適 ( 男性最悪 ) なマッチング

17 男性最適なマッチングと女性最適なマッチング男性側がプロポーズ男性最適なマッチング ( 証明 ) ゲールシャープレイのアルゴリズムにより到達したマッチング µ* µ* において, すべての男性に対し, このアルゴリズムで拒否された女性とのペアを含む安定なマッチングは存在しないを証明する µ* において, すべての男性が安定マッチングの中で最も好ましい女性とペア帰納法 : 第 1ステップそれ以前に拒否された男性なし第 kステップにおいて, すべての男性にとって, それ以前のステップで拒否された女性とのペアを含む安定なマッチングは存在しないと仮定第 k+1ステップ : 第 kステップで,w が m を拒否したとし, (w, m) はいかなる安定なマッチングにも含まれないことを示す

18 男性最適なマッチングと女性最適なマッチング帰納法 : 第 1ステップそれ以前に拒否された男性なし第 kステップにおいて, すべての男性にとって, それ以前のステップで拒否された女性とのペアを含む安定なマッチングは存在しないと仮定第 k+1ステップ : 第 kステップで,w が m を拒否したとし, (w, m) はいかなる安定なマッチングにも含まれないことを示す w がキープしていた男性を m とすると,m > w m m は w にプロポーズ w より好ましい女性からは拒否帰納法の仮定 w より好ましい女性とのペアを含む安定なマッチングなし (w, m) を含む安定なマッチング µ が存在すると仮定矛盾を示す

19 男性最適なマッチングと女性最適なマッチング第 k+1ステップ : 第 kステップで,w が m を拒否したとし, (w, m) はいかなる安定なマッチングにも含まれないことを示す w がキープしていた男性を m とすると,m > w m (*) m は w にプロポーズ w より好ましい女性からは拒否帰納法の仮定 w より好ましい女性とのペアを含む安定なマッチングなし (**) (w, m) を含む安定なマッチング µ が存在すると仮定矛盾を示す µ =.. w µ -1 (m ).... m m.. µ 安定ゆえ,(**) から w > m µ -1 (m ) (*) と合わせ (w, m ) は µ をブロック µ が安定であることに矛盾 ( 証明終 )

20 男性最適なマッチングと女性最適なマッチング男性最適なマッチングが女性最悪であることの証明到達した男性最適な安定なマッチングを µ とし, 任意の安定なマッチング µ をとる µ =.. w µ -1 (m ).... m m.. µ =.. w µ -1 (m ).... m m.. 任意の w に対して, m(=µ(w)) m (=µ (w)) m > w m を示せばよい m > w m と仮定 µ が男性最適 w > m µ -1 (m ) m > w m と合わせ,(w, m) が µ をブロック µ が安定であることに矛盾 ( 証明終 )

21 男性と女性の人数が異なる場合男性,, 女性, 独身でいる状態を s で表す : > > s, : > > s, : > s > : > > > s, : > s > > 男性女性男性 : s より好ましくない女性にはプロポーズしない女性 : s より好ましくない男性はプロポーズされてもリストに載せず拒否 s s s ゲールシャープレイのアルゴリズム若干修正して適用可能

22 戦略的な行動をとる場合 (85-86 ページ ) 男性,, 女性,,, d : d > >,, d, s : > d >,, s : >,. d, s : >,, s : >,, s : s >,, d : > >, s ゲールシャープレイアルゴリズム d : > s >, d d d は選好を偽ることにより, よりよいとペアを作れる

23 多対一のマッチング内部進学者の学部への配属 S : 内部進学者の集合, s S の D に関する選好 > s D : 学部の集合, d D の S に関する選好 > d 受け入れ可能人数 q d ゲールシャープレイのアルゴリズム 1 学生は自分の好ましい学部から順にプロポーズする 2 学部は q d までリストにキープする 3 学生数が q d を超えたら, > d に基づいて拒否する学生最適なマッチングに到達する実際の適用例 : アメリカにおけるインターンの病院への配属 (88ページから91ページ) 日本のある大学における付属高校からの進学者の学部への振り分け東工大の学科所属, 研究室所属???

24 2 つのサイドに分けられない場合 ( ルームメイト問題 ) ルームメイト問題 :,,, D の 4 人の寮生を 2 人ずつ 2 部屋に分ける各寮生の好み : : > > D, : > > D, : > > D, D: > > コアは空 : (D, ) (, ) ブロック (D, ) (, ) ブロック (D, ) (, ) ブロック

25 2 つのサイドに分けられない場合 ( 非分割財の交換 ) 非分割財の交換 :,,, D が非分割財 ( 家など ) を持っており, 各人の好みは : > > D >, : > > D >, : > > D >, D: > > > D であるシャープレイスカーフのアルゴリズム ( トップトレーディングサイクル ) 第 1ステップ : 各プレイヤーは自分の最も好む財を指定サイクルができればその中のプレイヤーは財を交換して退出第 2ステップ : 残ったプレイヤーはその中で自分の最も好む財を指定サイクルができればその中のプレイヤーは財を交換して退出以下同様

26 トップトレーディングサイクル : > > D >, : > > D >, : > > D >, D: > > > D シャープレイスカーフのアルゴリズム ( トップトレーディングサイクル ) 第 1 ステップ : 各プレイヤーは自分の最も好む財を指定サイクルができればその中のプレイヤーは財を交換して退出第 2 ステップ : 残ったプレイヤーはその中で自分の最も好む財を指定サイクルができればその中のプレイヤーは財を交換して退出以下同様 D トップトレーディングサイクル有限回で終了しコアを導く

27 次回までの課題 1. 以下の選好を持つマッチングゲームにおいて男性側からプロポーズする場合と女性側からプロポーズする場合のそれぞれにおいてゲールシャープレイのアルゴリズムによって得られるマッチングを求め, コアに属することを確かめよ,, は男性であり,,, は女性である s は独身の状態を表す () : > > > s, : > > > s, : > > > s : > > > s, : > > > s, : > > >s () : > > s >, : > > s >, : > > s > : > > > s, : > > > s, : > > >s

Microsoft PowerPoint - 13基礎演習C_ITプランナー_2StableMatching.pptx

Microsoft PowerPoint - 13基礎演習C_ITプランナー_2StableMatching.pptx 2013/4,5,6,7 Mon. 浮気しない? カップル 6 人の男女がいます. 少子化対策? のため,6 組のカップルを作り結婚させちゃいましょう. でも各自の好き嫌いを考えずに強引にくっつけちゃうと, 浮気する人が出るかもしれません. 浮気しないように 6 組のカップルをつくれますか? どうすれば浮気しないの? 浮気しないってどういうこと? 浮気ってどういう状況で起こる? 浮気するしないを

議会における政党のパワーを ゲーム理論から見ると？

議会における政党のパワーをゲーム理論から見ると？