主張

※マッチング$\,M\,$に飽和されていない点$\,v\,$$\,\cdots\,$マッチング$\,M\,$が点$\,v\,$を端点とする辺を含むこと。

日本で絶望の定理と言えば，上の定理を指します。

しかし海外では病院僻地定理(rural hospitals theorem)と呼ばれていて，絶望の定理とは呼ばれていないことに注意してください。

このサイトではWikipediaにおける病院僻地定理の，一対一における場合を絶望の定理，多対一における場合を病院僻地定理として改めて区別することにします。

イメージ

この定理も安定マッチングのイメージで解説した下のお見合いのイメージで捉えてみましょう。

このイメージ上で，
様々なマッチングは，様々な世界線におけるお見合い結果と考えることができます。

例えば$2$つのマッチング$\,A,B\,$がある場合，
ある世界線では$\,A\,$というお見合い結果が実現し，
別の世界線では$\,B\,$というお見合い結果が実現するイメージです。

そのように考えれば，安定マッチングは数あるお見合い結果(マッチング)の中で全体的に幸せな結果，
つまり「全体的なハッピーエンド」として考えられます。

このとき絶望の定理は次のように書き換えられます。

結局，全体的なハッピーエンドにおいて幸せになれない人が幸せになるには，
全体的な幸せを壊すことやパートナーに求める条件を妥協することなどが必要だとということですね。

絶望の定理の証明を$2$つ紹介します。

どちらの証明が理解しやすいか判断がつかなかったので，どっちも紹介することにしました。

どちらもお見合いの設定で証明を行いますが，数学的な言い換えができるように書いていますので，
厳密性が気になる方は数学的には何を述べているのかを考えながら読むと良いでしょう。

永遠に長くなる鎖を利用した証明

$2$部グラブ$\,G=(X\cup Y,E)\,$において，ある人$\,x_1 \in G\,$は安定マッチング$\,D\,$でパートナーができなかったとします。

一般性は失われないので$\,x_1 \in X\,$，つまり$\,x_1\,$は男であるとします。

そして，ある別の安定マッチング$\,M\,$では$\,x_1\,$に彼女ができたと仮定し，
背理法により証明していきます。

安定マッチング$\,M\,$においては彼女$\,y_1 \in Y\,$がいるので，下図のようになります。

このとき安定マッチング$\,D\,$において，女性$\,y_1\,$に男性$\,x_1\,$より魅力的な彼氏がいないとすると$\,D\,$の安定性に矛盾してしまいます。

よって$\,D\,$において$\,x_1\,$より魅力的な$\,y_1\,$の彼氏$\,x_2\,$が存在することが分かります(下図)。

さらに安定マッチング$\,M\,$において，男性$\,x_2\,$に女性$\,y_1\,$より魅力的な彼女がいないとすると$\,M\,$の安定性に矛盾してしまいます。

よって$\,M\,$において$\,y_1\,$よりも魅力的な$\,x_2\,$の彼女$\,y_2\,$が存在することが分かります(下図)。

同様の議論で下図のような鎖を作り続けることができます。

このとき一つ問題となることがあります。

それは男性$\,x_1,x_2,\ldots,x_n\,$や女性$\,y_1,y_2,\ldots,y_n\,$は異なる男性・女性なのか？という問題です。

そうでない場合，例えば$\,x_1=x_3\,$のとき，下図のように鎖が縮んでしまいます。

後でこの鎖が永遠に長くなることを示して矛盾を導くため，このような場合があると困ります。

そこでこの鎖が縮まない，
つまり$\,x_1,x_2,\ldots,x_n\,$や$\,y_1,y_2,\ldots,y_n\,$は異なる男性・女性であることを示します。

帰納的に示しましょう。

$\,x_1\,$と$\,x_2\,$，$\,y_1\,$と$\,y_2\,$が異なることは$\,x_2,y_2\,$の取り方から明らかです。

ここで$\,x_1,x_2,\ldots,x_{k} \,$や$\,y_1,y_2,\ldots,y_k\>\; (2 \leq k \leq n-1)\,$が互いに異なるとします。

このとき$\,x_{k}\,$と$\,x_{k+1}\,$，$\,y_{k}\,$と$\,y_{k+1}\,$が異なることは，$\,x_{k+1},y_{k+1}\,$の取り方から明らかです。

また$\,x_1\,$と$\,x_{k+1}\,$も異なります。

なぜなら元々$\,D\,$において$\,x_1\,$に彼女はできなかったという状況であるのに，
同じだとすると，彼女$\,y_k\,$ができてしまうからです。

また$\,x_{k+1}\,$は$\,x_2,x_3,\ldots,x_{k-1}\,$とも異なります。

なぜなら$\,x_i\>\;(2\leq i \leq k-1)\,$と同じだとすると

$\,x_i\,$には$\,D\,$において二人の彼女$\,y_{i-1},y_k\,$が存在することになってしまうからです。

同様に二人以上彼氏を作らないことから，$\,y_{k+1}\,$は$\,y_1,y_2,\ldots,y_{k-1}\,$とは異なることが分かります。

以上より$\,x_1,x_2,\ldots,x_n\,$や$\,y_1,y_2,\ldots,y_n\,$は異なる男性・女性であることが分かりました。

そのため下の鎖は永遠に長くなることとなり，これは$\,G\,$の点が有限であることに矛盾します。

したがって題意は示されました。$\quad\square$

ゲイル-シャプレイのアルゴリズムを利用した証明

※ゲイル-シャプレイのアルゴリズム(以下GSAと呼びます)を知らない方は，こちらで確認してください。

証明を理解するために次の用語を導入します。

定義よりこのような男性(女性)最良マッチングが少なくとも一つ存在することを示せたら，
絶望の定理の証明としては十分であることが分かりますね。

よってGSAによって得られる安定マッチングが男性最良であることを示すことに問題は帰着しました。

そのためには次の補題を証明すれば十分です。

GSAでは男性の好み順に告白を行うので，上のことを示せば，
他の安定マッチングでGSAの安定マッチングよりも幸せになることはなくなるからです。

以下では，この補題を数学的帰納法を用いて証明していきます。

GSAにおいて「男性が告白$\,\to\,$女性が受理・拒否」という作業が$\,n\,$回行われたときを考えます。

まず$\,n=1\,$のときについて考えましょう。

ここに証明のpointがつまっているので，じっくりと考えていきましょう。

$\,1\,$回の作業の結果，男性$\,u\,$が女性$\,v\,$に振られたとします。

そして，ある別の安定マッチング$\,M\,$では男性$\,u\,$と女性$\,v\,$が付き合っていたとしましょう。

振られたことから，そのとき女性$\,v\,$には男性$\,u\,$よりも魅力的な男性$\,x\,$の手紙を持っていることが分かります(下図)。

作業はまだ$\,1\,$回しか行われていないため，女性$\,v\,$は男性$\,x\,$にとっても第一候補です。

そのため$\,M\,$において男性$\,x\,$に彼女ができたとしても，女性$\,v\,$よりは魅力的ではありません。

これは男女$\,xv\,$が不安定な組となり，$\,M\,$の安定性に矛盾してしまいます。

よって$\,n=1\,$のときは示されました。

次に$\,n \leq k\,$のとき仮定が成り立つ，

つまり「$\,k\,$回の作業内で振られた男性は，振った女性と他の安定マッチングで付き合うことはない」ことが成り立ったとしましょう。

そして$\,k+1\,$回作業後，男性$\,u\,$が女性$\,v\,$に振られたのに，別の安定マッチング$\,M\,$では男性$\,u\,$と女性$\,v\,$が付き合っていたとしましょう。

ここでも同様に振られたことから，
$k+1$回目の作業では女性$\,v\,$には男性$\,u\,$よりも魅力的な男性$\,x\,$の手紙を持っていることが分かります(下図)。

このとき男性$\,x\,$のランキングで，$\,v\,$よりも魅力的な女性たちについて考えましょう。

GSAでは男性の好み順に告白するので，男性$\,x\,$は$\,k\,$回の作業内でこの女性たちへ告白を行っており，さらに振られています。

そのため帰納法の過程から$\,M\,$において，男性$\,x\,$は$\,v\,$よりも魅力的な彼女はできないということです。

これは男女$\,xv\,$が不安定な組となり，$\,M\,$の安定性に矛盾してしまいます。

よって$\,n=k+1\,$のときも成り立つことが分かりました。

したがって帰納法より補題が示されたので，GSAが男性最良性をを持つことも分かり，題意が示されました。$\quad\square$

今回の記事では絶望の定理を解説いたしました。

名前だけでなく，主張の面白さを理解していただけたでしょうか？

絶望の定理を多対一に拡張した病院僻地定理については要望があったら，記事にしたいと思います。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• $[1]$ D.G. McVitie,L.B. Wilson.”The Stable Marriage Problem”.Communications of the Association for Computing Machinery.1971出版.14巻.p.486-490
• $[2]$ “Rural hospitals theorem”.Wikipedia.2022-01-08更新.https://en.wikipedia.org/wiki/Rural_hospitals_theorem.2024-06-09参照.