トップ > 数理計画用語集 > 安定結婚問題

数理計画用語集

安定結婚問題

読み:あんていけっこんもんだい
英名:Stable Marriage Problem

同数の男性と女性が存在し,各人が異性に対して順序付けを持っているとする(同率はないと仮定する).このとき,以下の安定性を持つマッチングを求める問題を安定結婚問題(Stable Matching Problem,以下 SM と略す)と呼ぶ.

ある人equationにとって異性equationequationよりも好ましいときに

equation

と書くこととする.男女のペアequationが次の3条件を満たすとき,equationは Blocking Pair と呼ばれる.equationは人equationのペアの相手を表すものとする.

equation(従ってequationも成立)

equation

equation

マッチング equationは Blocking Pair が存在しないときに安定であると呼ばれる.

任意のSMの例に対し安定マッチングが存在し,Gale-Shapley アルゴリズムを用いることでequation時間で求めることが可能である.

Gale-Shapley アルゴリズムにより求まる安定マッチングは,男性にとっての最適解(各男性が安定マッチングの中でとり得る最も良い相手を選んで求まる解)であり,女性にとっての最低解(各女性が安定マッチングの中でとり得る最も悪い相手を選んで求まる解)になっている.アルゴリズム内での男性,女性の役割を交換すれば女性にとっての最適解が求まる.そこで,両者にとっての公平性を組み込んだ安定結婚問題の変種も考えられている.

マッチングequationequationでのコスト関数equationequationequationにおける順位とし,各種コスト関数equation をつぎで与える.

equation

equation

equation

equationの最小化問題をそれぞれ Egalitarian SM ,Minimum Regret SM ,Sex-Equal SM と呼ぶ. Egalitarian SM, Minimum Regret SM の2問題に関して言えば,多項式時間で求解可能であるが[1,2] ,一方で Sex-Equal SMはNP 困難であることが示されている[3].

[参考]
[1] D. Gusfield,Three fast algorithms for four problems in stable marriage,SIAM J. Comput 16 (1985)
[2] T. Feder,A new fixed point approach for stable networks and stable marriages,J. Comput. System Sci. 45 (1992)
[3] A. Kato,Complexity of the sex - equal stable marriage problem,Japan J. Ind. Appl. Math. 10 (1993)