2005 年度 冬学期 離散情報論

2005 年 10 月 24 日

Lecture 3（安定マッチング）
教員: 岩田 覚 助教授

文責: 杉村 由花

本講義では主に離散最適化に関する話題を扱う. 教科書は [4] である.

1 安定マッチング
安定マッチングの考え方は，Gale & Shapley の論文 [1] で 1962 年に提唱された．安定マッチン
グとは，例えば以下のような設定で表される問題である．
あるところに，図 1 に示される 4 人ずつの男女がいたとする（左に男性，右に女性を書いてある）．この図で，線で結ばれた者同士は互いに友人である．また，各々友人に対して好みの順序が定まっているとする（表 1, 2）．このとき，友人同士で結婚するとすると，合理的なマッチングはどうなるか？*1

td
t
³dQ³³
@Q
³³³
@Qdt³³@Qtd³´Q³³´@³Q³³@´Q´Qddt³³t³³´ @³´ ³@´³³
dt³@dt´³AlanBillCharlesDavid

Kathy
Lucy
Mary
Nancy

図 1 男女 4 人ずつの友人関係

表1好きA

*1

表2

男性側の好み←≤女性側の好み

嫌い

好き→←K

M

N–K

B

LK––C

L

M–DM

NL

嫌い

≤

–→

B

A–

L

D

B

C––

M

AC

D––N

D

A––

アメリカでは，1 対多に拡張された安定マッチング問題を研修医と病院のマッチングに応用しているが，今回は 1 対1 のものだけを扱うことにする．

1

この問題に対し，次のような条件を満たす安定マッチングを求めることにしよう．

2 部グラフ G = (U, V ; E) において，各点 u ∈ U に対して，u に接続する枝の間に全順序 ≤u ,各点 v ∈ V に対して，v に接続する枝の間に全順序 ≤v が定まっているとすると，

M ⊆ E: 安定マッチング ⇐⇒ ∀e = (u, v) ∈ E \ M , ∃f ∈ M , f

なお，ここで e = (u, v1 ), f = (u, v2 ) において fu e or fv e.

「u は v1 よりも v2 を好む」ことを表u e とは，すとする．すなわち，安定マッチングを求めることは，今ペアになっていない 2 人で「今のペアを維持するよりもその 2 人が結婚した方が互いに幸せである」という組合せがないようにマッチングすることである．
ここで，次の定理が成り立つ．
定理 3-1. 安定マッチングは必ず存在する．
安定マッチングのうちの 1 つを求めるのは簡単である．例えば，次のようにすればよい（Gale-Shapley のアルゴリズム）．
1. まず，男性側がそれぞれもっとも好む女性にプロポーズする．
2. 女性側は，プロポーズを受けた中で，もっとも好む男性をキープする．男女ともに，断られた（断った）相手は二度と選択肢にのぼることはない．

3. 断られた男性は，次に好む女性にプロポーズする．
4. 女性は，現在キープしている男性よりも好みの男性からプロポーズを受けた場合，現在キープしている相手を断る．

5. 断られた男性にまだ結婚相手の候補がいるならば，3 に戻る．
例として，Gale-Shapley のアルゴリズムをはじめの例に適用すると，表 3–8 のように動く．
ループを繰り返す度に結婚相手の候補が減っていくので，Gale-Shapley のアルゴリズムは有限時間で終了する．そして，このアルゴリズムの出力は安定マッチングになっている．（ある男性にとって今の相手より好みの女性に関し，その女性にとってもその男性が今の相手より好みであったなら，この男性からのプロポーズ（これは，必ず行われているはず）を断ったはずがない，と考えると，この出力が安定マッチングになっているとわかる．）
安定マッチングは唯一ではないことに注意しよう（たとえば，男性・女性の立場を入れ替えてGale-Shapley のアルゴリズムを行うと，一般には元と違った出力が得られる）．すると，このアルゴリズムによる出力とは別に「みんなが，もっと幸せに」なれるマッチングがあるのではないか，と考えたくなるが，それには新たな「幸福度」の基準を導入しなければならないため，この話題を超えている．（「幸福度」を考慮した最適安定マッチングなどについては，[3] が参考になる．）しかし，Gale-Shapley のアルゴリズムで得られたマッチングは，安定マッチングの中でもっとも男性

2

表3

表 4 女性側の反応

男性側からプロポーズ

好き←A≤嫌い好き→

←–−→

K

M

NK

B

B

L

K––L

DCL

M––M

A

D

M

N

L–N

D

≤

A°

表 5 Charles のプロポーズ

嫌い好き→←––−→B /°
C –
D°

CA–A
B

K°

嫌い≤→

M

N–L°

K––

N–C/
L M

–––DM°L–?
表6Mary の反応

好きK

←
BL

DM

AND≤

A°

表 7 David のプロポーズ

嫌い好き→←––B /°C –C /°
D –A––−→

AB
CDK°

≤

表 8 アルゴリズム終了

嫌い好き→

←N

K––L

D

M/
L °

––M

AL–N

D°

L°

/
M N–−→

M

K

B

嫌い≤A°

–→–B /C –°C /°D –A––

側の好みを反映したものになっている*2 ．
また，もう 1 つ注意すべきなのは，安定マッチングは完全マッチングとは限らないということである．はじめの例において，Mary の Charles と David に対する好みの順序を入れ換えてGale-Shapley のアルゴリズムを実行すると，完全マッチングにならないことがわかる．なお，ある安定マッチングにおいてペアを作れなかった人は，どんな安定マッチングにおいてもペアを作れないことが証明されており，「絶望の定理」と呼ばれている．

2 安定マッチングからリスト彩色へ
2 部グラフ G = (U, V ; E) において，頂点の最大次数を d∗ , 辺彩色に必要な最低色数を γ とすると，γ = d∗ である．これは，第 1 回で扱ったことであった．
今，各枝 e に着色可能な色のリスト L(e) が与えられているものとする．このとき，隣接する枝同士が異なる色となるようにリスト内の色を使って彩色できるとき，G はリスト彩色可能という*3 ．

*2 だから，みんなはどうすればいいか…わかるよね？
*3 歴史的には，Dinitz により 1978 年に提唱された「完全 2 部グラフ Kn,n は n 色でリスト彩色可能か？」という問いに端を発する．この問題の解決は，[2] による．

3BB¢Bg¢
B@¢@B©
@B¢©©©
¡µ@Bde¡©
t¢¡tvu d¡¤B@+́´´¡ ¤B@¡ ¤B @hB@¡¤¡¤BB¤¤
図2

枝に順序をつける

定理 3-2 (Galvin, 1995). 2 部グラフ G = (U, V ; E) において∀e ∈ E, |L(e)| ≥ γ =⇒ リスト彩色可能．
証明. G 上の辺彩色 φ: E → {1, 2, . . . , γ} を考える．ここで塗る色は，L(e) に関係なく好きに塗ってよいとすると，2 部グラフなので γ 色で塗ることができる．

u ∈ U に接続する枝 e, h に関して∆h ≤u e ⇐⇒ φ(h) ≥ φ(e),v ∈ V に接続する枝 e, g に関して∆g ≤v e ⇐⇒ φ(g) ≤ φ(e)とする（図 2）．
枝 e = (u, v) に関して，D(e) = {h|h ≤u e} ∪ {g|g ≤v e}とすると，|D(e)| ≤ γ.

よって，次の命題 3-3 により定理は証明される．

命題 3-3. 2 部グラフ G = (U, V ; E) において∀e ∈ E, |L(e)| ≥ |D(e)| =⇒ リスト彩色可能．
証明. 証明は，帰納法によって行う．
色 l に着目し，El = {e|l ∈ L(e)} を枝集合とする G の部分グラフ

Gl = (U, V ; El )を考えると，Gl には安定マッチングM が存在する．そこで，M の各枝に色 l をつけ，E から削除する．また，El の各枝 e のリスト L(e) から l を削除する．

4

このとき，e ∈ E \ El に関しては，L(e) は変化せず，|D(e)| は増えることはない．一方，e ∈ El \ M に関しては，|L(e)| が 1 減少するが，D(e) ∩ M 6= ∅（安定マッチングの定義より）なので，|D(e)| も少なくとも 1（実際には 1 または 2）減少．したがって |L(e)| ≥ |D(e)|．
この証明に沿って彩色を行うとき，もっとも時間がかかるのは安定マッチング M を求めるところである．グラフの辺数 |E| = m, 使用可能な全色数 |L| = k とすると，色 l について安定マッチングを求めるときには，最悪の場合辺でつながれた全てのペアを 1 回ずつ調べる（女性側から見ると，今キープしている人と新しくプロポーズしてきた人の順位を比較する）ので，計算量はO(|El |). よって，全ての色についてマッチングを求めるので，|El | ≤ m よりリスト彩色の計算量は O(km) となる．

定理 3-2 に関連して，次の予想が提唱されているが，未解決である．
予想 3-4. 一般のグラフにおいて，∀e ∈ E, |L(e)| ≥ γ =⇒ リスト彩色可能．

参考文献[1] D. Gale and L. S. Shapley: College Admissions and the Stability of Marriage. Amer. Math.
Monthly, 69 (1962), pp. 9–14.
[2] F. Galvin: The list chromatic index of a bipartite multigraph. Journal of Combinatorial
Theory, B63 (1995), pp. 153–158.
[3] D. Gusfield and R. W. Irving: The Stable Marriage Problem: Structure and Algorithms.
MIT Press, 1989.
[4] A. Schrijver: Combinatorial Optimization. Springer-Verlag, 2003.

5