安定結婚問題（集団見合い問題）

安定結婚問題とは

問題の説明

男女それぞれＮ人のグループがいます。各人が、異性のＮ人について好きな順序の表がつけられており、なるべく好きな人と結婚したいと思っています。
　結果として４組のペアが成立します。そのとき、ペアにならなかった２人が、互いに結婚相手よりも好きだとなると浮気をする危険性があります（そのペアをブロッキングペアといいます）。「安定」結婚問題とは、ブロッキングペアを生じない組合せを求める問題です。

Ｎ＝４人とします。男性をＡ，Ｂ，Ｃ，Ｄとし、女性をａ，ｂ，ｃ，ｄとします。それぞれ、異性の好きな順序が図のようになっているとします（順位表は瀧本英二「計算機科学的意思決定論　第２回」を参考にさせていただきました）。

上図（Ａ－ａ、Ｂ－ｂ、Ｃ－ｃ、Ｄ－ｄ）の場合、Ｂとｄがブロッキングペア（浮気をしたい相手）になっています。
　ｄにとっては、ＤよりもＢのほうが好きだし、Ｂはｂよりもｄのほうが好きなので、左図の関係を破壊してＢ－ｄの関係をもちたいと思うでしょう（不倫をする）。
　それに対して、下図（Ａ－ｂ、Ｂ－ｄ、Ｃ－ａ、Ｄ－ｃ）では、一方が現在の婚約者よりも好きな異性がいたとしても、その相手が自分よりも好きな人と婚約している（例えば、ｃは最悪のＤになりましたが、他のＡ～Ｂは、みなｃよりも好きな人と婚約しています）のですから、不倫の関係が成立しません。すなわち、安定マッチングになってます。

婚約成立のルール

ここでは、男性から女性にプロポーズすることにします。
　プロポーズされた女性は、未だ婚約していないならば、このプロポーズを受諾して婚約しなければなりません。
　婚約しているならば、婚約者とプロポーズ男性と比較して、婚約者のほうが好きならばプロポーズを拒絶し、そうでなければ、婚約を解消してプロポーズを受諾して、新しく婚約をします。
　婚約している男性は、他の女性にプロポーズすることはできません。また、以前にプロポーズして拒絶された女性にプロポーズすることはできません。

Gale-Shapley の解法

安定結婚問題では、必ず一つ以上の解が存在することが証明されています。その一つの解を求める方法として、Gale-Shapleyのアルゴリズム（１９６２年）が有名です。
　この解法は、必ず「一つ」の解を求められますが、「すべての」解を得るものではありません。

初期設定

全ての参加者は独身（男性はプロポーズをしていないし、女性はプロポーズを受けていない）とする。

プロポーズと婚約成立

独身（婚約者がいない）男性がが存在する間、以下の操作を繰り返す。その男性をＭ[i]とする。

• 男性Ｍ[i]は、まだプロポーズしていない女性の中で、最も好きな女性Ｗ[j]にプロポーズする
• 女性Ｗ[j]は、次の条件により、受諾あるいは拒絶を行う。
  ・Ｗ[j]に婚約者がいない場合；
  　　　プロポーズを受諾し、Ｗ[j]とＭ[i]の婚約が成立する。
  ・Ｗ[j]が既に他の男性Ｍ[k]と婚約している場合
  　　　Ｗ[j] が、Ｍ[i] よりもＭ[k] のほうが好きなとき
  　　　　　　Ｗ[j] は、Ｍ[i] のプロポーズを拒絶する。
  　　　Ｗ[j] が、Ｍ[k] よりもＭ[i] のほうが好きなとき
  　　　　　　Ｗ[j] は、Ｍ[k] との婚約を破棄する。
  　　　　　　Ｗ[j] は、Ｍ[i] のプロポーズを受諾する。

出力

現在婚約しているペアの集合を出力する

数値例

主な変数

好順位表
　ＱＭ[i,j] 　　　　　　　　　　ＱＷ[j,i]
　 男性 　好　　　　　嫌　　　　 女性 　好　　　　　嫌
　　　　　１　２　３　４　　　　　　　　１　２　３　４
　　Ａ　　ｂ　ａ　ｃ　ｄ　　　　　ａ　　Ｃ　Ｄ　Ｂ　Ａ
　　Ｂ　　ａ　ｄ　ｂ　ｃ　　　　　ｂ　　Ｄ　Ｂ　Ａ　Ｃ
　　Ｃ　　ｂ　ａ　ｃ　ｄ　　　　　ｃ　　Ａ　Ｃ　Ｂ　Ｄ
　　Ｄ　　ｄ　ｃ　ｂ　ａ　　　　　ｄ　　Ｃ　Ｂ　Ａ　Ｄ
逆好順位表
　ＲＷ[j,i]
　 女性 　好　　　　　嫌
　　　　　Ａ　Ｂ　Ｃ　Ｄ
　　ａ　　４　３　１　２
　　ｂ　　３　２　４　１
　　ｃ　　１　３　２　４
　　ｄ　　３　２　１　４

• ＱＭとＱＷ：これらは入力されるデータです。例えば、ＲＭ[Ａ][ｃ]＝３とは、男性Ａは女性ｃを３番目に好きであることを示します。
• ＲＷ：ＱＷを逆に、女性ａからみて、男性Ａは好順位が４であることを、ＲＷ[ａ][Ａ]＝４で表します。これはＱＷから得られます。

プロポーズ表　　　　　　　　男性婚約表　　 女性婚約表
　ＰＭ[i][j]　　　　　　　　　ＳＭ[i]　　　　ＳＷ[j]
　　　　　ａ　ｂ　ｃ　ｄ
　　Ａ　　２　１　０　０　　　　Ａ　ａ　　　　ａ　Ａ
　　Ｂ　　・　・　・　・　　　　Ｂ　０　　　　ｂ　ｂ
　　：　　　　　　　　　　　　　：　　　　　　：

• ＰＭ：男性のプロポーズ履歴です。男性Ａは、これまでに女性ｂとａにプロポーズして、ｂには拒絶あるいは婚約破棄をされ、現在ａと婚約していること、そして、ｃとｄには未だプロポーズしていないことを示します。初期状態ではすべてが０になっています。
• ＳＭ：男性の婚約状況を示します。ＳＭ[Ａ]＝ａとは、現在男性Ａは女性ｂと婚約していることを示し、ＳＭ[Ｂ]＝０とは、男性Ｂは婚約者がいない（独身）であることを示します。初期状態ではすべてが０になっています。
  
• ＳＭ０：ＳＭのうち０である個数、すなわち、独身男性数です。初期状態ではＳＭ０＝Ｎであり、ＳＭ０＝０となったときに、処理が終了します。
• ＳＷ：女性の婚約状況を示します。ＳＷ[ａ]＝Ａとは、女性ｂは男性Ａと婚約していることを示し、女性ｂは婚約者がいない（独身）であることを示し、ＳＷ[ｂ]＝Ａとは、ます。初期状態ではすべてが０になっています。

解法の実験

Gale-Shapleyのアルゴリズムにそって、トレースを行います。

１巡目：男性全員が独身（ＳＭ０＝４）

• 男性Ａ：好順位１の女性ｂ（ＲＭ[Ａ][1]＝ｂ）にプロポーズ（ＰＭ[Ａ][ｂ]＝１）。
  ｂは独身（ＳＷ[ｂ]＝０）なので、プロポーズ受諾。Ａ－ｂの婚約成立（ＳＷ[ｂ]＝Ａ、ＳＭ[Ａ]＝ｂ、ＰＭ[Ａ][ｂ]＝２、ＳＭ０＝Ｎ－１＝３)。
• 男性Ｂ：好順位１の女性ａ（ＲＭ[Ｂ][1]＝ａ）にプロポーズ（ＰＭ[Ｂ][ａ]＝１）。
  ａは独身（ＳＷ[ａ]＝０）なので、プロポーズ受諾。Ｂ－ａの婚約成立（ＳＷ[ａ]＝Ｂ、ＳＭ[Ｂ]＝ａ、ＰＭ[Ｂ][a]＝２、ＳＭ０＝３－１＝２)。
• 男性Ｃ：好順位１の女性ｂ（ＲＭ[Ｃ][1]＝ｂ）にプロポーズ（ＰＭ[Ｃ][ｂ]＝１）。
  ｂはＡと婚約中（ＳＷ[ｂ]＝Ａ）なので、ＣとＡを比較。Ｃは４位（ＲＷ[ｂ][Ｃ]＝４）、Ａは３位（ＲＷ[ｂ][Ａ]＝３）で、Ａのほうが好き（ＲＷ[ｂ][Ｃ]＞ＲＷ[ｂ][Ａ]）だから、Ａとの婚約を続けて、Ｃのプロポーズを拒絶。
• 男性Ｄ：好順位１の女性ｄ（ＲＭ[Ｄ][1]＝ｄ）にプロポーズ（ＰＭ[Ｄ][ｄ]＝１）。 ｄは独身（ＳＷ[ｄ]＝０）なので、プロポーズ受諾。Ｄ－ｄの婚約成立（ＳＷ[ｄ]＝Ｄ、ＳＭ[Ｄ]＝ｄ、ＰＭ[Ｄ][ｄ]＝２、ＳＭ０＝２－１＝１)。

ここまでの状況
プロポーズ表　　　　　　　　男性婚約表　　 女性婚約表
　ＰＭ[i][j]　　　　　　　　　ＳＭ[i]　　　　ＳＷ[j]
　　　　　ａ　ｂ　ｃ　ｄ
　　Ａ　　０　２　０　０　　　　Ａ　ｂ　　　　ａ　Ｂ
　　Ｂ　　２　０　０　０　　　　Ｂ　ａ　　　　ｂ　Ａ
　　Ｃ　　０　１　０　０　　　　Ｃ　０　　　　ｃ　０
　　Ｄ　　０　０　０　２　　　　Ｄ　ｄ　　　　ｄ　Ｄ

２巡目：独身男性はＣの１人（ＳＭ０＝１）

• 男性Ａ：すでにｂと婚約している（ＳＭ[Ａ]＝ｂ≠０）ので何もしない。
• 男性Ｂ：すでにａと婚約している（ＳＭ[Ｂ]＝ａ≠０）ので何もしない。
• 男性Ｃ：独身（ＳＭ[Ｃ]＝０）なので、プロポーズを続ける。
  好順位１のｂには既にプロポーズした（ＰＭ[Ｃ][ｂ]＝１）ので、次の順位２の女性ａ（ＱＭ[Ｃ][２]＝ａ）にプロポーズする（ＰＭ[Ｃ][ａ]＝１）。
  ａはＢと婚約中（ＳＷ[ａ]＝Ｂ）なので、ＣとＢを比較。Ｃは１位（ＲＷ[ａ][Ｃ]＝１）、Ｂは３位（ＲＷ[ａ][Ｂ]＝４）で、Ｃのほうが好き（ＲＷ[ａ][Ｃ]＜ＲＷ[ａ][Ｂ]）だから、Ｂとの婚約を破棄（ＳＷ[ａ]＝０、ＳＭ[Ｂ]＝０、ＰＭ[Ｂ][ａ]＝１、ＳＭ０＝１＋１＝２)して、Ｃと婚約する（ＳＷ[ａ]＝Ｃ、ＳＭ[Ｃ]＝ａ、ＰＭ[Ｃ][ａ]＝２、ＳＭ０＝２－１＝１)。
。
• 男性Ｄ：すでにｄと婚約している（ＳＭ[Ａ]＝ｂ≠０）ので何もしない。

ここまでの状況
プロポーズ表　　　　　　　　男性婚約表　　 女性婚約表
　ＰＭ[i][j]　　　　　　　　　ＳＭ[i]　　　　ＳＷ[j]
　　　　　ａ　ｂ　ｃ　ｄ
　　Ａ　　０　２　０　０　　　　Ａ　ｂ　　　　ａ　Ｃ
　　Ｂ　　１　０　０　０　　　　Ｂ　０　　　　ｂ　Ａ
　　Ｃ　　２　１　０　０　　　　Ｃ　ａ　　　　ｃ　０
　　Ｄ　　０　０　０　２　　　　Ｄ　ｄ　　　　ｄ　Ｄ

３巡目：独身男性はＢの１人（ＳＭ０＝１）

• 男性Ａ：すでにｂと婚約している（ＳＭ[Ａ]＝ｂ≠０）ので何もしない。
• 男性Ｂ：独身に戻った（ＳＭ[Ｂ]＝０）なので、プロポーズを続ける。
  好順位１のａには既にプロポーズした（ＰＭ[Ｂ][ａ]＝１）ので、次の順位２の女性ｄ（ＱＭ[Ｂ][２]＝ｄ）にプロポーズする（ＰＭ[Ｂ][ｄ]＝１）。
  ｄはＤと婚約中（ＳＷ[ｄ]＝Ｄ）なので、ＢとＤを比較。Ｂは２位（ＲＷ[ｄ][Ｂ]＝２）、Ｄは４位（ＲＷ[ｄ][Ｄ]＝４）で、Ｂのほうが好き（ＲＷ[ｄ][Ｂ]＜ＲＷ[ｄ][Ｄ]）だから、Ｄとの婚約を破棄（ＳＷ[ｄ]＝０、ＳＭ[Ｄ]＝０、ＰＭ[Ｄ][ｄ]＝１、ＳＭ０＝１＋１＝２)して、Ｂと婚約する（ＳＷ[ｄ]＝Ｂ、ＳＭ[Ｂ]＝ｄ、ＰＭ[Ｂ][ｄ]＝２、ＳＭ０＝２－１＝１)。
• 男性Ｄ：独身に戻った（ＳＭ[Ｄ]＝０）ので、プロポーズを続ける。
  好順位１のｄには既にプロポーズした（ＰＭ[Ｄ][ｄ]＝１）ので、次の順位２の女性ｃ（ＱＭ[Ｄ][２]＝ｃ）にプロポーズする（ＰＭ[Ｄ][ｃ]＝１）。
  ｃは独身（ＳＷ[ｃ]＝０）なので、プロポーズ受諾。Ｄ－ｃの婚約成立（ＳＷ[ｃ]＝Ｄ、ＳＭ[Ｄ]＝ｃ、ＰＭ[Ｄ][ｃ]＝２、ＳＭ０＝１－１＝０)。

ここまでの状況
プロポーズ表　　　　　　　　男性婚約表　　 女性婚約表
　ＰＭ[i][j]　　　　　　　　　ＳＭ[i]　　　　ＳＷ[j]
　　　　　ａ　ｂ　ｃ　ｄ
　　Ａ　　０　２　０　０　　　　Ａ　ｂ　　　　ａ　Ｃ
　　Ｂ　　１　０　０　２　　　　Ｂ　ｄ　　　　ｂ　Ａ
　　Ｃ　　２　１　０　０　　　　Ｃ　ａ　　　　ｃ　Ｄ
　　Ｄ　　０　０　２　１　　　　Ｄ　ｃ　　　　ｄ　Ｂ

独身男性は０人（ＳＭ０＝０）なので終了

安定マッチングが完成。ＳＭの表から
　　Ａ－ｂ、Ｂ－ｄ、Ｃ－ａ、Ｄ－ｃ
が得られる。

解の吟味

好順位の何番目と結婚できたかを調べると、
　 男性　相手の好順位　 女性　相手の好順位
　　Ａ　　ｂは１位　　　　ａ　　Ｃは１位
　　Ｂ　　ｄは２位　　　　ｂ　　Ａは３位
　　Ｃ　　ａは２位　　　　ｃ　　Ｄは４位
　　Ｄ　　ｃは２位　　　　ｄ　　Ｂは２位
となり、明らかに女性が不利な結果になっています。これは「男性からプロポーズする」ことに起因しており、女性からプロポーズするように変えれば、Ａ－ｃ、Ｂ－ｄ、Ｃ－ａ、Ｄ－ｂの安定解が得られ、逆の結果になります。
　 男性　相手の好順位　 女性　相手の好順位
　　Ａ　　ｃは３位　　　　ａ　　Ｃは１位
　　Ｂ　　ｄは２位　　　　ｂ　　Ｄは１位
　　Ｃ　　ａは２位　　　　ｃ　　Ａは１位
　　Ｄ　　ｂは３位　　　　ｄ　　Ｂは２位

計算プログラム

プロポーズする側を男性とします。
上記での男女の氏名は、Ａ，Ｂ，～やａ，ｂ，～などの記号ではなく、共に１，２，～の数字にします。
好順位に同一順位や抜け順位がなってはいけません。