安定結婚問題

安定結婚問題：Stable marriage problem †

安定マッチング問題の1つで、D.Gale(デイヴィッド・ゲール)とL.S.Shapley(ロイド・シャプレイ）によって1962年に提唱された問題である。

安定結婚問題とは、ひとつの安定的な結婚のマッチングを見つける問題である。順にペアを作っていく。 互いに現在組んでいる相手よりも好きであるペア （以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。

一般に、次のように記述される。

それぞれｎ人の男性と女性がいて、各人が異性の好みの順序１からｎまでランクづける。男女は現在のパートナーよりも良い人がいなくなれば、ペアとなる。もし、お互いに現在の相手より良い人がいなければ安定である。

• In mathematics, the stable marriage problem (SMP) is the problem of finding a stable matching.

• It is commonly stated as:

• Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

• 4人の男女がそれぞれ好みの順序を表明してペアとなる場合
  • 安定マッチングの例
    
  • 安定でないマッチングの例
    
    4番目の点線にブロッキングペアがある。

解法 ゲール・シャプレイ(Gale-Shapley)アルゴリズム †

安定結婚問題の例が与えられたとき安定マッチングは必ず1つ以上存在する。そのうちの1つ(ないし、2つ)をGaleとShapleyにより提案された、ゲール-シャプレイ(Gale-Shapley)アルゴリズム（以下、G-Sアルゴリズムと略す）を用いて求めることができる。

• In 1962, David Gale and Lloyd Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.

このアルゴリズムは、各ラウンド（繰り返し）において、各男性が順に最も好ましい女性（まだプロポーズを受け入れていない）にプロポーズする。各女性は(残された中で)好ましい男性には、maybeと答え、そして、暫定的に、結婚する。残りの男性にはNoと答える。好ましい男性が暫定結婚している場合はそれを解消して結婚できる。 次のラウンジでは、同様である。残された各男性が引き続き、まだプロポーズしていない女性にプロポーズする。次に女性が引き続きmaybeならば暫定結婚、そうでなければかNOを表明する。もし好みの男性がいれば暫定結婚を解消して結婚できる。 これを、残されたペアがいなくなるまで続けて、婚約しているペアの集合をマッチング結果として出力する。

アルゴリズムは男性がプロポーズするという形式で記述されている。しかし、女性がプロポーズするという形式に変えてもなんら妥当性が失われるわけではない。男性がプロポーズすれば、男性の希望を最も反映した(各男性ごとの安定パートナーの中で最も好ましい女性とペアになっている)男性最良安定マッチングが得られ、女性がプロポーズすると、女性最良安定マッチングを得る。

• The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed. Each woman then considers all her suitors and tells the one she most prefers "Maybe" and all the rest of them "No". She is then provisionally "engaged". In each subsequent round, each unengaged man proposes to one woman to whom he has not yet proposed (the woman may or may not already be engaged), and the women once again reply with one "maybe" and reject the rest. This may mean that already-engaged women can "trade up", and already-engaged men can be "jilted".

G-Sアルゴリズムは、

1人の男性が同じ女性に2度以上プロポーズしない
女性は婚約すると独身に戻らない
女性はプロポーズされる際その相手が悪くなることはない

ということからこのアルゴリズムが、必ず結婚できること、有限回の操作で安定マッチングを必ず導いて終了することがいえる。

• This algorithm guarantees that:

• Everyone gets married: Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.
• The marriages are stable: Let Alice be a woman and Bob be a man. They are each paired/partnered/married, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.