制度設計（メカニズムデザイン）・市場設計（マーケットデザイン）の ご利益：マッチング理論を例にして 制度を「うまく」つくって，「望ましい」結果を達成したい！ 本日の授業内容は 坂井豊貴（2013）『マーケットデザイン』ちくま新書 の第二章「両想いの実現」 の簡単な紹介． ・人と人あるいは人と組織との「望ましい」組合せとは？ ・「望ましい」組合せを達成する方法は？ 1 本日は，ゼミの配属の問題， つまり学生と教員との組合せの問題を考える． ３人の学生：学生１，２，３ ４人の教員：教員４，５，６，７ ・ゼミは必修ではない． ・各教員の受入れ学生数は多くても１名（誰も受入れなくてもよい）． よって， ・どのゼミにも属さない学生が出てくることを許す． 学生の教員に対する希望順位と，教員の学生に対する希望順位とは， 次の表で表せるとする． 2 学生の希望順位 １位 ２位 ３位 ４位 ５位 学生１ ４ ５ ７ ０ ６ 学生２ ５ ６ ４ ０ ７ ここで，「０」は「ゼミに 学生３ ４ ７ ０ ６ ５ 入らない」を意味する． 教員の希望順位 １位 ２位 ３位 ４位 教員４ ３ ２ １ ０ 教員５ ３ １ ２ ０ 教員６ ３ １ ０ ２ ここで，「０」は「学生を受入れ 教員７ １ ２ ０ ３ ない」を意味する． 3 ●神戸大学経済学部のゼミ配属方式（のイメージ） 学生には２回の応募機会がある．（実際の方式では３回．） 【応募１回目】 ・各学生は，教員１人に応募する（ゼミに入らない「０」でも可）． ・各教員は，応募者がいる場合には，その中から学生１人を受入れる （学生を受入れない「０」でも可）． （実際の方式では定員未充足の場合は受入れなければなりません．） 【応募２回目】 ・１回目でゼミが決まらなかった各学生は，１回目で受入れ学生が 誰もいなかった教員１人に応募する（ゼミに入らない「０」でも可）． ・各教員は，応募者がいる場合には，その中から学生１人を受入れる （学生を受入れない「０」でも可）． 4 学生と教員が，希望順位に 素直に行動すると．．． 【応募１回目】 ・学生１と学生３が教員４に応募し， 教員４は学生３を受入れる． ・学生２は教員５に応募し， 教員５は学生２を受入れる． 【応募２回目】 ・学生１が教員７に応募し， 教員７は学生１を受入れる． 最終的に，（学生１，教員７），（学生２，教員５），（学生３，教員４）の組が でき，教員６はゼミ生なし．このような組合せのことをマッチングとよぶ． 5 ◆神戸大学経済学部のマッチング方式の問題点 問題点１．「抜け駆け」が生じる． ・学生１は教員７と組になっているが， 学生１は，教員７よりも，教員５の方が好ましい． ・教員５は学生２と組になっているが， 教員５は，学生２よりも，学生１の方が好ましい． → 学生１と教員５とで「抜け駆け」が生じる． 「抜け駆け」が生じるマッチングでは， ①そのようなマッチングを阻止する動きが起こる可能性がある； ②「両想い」の組合せをつくることに失敗している． 「抜け駆け」が生じないマッチングのことを安定的なマッチングという． 6 問題点２．希望順位について「戦略的操作」が生じる． 学生１が，学生３との競合を避けるために，自分の希望順位があたかも 以下の嘘の希望順位であるように振る舞うことで得をする． １位 ２位 ３位 ４位 ５位 学生１の本当の希望順位 ４ ５ ７ ０ ６ 学生１の嘘の希望順位 ５ ４ ７ ０ ６ 【応募１回目】 ・学生１と学生２が教員５に応募し， 教員５は学生１を受入れる． 学生１は，本当のことをいうと教員７と組になり， 上の嘘をつくと教員５と組になる． よって，嘘をつくことで（本当の希望順位で見て）得をしている． 7 希望順位について「戦略的操作」が生じるマッチング方式では， ①各学生の意思決定（どのような希望順位で振る舞うか）が複雑になる； ②戦略的操作の結果，本当の希望順位で見て，「両想い」でない 組合せが生じる可能性がある． 希望順位について「戦略的操作」が生じないことを「耐戦略性」という． ↓ ・耐戦略性を満たし， ・学生・教員がどのような希望順位を持つ場合にも 安定的なマッチングを達成する マッチング方式を設計する． 8 ●受入保留方式（ゲール＝シャプリー・アルゴリズム） Gale, D. and L. S. Shapley (1962) “College Admissions and the Stability of Marriage,” American Mathematical Monthly, Vol. 69, pp. 9-15. 受入保留方式のポイント 応募の各回において，「受入れ」ではなく，「仮受入れ」を行う． 以下では，各ステップにおいて，学生に応募先を表明させたり， 教員に仮受入れする学生を表明させているように話を構成している． しかし，実際は，予め学生と教員の希望順位を提出させておけば， 後は受入保留方式で自動的に処理することが可能である． 9 【ステップ１】 ・各学生は，希望順位が１位の教員に応募する（ゼミに入らない「０」でも 可）． ・各教員は，応募者がいる場合には，その中から最も希望順位の高い 学生１人を仮受入れする（学生を受入れない「０」でも可）． ・学生１と学生３は教員４に応募し， 教員４は学生３を仮受入れする． 学生１は仮受入れを拒否される． ・学生２は教員５に応募し， 教員５は学生２を仮受入れする． 10 【ステップ２】破線（赤色） ・前回のステップで仮受入れを拒否された各学生は，これまでに 仮受入れを拒否されていない中で希望順位が最も高い教員に応募する （ゼミに入らない「０」でも可）． ・各教員は，仮受入れ中の学生と新たな応募者（ただし，それらがいる 場合）の中から，最も希望順位の高い学生１人を仮受入れする （学生を受入れない「０」でも可）． ・学生１は教員５に応募し， 教員５は学生１と仮受入れ中の学生２の中から 学生１を新たに仮受入れする． 学生２は仮受入れを拒否される（解かれる）． 11 【ステップ３】一点鎖線（青色） これ以降のステップはステップ２と同様． ・学生２は教員６に応募し， 教員６は学生２の仮受入れを拒否する． 【ステップ４】点線（緑色） ・学生２は教員４に応募し， 教員４は学生２と仮受入れ中の学生３から 学生３を継続して仮受入れする． 学生２は仮受入れを拒否される． 12 【ステップ５】長破線（紫色） ・学生２は，教員７にはまだ仮受入れを 拒否されていないが，教員７よりも ゼミに入らない「０」の方がよいので， ゼミに入らない． 仮受入れを拒否された（つまり，新たに 応募する）学生がいないので，プロセスは終わり． 最終的に， ・（学生１，教員５），（学生３，教員４）の組ができ， ・学生２はゼミに入らず， ・教員６と教員７はゼミ生なし． 13 ◆受入保留方式で得られるマッチングは安定的である． p. 13で得られたマッチングは，抜け駆けが生じないので，安定的である． 学生の希望順位 １位 ２位 ３位 ４位 ５位 学生１ ４ ⑤ ７ ０ ６ 学生２ ５ ６ ４ ⓪ ７ 学生３ ④ ７ ０ ６ ５ 教員の希望順位 ○で囲まれた番号は， １位 ２位 ３位 ４位 教員４ ③ ２ １ ０ p. 13 で得られたマッチングで 教員５ ３ ① ２ ０ できた組での相手を表してい 教員６ ３ １ ⓪ ２ る（ただし，０は誰とも組に 教員７ １ ２ ⓪ ３ なっていない状態を表す）． 14 学生側から見て，抜け駆けの相手を探そうとしても，見つからない． ・学生１にとって組になっている教員５よりも好ましいのは教員４だけだが， 教員４にとっては，学生１よりも，組になっている学生３が好ましい． ・学生２にとってゼミに入らないよりも好ましいのは教員４・５・６だが， 教員４にとっては，学生２よりも，組になっている学生３が好ましく， 教育５にとっては，学生２よりも，組になっている学生１が好ましく， 教員６にとっては，学生２よりも，ゼミ生なしが好ましい． ・学生３にとって教員４は最も好ましい． 学生側から見て抜け駆けの相手が見つからないということは， 教員側から見ても抜け駆けの相手を見つけることはできない． 注意．受入保留方式において，教員が応募する（学生を勧誘する） 場合に得られるマッチングも安定的である． 15 ◆受入保留方式は，応募する側には希望順位について「戦略的操作」が 生じない，つまり（応募側の）片側耐戦略性を満たす． （教員が学生を勧誘する場合も同様．） 例えば，p. 13 で得られたマッチングを見ると， 神戸大学経済学部のマッチング方式において， 嘘の希望順位であるように振る舞うことで得をした学生１は， 受入保留方式で教員５の希望順位を２位としても， 教員５と組になれるので，嘘をつく必要がなくなっている． 注意．応募される側には「戦略的操作」が生じうる． つまり，受入保留方式は両側耐戦略性を満たさない． 16 ●受入保留方式の拡張版 ここまで，一対一のマッチングを考えてきた． でも，通常は教員（ゼミ）の受入れ学生数は複数では？ → 一対多のマッチングを考えなければならない → 教員の受入れ学生数を増やして，受入保留方式を適用する ６人の学生：学生１，２，３，４，５，６ ２人の教員（ゼミ）：教員７，８ 各教員の受入れ学生数は２名まで（誰も受入れなくてもよい）とする． 学生の教員に対する希望順位と，教員の学生に対する希望順位は， 次の表で表せるとする． 17 学生の希望順位 １位 ２位 ３位 学生１ ７ ８ ０ 前と同様に，「０」は 学生２ ８ ７ ０ 「ゼミに入らない」 学生３ ７ ０ ８ あるいは 学生４ ７ ０ ８ 「（順位が０より低い）学生を 学生５ ７ ８ ０ 受入れない」 学生６ ８ ７ ０ ことを意味する． 教員の希望順位 １位 ２位 ３位 ４位 ５位 ６位 ７位 教員７ ３ ２ ６ ４ ５ ０ １ 教員８ ３ １ ６ ５ ４ ０ ２ 18 【ステップ１】 ・学生１，３，４，５は教員７に応募し， 教員７は学生３，４を仮受入れする． 学生１，５は仮受入れを拒否される． ・学生２，６は教員８に応募し， 教員８は学生６を仮受入れする． 学生２は仮受入れを拒否される． 19 【ステップ２】破線（赤色） ・学生１，５は教員８に応募し， 教員８は，学生１，５と 仮受入れ中の学生６の中から， 学生６の仮受入れを継続し， 学生１を新たに仮受入れする． 学生５は仮受入れを拒否される． ・学生２は教員７に応募し， 教員７は，学生２と 仮受入れ中の学生３，４の中から， 学生３の仮受入れを継続し， 学生２を新たに仮受入れする． 学生４は仮受入れを拒否される（解かれる）． 20 【ステップ３】一点鎖線（青色） ・学生４は，教員８にはまだ仮受入れを 拒否されていないが，教員８よりも ゼミに入らない「０」の方がよいので， ゼミに入らない． ・学生５は，既に教員７・８に仮受入れを 拒否されているので， ゼミに入らない「０」を選ぶしかない． 仮受入れを拒否された（つまり， 新たに応募する）学生がいないので， プロセスは終わり． 最終的に， ・（学生２・３，教員７），（学生１・６，教員８）の組ができ， ・学生４と学生５はゼミに入らない． 21 ◆受入保留方式の拡張版で得られるマッチングも安定的である． 学生の希望順位 p. 21で得られたマッチングは，抜け駆 １位 ２位 ３位 けが生じないので，安定的である． 学生１ ７ ⑧ ０ 学生２ ８ ⑦ ０ （簡単なので）教員側から抜け駆けの 学生３ ⑦ ０ ８ 学生４ ７ ⓪ ８ 学生５ ７ ８ ⓪ 学生６ ⑧ ７ ０ 可能性をみてみる． ・教員７は抜け駆けしたいと思わない． ・教員８は学生３と抜け駆けしたいが， 学生３は組になっている教員７がよい． 研究室が持つ希望順位 １位 ２位 ３位 ４位 ５位 ６位 ７位 教員７ ③ ② ６ ４ ５ ０ １ 教員８ ３ ① ⑥ ５ ４ ０ ２ 22 ◆受入保留方式の拡張版は， ・応募する側が学生の場合には，学生側の片側耐戦略性を満たす； ・応募する側が（複数の学生と組になる可能性のある）教員の場合には， 「戦略的操作」が生じうる，つまり教員側の片側耐戦略性を満たさない． ◆受入保留方式の拡張版は，研修医と病院のマッチング（日本でも 2004 年に導入）や学校選択の問題に応用されている． ●練習問題（坂井（2013）pp. 112-115 より） 学生の希望順位 １位 ２位 ３位 ４位 ５位 学生１ ６ ５ ４ ０ ７ 状況は p. 2 と同じ． 学生２ ５ ７ ６ ４ ０ 学生と教員の 学生３ ５ ４ ０ ７ ６ 希望順位が異なる． 23 【問題】これらの希望順位のも 教員の希望順位 １位 ２位 ３位 ４位 と，受入保留方式を用いた場 教員４ １ ２ ０ ３ 合に得られるマッチングにつ 教員５ １ ２ ３ ０ いて，学生側から応募する場 教員６ ３ ２ １ ０ 合と，教員側から勧誘する場 教員７ ３ ０ １ ２ 合のそれぞれについて考えな さい． 【答え】 ・学生側から応募する場合には，（学生１，教員６），（学生２，教員５）の 組ができ，学生３はゼミに入らず，教員４と教員７はゼミ生なし． ・教員側から応募する場合には，（学生１，教員５），（学生２，教員６）の 組ができ，学生３はゼミに入らず，教員４と教員７はゼミ生なし． （これから，一般に，安定なマッチングは１つとは限らないことが分かる．） 24
© Copyright 2025 ExpyDoc
