安定結婚問題#

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

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

ある人 \(p\) にとって異性 \(p_1\) が \(p_2\) よりも好ましいときに

(24)#\[p_1 \succ_p p_2\]

と書くこととする．男女のペア \((m,w)\) が次の3条件を満たすとき，\((m,w)\) は Blocking Pair と呼ばれる． \(M(p)\) は人 \(p\) のペアの相手を表すものとする．

\(m \ne M(w)\)（従って \(w \ne M(m)\) も成立） \(w \succ_m M(m)\) \(m \succ_w M(w)\)

マッチング \(M\) は Blocking Pair が存在しないときに安定であると呼ばれる．

任意の SM の例に対し安定マッチングが存在し，Gale-Shapley アルゴリズムを用いることで \(O(N^2)\) 時間で求めることが可能である． Gale-Shapley アルゴリズムにより求まる安定マッチングは，男性にとっての最適解（各男性が安定マッチングの中でとり得る最も良い相手を選んで求まる解）であり，女性にとっての最低解（各女性が安定マッチングの中でとり得る最も悪い相手を選んで求まる解）になっている．アルゴリズム内での男性，女性の役割を交換すれば女性にとっての最適解が求まる．そこで，両者にとっての公平性を組み込んだ安定結婚問題の変種も考えられている．

マッチング \(M\) の \(p\) でのコスト関数 \(c_M(p)\) を \(M(p)\) の \(p\) における順位とし，各種コスト関数 \(c(M)\)，\(r(M)\)，\(d(M)\) をつぎで与える．

(25)#\[\begin{split}\begin{array}{l} c(M) = \sum_p{c_M(p)} \\ r(M) = \max_p c_M(p) \\ d(M) = \left| \sum_m{c_M(m)} - \sum_w{c_M(w)} \right| \end{array}\end{split}\]

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

参考文献

[1]

Dan Gusfield. Three Fast Algorithms for Four Problems in Stable Marriage. SIAM Journal on Computing, 16(1):111–128, feb 1987. URL: http://epubs.siam.org/doi/10.1137/0216010, doi:10.1137/0216010.

[2]

Tomás Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45(2):233–284, oct 1992. URL: https://linkinghub.elsevier.com/retrieve/pii/002200009290048N, doi:10.1016/0022-0000(92)90048-N.

[3]

Akiko Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, 10:1–19, 1993. URL: https://api.semanticscholar.org/CorpusID:121978588.