Deferred-Acceptanceアルゴリズム

安定結婚問題や大学選択問題を解くDeferred-Acceptanceアルゴリズム（Gale-Shapleyアルゴリズム）を実装してみる。

現状

1対1のDAアルゴリズムは完成。

要求仕様: https://github.com/OyamaZemi/exercises2015/tree/master/ex02
実行結果: https://github.com/13tsuyoshi/DA_algorithms/blob/master/DA_Algorithms.ipynb

今後簡単にできそうなこと

• DAアルゴリズムから出てきたマッチングが、本当にStableかを確かめる（Blocking Pairが無いことを確かめる）関数を作る
• apply側の申し込み順を入れ替えても、結果は変わらないことを確かめる
• apply側とhost側の効用（人数n - マッチングした相手の順位k）を計算する関数を作る
• DAアルゴリズムがapply側の効用を最大化（host側の効用を最小化）していることを確かめる
• apply側に虚偽申告をするインセンティブが無い一方、host側には虚偽申告をするインセンティブがあることを確かめる
• 不完全な選好表に対応する
• 多対1のDAアルゴリズムの実装

難しそうなこと

• Stable Matchingを全出力する関数を作る（指数オーダらしい）
• 男女の効用和を最大化 / 効用差を最小化するマッチングを考える
• 同順を許した選好に対応する（進振りにおいて、学部は点数の同じ学生に優劣を付けないはず）

文献

Paperと本

※以下にあるPaperは全てSSL-VPN Gatewayを使って（学外からでも）読める。

• D. Gale and L.S. Shapley, "College Admissions and the Stability of Marriage," American Mathematical Monthly 69 (1962), 9-15
  元論文。安定結婚問題（1対1）、学校選択問題（多対1）の定式化、GSアルゴリズムの導入・安定マッチングを必ず求められることの証明

• A.E. Roth, "Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions," International Journal of Game Theory 36 (2008), 537-569
  DAアルゴリズムのいろいろ（？）

• 坂井豊貴・藤中裕二・若山琢磨『メカニズムデザイン -資源配分制度の設計とインセンティブ-』(2008) ミネルヴァ書房
  第7章で安定結婚問題(1対1)におけるGSアルゴリズムについて詳しく（証明付きで）解説されている。また、apply側が虚偽の選好を表明するインセンティブを持たないこと、一方host側はそれを持つことが示されている。多対1マッチングについては少しだけ。

• 小島武仁・安田洋祐「マッチング・マーケットデザイン」『経済セミナー』2009年4・5月号
  研修医マッチングと学校選択の話。DAアルゴリズムについての詳しい解説有。研修医マッチングのパートは研修医マッチングの経済学 - ECONO斬り！！にある。

• Robert W. Irving, David F. Manlove and Gregg O’Malley, "Stable Marriage with Ties and Bounded Length Preference Lists," Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, UK.
  安定結婚問題で選好順位にタイを認めたり、不完全な選好リスト（こいつとだけは絶対ペアになりたくない！）を許した時の計算時間について

• 柳澤弘揮・宮崎修一・岩間一雄 「片方のみがタイを持つ安定結婚問題に対する25/17 近似アルゴリズム」 『数理解析研究所講究録』第1691巻 (2010), 136-141頁
  序章に、タイと不完全なリストを認めた場合の計算量の問題と近似アルゴリズムの話題が簡単に書かれている

Webページ

• 経済学で理想のパートナーを探そう！ - ゲール＝シャプレーアルゴリズムを合コンのマッチング問題から考える
  安定結婚問題（1対1）におけるGSアルゴリズムのわかりやすい解説。

• 安定マッチング - 各種アルゴリズムの C++ による実装
  GSアルゴリズムに加えて、それ以外の安定マッチング（男女の効用の和を最大にするマッチング、男女の効用差を最小にするマッチング）についても解説されている。タイや不完全なリストを許した時の具体的な実装に関するヒントも有。

• Introduction to Market Design and Two-Sided Matching Markets
  Fuhito Kojima先生の（授業?）スライド。