Irving

個人的メモ

まず Phase $1$ で GaleSharpley のような方法でマッチングを考えていき, 各人について [その時点での最善のプロポーズ先, その時点で受けた最善のプロポーズ] に優先順位のリストを限定する. 次にPhase $2$ で優先順位のリストの要素数で $2$ 以上のものがある場合は、 誰かが最善のプロポーズ先を諦める(つまり reject される) 必要があるので、最善のプロポーズ先に断られて第二志望の人にプロポーズすると考える. その影響で第二志望の人もある人からのプロポーズを reject するためまたその人の新しいプロポーズ先を考えて... みたいな遷移を巡回するまで続け、 巡回列が見つかったらそれを基に暫定の優先順位リストを限定する.
上記の操作は安定マッチングの存在の可否に影響を及ぼさないため, 繰り返すと最終的に安定マッチングが得られるかもしくは安定マッチングが存在しないことが分かる. 気をつけて実装するとアルゴリズム全体での計算量は $\O (n^2)$ となる.
より知りたい方は元論文である "An Efficient Algorithm for the “Stable Roommates” Problem" [Irving 1985] をあたってみてください. .