安定結婚問題とゲール＝シャプレー法

Q: 安定結婚問題とゲール＝シャプレー法とは何ですか？

**安定マッチング（Stable Matching）**とは、2つの集合（例: 男性 M と女性 W）の全単射において、以下の条件を満たすペア (m, w) および (m', w') に対し、 「m が現在の相手 w より w' を好み、かつ w' も現在の相手 m' より m を好む」 ようなペア (m, w')（**ブロッキングペア / 駆け落ちペア**）が1組も存在しない状態を指す。

Q: 安定結婚問題とゲール＝シャプレー法は社会やプログラミングでどのように使われていますか？

PythonによるGale-Shapley安定マッチングアルゴリズムの実装: 医師臨床研修マッチングなどで実際に用いられているDAアルゴリズムの完全なコードです。

ノーベル経済学賞理論 — 研修医マッチングから大学入試まで、誰も浮気しない安定ペアリング

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 男性グループと女性グループ（または研修医と病院）が互いに好みの順位表を持っているとき、誰も不満を持たない『安定マッチング』が必ず存在する
2: Gale-Shapleyの受入保留アルゴリズム（Deferred Acceptance: DAアルゴリズム）は多項式時間で必ず安定解を導出する
3: 告白する側（プロポーズ側）に圧倒的に有利な安定解（提案者最適性）になるという非対称な数学的性質を持つ

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

2012年ノーベル経済学賞（ロイド・シャプレーとアルヴィン・ロス）を受賞した世紀のアルゴリズム。利害が衝突する人々をいかに公平・安定に引き合わせるかというメカニズムデザイン（市場設計）の至宝。

身につく武器・思考力

戦略的インセンティブとアルゴリズム設計の理解、駆け引きや不満を最小化する数理的思考力

実社会・ITでの活躍現場

•日本の医師臨床研修マッチング制度（JRMP）の公式割り当てアルゴリズム
•ニューヨークやボストンの公立高校・中学校の進学希望校マッチング
•腎臓移植ドナーと患者の全国交換ネットワーク（Kidney Exchange）
•マッチングアプリや就活サイトの配属・スカウト最適化

Layer 1 — 直感・シミュレーター

男女それぞれ4人の好みリストを設定し、「ステップ実行」ボタンを押してプロポーズと仮キープ（保留）が繰り返される様子を観察しましょう。誰も「あっちの人と結ばれた方がお互いハッピーなのに…」という駆け落ちペア（ブロッキングペア）が存在しない状態に必ず収束します。

ノーベル経済学賞の数理モデル

ゲール＝シャプレー法（受入保留DAアルゴリズム）のインタラクティブ・デモ

互いに好みの順位がバラバラな3組の男女。駆け引きや妥協を排除し、「プロポーズと仮キープ（保留）」のルールに従うだけで、全員が絶対に浮気しない安定状態へと収束します。

👨 男性側の希望順位（第1 ➔ 第2 ➔ 第3）

M1W1 ➔ W2 ➔ W3

M2W2 ➔ W1 ➔ W3

M3W1 ➔ W3 ➔ W2

👩 女性側の希望順位（第1 ➔ 第2 ➔ 第3）

W1M2 ➔ M1 ➔ M3

W2M1 ➔ M2 ➔ M3

W3M1 ➔ M2 ➔ M3

女性側の仮キープ（受入保留）状況ステップ: 0

空き（募集中）

アルゴリズム実行ログ

アルゴリズム開始前：全員が独身です。「次へ」を押してプロポーズを進めてください。

直感チェック！ミニクイズ

Gale-Shapleyアルゴリズムにおいて、提案する側（プロポーズ側）と受ける側（保留する側）の結果について正しい記述はどれ？

Layer 2 — 定義・受験・証明

定義

**安定マッチング（Stable Matching）**とは、2つの集合（例: 男性 $M$ と女性 $W$ ）の全単射において、以下の条件を満たすペア $(m, w)$ および $(m', w')$ に対し、「 $m$ が現在の相手 $w$ より $w'$ を好み、かつ $w'$ も現在の相手 $m'$ より $m$ を好む」ようなペア $(m, w')$ （**ブロッキングペア / 駆け落ちペア**）が1組も存在しない状態を指す。

公式・数理モデル

\text{ブロッキングペアの非存在条件:} \neg \exists (m, w') \in M \times W \quad \text{s.t.} \quad w' \succ_m \mu(m) \ \land \ m \succ_{w'} \mu(w') \text{（} \mu \text{ はマッチング写像、} \succ \text{ は選好順序）}

証明・導出

**ゲール＝シャプレーの定理（1962年）** 任意の人数・任意の選好リストに対して、安定マッチングは常に少なくとも1つ存在し、DAアルゴリズムによって高々 $n^2 - 2n + 2$ 回のステップで停止する。

**アルゴリズムの手順（男性提案型）:** 1. 各男性は、まだ自分を振っていない女性の中で最も好きな女性にプロポーズする。 2. 各女性は、プロポーズしてきた男性たち（および現在キープしている男性）の中で、最も好みの男性を1人だけ『仮キープ（保留）』し、それ以外の男性を断る。 3. 断られた男性が残っている限り、1〜2を繰り返す。 4. 全員が仮キープされた時点でマッチング成立。

**安定性の証明（背理法）:** もし成立したマッチングにブロッキングペア $(m, w')$ が存在したと仮定する。 $m$ は現在の妻よりも $w'$ が好きなので、アルゴリズムの過程で現在の妻にプロポーズする前に必ず $w'$ にプロポーズしているはずである。そのとき $w'$ が $m$ を断った理由は、その時点で $m$ より好きな男性をキープしたからである。女性はステップが進むにつれてより好みの男性に乗り換えていくため、最終的な $w'$ の夫は $m$ よりも好みの男性であるはずである。これは「 $w'$ が現在の夫より $m$ を好む」というブロッキングペアの仮定に矛盾する。したがってブロッキングペアは存在し得ない（Q.E.D.）。

押さえておきたいポイント

提案する側（プロポーズ側）にとって、すべての安定マッチングの中で『最良』の結果になる（提案者最適性）
提案を受ける側（女性側）にとっては、すべての安定マッチングの中で『最悪』の結果になる（受取人最悪性）
研修医マッチングでは、研修医の希望を最大限叶えるため『研修医が提案する側（研修医提案型）』が世界標準として採用されている

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

PythonによるGale-Shapley安定マッチングアルゴリズムの実装

医師臨床研修マッチングなどで実際に用いられているDAアルゴリズムの完全なコードです。

1def gale_shapley(men_prefs, women_prefs):
2    """
3    men_prefs: { 'M1': ['W1', 'W2', 'W3'], ... }
4    women_prefs: { 'W1': ['M2', 'M1', 'M3'], ... }
5    """
6    # 各女性のキープ相手
7    women_partner = {w: None for w in women_prefs}
8    # 未婚の男性リスト
9    free_men = list(men_prefs.keys())
10    # 各男性が次にプロポーズする女性のインデックス
11    propose_index = {m: 0 for m in men_prefs}
12    
13    while free_men:
14        m = free_men.pop(0)
15        # 次に好みな女性
16        w = men_prefs[m][propose_index[m]]
17        propose_index[m] += 1
18        
19        current_partner = women_partner[w]
20        if current_partner is None:
21            # 相手がいなければ仮キープ
22            women_partner[w] = m
23        else:
24            # 現在の相手と新規提案者を比較
25            pref = women_prefs[w]
26            if pref.index(m) < pref.index(current_partner):
27                # 新しい男性のほうが好きなので乗り換え
28                women_partner[w] = m
29                free_men.append(current_partner)
30            else:
31                # 既存の相手をキープ、新規男性を振る
32                free_men.append(m)
33                
34    return {m: w for w, m in women_partner.items()}