安定結婚問題「絶望の定理」の証明

はじめに

この記事ではこちらの記事で紹介した絶望の定理の証明を行っていきます。
（安定結婚問題って何？という方は上の記事を先に読むことを強くお勧めします！）

絶望の定理とは「ある安定マッチングに入れなかった男女はあらゆる安定マッチングに入れない」という主張で、安定結婚問題という数学の問題をめぐる定理です。
ネットで探してみてもきちんとした証明が見つけられなかったので、気合を入れて証明してみました。

「証明ってアレでしょ...数式とかいっぱい出てくるんでしょ...」と思う方もいるかもしれませんが、本記事には数式はほとんど出てきません。そのかわりに言葉と図による説明が続きます。
**こんな証明もあるんだ！**という新たな発見があると思うので、証明に慣れ親しんでいない人も是非読んでみてもらえると嬉しいです。

定義

まず、証明に必要な用語の定義を行います。
用語の解釈的な説明はこちらの記事に譲るとして、本記事では数学的に正確な定義をするという観点で筆を進めていきます。

男女集合、選好リスト、受け入れ可能ペア

安定結婚問題のインスタンスは男性集合、女性集合、および各人の選好リストから構成されます。
選好リストからは受け入れ可能ペアという集合が誘導されます。

男性集合、女性集合とはその名の通りマッチングシステム(例えば合コン)に参加する男女の集合です。$M$を男性の集合、$W$を女性の集合と表記することにします。こちらの記事 の例でいえば$M$は $\{ \rm Alex, Bob, Carl \}$であり、$W$は$\{ \rm Alice, Becky, Candy \}$です。

**選好リスト(preference list)**とは各個人がもつ異性への好みを表すリストのことです。
男性$m$の選好リスト上で女性$w_1$が女性$w_2$よりも上位にいる（つまり、男性$m$は$w_1$よりも$w_2$を好んでいる）ことを$w_1 \succ_m w_2$と表記します。
女性の選好リストについても同様に、$m_1 \succ_w m_2$を定義します。

互いが互いの選好リストに含まれているような男女ペアを**受け入れ可能ペア(acceptable pair)**と呼びます。受け入れ可能ペア全体の集合を$A$と表記します。
こちらの記事 の例でいえば$A$の要素は (Alex, Alice), (Bob, Alice), (Alex, Becky), (Bob, Becky), (Carl, Becky), (Bob, Candy) です。

マッチング

$A$の部分集合のうち、同じ人間が2回現れないものをマッチングと呼びます。
例えば$\{ \rm (Alex, Alice), (Bob, Becky) \}$はマッチングです。
一方で、$\{ \rm (Alex, Alice), (Bob, Becky), (Bob, Candy) \}$ はマッチングではありません。Bobが二回登場しているからです。誰かが二股してるような男女ペアの集合はマッチングと認めないということです。
マッチング$\mu$において男性$m$とマッチしている女性を$\mu(m)$と表記します。同様に、女性$w$のマッチしている相手を$\mu(w)$と表記します。

マッチング$\mu$においてマッチしていない人間の集合を$S_\mu$と表記します。(Single personのSです。)
例えば$\mu = \{ \rm (Alex, Alice), (Bob, Becky) \}$について、CandyとCarlはマッチングに含まれていません。したがって、$S_\mu = \{ \rm Candy, Carl \}$です。
このときCandyとCarlはマッチング$\mu$において独身であると言います。

ブロッキングペアと安定マッチング

安定結婚問題において中心的な概念となる**ブロッキングペア(blocking pair)**について定義します。

$\mu$を$A$上のマッチングとします。このとき、$(m, w) \in A$が$\mu$に対するブロッキングペアであるとは、$(m, w)$が次の$\rm (BP1), (BP2), (BP4), (BP4)$のいずれかを満たすことを指します:

\begin{align}
\rm{(BP1)} & \quad m \succ_w \mu(w) \quad \land \quad w \succ_m \mu(m) \\
\rm{(BP2)} & \quad m \succ_w \mu(w) \quad \land \quad m \in S_\mu \\
\rm{(BP3)} & \quad w \in S_\mu \quad \land \quad w \succ_m \mu(m) \\
\rm{(BP4)} & \quad w \in S_\mu \quad \land \quad m \in S_\mu
\end{align}

上の式の中の $\land$ は論理積（＝かつ、And）を表します。
ブロッキングペアとは、概念的には「現在のマッチングを裏切って駆け落ちをするインセンティブをもつ男女ペア」のことを指します。このようなペアできるマッチングは不安定であるとみなされ、不安定なマッチングを生み出すマッチングシステムは遅かれ早かれ崩壊してしまうという報告がなされています。¹
ブロッキングペアのいないマッチングを**安定マッチング(stable matching)と呼びます。
男性集合、女性集合、各人の選好リストを受け取り、安定マッチングを求める問題を安定結婚問題(stable marriage problem)**と呼びます。

安定結婚問題の具体例

安定結婚問題のインスタンスとマッチングの例を以下の図に示します。
$M=\{ \rm A, B, C, D, E \}$, $W = \{ \rm a, b, c, d, e \}$であり、各個人の横に記載しているのが選好リストです。
紫の線で表現されているペアの集合 $\mu = \{ \rm (A, b), (B, d), (C, e), (D, a) \}$ はマッチングです。また、$S_\mu = \{ \rm E, c \}$ です。

ここで、$\mu$ に対するブロッキングペアが少なくとも2つ存在します。$\rm (A, a)$と$\rm (C, c)$です。
$\rm (A, a)$について： $\rm A \succ_a \mu(a)$ かつ $\rm a \succ_A \mu(A)$のため、$\rm (A, a)$ は$\rm (BP1)$を満たしています。したがって$\mu$に対するブロッキングペアです。
$\rm (C, c)$について： $\rm{c} \in S_\mu$ かつ $\rm c \succ_C \mu(C)$ のため、$\rm (C, c)$ は$\rm (BP3)$を満たしています。したがって$\mu$に対するブロッキングペアです。

下の図で表されるマッチングはGale-Shapleyアルゴリズムという有名なアルゴリズムを使って求めた安定マッチングです。
ブロッキングペアが存在しないことをご自身で確かめてみてください。²

絶望の定理

先にも書きましたが、絶望の定理とは「ある安定マッチングに入れなかった男女はあらゆる安定マッチングに入れない」という定理です。
これをもう少し厳密に書くと次のような主張になります。

同一のインスタンス上の安定マッチング$\mu_1, \mu_2$について、$p \in S_{\mu_1}$かつ$p \not \in S_{\mu_2}$となるような $p \in M \cup W$は存在しない。

すなわち、すべての男女は「$\mu_1$中でも$\mu_2$中でもマッチしている」人と「$\mu_1$中でも$\mu_2$中でもマッチしていない」人のいずれかに分類できるという主張です。
マッチしていない側に振り分けられてしまった人にしてみれば、まさに絶望の定理というわけです。

絶望の定理の証明

これから絶望の定理の証明を行っていきます。³
絶望の定理を証明する流れは以下のようになります。

1. 2つのマッチングを重ね合わせたグラフの連結成分はパス、サイクル、孤立点の3つに分類される。
2. マッチング$\mu_1$中でマッチしており$\mu_2$中で独身である人がいるならば、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にパスが存在する。つまり、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にパスが存在しなければ、そのような人は存在しない。
3. $\mu_1$と$\mu_2$がともに安定マッチングであるならば、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にはパスは存在しない。

この1, 2, 3をすべて示すことができれば、ただちに「$\mu_1$と$\mu_2$がともに安定マッチングであるならば、$\mu_1$中でマッチしており$\mu_2$中で独身である人はいない」という命題（＝絶望の定理）を導くことができます。

数学の証明ではこんなふうに、ある命題を複数の命題に分割し、分割したそれぞれの命題を証明することで元の命題を示すということがよく行われます。元の命題を定理(Theorem)、分割した命題を**補題(Lemma)**と呼びます。
今回で言えば、絶望の定理は「定理」、上の1～3の命題は「補題」です。

ここから1～3の補題について説明していきます。

マッチングを重ね合わせたグラフ

$\mu_1, \mu_2$を（安定とは限らない）一般のマッチングとします。このとき、$\mu_1$と$\mu_2$を重ね合わせたグラフを$\mu_1+\mu_2$と表記します。
$\mu_1+\mu_2$は$\mu_1$と$\mu_2$のリンクをすべて含んでいるようなグラフになります。
下の図は$\mu_1, \mu_2, \mu_1+\mu_2$の例です。

この例において、$\mu_1+\mu_2$を重ねたグラフ中の連結成分（リンクでつながっている部分）は下の図のように合計6つ存在します。

①③④のように、ノード→リンク→ノード... の列が閉じている連結成分をサイクルと呼びます。
②のように、ノードから始まってノードで終わる連結成分をパスと呼びます。
⑤⑥のように、リンクにつながっていないノードを孤立点と呼びます。

このとき以下の補題1が成立します。

任意のマッチング$\mu_1, \mu_2$について、$\mu_1+\mu_2$中の連結成分は、サイクル、パス、孤立点のいずれに分類できる。

この補題は$\mu_1$および$\mu_2$の各頂点の次数（つながっているリンクの数）が高々1であることから容易に導くことができますが、証明は割愛します。

また、$\mu_1+\mu_2$の連結成分に関する重要な観察として以下の3つがあります。

• サイクルに属するすべての人は、$\mu_1$中でも$\mu_2$中でもマッチしている。
• 孤立点にに該当する人は、$\mu_1$中でも$\mu_2$中でもマッチしていない。
• パスの始点と終点以外の人は、$\mu_1$中でも$\mu_2$中でもマッチしている。始点と終点に該当する人は、$\mu_1$と$\mu_2$の一方ではマッチしており、もう一方ではマッチしていない。

ここから次のように補題2を導くことができます。

マッチング$\mu_1$中でマッチしており$\mu_2$中で独身である人がいるならば、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にパスが存在する。つまり、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にパスが存在しなければ、そのような人は存在しない。

安定マッチングを重ね合わせたグラフの特徴

ここまでで、絶望の定理を証明する準備がすべて整いました。
ここから3つの補題の中で最も重要な次の命題を証明していきます。

$\mu_1$と$\mu_2$がともに安定マッチングであるならば、$\mu_1$と$\mu_2$を重ね合わせたグラフ中にはパスは存在しない。

背理法を用います。
$\mu_1$と$\mu_2$がともに安定マッチングであり、$\mu_1+\mu_2$中にパスが存在すると仮定します。

下の図のように、パス中の男女に $m_1, w_1, m_2, \dots , m_{n-1}, w_{n-1}, m_n, w_n$ という順番で名前をつけていきます⁴。 ここで、$n$はパスの長さです。
下の図を見てわかるように、パスは「男性→$\mu_2$のリンク→女性→$\mu_1$のリンク→男性...」という繰り返しが続き、最後に女性で終わるような構造をしています。

このときまず、$m_2 \succ_{w_1} m_1$であることがわかります。なぜなら、もし$m_1 \succ_{w_1} m_2$であれば、$(m_1, w_1)$が$\mu_1$に対するブロッキングペア$\rm (BP2)$となってしまい、$\mu_1$が安定マッチングであるという仮定に矛盾するためです。

次に$w_2 \succ_{m_2} w_1$であることがわかります。なぜなら、もし$w_1 \succ_{m_2} w_2$であれば、$(m_2, w_1)$が$\mu_2$に対するブロッキングペア$\rm (BP1)$となってしまい、$\mu_2$が安定マッチングであるという仮定に矛盾するためです。
（ひとつ上の議論で$m_2 \succ_{w_1} m_1$となることが確定していることに注意。）
同様にして、

\begin{align}
\rm{(\alpha)} & \quad w_i \succ_{m_i} w_{i-1} \quad (i = 2, 3, ..., n) \\
\rm{(\beta)} & \quad m_{i+1} \succ_{w_i} m_i \quad (i = 1, 2, ..., n-1)
\end{align}

を導くことができます。

パスの最後の部分については $w_{n-1} \succ_{m_n} w_n$になっている必要があります。なぜなら、もし$w_{n} \succ_{m_n} w_{n-1}$であれば、$(m_n, w_n)$が$\mu_1$に対するブロッキングペア$\rm (BP3)$になってしまい、$\mu_1$が安定マッチングであるという仮定に矛盾するためです。
一方でこれは**$\rm (\alpha)$に矛盾します**。

つまり、「各男女がマッチング$\mu_1$と$\mu_2$でマッチしている異性のうち、どちらを好んでいるか？」という問いに答えようとすると、どのようなパターンでも矛盾が発生してしまうのです。

したがって背理法の仮定が棄却され、補題3が証明されました。（証明終了）

おわりに

安定結婚問題の「絶望の定理」を証明しました。いかがでしたでしょうか？
最後までついていけなかったという方も、証明の雰囲気を味わっていただけたなら筆者としてはとても嬉しく思います。

最後まで読んでいただき、ありがとうございました。

1. Roth, Alvin E. "The economist as engineer: Game theory, experimentation, and computation as tools for design economics." Econometrica 70.4 (2002): 1341-1378. ↩

2. $(\rm{E}, \rm{b})$は受け入れ可能ペアではないため$\rm (BP4)$に該当しないことに注意。 ↩

3. ここで紹介している証明はこの記事の執筆者のオリジナルの方法になります。(ちゃんと調査したわけではないので、もしかしたら先に同じ証明方法を発表している研究者がいるかもしれませんが...) もしあなたが大学院生で、正式な引用元を探している場合は、下記の文献に査読付きの証明が載っているのでそちらを参考にしてみてください：Gusfield, Dan, and Robert W. Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. ↩

4. 実はここで議論の一般性が失われています。なぜならパスには偶数長のものと奇数長のものがあるためです。（図は奇数長のパスを表しています。）しかし、偶数長のパスが存在しないことについてもこの記事とまったく同じ手順で証明することができます。 ↩