安定結婚問題

提供: ORWiki
2007年7月9日 (月) 14:42時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【あんていけっこんもんだい (stable marriage problem)】''' 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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