はじめに
学校の研究室選びや新入社員の配属、さらには婚活やマッチングアプリに至るまで、「誰と誰を組み合わせるのが一番良いのか」という問題は、私たちの日常や社会のいたるところに存在しています。お互いの希望が食い違って不満が出たり、後から「やっぱりあっちの人が良かった」と関係が破綻してしまったりすることに頭を悩ませた経験はありませんか？
👇 本記事でわかる3つの重要ポイント 👇
- 【テーマ1】誰も「今の相手より別の相手が良い」とお互いに乗り換えない「安定」の仕組み
- 【テーマ2】ノーベル経済学賞にも輝いた「ゲール・シャプレー・アルゴリズム」の具体的なマッチング手順
- 【テーマ3】就職活動、研修医の病院配属、腎臓移植など、身近な社会問題を解決している驚くべき実例
数学や経済学と聞くと少し難しく感じるかもしれませんが、このアルゴリズムの考え方はとてもシンプルで明快です。本記事を読めば、世の中の複雑なマッチングがどのようにして「全員にとって最も平和で不満の少ない形」に導かれているのかがスッキリ分かります。ぜひ最後まで楽しんでご覧ください。
安定結婚問題とは？数学が解き明かした「平和なペアリング」の概念
「安定結婚問題（Stable Marriage Problem）」とは、同数の男女がそれぞれ結婚したい相手を好みの順に順位づけしているとき、どのような組み合わせを作れば最も平和で破綻しないペアリングが完成するかを探る、数学およびゲーム理論の有名なテーマです。この問題は、1962年にアメリカの数学者デイヴィッド・ゲール氏とロイド・シャプレー氏によって発表され、のちに経済学やコンピュータサイエンスの分野に大きな革命をもたらしました。
この理論が目指すのは、単に「みんなが一番好きな人と結ばれること」ではありません。現実問題として、特定の一番人気の人に希望が集中してしまえば、全員の第一希望を叶えることは不可能です。そこで重要になるのが、「安定」というキーワードになります。
「不安定」なペアリングとはどういう状態か？
この理論における「安定」を理解するためには、まず「不安定な状態」をイメージすると非常にわかりやすいです。例えば、男性Aさんと女性Xさん、男性Bさんと女性Yさんがそれぞれペアになったとします。ところが、Aさんは今のパートナーであるXさんよりもYさんのほうが好きで、同時にYさんも今のパートナーであるBさんよりAさんのほうが好きだったとします。
この場合、AさんとYさんはお互いに「今の相手を捨てて、二人で手を組んで駆け落ち（浮気）したほうが幸せになれる」という利害の一致が生まれてしまいます。このように、現在の組み合わせを解消してお互いに乗り換えたいと望むペアが存在する状態を、数学の世界では「不安定（ブロッキングペアが存在する状態）」と呼んでいます。このようなペアが一つでも存在すると、マッチング全体が崩壊に向かってしまいます。
「安定なマッチング」がもたらす全員の納得感
一方、「安定なマッチング」とは、どの男女を取り出してみても「今の相手よりもお互いに惹かれ合っている別の相手」が存在しない状態を指します。たとえ第一希望の相手と結ばれなかったとしても、「自分がもっと良いと思っている相手は、すでに自分よりも好きな人と結ばれている」という状況が全員に対して成立しているため、誰も浮気や乗り換えをすることができません。
つまり、全員にとって100点満点の完璧な相手ではないかもしれませんが、お互いの妥協点の中で「これ以上どう動いても関係を破綻させられない、最も平和で納得感の高い組み合わせ」が導き出されるのです。これが安定結婚問題の基本的な目指すべきゴールになります。
ゲール・シャプレー・アルゴリズム（GS法）の仕組み
では、どのようにしてその「絶対に破綻しない安定なペア」を見つけ出すのでしょうか。その具体的な手順を示したのが「ゲール・シャプレー・アルゴリズム」、通称「受領・保留（Deferred Acceptance）方式」と呼ばれる手順です。この方法は非常にシンプルでありながら、どんな参加者や好みの順位であっても、必ず安定したペアリングを1つ以上導き出せるという素晴らしい特徴を持っています。
具体的なステップ：プロポーズと「キープ」の繰り返し
このアルゴリズムは、ラウンドごとにステップを踏みながら進められます。ここでは分かりやすく、男性側から女性側へアプローチ（プロポーズ）を行う形で解説します。
ステップ1：第一希望への一斉プロポーズ
すべての男性は、自分の好みランキングで1位に設定している女性に対して一斉にプロポーズを行います。
ステップ2：女性側の「キープ」と「お断り」
女性は、自分にプロポーズしてきた男性たちを比較します。もし1人からしかプロポーズされていなければ、その男性を「ひとまずキープ（保留）」します。もし複数の男性から同時にプロポーズされた場合は、その中で自分の好みの順位が最も高い男性1人だけをキープし、それ以外の男性にはハッキリと「お断り」を告げます。なお、誰からもプロポーズされなかった女性はそのまま待機します。
ステップ3：振られた男性による再アタック
女性にお断りされてしまった男性たちは、まだ自分を振っていない相手の中で、次に好みの順位が高い女性（2位の相手）へ向けて一斉に次のプロポーズを行います。すでに誰かをキープしている女性であっても、アプローチを受ける対象になります。
ステップ4：より良い相手への「乗り換え」と再キープ
新しくプロポーズを受けた女性は、新しく来た男性と現在キープしている男性を比較します。もし新しく来た男性のほうが自分の好みの順位が上であれば、あっさりと現在キープしている男性をお断りし、新しい男性をキープし直します。逆に、現在のキープ相手のほうが好きであれば、新しく来た男性をお断りします。
ステップ5：全員のペアが確定するまで継続
お断りされた男性は、さらにリストの下の相手へアタックを続けていきます。このプロセスを繰り返していくと、最終的に誰も断られなくなるタイミング、つまりすべての人が誰か1人とキープし合っている状態が必ず訪れます。その時点で全員の組み合わせを正式決定としてマッチングが終了します。
なぜこの手順で「絶対に破綻しないペア」ができるのか？
このアルゴリズムの秀逸な点は、女性が一度手に入れたキープ相手を「より良い男性が現れた時だけ乗り換える」というルールにあります。女性にとって、マッチングが進むにつれて相手のランクが上がることはあっても、下がることはありません。
男性側から見ても、上から順番にプロポーズして断られているということは、「自分を振った女性たちは全員、自分よりも好きな男性とペアになっている」という状態が保証されます。そのため、後から男性が「あっちの女性のほうが良かったな」と思ったとしても、その女性はすでにその男性よりも大好きな相手と結ばれているため、乗り換えに応じることは絶対にありません。こうして、自然と浮気相手が存在しない「安定」が数学的に必ず完成するのです。
提案する側とされる側で生まれる「立場の違い」と特徴
このアルゴリズムには、もうひとつ非常に興味深い数学的性質が隠されています。それは、「自分からアプローチ（提案）する側」と「待って選ぶ（受領する）側」で、結果の有利さに大きな差が生まれるという点です。
アプローチする側（提案側）にとって「最良」の結果になる
数学的な証明によると、積極的にプロポーズを行う側は、実現可能なあらゆる安定マッチングの組み合わせの中で「自分にとって最も順位の高い相手」と結ばれることが証明されています。これを専門用語で「提案側最良（Proposer-Optimal）」と呼びます。
アプローチする側は、常に自分の好きな順位の高い相手から順番に声をかけていくため、可能な限り上位の相手を確保しやすい構造になっているのです。さらに、提案側には「自分の好みの順位に嘘をつかず、本音で行動することが常に最も得をする」という耐戦略性と呼ばれる性質も備わっています。
待つ側（受領側）にとっては「最悪」の結果になる？
対照的に、相手からの提案を待ってキープと選別を行う側は、安定マッチングの範囲内において「自分にとって最も順位の低い相手」と結ばれてしまうという性質があります。これを「受領側最悪（Receiver-Pessimal）」と呼びます。
待っている側は、自分から能動的に好きな相手を選びに行くことができず、あくまで「自分に声をかけてくれた人たちの中」から選ばざるを得ないため、結果的に好みの順位が低めの相手で妥協せざるを得ない構造になりやすいのです。日常生活における恋愛や人間関係でも「自分から積極的に声をかけたほうが、より理想の相手を掴みやすい」とよく言われますが、これは数学の理論上でも見事に証明されている面白い事実と言えます。
社会の課題を解決したノーベル賞の実績と応用例
「結婚問題」という名称こそついていますが、この理論は単なる恋愛のパズルにとどまりません。現実の社会で発生する「お金を介さずに、双方の希望を考慮して公平に人を割り振らなければならない問題」を解決するための強力な武器として世界中で活用されています。この功績により、提唱者の一人であるロイド・シャプレー氏は2012年にノーベル経済学賞を受賞しました。
アメリカの研修医マッチングシステム（NRMP）の改革
もっとも有名かつ劇的な応用例が、アメリカにおける医学部の卒業生と研修先病院をマッチングするシステム「NRMP」です。1940年代から50年代のアメリカでは、病院側が優秀な研修医を少しでも早く囲い込もうとするあまり、まだ学生の早い段階で強引な内定を出したり、わずか数時間での決断を迫ったりする熾烈な青田買いが横行し、医療界は大混乱に陥っていました。
そこでゲール・シャプレーのアルゴリズムを応用した自動配属システムが導入されたところ、病院側も医学生側も事前の駆け引きをする必要がなくなり、全員が本音の希望リストを提出するだけで、破綻のない最適な配属が一瞬で決まるようになりました。現在では日本をはじめとする世界中の研修医マッチング制度でも同様の考え方が広く導入されています。
学校選択制度（高校や大学の研究室・学科配属）
アメリカのニューヨーク市やボストン市などの公立学校における進学先選択や、大学における希望研究室の配属などにも、このアルゴリズムが導入されています。
従来の先着順や単純な志望動機の選考では、「第一志望に落ちたら、滑り止めの学校もすでに埋まっていて行き場を失う」というリスクを恐れ、生徒が本当に学びたい学校ではなく、受かりそうな安全校を嘘の第一志望として出願する歪みが発生していました。ゲール・シャプレー方式を採用することで、生徒はリスクを恐れずに「行きたい順」にそのまま希望を出すことができるようになり、教育現場の公平性と満足度が劇的に改善されました。
命を救う「腎臓ドナー交換移植」への発展
さらにこの理論は、病気で腎臓移植を必要とする患者さんたちの命を救う仕組みにも発展しました。例えば、「患者AさんとドナーAさん（家族など）」、「患者BさんとドナーBさん」がいたとします。家族間で移植を行いたくても、血液型や抗体の不適合によって移植ができないケースが多々あります。
しかし、ドナーAさんの腎臓が患者Bさんに適合し、ドナーBさんの腎臓が患者Aさんに適合する場合、お互いのペアでドナーを交換し合えば、2人とも移植を受けて命を救うことができます。シャプレー氏とともにノーベル賞を受賞したアルヴィン・ロス氏は、このアルゴリズムを応用して複数のペアを複雑に繋ぎ合わせる「腎臓交換プログラム」を構築し、これまで諦めざるを得なかった何千人もの命を救う仕組みを確立しました。
私たちが日常の意思決定に活かせるヒント
この高度なアルゴリズムの考え方は、私たちの身近な生活や仕事、人生の選択においても、とても有益なヒントを与えてくれます。
本音の希望リスト（優先順位）を明確にする重要性
アルゴリズムが正しく機能するための大前提は、「自分にとって何が一番大切で、何が二番目なのか」という優先順位がハッキリしていることです。就職先を選ぶときも、住む家を探すときも、パートナーを探すときも、自分の中の順位づけが曖昧なままだと、どんな結果が出ても「本当にこれで良かったのだろうか」と後悔が生まれてしまいます。まずは自分自身の価値観を整理することが、安定した選択への第一歩になります。
「自分からアクションを起こす側」に回るメリット
提案側が最も良い結果を得られるという数学の法則は、私たちの実生活にもそのまま当てはまります。仕事のチャンスでも、憧れのプロジェクトでも、あるいは人間関係でも、相手からの誘いを待つ受け身の姿勢でいると、「自分に声をかけてくれた限られた選択肢」の中からしか選ぶことができません。失敗や断られることを恐れずに、自分から上位の希望に向かって積極的に手を挙げプロポーズしていく姿勢こそが、結果として最も満足のいく現実を引き寄せる近道になります。
まとめ
安定結婚問題（ゲール・シャプレー・アルゴリズム）は、「全員が一番好きな相手と結ばれる」という非現実的な夢を追うのではなく、「誰もが今の相手を捨てて別の誰かと結託することができない、最も破綻しにくい平和な最適解」を見つけ出す素晴らしい知恵です。
一見すると難しそうに見える数学や経済学の理論ですが、その本質は「人と人の希望の食い違いをどう調整し、社会全体の不満を最小限に抑えるか」という、極めて人間味あふれる温かいテーマに向けられています。学校の配属や研修医制度、さらには医療の現場に至るまで、このアルゴリズムは今も世界中で無用な争いや後悔を減らし、人々をより良い未来へと導いています。
もし皆さんが人生の選択や人間関係のマッチングで迷ったときは、ぜひこの理論を思い出してみてください。自分の優先順位をしっかりと見極め、恐れずに自分から希望に向かって行動を起こすことの大切さを、このノーベル賞の理論がそっと背中を押して教えてくれています。
参考リスト
- The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012 – NobelPrize.org
- The Gale-Shapley Algorithm and Market Design (National Bureau of Economic Research)
- How the Matching Algorithm Works – National Resident Matching Program (NRMP)
- Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. The American Mathematical Monthly.
