Gale Sharpley

個人的メモ

実装では男性側から順番に女性にマッチングを申し込み, 申し込まれた女性は自分にとってその人よりも優先順位の高い人が現れるまでそのオファーを保持する. そしてもしそのような人が現れた場合はそちらの人のオファーを保持する. 男性側はもし断られた場合は次に優先順位の高い女性にマッチングを申し込む.
以上の操作は有限回で終了し, 繰り返して得られた完全マッチングは安定マッチングとなることが言え, また計算量はグループ内の人数を $n$ としたとき $\O (n^2)$ である(同じ女性から $2$ 度断られることはないので).
このようにして得られた安定マッチングはすべての男性にとってあり得る安定マッチングのうち最も優先順位の高い人とマッチングしており, 逆にすべての女性にとってあり得る安定マッチングのうち最も優先順位の低い人とマッチングしていることが言える.
つまりそれぞれの立場は公平ではなく, 男性側と女性側の立場入れ替えた場合に同じ安定マッチングが得られるとは限らない(むしろ同じ安定マッチングが得られた場合はそれが唯一の安定マッチングである).

(補足)
男性側から申し込む場合の Gale-Sharpley において女性は自分の優先順位について虚偽の申告をすることによってより優先順位の高い相手とマッチングすることが可能になる(strategy-proof ではないと言う).
$2$ つ以上の安定マッチングが存在するようなインスタンスに対して strategy-proof 性を満たす安定マッチングアルゴリズムは存在しない. ただし男性にとっては真の優先順位を申告することが weakly dominant (どんな嘘の優先順位リストよりも同等以上に良い結果を得られる)な戦略であることも分かっている.
この問題の一般化として優先順位リストが不完全である場合(絶対に無理な人がいるみたいな)や優先順が strict order ではない場合(タイも許す)などがある(SMI, SMT, SMTI などと呼ばれる).