2015/04/12

安定マッチングとGale-Shapleyアルゴリズム

分野: グラフ理論  レベル: 数学オリンピック

Gale-Shapleyアルゴリズムを用いて安定マッチングを求めることができる。

問題設定

今回考えるのは安定結婚問題と呼ばれるものです。

安定結婚問題の例

$n$ 人の男性と $n$ 人の女性がいて,各人の異性に対する希望順位が与えられた状況を考えます。全員が「それなりに幸せになれる」ような結婚のペアの決め方(完全マッチング)を求めるのが目標です。

安定マッチング

安定結婚問題では「全員がそれなりに幸せになれる」→「かけおちするペアが発生しない」と考えます。

「かけおちするペア」とは,夫婦でない二人組で,お互い今の相手よりも希望順位が高いペアです。不安定対と言います。

安定マッチングとは

例えば,先ほどの例において緑の線$(A,c),(B,b),(C,a)$ をペアにしてみます。このとき$(B,c)$ が不安定対となります。なぜなら $B$ は今の相手 $b$ よりも新しい相手候補 $c$ の方が順位が高く、 $c$ も今の相手 $A$ よりも新しい相手候補 $B$ の方が順位が高いため,かけおちしたいと思ってしまうからです。

不安定対が存在しないような完全マッチングのことを安定マッチングと言います。安定マッチングを機械的に見つけてくれるのがGale-Shapley(ゲール-シャプレー)アルゴリズムです。

Gale-Shapleyアルゴリズム

以下の具体例も参照しながら理解してみてください!

1.誰にもキープされていない男性1人が,(今までふられていない中で)一番結婚したい女性に告白する。

2.告白を受けた女性は
受理パターン:相手がいない or 今キープしている人よりもよい相手なら告白してきた人をキープにする(今までキープしてた人とはさよならする)
拒否パターン:今キープしている人の方がよいなら告白を断る。

1,2を何回も繰り返し,全男性が誰かしらにキープされたらその時点のペア(完全マッチング)を取ってくる。これによって安定マッチングが得られる!

具体例

さっきの例でGale-Shapleyをやってみます。

ゲールシャプレーの例
  • Aがcに告白,cは相手がいないので受理(キープ)
  • Bがcに告白,cはキープしてるAよりもBのがよいのでAをふってBをキープ
  • Cがaに告白,aは相手がいないので受理

(ここまで経過した状態が上側の図)

  • Aは第一希望にふられたので第二希望のaに告白,aはキープしてるCよりもAのがよいのでCをふってAをキープ
  • Cがcに告白,cはキープしてるBよりもCのがよいのでBをふってCをキープ
  • Bがbに告白,bは相手がいないので受理(Bで妥協)

全男性が誰かにキープされたのでここで終了。安定マッチングが得られた。
(ゲールシャプレーで安定マッチングが得られることの証明は省略します。背理法で証明できますのでやってみてください)

補足

  • お互い1位どうしに希望すればそのペアは必ず安定マッチングに含まれます。
  • Gale-Shapleyの計算量は $O(n^2)$ です。効率的に安定マッチングが計算できます!
  • (男性が告白するタイプの)Gale-Shapleyアルゴリズムにおいて,出力される安定マッチングは,男性がどのような順番で告白するかによりません。
  • 役割を交換して,女性側が告白し男性側がキープするタイプのアルゴリズムも考えることができます。男性告白タイプ,女性告白タイプ,どちらを使っても安定マッチングを得ることはできますが,(一般には)異なる安定マッチングが得られます。

・似て非なる話題としてHallの結婚定理というものがあります。→Hallの結婚定理とその証明

安定マッチングが複数あるときにどれを選ぶのかは別の基準,観点で考える必要があります。

Tag: 数学の定理No.1決定戦

分野: グラフ理論  レベル: 数学オリンピック