安定結婚問題とは
問題の説明
男女それぞれN人のグループがいます。各人が、異性のN人について好きな順序の表がつけられており、なるべく好きな人と結婚したいと思っています。
結果として4組のペアが成立します。そのとき、ペアにならなかった2人が、互いに結婚相手よりも好きだとなると浮気をする危険性があります(そのペアをブロッキングペアといいます)。「安定」結婚問題とは、ブロッキングペアを生じない組合せを求める問題です。
N=4人とします。男性をA,B,C,Dとし、女性をa,b,c,dとします。それぞれ、異性の好きな順序が図のようになっているとします(順位表は瀧本英二「計算機科学的意思決定論 第2回」を参考にさせていただきました)。
上図(A-a、B-b、C-c、D-d)の場合、Bとdがブロッキングペア(浮気をしたい相手)になっています。
dにとっては、DよりもBのほうが好きだし、Bはbよりもdのほうが好きなので、左図の関係を破壊してB-dの関係をもちたいと思うでしょう(不倫をする)。
それに対して、下図(A-b、B-d、C-a、D-c)では、一方が現在の婚約者よりも好きな異性がいたとしても、その相手が自分よりも好きな人と婚約している(例えば、cは最悪のDになりましたが、他のA~Bは、みなcよりも好きな人と婚約しています)のですから、不倫の関係が成立しません。すなわち、安定マッチングになってます。
婚約成立のルール
ここでは、男性から女性にプロポーズすることにします。
プロポーズされた女性は、未だ婚約していないならば、このプロポーズを受諾して婚約しなければなりません。
婚約しているならば、婚約者とプロポーズ男性と比較して、婚約者のほうが好きならばプロポーズを拒絶し、そうでなければ、婚約を解消してプロポーズを受諾して、新しく婚約をします。
婚約している男性は、他の女性にプロポーズすることはできません。また、以前にプロポーズして拒絶された女性にプロポーズすることはできません。
Gale-Shapley の解法
安定結婚問題では、必ず一つ以上の解が存在することが証明されています。その一つの解を求める方法として、Gale-Shapleyのアルゴリズム(1962年)が有名です。
この解法は、必ず「一つ」の解を求められますが、「すべての」解を得るものではありません。
- 初期設定
- 全ての参加者は独身(男性はプロポーズをしていないし、女性はプロポーズを受けていない)とする。
- プロポーズと婚約成立
- 独身(婚約者がいない)男性がが存在する間、以下の操作を繰り返す。その男性をM[i]とする。
- 男性M[i]は、まだプロポーズしていない女性の中で、最も好きな女性W[j]にプロポーズする
- 女性W[j]は、次の条件により、受諾あるいは拒絶を行う。
・W[j]に婚約者がいない場合;
プロポーズを受諾し、W[j]とM[i]の婚約が成立する。
・W[j]が既に他の男性M[k]と婚約している場合
W[j] が、M[i] よりもM[k] のほうが好きなとき
W[j] は、M[i] のプロポーズを拒絶する。
W[j] が、M[k] よりもM[i] のほうが好きなとき
W[j] は、M[k] との婚約を破棄する。
W[j] は、M[i] のプロポーズを受諾する。
- 出力
- 現在婚約しているペアの集合を出力する
数値例
主な変数
好順位表
QM[i,j] QW[j,i]
男性 好 嫌 女性 好 嫌
1 2 3 4 1 2 3 4
A b a c d a C D B A
B a d b c b D B A C
C b a c d c A C B D
D d c b a d C B A D
逆好順位表
RW[j,i]
女性 好 嫌
A B C D
a 4 3 1 2
b 3 2 4 1
c 1 3 2 4
d 3 2 1 4
- QMとQW:これらは入力されるデータです。例えば、RM[A][c]=3とは、男性Aは女性cを3番目に好きであることを示します。
- RW:QWを逆に、女性aからみて、男性Aは好順位が4であることを、RW[a][A]=4で表します。これはQWから得られます。
プロポーズ表 男性婚約表 女性婚約表
PM[i][j] SM[i] SW[j]
a b c d
A 2 1 0 0 A a a A
B ・ ・ ・ ・ B 0 b b
: : :
- PM:男性のプロポーズ履歴です。男性Aは、これまでに女性bとaにプロポーズして、bには拒絶あるいは婚約破棄をされ、現在aと婚約していること、そして、cとdには未だプロポーズしていないことを示します。初期状態ではすべてが0になっています。
- SM:男性の婚約状況を示します。SM[A]=aとは、現在男性Aは女性bと婚約していることを示し、SM[B]=0とは、男性Bは婚約者がいない(独身)であることを示します。初期状態ではすべてが0になっています。
- SM0:SMのうち0である個数、すなわち、独身男性数です。初期状態ではSM0=Nであり、SM0=0となったときに、処理が終了します。
- SW:女性の婚約状況を示します。SW[a]=Aとは、女性bは男性Aと婚約していることを示し、女性bは婚約者がいない(独身)であることを示し、SW[b]=Aとは、ます。初期状態ではすべてが0になっています。
解法の実験
Gale-Shapleyのアルゴリズムにそって、トレースを行います。
- 1巡目:男性全員が独身(SM0=4)
-
- 男性A:好順位1の女性b(RM[A][1]=b)にプロポーズ(PM[A][b]=1)。
bは独身(SW[b]=0)なので、プロポーズ受諾。A-bの婚約成立(SW[b]=A、SM[A]=b、PM[A][b]=2、SM0=N-1=3)。
- 男性B:好順位1の女性a(RM[B][1]=a)にプロポーズ(PM[B][a]=1)。
aは独身(SW[a]=0)なので、プロポーズ受諾。B-aの婚約成立(SW[a]=B、SM[B]=a、PM[B][a]=2、SM0=3-1=2)。
- 男性C:好順位1の女性b(RM[C][1]=b)にプロポーズ(PM[C][b]=1)。
bはAと婚約中(SW[b]=A)なので、CとAを比較。Cは4位(RW[b][C]=4)、Aは3位(RW[b][A]=3)で、Aのほうが好き(RW[b][C]>RW[b][A])だから、Aとの婚約を続けて、Cのプロポーズを拒絶。
- 男性D:好順位1の女性d(RM[D][1]=d)にプロポーズ(PM[D][d]=1)。
dは独身(SW[d]=0)なので、プロポーズ受諾。D-dの婚約成立(SW[d]=D、SM[D]=d、PM[D][d]=2、SM0=2-1=1)。
ここまでの状況
プロポーズ表 男性婚約表 女性婚約表
PM[i][j] SM[i] SW[j]
a b c d
A 0 2 0 0 A b a B
B 2 0 0 0 B a b A
C 0 1 0 0 C 0 c 0
D 0 0 0 2 D d d D
- 2巡目:独身男性はCの1人(SM0=1)
-
- 男性A:すでにbと婚約している(SM[A]=b≠0)ので何もしない。
- 男性B:すでにaと婚約している(SM[B]=a≠0)ので何もしない。
- 男性C:独身(SM[C]=0)なので、プロポーズを続ける。
好順位1のbには既にプロポーズした(PM[C][b]=1)ので、次の順位2の女性a(QM[C][2]=a)にプロポーズする(PM[C][a]=1)。
aはBと婚約中(SW[a]=B)なので、CとBを比較。Cは1位(RW[a][C]=1)、Bは3位(RW[a][B]=4)で、Cのほうが好き(RW[a][C]<RW[a][B])だから、Bとの婚約を破棄(SW[a]=0、SM[B]=0、PM[B][a]=1、SM0=1+1=2)して、Cと婚約する(SW[a]=C、SM[C]=a、PM[C][a]=2、SM0=2-1=1)。 。
- 男性D:すでにdと婚約している(SM[A]=b≠0)ので何もしない。
ここまでの状況
プロポーズ表 男性婚約表 女性婚約表
PM[i][j] SM[i] SW[j]
a b c d
A 0 2 0 0 A b a C
B 1 0 0 0 B 0 b A
C 2 1 0 0 C a c 0
D 0 0 0 2 D d d D
- 3巡目:独身男性はBの1人(SM0=1)
-
- 男性A:すでにbと婚約している(SM[A]=b≠0)ので何もしない。
- 男性B:独身に戻った(SM[B]=0)なので、プロポーズを続ける。
好順位1のaには既にプロポーズした(PM[B][a]=1)ので、次の順位2の女性d(QM[B][2]=d)にプロポーズする(PM[B][d]=1)。
dはDと婚約中(SW[d]=D)なので、BとDを比較。Bは2位(RW[d][B]=2)、Dは4位(RW[d][D]=4)で、Bのほうが好き(RW[d][B]<RW[d][D])だから、Dとの婚約を破棄(SW[d]=0、SM[D]=0、PM[D][d]=1、SM0=1+1=2)して、Bと婚約する(SW[d]=B、SM[B]=d、PM[B][d]=2、SM0=2-1=1)。
- 男性D:独身に戻った(SM[D]=0)ので、プロポーズを続ける。
好順位1のdには既にプロポーズした(PM[D][d]=1)ので、次の順位2の女性c(QM[D][2]=c)にプロポーズする(PM[D][c]=1)。
cは独身(SW[c]=0)なので、プロポーズ受諾。D-cの婚約成立(SW[c]=D、SM[D]=c、PM[D][c]=2、SM0=1-1=0)。
ここまでの状況
プロポーズ表 男性婚約表 女性婚約表
PM[i][j] SM[i] SW[j]
a b c d
A 0 2 0 0 A b a C
B 1 0 0 2 B d b A
C 2 1 0 0 C a c D
D 0 0 2 1 D c d B
- 独身男性は0人(SM0=0)なので終了
- 安定マッチングが完成。SMの表から
A-b、B-d、C-a、D-c
が得られる。
解の吟味
好順位の何番目と結婚できたかを調べると、
男性 相手の好順位 女性 相手の好順位
A bは1位 a Cは1位
B dは2位 b Aは3位
C aは2位 c Dは4位
D cは2位 d Bは2位
となり、明らかに女性が不利な結果になっています。これは「男性からプロポーズする」ことに起因しており、女性からプロポーズするように変えれば、A-c、B-d、C-a、D-bの安定解が得られ、逆の結果になります。
男性 相手の好順位 女性 相手の好順位
A cは3位 a Cは1位
B dは2位 b Dは1位
C aは2位 c Aは1位
D bは3位 d Bは2位
計算プログラム
プロポーズする側を男性とします。
上記での男女の氏名は、A,B,~やa,b,~などの記号ではなく、共に1,2,~の数字にします。
好順位に同一順位や抜け順位がなってはいけません。
男性(=女性)の人数n
男性からみた女性の好順位(QM)
↓男性、好順位→
女性からみた男性の好順位(QW)
↓女性、好順位→