メインコンテンツへ

サイエンス&テクノロジーが切り開く新たな世界

青山学院大学 理工学部物理・数理学科教授 杉原 正顯

青山学院大学
理工学部物理・数理学科教授
杉原 正顯 [Masaaki Sugihara]

「安定結婚問題」の解法―ノーベル賞を受賞したアルゴリズム

第1回 2016/7/2(土)

講義題目の「安定結婚問題」とはつぎのような問題です:
同数の男性と女性がいて、各人の異性に対する好みの順位が与えられたとき、全員が「それなりに幸せになれる」ような結婚のペアを決める問題です。全員が「それなりに幸せになれる」状況としては、いろいろ考えられますが、多少消極的ですが、互いに現在組んでいる相手よりも好きであるペアが存在しない状況(この状況を安定といいます)を考えます。

例をあげます。3人の男性(a, b, cで表します)、女性(A, B, Cで表します)がいて、以下のような好みであるとします:

男性(a, b, c)の好み

1位 2位 3位
a A B C
b B A C
c A C B

女性(A, B, C)の好み

1位 2位 3位
A b a c
B c b a
C a c b

このとき、たとえば、ペア a-B, b-C, c-A は安定ではありません。実際、aはBよりAを好み、Aはcよりaを好んでいるので、互いに現在組んでいる相手よりも好きであるペアa-Aができてします(このペアは駆け落ちしてしまう!)。一方、ペアa-A, b-B, c-Cは安定な状況です。

この「安定結婚問題」は、学生の学校への配属、研修医の病院への配属等にも応用できるものであり、ゲールとシャプレイによって1962年に定式化され、人々の好みがどうであっても、その解、つまり、安定な状況が存在することが証明され、さらに、安定な状況を見つける高速な計算法(アルゴリズム)も与えられました(シャプレイは、この業績および関連分野における業績によって、2012年にノーベル経済学賞を受賞しています)。

本講義では、安定結婚問題についてより詳しく説明した後、その解法(高速なアルゴリズム)について詳細に説明します。

プロフィール

青山学院大学 理工学部物理・数理学科教授
杉原 正顯 [Masaaki Sugihara]

東京大学工学部卒業、同大学院工学系研究科修士課程修了、同大学院工学系研究科博士課程修了。工学博士。筑波大学、一橋大学、名古屋大学、東京大学において教鞭をとり、現在、青山学院大学理工学部教授。名古屋大学、東京大学名誉教授。専門分野は数値解析学。主な著書に、『数値計算法の数理』(岩波、1994年)、『複素関数論』(岩波、2003年)、『線形計算の数理』(岩波、2009年)、『線形代数Ⅰ、Ⅱ』(丸善、2015、2013年)等がある。

大学案内