Gale-Shapleyアルゴリズム

Gale-Shapleyアルゴリズムは、安定結婚問題（stable marriage problem）を解決します。これは、2つのグループ（例：研修医と病院、学生と学校）をマッチングする際に、どのペアも割り当てられたパートナーよりも互いを好むことがないようにする方法です。David GaleとLloyd Shapleyによって1962年に導入されたこのアルゴリズムは、繰り延べ受諾（deferred acceptance）プロセスを通じて多項式時間で安定したマッチングを保証します。このプロセスでは、一方の側が順次提案し、もう一方の側が応答し、より良い選択肢が現れると選択を修正します。