安定結婚問題「絶望の定理」の紹介

はじめに

この記事では巷で絶望の定理¹と呼ばれている定理の紹介を行っていきます。
絶望の定理は安定結婚問題というグラフ理論の問題における定理です。"絶望"という名前のインパクトでときどき話題になっているよう。
→ 「数学の定理No.1決定戦」高校数学の美しい物語

定理の名前だけが独り歩きして日本語での解説があまりないように思ったので、研究していた頃の記憶をたどりながらご紹介しようと思います。

2020/3/15 追記：
絶望の定理の証明をこちらの記事にまとめました！
安定結婚問題「絶望の定理」の証明

絶望の定理とは？

安定マッチングと駆け落ちペア

絶望の定理とは、ある安定マッチングに入れなかった人間は、すべての安定マッチングに入ることができないという定理です。
安定マッチングとは駆け落ちするペアが存在しないマッチングのことです。

男女3対3の合コンを例にとって説明します。下の図を見てください。

こちらの図は合コンが終わった後の、各人の異性への評価を表しています。雲マークはデートしたい相手の希望リストです。希望リストの左側にある異性ほど評価が高いことを表しています。
例えばAliceが最もデートに行きたいと思っているのはAlexで、AlexがだめならBobと行きたいと思っています。Aliceの希望リストにはCarlが記載されていないので、Carlとデートするくらいならデートしないほうがマシだとも思っています。

合コン終了後にくじ引きを行い、最終的に次のような組合せでデートを行うことになりました。

AliceとAlex, BeckyとCarl, CandyとBobがそれぞれペアになっています。こうした、2つの集合（この場合は男性集合、女性集合）の要素同士の対応付けをマッチングと呼びます。

マッチングは実生活の様々なところに現れます。合コンは男性-女性のマッチングですが、例えば就職活動は応募者-企業のマッチングです。研究室配属は学生-研究室のマッチングです。
マッチングにおいて、誰と誰がペアになるのかはとても重要なことです。マッチングのシステムに参加する誰もが、少しでも自分の希望リストの上位の相手とマッチしたいと考えているからです。もしミスマッチがあれば、参加者はマッチングのシステムを裏切って勝手に別の参加者とペアを組んでしまうかもしれません。

上の合コンのマッチングにおいて、BeckyとBobの希望リストに注目してみます。

Beckyは現在マッチしている相手（Carl）よりもBobとデートに行きたいと思っており、Bobも現在マッチしている相手（Candy）よりもBeckyとデートに行きたいと思っています。このように、互いに現在マッチしている相手よりも互いを好むような男女ペアを駆け落ちペアと呼びます。BeckyとBobはこのマッチングに対する駆け落ちペアです。BeckyとBobは今回のマッチングに不満を持っており、それぞれCarlとCandyとのデートをすっぽかして勝手にデートしてしまうかもしれないからです。

駆け落ちペアの存在するマッチングを不安定マッチングと呼び、駆け落ちペアの存在しないマッチングを安定マッチングと呼びます。例えば下のマッチングは安定マッチングです。つまり、下のマッチング中のどの男女ペアもマッチングを破って駆け落ちするインセンティブを持ちません。

例えばBeckyとAlexについて考えてみると、Alexは現在マッチしている相手（Alice）よりもBeckyを好みますが、BeckyはAlexよりも現在マッチしている相手（Bob）を好むため駆け落ちすることはありません。このように、男女のどちらかだけが現在マッチしている相手を裏切りたくても駆け落ちペアにはなりません。CandyとCarlはデートする相手がいませんが、お互いに「お前とデートするくらいならデートしないほうがマシ！」と思っているため、不満は発生しません。

安定マッチングは1つだけではなく複数存在する可能性があります。例えば次のマッチングは同様に安定マッチングです。

絶望の定理

上でも書いたように、絶望の定理より、CandyとCarlはいかなる安定マッチング中でもデートする相手がいないことがわかります。逆に言えばCandyやCarlとマッチした相手は必ずCandyやCarlのデートをすっぽかしてしまいます。なかなか悲惨です。²

今回の例では、CandyやCarlは人気がないのに選り好みをしているので、マッチできなくても仕方ないような気がします。
絶望の定理は、今回だけでなく任意のケースにおいて、ある安定マッチングに入れなかった人間はすべての安定マッチングに入ることができないということを主張しているのです。

安定結婚問題

与えられた男女の集合と各人の希望リストから、安定マッチングを計算する問題を安定結婚問題(Stable Marriage Problem)と言います³。絶望の定理は、安定結婚問題をめぐる定理のひとつだと言うことができます。

男女のマッチングを研究して何になるのだろう？ と思う方もいると思いますが、安定結婚問題は制度設計（メカニズムデザイン）という研究領域の先駆けとして非常に評価されている問題です。2012年には安定結婚問題の提唱者の一人であるL. S. Shapley教授にノーベル経済学賞が授与されています。
ざっくり言うと、それまでの経済学が「既に存在する市場」を解析して理論を打ち立てていたのに対し、制度設計では経済学などで得られた理論や知見をもとに市場をどう設計するかが研究されています。

安定結婚問題の現実への応用例としては、例えば次のようなものがあります。

• 医師臨床研修マッチング（医師臨床研修マッチング協議会）
• 公立学校選択制(The Stable Marriage Problem and School Choice)
• 研究室配属（お茶の水女子大学 ）

おわりに

「絶望の定理」について紹介しました。
安定結婚問題にはほかにも面白い定理や不思議な定理がいろいろあるので、今後も紹介していこうと思います。
最後まで読んでいただき、ありがとうございました。

1. この定理の正式な名前は Rural Hospital Theorem (田舎の病院定理)と言います。2部グラフを男性-女性のマッチングではなく、研修医-病院の配属マッチングでモデル化しており、人気のない病院にはまったく研修医が集まってこないという意味の定理になっています。 ↩

2. とはいえ、CandyやCarlは「この人とデートするくらいならデートしないほうがマシ」という相手とのデートを回避しているわけで、そこまで悲惨でもないのかもしれません。
   ためしに以下のマッチングのように、CandyとCarlをむりやりマッチングに入れてみます。すると、Candy, CarlとマッチしているAlex, Beckyが駆け落ちペアになってしまいます。
   ↩

3. 今回紹介したのはGaleとShapleyのオリジナルの安定結婚問題ではなく、安定結婚問題から派生した問題の一種(Stable Marriage with Incomplete Lists, SMI)です。オリジナルの問題はそもそも全員がマッチするので、絶望の定理は成り立ちません。オリジナルの安定結婚問題については以下の文献を参照ください：Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. ↩