離散数学入門#12: マッチング(3)：安定結婚問題とGale–Shapleyアルゴリズム，臨床研修マッチングへの応用
視聴回数 20,407 回
0
0
早稲田大学の全学部の3〜4年生を対象とする全学オープン科目「離散数学入門」（担当教員：早水 桃子）の授業動画です．文理を問わず，誰でもグラフ理論やグラフアルゴリズムの初歩を学ぶことができます．グラフ理論の定理やグラフに関するアルゴリズムを正しく理解して，現実の諸問題を解決するための応用力を身につけましょう．
---------------------------------------------------------------------------------------
最大マッチングが全体の利益を最大化するマッチングであるのに対して，安定マッチングは個人の選好を考慮して皆がそれなりに納得できるようにしたマッチングです．安定マッチング問題を解くGale-Shapleyのアルゴリズムはノーベル経済学賞を授与されたことでも知られ，研修医の病院配属，学生の研究室配属，公立学校の割当て，腎臓の交換移植のドナーとレシピエントの割当てなど，実社会の多くの場面で使われています．教科書には含まれていない話題ですが，今回はGale-Shapleyアルゴリズムの説明とその正当性の証明をして，安定結婚問題および研修医配属問題とその周辺を解説します．
0:00 オープニング
1:10 「安定」なマッチングとは？
8:45 安定結婚問題
10:59 安定マッチングを求めるGale–Shapleyのアルゴリズム
19:45 Gale–Shapleyアルゴリズムの正当性の証明
22:40 注意(1)：GSアルゴリズムは男女平等ではない
25:03 注意(2)：安定マッチングは複数存在しうる
25:35 注意(3)：安定マッチング≠不満を最小化するマッチング
27:36 発展形(1)：選好順序リストが不完全な安定結婚問題
30:35 発展形(2)：研修医配属問題
34:53 マッチングプログラムに参加する人へのアドバイス：Gale-Shapleyアルゴリズムの耐戦略性
36:32 参考図書
▷ 再生リスト：「離散数学入門」の動画一覧
https://youtube.com/playlist?list=PLCo60G1m_ibpJgfB4WcGwWybC6sfyawoL
---------------------------------------------------------------------------------------
▷ 2021年度 授業シラバス
https://www.wsl.waseda.jp/syllabus/JAA104.php?pKey=2602023030012021260202303026&pLng=jp
▷ Twitter（早稲田大学 早水桃子研究室）
https://twitter.com/hayamizu_lab
▷ 質問箱
https://peing.net/ja/hayamizu_lab
---------------------------------------------------------------------------------------
▷ 教科書
『例題で学ぶグラフ理論』（安藤 清, 土屋 守正, 松井 泰子 共著）森北出版
https://www.amazon.co.jp/dp/4627052812/ref=cm_sw_r_tw_dp_XY1C405DW1N0ZHG0NF7H
▷ 参考書やアプリなど
・『グラフ理論入門：基本とアルゴリズム』（宮崎 修一 著） 森北出版
https://www.amazon.co.jp/dp/4627852819/ref=cm_sw_r_tw_dp_E85NNF8V37QWSNZ7CC0H
・『グラフ理論入門』（R.J. ウィルソン 著, 西関 隆夫, 西関 裕子 共訳）近代科学社
https://www.amazon.co.jp/dp/4764902966/ref=cm_sw_r_tw_dp_CZH6YAY86MBG5FTHYK2B
・『アルゴリズム図鑑 絵で見てわかる26のアルゴリズム』（石田 保輝, 宮崎 修一 共著）森北出版（iOS/Android 無料アプリ版だと色々なアルゴリズムをアニメーションで学べます．）
https://www.amazon.co.jp/dp/4798149772/ref=cm_sw_r_tw_dp_WQP59HC2MYF78CRCG6E5
---------------------------------------------------------------------------------------
【モデレーターより】
早水研究室の動画を見てくださり誠に有難うございます。当チャンネルの動画は早稲田大学の学生や教員が視聴するものですので、YouTubeのポリシーに反するコメントや教育上の観点から不適切と思われるコメントは、モデレーターの判断で削除する場合がございます。受講生や他の教員に読まれることを想定した上でのコメント投稿をお願い申し上げます。
編集アシスタント：SK
---------------------------------------------------------------------------------------
最大マッチングが全体の利益を最大化するマッチングであるのに対して，安定マッチングは個人の選好を考慮して皆がそれなりに納得できるようにしたマッチングです．安定マッチング問題を解くGale-Shapleyのアルゴリズムはノーベル経済学賞を授与されたことでも知られ，研修医の病院配属，学生の研究室配属，公立学校の割当て，腎臓の交換移植のドナーとレシピエントの割当てなど，実社会の多くの場面で使われています．教科書には含まれていない話題ですが，今回はGale-Shapleyアルゴリズムの説明とその正当性の証明をして，安定結婚問題および研修医配属問題とその周辺を解説します．
0:00 オープニング
1:10 「安定」なマッチングとは？
8:45 安定結婚問題
10:59 安定マッチングを求めるGale–Shapleyのアルゴリズム
19:45 Gale–Shapleyアルゴリズムの正当性の証明
22:40 注意(1)：GSアルゴリズムは男女平等ではない
25:03 注意(2)：安定マッチングは複数存在しうる
25:35 注意(3)：安定マッチング≠不満を最小化するマッチング
27:36 発展形(1)：選好順序リストが不完全な安定結婚問題
30:35 発展形(2)：研修医配属問題
34:53 マッチングプログラムに参加する人へのアドバイス：Gale-Shapleyアルゴリズムの耐戦略性
36:32 参考図書
▷ 再生リスト：「離散数学入門」の動画一覧
https://youtube.com/playlist?list=PLCo60G1m_ibpJgfB4WcGwWybC6sfyawoL
---------------------------------------------------------------------------------------
▷ 2021年度 授業シラバス
https://www.wsl.waseda.jp/syllabus/JAA104.php?pKey=2602023030012021260202303026&pLng=jp
▷ Twitter（早稲田大学 早水桃子研究室）
https://twitter.com/hayamizu_lab
▷ 質問箱
https://peing.net/ja/hayamizu_lab
---------------------------------------------------------------------------------------
▷ 教科書
『例題で学ぶグラフ理論』（安藤 清, 土屋 守正, 松井 泰子 共著）森北出版
https://www.amazon.co.jp/dp/4627052812/ref=cm_sw_r_tw_dp_XY1C405DW1N0ZHG0NF7H
▷ 参考書やアプリなど
・『グラフ理論入門：基本とアルゴリズム』（宮崎 修一 著） 森北出版
https://www.amazon.co.jp/dp/4627852819/ref=cm_sw_r_tw_dp_E85NNF8V37QWSNZ7CC0H
・『グラフ理論入門』（R.J. ウィルソン 著, 西関 隆夫, 西関 裕子 共訳）近代科学社
https://www.amazon.co.jp/dp/4764902966/ref=cm_sw_r_tw_dp_CZH6YAY86MBG5FTHYK2B
・『アルゴリズム図鑑 絵で見てわかる26のアルゴリズム』（石田 保輝, 宮崎 修一 共著）森北出版（iOS/Android 無料アプリ版だと色々なアルゴリズムをアニメーションで学べます．）
https://www.amazon.co.jp/dp/4798149772/ref=cm_sw_r_tw_dp_WQP59HC2MYF78CRCG6E5
---------------------------------------------------------------------------------------
【モデレーターより】
早水研究室の動画を見てくださり誠に有難うございます。当チャンネルの動画は早稲田大学の学生や教員が視聴するものですので、YouTubeのポリシーに反するコメントや教育上の観点から不適切と思われるコメントは、モデレーターの判断で削除する場合がございます。受講生や他の教員に読まれることを想定した上でのコメント投稿をお願い申し上げます。
編集アシスタント：SK
