安定結婚問題
呑谷優奈(指導教員：萩田真理子)

はじめに1グとなる．また，どの男性も，このアルゴリズムで得られる安定マッチングにおける パートナーの方が，他の安定マッチングにおけるパー トナーよりも好みであることが知られている．これは，男性のランクの和が最小の解となり，男性最良安定マッチングと呼ばれる．
逆に，女性からプロポーズした場合は，女性優先 GSアルゴリズムと呼び，解は女性最良安定マッチングとなる．

２部グラフにおけるマッチング問題は，労働者に仕事を割り当てる数学モデルとして知られている．その中でも，安定結婚問題は更にマッチングの「安定性」という概念を導入したものであり，広く応用されており，例として研究室配属や，研修医のマッチングなどに使われている．本研究では，安定結婚問題の解法として良く知られるゲイル・シャプレーアルゴリズムを用い，より全体の不満度の小さい安定マッチングを求めることを目的とする．

GS アルゴリズムで求められる解には偏りがある．そのため，ランクの総和が大きな安定マッチングが解となる例題の選好順序にはどのような傾向があるのか，同じ例題に対する男性最良安定マッチングと女性最良安定マッチングの差について検証するための実験を行った．

安定結婚問題2

実験

4

安定結婚問題とは，各 n 人の男女と，各個人の選好順序という例題が与えられたときに，解として安定マッチングを求める問題である．ここで，選好順序とは，各個人の好みに基づき異性全員を全順序で並べたリストである．安定マッチングとは，互いに現在の相手よりも好きであるペア (ブロッキングペア) が存在しないマッチングのことである．また，あるマッチングにおいて，m のパートナー w が m の選好順序において i番目の時，m のランクを i − 1 とする．つまり，ランクとは不満度であり，ランクの総和が小さい程全体の不満度は小さく，男女のランクの差が小さい程，男女が平等であるということになる．
ゲイルとシャプレーはどのような例題に対しても少なくとも１つの安定マッチングが存在し，その１つを多項式時間で求められることを示した．

4.1

以下は男女の参加人数が各 3 人の時の実験概要であるが，同様にして 4 人の場合も行う．尚，5 人以上の場合については，計算量が大きいため実施できなかった．

• 男性 [mA，mB ，mC]，女性 [wa，wb，wc] を用意する．
• 選好順序を以下の様に決める．
– 男性，女性各 3 人を辞書式に並び替えたリス
トを用意し，それぞれ 0 から番号を付ける．
これは選好順序の候補のリストである．
– 女性は選んだ選好順序の番号が wa ≤ wb ≤wc となる様に選好順序を決める．

ゲイル・シャプレーアルゴリズム

3

ゲイル・シャプレーアルゴリズム (GS アルゴリズム)とは，任意の例題に対して，多項式時間 O(n2 ) で解を見つけるアルゴリズムである．

3.1– 男性は mA のみ選好順序を固定し，残りの2 人は全通りの選好順序を選ぶ．
• 男性優先 GS アルゴリズム，女性優先 GS アルゴ
リズムを上で決めた例題について実行する．

アルゴリズム

最初に全員の状態をフリーとする．全員の状態が婚約となったときのマッチングを安定マッチングとする．

男性 mA を 0 から 5 まで動かせば，男女合計 6 人の選好順序の組み合わせを重複を除き全て調べることができる．

• フリーである男性 m が存在する限り，以下を繰り返す．

4.2

1. w を m がまだプロポーズしていない女性の中で最も好みの女性であるとする．

実験結果

実験の結果，参加人数が 3 人の場合と 4 人の場合では同様の結果が出た．ここでは参加人数 4 人の結果のみ紹介する．図 1 から分かるように，全通りの選好順序について調べているため，男性優先と女性優先では真逆の結果となっている．

2. もし w がフリーであれば，m と w の状態を婚約とする．
そうでなければ，現在の婚約者と m のうち，w にとってより好みの男性と婚約させ，拒否された男性をフリーにする．
3.2

実験概要

男性最良安定マッチング

上に示したアルゴリズムでは，男性から女性にプロポーズをしており，これを男性優先 GS アルゴリズムと呼ぶ．男性は今のパートナーよりも好みの女性には必ず振られており，振った女性はその男性よりも好みの相手と婚約していることになるため，安定マッチン

図 1: それぞれの平均
図 2，3 より，優先された方の性別のランクの和の平均にはほとんど差はないことが分かる．そのため，ラ5

ンクの総和と差の平均はもう一方の性別のランクの和の平均に依存している．その結果，男性優先，女性優先の両方で男性 mA の選好順序が 23 の時，即ち辞書式で一番最後の時に，ランクの総和と差の平均が最大となっている．従って，あまり良くない安定マッチングが解となっていることが分かる．その様な例題では，ランクの総和と差がより小さい安定マッチングが存在する可能性が高いと考えられる．

人ランクの大きい順に z を選ぶ．３人のパートナーを交換する．

(d) (b) でできた２つのマッチングにブロッキングペアがあるか調べる．ブロッキングペアがない場合は，安定マッチングリストに追加する．ブロッキングペアがある場合は，(c) に戻る．
3. 2 で新しい安定マッチングが求められた場合は，その安定マッチングに対して 2 を実行する．求められなかった場合は，4 へ．
4. 安定マッチングリストを返す．
5.2

まず，本アルゴリズムの正当性を確かめた．参加人数が 9 人までであれば，任意の例題に対する全ての安定マッチングを求めることができる．そのため，参加人数が各 9 人であるランダムな例題を与えた．その例
題 150 件の内，安定マッチングが 1 つしかない (男性最良，女性最良安定マッチングが一致) ものが 29 件，安定マッチングが 2 つのものが 40 件，安定マッチングが 3 つ以上あるものが 51 件であり，その中で GS アルゴリズムの解よりもランクの総和が小さい安定マッチングがあるものが 27 件であった．本アルゴリズム
では，その 27 件の全てにおいてランクの総和が最小である解を求めることができた．また，27 件中 23 件に関しては，GS アルゴリズムの解よりもランクの総和が小さい解全てを求めることができた．
次に，人数が多くなった場合により良い解がどの程度見つけられるのかについて確かめた．参加人数が各20 人であるようなランダムな例題 156 件を与えたところ，より良い解が見つかったものが 73 件であった．
また，参加人数が各 30 人であるような例題 141 件を与えたところ，より良い解が見つかったものが 69 件であった．これより，人数が多くなるにつれて，本アルゴリズムでより良い解が求められる割合が増えると考えられる．
また，本アルゴリズムにより非常に改善される例もあった．参加人数各 9 人のある例題に対して，男性最良，女性最良安定マッチングのランクの総和が共に 72であったが，3 組のペアの交換を 3 回行うことで，ランクの総和が 18 にまで改善された．この様な例題を拡張することで，参加人数が増えても本アルゴリズムで改良できる様な例題が存在することが分かる．

図 2: 男女各 4 人の男性優先 GS アルゴリズム

図 3: 男女各 4 人の女性優先 GS アルゴリズム

提案手法

5

全体の不満度を減らすために，男性最良安定マッチング，女性最良安定マッチングよりもランクの総和が小さい安定マッチングを求める. 次のような方法で解を求める．

5.1

評価アルゴリズム1. 男性優先 GS アルゴリズム，女性優先 GS アルゴリズムを実行する．解が一致した場合は，それを返す．
2. 安定マッチングを受け取ったら，ランクの和の大きい方の性別に対して，ランクの大きい順に参加(n−1)
者を並び替える．その中で，ランクが 2 以上の人をランクの大きい順に x とする．x に対して，次の (a)，(b) を繰り返し，その後 (c)，(d) を繰り返す．

6

まとめと今後の課題

本研究では，GS アルゴリズムよりもランクの総和が小さな解を求めるアルゴリズムの提案を行った．その結果，求められる例題も多くあったが，本アルゴリズムでは上手く行かない例も存在した．今後はそのような例題についても，より良い解を見つけられるようなアルゴリズムの考案を行って行きたい．

(a) ランクの大きい順に y を選び，x と y のパートナーを交換する．

参考文献(b) (a) でできたマッチングにブロッキングペアがあるか調べる．ブロッキングペアがない場合は，安定マッチングリストに追加する．ブロッキングペアがある場合は，(a) に戻る．

[1] Rebert A.Wilson,Colourings and the Four-ColourTheorem,Oxford Science Publications(2002)[2] 池田文男，「数学トレッキングツアー」, 教育出版株
式会社 (2006)(c) ランクの大きい順に y を選び，更にもう１
6