【グラフ理論】安定マッチングとは？ 定義・イメージからゲイル-シャプレイのアルゴリズムまで解説
こんにちは！半沢です！
今回の記事ではグラフ理論における安定マッチング(stable matching)について解説したいと思います。
定義・性質から，安定マッチングを構成するゲイル-シャプレイのアルゴリズム(Gale-Shapley algorithm)まで解説したいと思います。
このアルゴリズムは絶望の定理の証明の鍵となります。
またアルゴリズムの正当性の証明も非常に面白いので，ぜひ読んでいってください。
安定マッチング(stable matching)
導入
安定マッチングの定義を理解するために次の用語を導入します。
定義
グラフ\(\,G\,\)の点\(\,v\,\)に対して，その隣接点の集合を\(\,N(v)\,\)と書くことにする。
\(\,N(v)\,\)にある全順序\(\,\stackrel{v}{\leq}\,\)が定められているとき，\(\,N(v)\,\)を\(\,v\,\)のランキングと呼ぶ。
またグラフ\(\,G\,\)の各\(\,N(v)\,\)がランキングであるとき，\(\,G\,\)をランキンググラフと呼ぶ。
小難しい言葉を使っていますが，イメージはとてつもなく簡単です。
例えばグラフ\(\,G\,\)を次のように構成しましょう。
\(\,G\,\)の点\(\,\cdots\,\)ある会社の人たち
\(\,G\,\)の辺\(\,\cdots\,\)お互いが知り合いであるとき，かつそのときに限り\(2\)人(点)は辺で結ばれる
このとき\(\,G\,\)の中のある人\(\,v\,\)のランキング\(\,N(v)\,\)が
\(N(v)=\{z_1 \stackrel{v}{\gt} z_2 \stackrel{v}{\gt} \cdots \stackrel{v}{\gt} z_n\}\)となっていたとします。
これは\(\,v\,\)さんの知り合い\(\,z_1,z_2,\ldots,z_n\,\)を，\(\,v\,\)さんの好み順に並べたものと考えることができます。
※実際は，このように考えるためにランキングを定義したという方が正しいです。
ランキング\(N(v)\)とは\(v\)さんの好み順である。
定義・性質
それでは安定マッチングの定義を確認していきましょう。
定義
安定マッチングとは
\(2\)部ランキンググラフ\(G=(X\cup Y, E)\)のマッチング\(M\)で次の条件\(\,(\mathrm{i})\,\)を満たすものである。
条件\(\,(\mathrm{i})\,\)
\(\,M\,\)に属さない\(\,G\,\)の任意の辺\(\,uv\,(u\in X,\,v\in Y)\,\)に対して
\(\,x \stackrel{v}{\gt} u\,\)かつ\(\,xv \in M\,\)となるような\(\,x \in X\,\)が存在する，
もしくは\(\,y \stackrel{u}{\gt} v\,\)かつ\(\,uy \in M\,\)となるような\(\,y\in Y\,\)が存在する。
※\(2\)部グラフ\(G=(X\cup Y, E)\)の表式は\(X,Y\)を部集合，\(E\)を辺集合とする\(2\)部グラフを表すとしています。
例えば下の\(2\)部ランキンググラフではマッチング\(\,M=\{aC,bD,cA\}\,\)が安定マッチングとなっています。
イメージについては次節で確認しましょう。
またゲイル-シャプレイのアルゴリズムで，安定マッチングの存在性が保証されるので，ここで明示しておきます。
安定マッチングは常に存在する。
イメージ
この節では安定マッチングのイメージを確認していきましょう。
マッチングは男女のお見合いとして考えると分かりやすいので，ここでもそうします。
つまり\(2\)部ランキンググラフ\(G=(X\cup Y, E)\)について
\(\,X\,\)の点\(\,\cdots\,\)男性
\(\,Y\,\)の点\(\,\cdots\,\)女性
辺\(\,uv\,\)\(\,\cdots\,\)男性\(u\)と女性\(v\)のお互いが興味がある状態
ランキング\(\,N(v)\,\)\(\,\cdots\,\)\(\,v\,\)さんの好み順
として考えていきます。
この状況において，マッチング\(\,M\,\)はお見合い結果を表します。
例えば，先程赤で示したマッチング\(\,M=\{aC,bD,cA\}\,\)について考えましょう。
これはお見合いの結果，カップル\(\,aC,bD,cA\,\)ができたことを表します。
それでは安定マッチングのイメージはどうなるでしょうか？
安定マッチングの定義の条件\(\,(\mathrm{i})\,\)をこの設定で書き換えると次のようになります。
条件\((\,\mathrm{i}’)\,\)
お互いに興味はあったが，お見合い後付き合わなかったどの男女\(\,uv\,\)についても
女性\(\,v\,\)は，\(\,u\,\)よりも素敵な男性\(\,x\,\)とカップルになっているか
男性は\(\,u\,\)は，\(v\)よりも素敵な女性\(\,y\,\)とカップルになっている。
まあまあ分かり安くなりましたが，この条件が「安定性」を表すことはまだ掴みにくいですね。
そこで条件\(\,(\mathrm{i}’)\,\)を否定して，「不安定な」条件\(\,(\mathrm{ii})\,\)を考えましょう。
条件\(\,(\mathrm{ii})\,\)
お互い興味はあったけれど，お見合い後付き合わなかったある男女\(\,uv\,\)について
女性\(\,v\,\)は，\(\,u\,\)よりも素敵な男性\(\,x\,\)とカップルになっておらず，
さらに男性は\(\,u\,\)は，\(\,v\,\)よりも素敵な女性\(\,y\,\)とカップルになってもない。
条件\(\,(\mathrm{ii})\,\)の男女\(\,uv\,\)について，次の\(3\)通りに分けて考えます。
\([1]\) 男性\(\,u\,\)，女性\(\,v\,\)のどちらにもパートナーができた場合
\([2]\) 男性\(\,u\,\)，女性\(\,v\,\)のどちらかにのみパートナーができた場合
\([3]\) 男性\(\,u\,\)，女性\(\,v\,\)のどちらにもパートナーができなかった場合
数学的に書き換えれば次の場合分けと等価です。
\([1]\) マッチング\(\,M\,\)が\(\,u\,\)を端点とする辺と\(\,y\,\)を端点とする辺を含む場合
\([2]\) マッチング\(M\)が\(\,u\,\)を端点とする辺と\(\,y\,\)を端点とする辺のどちらか一方のみを含む場合
\([3]\) マッチング\(M\)が\(\,u\,\)を端点とする辺と\(\,y\,\)を端点とする辺を含まない場合
この\(3\)つの場合において\(\,(\mathrm{ii})\,\)が「不安定さ」を表すことを確認しましょう。
ここでいう「不安定さ」とは「しばらく時間が経つと，お見合い結果が変わってしまうこと」とします。
\([1]\)の場合
上図のようになっていて，
男女\(\,u,v\,\)が「今のカップル(赤線)より\(\,uv\,\)自身でカップルになる方が魅力的だ」と感じる状況になっています。
そのため時間が経過すると男女\(\,uv\,\)は駆け落ちし，お見合い結果が変わってしまうため不安定です。
\([2]\)の場合
例えば，男性\(\,u\,\)のみにパートナーができた場合は上図のようになっています。
よって\([2]\)の場合も\([1]\)の場合と同様に「駆け落ちする男女\(\,uv\,\)」が存在するため不安定です。
\([3]\)の場合
上図のようになっており，お互いに興味はあったのに，運悪く余ってしまった男女\(\,uv\,\)が存在する状況になっています。
よって時間が経過すると，男女\(\,uv\,\)は独り身でいるくらいなら付き合った方が良いと考え，カップル\(\,uv\,\)が形成されます。
つまりお見合い結果が変化してしまうため，不安定です。
このように条件\(\,(\mathrm{ii})\,\)はお見合い結果の不安定性を表しています。
そのためその否定である安定マッチングの条件\(\,(\mathrm{i})\,\)は安定性と表しているというイメージですね。
安定マッチングの「安定」とはお見合い結果が変わらないことである。
ゲイル-シャプレイのアルゴリズム(Gale-Shapley algorithm)
ここでは，安定マッチングの存在性や絶望の定理の証明に関係するゲイル-シャプレイのアルゴリズムについて解説します。
イメージ
前の時と同様，下のお見合いのイメージで解説します。
\(\,X\,\)の点\(\,\cdots\,\)男性
\(\,Y\,\)の点\(\,\cdots\,\)女性
辺\(\,uv\,\)\(\,\cdots\,\)男性\(u\)と女性\(v\)のお互いが興味がある状態
ランキング\(\,N(v)\,\)\(\,\cdots\,\)\(\,v\,\)さんの好み順
マッチング\(\,M\,\)\(\,\cdots\,\)お見合い結果
このときゲイル-シャプレイのアルゴリズムは次のようになります。
ゲイル-シャプレイのアルゴリズム
\([1]\) 男性たちは，最も魅力的だと思う女性に手紙で告白を行う(好みの女性がいない場合はお見合い会場から退場してもらう)。
\([2]\) 手紙を受けとった女性は，手紙の男性たちの中から，最も魅力的な男性の手紙のみキープし，他の手紙は捨てる。
\([3]\) 手紙を女性にキープされていない男性たちは再び，まだ告白していない女性の中で最も魅力的だと思う女性に手紙で告白を行う(好みの女性がいない場合は退場してもらう)。
\([4]\) 手紙を受け取った女性は，キープした手紙の男性も含めた手紙の男性たちの中から，最も魅力的な男性の手紙のみキープし，他の手紙は捨てる。
\([5]\) 手順\([3],[4]\)を手紙をキープされていない男性が会場からいなくなるまで繰り返す。
\([6]\) 会場に残った手紙持ちの女性とその手紙の男性をカップルにし，お見合いを終了すれば，そのお見合い結果は安定マッチングとなる。
次節ではこのアルゴリズムが本当に安定マッチングを形成するのかの証明を確認しましょう。
証明
ゲイル-シャプレイのアルゴリズムで出力されるマッチング\(M\)が安定となること
つまり\(M\)が下の条件\(\,(\mathrm{i’})\,\)を満たすことを証明していきます。
条件\(\,(\mathrm{i}’)\,\)
お互いに興味はあったが，お見合い後付き合わなかったどの男女\(\,uv\,\)についても
女性\(\,v\,\)は，\(\,u\,\)よりも素敵な男性\(\,x\,\)とカップルになっているか
男性は\(\,u\,\)は，\(v\)よりも素敵な女性\(\,y\,\)とカップルになっている。
お互い興味はあったけれど，お見合い後付き合わなかった男女\(\,uv\,\)について，
その付き合わなかった理由は次の\(2\)通りの場合に分けられます。
\([1]\) 女性\(\,v\,\)が男性\(\,u\,\)の手紙を捨てた。
\([2]\) 男性\(\,u\,\)がそもそも女性\(\,v\,\)に手紙を渡していない。
まず\([1]\)の場合について考えましょう。
このとき手紙を捨てた理由は，手紙を捨てたときに女性\(\,v\,\)は男性\(\,u\,\)よりも魅力的な男性\(\,x’\,\)の手紙を持っていたからです\(\,(u\lt x’)\,\)。
アルゴリズムが経過するごとに，手紙の男性は女性\(\,v\,\)にとって，どんどん魅力的になっていきます(単調増加ということです)。
よってアルゴリズム終了時，女性\(\,v\,\)は手紙の男性\(\,x\,\)とカップルになっていますが，相手の男性\(\,x\,\)は男性\(\,u\,\)よりも魅力的です\(\,(u\lt x’ \leq x)\,\)。
そのため条件\(\,(\mathrm{i’})\,\)は満たされています。
次に\([2]\)の場合について考えましょう。
\([2]\)の場合について，男性\(\,u\,\)が興味を持っていたのにも関わらず，女性\(\,v\,\)に手紙を渡していない理由は
男性\(\,u\,\)にとって女性\(\,v\,\)よりも魅力的な別の女性\(\,y\,\)に手紙をキープされていたからです。
よってアルゴリズム終了時，男性\(\,u\,\)は\(\,v\,\)よりも魅力的な女性\(\,y\,\)とカップルになっています\(\,(v\lt y)\,\)。
故にこの場合も条件\(\,(\mathrm{ii})\,\)は満たされています。
つまり，どの場合も条件\(\,(\mathrm{i’})\,\)が満たされることが分かりました。
したがってゲイル-シャプレイのアルゴリズムによって得られるマッチングは安定マッチングとなります。
まとめ
今回の記事では安定マッチング(stable matching)を解説いたしました。
安定マッチングの基本的事項を押さえることができたでしょうか？
ここで紹介したゲイル-シャプレイのアルゴリズムの出力は安定性だけでなく，さらに男性最良性も持つことが知られています。
このことが絶望の定理の証明に関連することは，こちらで紹介しています。
良ければ読んでいってください。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
参考図書
- \([1]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.274-275.
