#64「Gale–Shapleyアルゴリズム（安定マッチング」問題を解く手法）について（ゲーム理論#7）」
Gale–Shapleyアルゴリズム（いわゆる「安定マッチング」問題を解く手法）は、一見すると数学パズルや理論的なお話に見えるかもしれない。しかし、このアルゴリズムは現実社会で非常に大きな役割を果たしている。
たとえば、大学入試や病院研修医の配属、さらには公立学校の入学割り当てなどにも応用され、制度設計を大きく変えてきた。その背後には「安定性」という独特の概念が横たわっている。安定マッチングが実現されると、「当事者同士がマッチング結果に対して文句のつけようがない」という状態になるわけだ。
ここでは、Gale–Shapleyアルゴリズムの基礎から応用事例、そこから生まれる制度設計の変化まで、具体例を交えながら紹介してみる。
1. Gale–Shapleyアルゴリズムとは何か
Gale–Shapleyアルゴリズムは、いわゆる「安定結婚問題」から生まれたアルゴリズムである。安定結婚問題とは、男女が同数いて、それぞれが相手に対して順位づけ（選好リスト）を持っている場合に、「誰もがより好ましいパートナーと駆け落ち（マッチングの変更）したいと思わないようなペアの組み合わせを求める」という問題だ。
ここで「駆け落ち」が起きる可能性があるとはどういうことか。たとえば、男性Aと女性Xがそれぞれ別の相手とペアになっているが、AにとってはXのほうが今のパートナーより好ましく、XにとってもAのほうが好ましい、というケースがあったらどうだろう。AとXは内緒で別のマッチングを結んだほうが互いに得になる。こうした状況を「不安定」と呼ぶ。
Gale–Shapleyアルゴリズムは、提案側（男性側か女性側かにより変化する）の一方が順に相手にアプローチしていき、拒否や暫定受け入れを繰り返しながら、最終的に安定した組み合わせを見つけるというシンプルなプロセスである。
具体的には男性主導（男性が提案役）のアルゴリズムを例にすると、男性たちは第一志望の女性に一斉に「付き合ってください」と提案する。女性たちは複数から提案があれば、一番好ましい男性を暫定的にキープし、それ以外を断る。男性は断られた場合、リストの中で次に好ましい女性へ提案し、女性側は常に暫定キープを見直していく。これを繰り返していくと、最終的にはすべての男性が受け入れ先を見つけ、女性側も余剰の提案を断り、ペアができあがる。しかも完成したペアは安定性を持つ。
ここで重要なのは、「男性側が提案役」の場合に得られる解は「男性最優」であり、逆に「女性側が提案役」の場合は「女性最優」となるということだ。（あくまで解説ということを補足する）
男性主導でアルゴリズムを走らせると、男性にとっては可能な安定解の中で一番好ましいマッチングを得られるが、女性にとっては可能な安定解の中では最悪という性質がある。
2. 「安定性」へのこだわりが生む実社会でのメリット
なぜ「安定性」が大事なのか。単に利害調整をするだけであれば、「どちらかが多少泣きを見ても一番効率の良いマッチングを選べばいいではないか」と考えるかもしれない。だが、相手がいるマッチングでは、人間関係が絡んでくる。とくに結婚問題はもちろん、大学・病院配属のように長期的な関係が続く場合、あとから「私のほうがあのプログラム（あるいはあの大学、あの病院）と組みたい」とか「あちらのほうが私を必要としてくれていた」などといった不平不満が湧くと、制度そのものの信頼が損なわれる。
不満が大きくなると、事後的な駆け落ち的な動きが出てくる可能性がある。そうなると、せっかく制度で決まったはずのマッチングが崩れてしまう。安定マッチングを求めるというのは、参加者が文句を言えない仕組みを確立し、結果を受け入れやすくするためでもある。これは社会的コストを下げるメリットを生む。人々が安心して「この制度で決まったなら仕方ない」と納得できるのは、とても大きい。
3. 大学入試や病院研修医マッチングでの応用
Gale–Shapleyアルゴリズムは「安定結婚問題」の解法として生まれたが、実際に名声を高めたのは、大学入試や病院研修医のマッチングへの応用だろう。米国では、医学生が卒業後に研修先となる病院プログラムをどこにするかというマッチングを「National Resident Matching Program（NRMP）」で行う。これは、医学生と病院の両方がそれぞれ志望順位を提示し、Gale–Shapleyアルゴリズムを改良した仕組みで組み合わせを決めている。
病院研修医マッチングの例で考えてみよう。医学生側の希望としては「できるだけ有名な病院で、しかも自分の専門分野が強いプログラム」が魅力的なはずだ。一方、病院としては「優秀な学生を確保したい」「専門領域を伸ばせる人材がほしい」などの条件がある。両者の希望が食い違うと、それぞれ次善策を探すことになるが、Gale–Shapleyアルゴリズムにより、誰も「もっとマシな相手と互いに合意できるんじゃないか」と不満を抱かないマッチングを実現できるわけだ。
大学入試でも同様に、志願者のリストと大学側の志望者リスト（あるいは成績順評価など）をもとに、安定した合否の割り当てを行うことが可能である。実際、日本の一部私立学校や海外の公立学校入学システムでは、Gale–Shapleyアルゴリズムにインスパイアされた仕組みが使われていることもある。
4. 提案側の「有利不利」問題
Gale–Shapleyアルゴリズムでは、提案役になる側（男性か女性か）によって結果が変わることはすでに触れた。実際の制度設計では、「だれを提案役とするのか」が争点になることもある。男性に有利になるなら、逆に女性視点では不利なわけだから、結婚相談所のようなサービスで安定マッチング手法を採用する場合、「どちらの性別に合わせるのか」など微妙な配慮が必要だろう。
大学や病院マッチングに置き換えると、「志願者が提案役」なのか「学校や病院が提案役」なのかで結果が微妙に変わる。志願者を提案役にすれば、志願者にとってはより良いマッチングが得られる傾向がある。逆に大学や病院を提案役にすると、そちらに有利な組み合わせになる。例えばNRMPでは、かつては病院側を提案役としていた時代もあったが、その後は医学生が提案役になるようアルゴリズムが改良され、医学生に有利な形にシステムが動いている。制度設計者は常に参加者の利害を見ながら、どちら側を提案役に設定するかを検討するわけだ。
5. 戦略的操作は可能か
安定マッチングとはいえ、実際には「希望リストを偽装すれば得をするのではないか」という疑念もつきまとう。Gale–Shapleyアルゴリズムでは、提案を受ける側（男性主導なら女性側）は戦略操作しても必ず得をするとは限らない、という理論的な性質がある。簡単にいうと「好きな順番を偽っても、それで良い結果が得られない」ことが証明されている。
ただし、提案を行う側は、戦略的に動けばより好ましい結果を引き出せる可能性が皆無ではないともされる。しかし、実際にそれを上手にコントロールするのは難しい場合が多い。自分だけでなく、他の提案者の動きも絡んでくるからだ。もし狙った相手に偽リストで提案しても、そこは既に別の人物を暫定的にキープしているかもしれないし、複雑な駆け引きが発生する。一つ確実に言えるのは、「素直に自分の選好通りのリストを出すのが一番楽だし、ハズレが少ない」ことである。実際、現行の大規模マッチング制度（大学入試や病院マッチング）では、「参加者が自分の本当の希望を正直に表明するのがベスト」という方針を前面に打ち出すことが多い。
6. 複数の安定マッチングと唯一性の問題
安定マッチングは必ず一意に決まるわけではない。理論上は、安定性を満たす組み合わせが複数存在し得る。男性最優安定マッチングや女性最優安定マッチングなど、同じ人数・同じ選好リストでも違う結果が出るのだ。
この点は大学や病院配属においても同様で、「どちらにとって有利な解をとるか」を決める要素が含まれる。たとえば、ある医学生にとっては第一志望のプログラムAと第二志望のプログラムBのどちらでも安定性を満たす可能性がある。しかし実際に制度を運用する際には、アルゴリズムを一つ定めているため結果は一通りに決まる。
なぜ複数の安定解があるのに、一つだけに限定するのか。理由はシンプルで、「現実には一つのペアリングしか実装できない」からだ。そこで制度設計上、「このアルゴリズムで実行します」という方法を公表し、それに基づいて唯一の答えを確定させるのが一般的だ。そのプロセスが参加者に周知され、一定の公平感が保たれれば、多くの人が納得しやすくなる。
7. 制度設計への影響：公立学校入学振り分けの例
米国ボストンでは、公立学校入学振り分けの改革にGale–Shapleyアルゴリズムが導入されたことで知られている。それまでの入学制度では、保護者側が作戦を立て、第一志望をあえて変えるなどの戦略的な出願を強いられるケースがあった。たとえば倍率が高い学校を第一志望に書くと落ちたときに次善校もままならない、という状況があったのだ。
制度改革で安定マッチングの考え方を取り入れると、「正直に第一志望を書くほうが得をする」となるため、保護者にとっても公平感が高まる。もちろん全員が第一志望に入れるわけではないのだが、「戦略操作をしなくても自分の希望がきちんと考慮される」という点が参加者に安心感を与える。結果的に制度運営者としても不満を抑えられ、入学手続きの混乱を減らせるメリットがある。
8. 拡張されたマッチング問題：カップル問題や不完全リスト
現実のマッチングには、往々にして「カップルで一緒にマッチしたい」といった制約や、誰とでもマッチングしていいわけではないような不完全リストが存在する。たとえば、医学生の夫婦が同じ地域の病院に配属されたいと望むケースだ。もし別々の州に飛ばされてしまったら、生活が成り立たないかもしれない。
こうした問題は、Gale–Shapleyアルゴリズムそのままでは解けない。2人1組が同時に移動するような拡張ルールを組み込む必要があり、そのためにアルゴリズムやマッチングの安定性の概念を拡張することになる。カップル制約が入ると、安定マッチングが存在しないケースが生まれる可能性もあるし、NP困難な問題として扱われることもある。
大学入試でも、自分の専門分野を重点的に考えて希望リストを大幅に削る受験生がいたり、定員を超える志願者が押し寄せる人気校があったりと、実務上はさまざまな制約がある。そのたびにアルゴリズム設計をカスタマイズし、なるべく安定性や公平性を損なわないように制度を組み立てるのが実務家の腕の見せどころである。
9. 市場デザインへの波及：臓器移植やシェアリングエコノミー
Gale–Shapleyアルゴリズムを含む「安定マッチング理論」は、より広い「市場デザイン（Market Design）」の文脈でも重要な位置づけを占める。市場デザインとは、「需要と供給がある場面で、どのようなルールを設計すると望ましい取引が成立するか」を研究する学問である。
たとえば、臓器移植のドナーとレシピエントをマッチングするケースを想像してみる。医療現場では臓器の適合度や移植の緊急性など、複数の基準が絡む。そこに患者側の選好をどう組み込むかは単純ではないが、「お互いが納得するかどうか」をキーにすると、安定性に近い観点からルール設計するアイデアも生まれる。
さらに、カーシェアやルームシェアなどのシェアリングエコノミーでも、利用者と提供者のマッチング問題をどのように最適化するかが課題になっている。Gale–Shapleyの発想は、単なる「結婚」や「入試」の世界を超え、「人」と「物」が納得感ある形で結びつく枠組みのヒントを与えている。
10. ノーベル経済学賞と今後の展望
Gale–Shapleyアルゴリズムを理論的に打ち立てたロイド・シャープレーは、ゲーム理論の大家だった。彼はアルヴィン・ロスとともに2012年にノーベル経済学賞を受賞している。ロスは安定マッチング理論を実際の病院マッチング制度などに応用し、社会に大きなインパクトを与えた立役者だ。
もともと数学やゲーム理論の世界にあったアイデアが、大学入試・病院配属・公立学校入学などの実社会で実装され、さらにシェアリングエコノミーや臓器移植など多岐にわたる分野にも波及している点は興味深い。純粋な研究が社会の問題解決に寄与し、それを経済学の視点から評価するという流れがある。マッチングの世界はこれからも複雑化が進むだろう。AI技術の発達に伴い、より大規模かつ柔軟なマッチングが可能になる一方、人々の選好や制約はさらに多様化し、制度設計には難しさが増していく。
今後は、カップル制約やチーム制約、多様性確保の要件など、理想とするマッチングをどこまで社会が求めるのかをめぐって議論が活発化するはずだ。たとえば、「女性枠を何割確保するか」「特定の専門領域を持つ学生を優先的に配置するか」といった社会的要請が入ると、それまでの純粋な「安定性」だけでは決められなくなってくる。
しかし、そのなかでも安定マッチングの概念が役立つ場面は多い。たとえ追加の制約が増えようとも、「当事者同士がマッチング結果を壊したいとは思わない状態をどう実現するか」という問いは普遍的だからだ。制度が人々から信頼され、その上で合意を得るためには、一定の「安定性」は欠かせない。
まとめ
Gale–Shapleyアルゴリズムは、一見すると単純な手続きでペアを組むだけのように見えるかもしれない。だが、その背後にある「安定性」の概念は、実は人間関係や組織運営、さらには社会の合意形成にまで深くかかわっている。現実には大学入試や病院研修医マッチングだけでなく、学校選択制度、就活マッチング、ルームシェアの仲介など、さまざまな領域で引用される考え方だ。
考えてみると、自分自身がどこかの組織やコミュニティに所属するときも、「妥協はしているが、最低限これなら納得できる」「仕方ないが、ここがベターだ」という感覚を持つことがあるだろう。それが社会全体のスケールで起きているのがマッチング問題だ。誰もが本音を出しやすくし、かつ結果について「仕方ない」と思える仕組みを作ること。ここにGale–Shapleyアルゴリズムの存在意義がある。
もし今後、就活のマッチングプロセスに本格的に取り入れられたらどうだろう。学生側は「第一志望」とか「第二志望」といったリストを正直に企業側へ伝え、企業側も「優秀度」「組織カルチャーとの相性」などを踏まえた優先順位を表明する。従来のように内定をあちこちでキープして最後に一つだけ選ぶという混乱が減り、「いつまでに返事をしないと取り消される」といった駆け引きも多少は緩和されるかもしれない。もちろん、実際にはさまざまな条件が絡むので簡単ではないが、将来的にはマッチング制度の形は大きく変わる可能性があるだろう。
Gale–Shapleyアルゴリズムは、その理論的背景の美しさだけでなく、参加者が「正直に行動しても損をしない」という仕組みづくりの土台を提供している。そして社会制度が複雑になるほど、この「安定性」と「戦略耐性」の両方をクリアする設計はさらに注目を浴びるはずだ。マッチングを単なる効率化の話ではなく、「人と人がどのようにしてお互いを必要としているか、あるいは避けているか」を映し出す社会的鏡として捉えることもできる。
以上、Gale–Shapleyアルゴリズムをめぐる基礎的な話から実社会への応用、そして将来の展望を概観した。大学入試、病院マッチング、公立学校入学から市場デザイン・臓器移植まで、マッチングが必要となる世界は広い。そしてマッチングをめぐる制度をどうデザインするかは、今後も極めて重要なテーマであり続けるだろう。自分の身の回りにも、「もし安定マッチングの考え方を使ったら、もっと円滑に物事が進むのではないか」と思える場面があるかもしれない。たとえば就職活動、引っ越し先の検索や部屋探し、あるいは保育園の入園枠争いなど。
そうしたときに、「安定マッチング」は何をもたらしてくれるのか。本当にそれはベストなのか。別のやり方はないのか。自分が提案側になるなら、どんな戦略をとるだろうか。ぜひ身近な問題に置き換えて考えてみると、安定マッチングの奥深さを体感できるはずだ。
主なトピックのまとめ
Gale–Shapleyアルゴリズムの概要
「安定結婚問題」を解くために開発されたアルゴリズム。
一方（提案側）がリスト順に相手へ求婚（提案）し、受け手は暫定的にキープしつつより好ましい提案があれば切り替える。
最終的には「安定マッチング」が得られる。
安定性の重要性
当事者同士が「駆け落ち（マッチングの変更）」したいと思わない状態を指す。
制度運営の安定や不満の最小化に寄与する。
男性最優／女性最優安定マッチング
アルゴリズム上、提案側に有利な安定解になる。
制度設計では「提案側をどちらにするか」が参加者の満足度に影響する。
大学入試・病院研修医マッチング（NRMP）への応用
研修先配属や入学割り当てなど、実社会で大規模に運用。
大学・病院と志望者の両方が納得感を得やすい。
戦略的操作の可否
受け手（非提案側）は選好リストを偽っても得をしづらい。
提案側に戦略的余地がある可能性はあるが、複雑で実行ハードルが高い。
唯一性と複数の安定マッチング
安定なマッチング解は一意とは限らない。
運用上はアルゴリズムを一つに定めて唯一の答えを出すのが一般的。
公立学校入学振り分け・ボストンの例
「第一志望を変えずに正直に書くほうが有利」という方針が保護者に好評。
戦略操作の必要性を減らして不満や混乱を抑える。
拡張問題：カップル制約や不完全リスト
夫婦やチームで同じ地域に配属されたい、などの制約で複雑化。
NP困難になるケースもあり、安定解が存在しない可能性も。
市場デザイン（Market Design）への影響
シェアリングエコノミーや臓器移植、オークション設計など多方面で応用。
「安定性」と「戦略耐性」の考え方は市場デザインの基礎の一つ。
歴史的背景とノーベル賞
ロイド・シャープレーとアルヴィン・ロスが2012年にノーベル経済学賞を受賞。
数学的アイデアが制度設計に影響し、社会にインパクトを与えた好例。
専門用語解説
安定結婚問題（Stable Marriage Problem）
男女が同数おり、それぞれが異性に対して選好リスト（好みの順序）を持つとき、「誰もがマッチング結果に納得する」ペアの組み合わせを探す問題。安定マッチング（Stable Matching）
あるペア（男女、医学生と病院など）がマッチング外で「互いに今の相手よりもお互い同士を好む」という状況が生じない組み合わせ。誰もが「駆け落ち」を望まない状態。Gale–Shapleyアルゴリズム
「安定結婚問題」を解くために提案されたアルゴリズム。提案側が希望順にアプローチし、受け手は常に最良の提案を暫定保持。最終的に安定マッチングに収束する。男性最優安定マッチング（Male-Optimal）
男性が提案側になったときに得られる安定解。男性にとっては最も好ましい安定マッチングだが、女性にとっては最悪の安定マッチングにもなる。女性最優安定マッチング（Female-Optimal）
女性が提案側になったときに得られる安定解。女性にとっては最も好ましく、男性にとっては最悪となる。戦略耐性（Strategy-Proofness）
あるメカニズム（アルゴリズム）において、参加者が自分の本当の選好を偽らずに表明することが最善になる性質。Gale–Shapleyアルゴリズムは非提案側に対して部分的な戦略耐性を示す。カップル制約（Couple Constraint）
病院研修医マッチングや大学入試などで、夫婦やチームが同じ地域または同じプログラムに行きたいという制約。複雑さが増し、必ずしも安定解が存在しない場合がある。大学入試・病院マッチング
大学や病院（受け手）と、受験生や研修医（提案側）との間で互いの希望順位に基づき割り当てを決める制度。米国ではNRMP (National Resident Matching Program) が代表例。NP困難（NP-hard）
計算量理論で、一般に高速（多項式時間）で最適解を見つけるのが非常に困難と考えられている問題のクラスを指す用語。制約が複雑化したマッチングはNP困難化するケースがある。市場デザイン（Market Design）
需要と供給を繋げるためのルール設計を学問的に研究する分野。安定マッチング理論を含むゲーム理論、オークション理論などの知見を活用して最適な制度を構築する。ロイド・シャープレー（Lloyd Shapley）
数学者・経済学者。ゲーム理論やマッチング理論に大きく貢献し、Gale–Shapleyアルゴリズムを共同提案。2012年にアルヴィン・ロスとノーベル経済学賞を受賞した。アルヴィン・ロス（Alvin E. Roth）
米国の経済学者。マッチング理論の実社会への応用（NRMPなど）を主導し、ロイド・シャープレーとともにノーベル経済学賞を受賞した。
文献・情報源
D. Gale, L. S. Shapley (1962), "College Admissions and the Stability of Marriage," The American Mathematical Monthly.
Gale–Shapleyアルゴリズムの元論文。
Alvin E. Roth (1984), "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy.
医学生と研修病院のマッチング事例を解説。
Alvin E. Roth (2015), "Who Gets What ― and Why: The New Economics of Matchmaking and Market Design," Eamon Dolan/Houghton Mifflin Harcourt.
一般読者向けに市場デザインやマッチングの考え方を解説。
日本語の入門書
小島武仁著『マッチングと市場のデザイン ― ビジネスや社会での大規模マッチングを考える』（岩波新書）など。