安定結婚問題

出典: ORWiki

【あんていけっこんもんだい (stable marriage problem)】

同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 (m, f) \, に対して, m \, が f \, より現在の相手を好むか, または f \, が m \, より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C" より作成