安定マッチング
求婚アルゴリズム（Gale–Shapley の繰延受入）が安定マッチへ収束する過程をステップ実行します 研修医マッチング等の基盤
4
7
ラウンド（求婚回数）
0
仮キープ数
0 / 4
ブロッキングペア
—
状態
準備完了
選好リスト（左から好きな順）
現在のマッチング（青=仮キープのリンク / 橙=今の求婚 / 赤破線=ブロッキングペア）
安定 ⇔ 互いに「今の相手より好き」なペア（ブロッキングペア）が 1 つも無い
2 つのグループ（例：研修医と病院、A と B）があり、各人が相手側を好きな順に並べた選好を持ちます。
全員をペアにする「マッチング」のうち、互いに今の相手より相手を好む二人組（ブロッキングペア）が存在しないものを
安定マッチングと呼びます。
Gale–Shapley の繰延受入アルゴリズムでは、求婚側が「まだ断られていない中で一番好きな相手」へ順に求婚し、 受ける側は「今キープしている相手」と「新しい求婚者」を比べて好きな方を仮キープ、もう一方を断ります。 断られた人は次の候補へ──を繰り返すと、必ず安定マッチに収束します。ステップ実行で確かめましょう。
Gale–Shapley の繰延受入アルゴリズムでは、求婚側が「まだ断られていない中で一番好きな相手」へ順に求婚し、 受ける側は「今キープしている相手」と「新しい求婚者」を比べて好きな方を仮キープ、もう一方を断ります。 断られた人は次の候補へ──を繰り返すと、必ず安定マッチに収束します。ステップ実行で確かめましょう。
いま何が起きている？
ここがポイント
- 必ず安定マッチに収束する ── 全員ペアになり、ブロッキングペアが 0 個で停止する（Gale–Shapley が証明）。
- 「仮キープ」がカギ ── 受ける側は確定せず保留するので、後からより良い求婚者が来れば乗り換えられる。
- 求婚側に有利 ── 求婚した側（A）は全員が「自分にとって可能な最良の安定相手」を得る。求婚する側を B に変えると結果が変わることがある。
- 研修医マッチング（NRMP／日本のマッチング）はこの仕組みの実応用。病院と研修医の希望から安定な配属を一括決定している。