安定結婚問題ソルバー

安定結婚問題ソルバー

安定結婚問題ソルバーは、ゲール＝シャプレーの保留受容アルゴリズムのインタラクティブな実装です。このアルゴリズムは、1962年にデビッド・ゲールとロイド・シャプレーによって、各メンバーが相手側の完全なランキングを持っている場合に、同サイズの2つのグループ間で常に安定したペアリングを生成できることが証明されました。このツールは嗜好リストを受け取り、アルゴリズムをステップごとに実行し、安定マッチング、アニメーション化された二部グラフの可視化、嗜好ヒートマップ、およびブロッキングペアが存在しないことの検証結果を表示します。

安定結婚問題とは？

同人数の2つの分離した集合（例えば、n人の男性とn人の女性、またはn人の志願者とnの職位）があり、全員が相手側の全メンバーに対する完全な嗜好リストを持っているとします。マッチングとは、これら2つの集合間の一対一のペアリングです。マッチング以外のペア (a, b) のいずれも、割り当てられた現在のパートナーよりもお互いと一緒にいることを望まない場合、そのマッチングは安定していると呼ばれます。

形式的には、マッチング M において、a が b' と、b が a' とマッチングされている場合、以下の条件を同時に満たすブロッキングペア (a, b) が存在しないとき、そのマッチングは安定しています。

もし両方の条件が成り立つなら、a と b の両方が現在のパートナーを捨ててお互いを選ぶため、マッチングは不安定になります。安定マッチングとは、そのようなペアが存在しない状態です。

ゲール＝シャプレーアルゴリズム

ゲールとシャプレーは、どのような嗜好セットに対しても安定マッチングが常に存在することを構成的に証明し、それを見つけるための効率的なアルゴリズムを提示しました。アルゴリズムは以下のラウンドで実行されます。

1. 婚約していないすべての提案者が、まだ自分を拒絶していない中で最も順位の高い受容者にプロポーズします。
2. プロポーズを1つ以上受け取った各受容者は、現在の暫定的な婚約者と比較して最も好む1人を選んで暫定的に受諾し、それ以外を拒絶します。
3. 拒絶された提案者は再びフリーになり、次のラウンドで次の候補に進みます。
4. すべての提案者が婚約した時点でアルゴリズムは終了します。これは最大 n² 回のプロポーズで必ず発生します。

重要な理論的特性

存在性と唯一性

安定マッチングは常に存在しますが（Gale & Shapley, 1962）、必ずしも唯一ではありません。特定の嗜好セットに対して複数の安定マッチングが存在する場合があり、それらは共通の嗜好によって順序付けられた束を形成します。

提案者最適性

片方の側が提案する場合、ゲール＝シャプレーは提案者最適安定マッチングを生成します。すべての提案者は、あらゆる安定マッチングにおいてペアになり得る最高のパートナーを得られます。対称的な議論により、これは受容者最悪マッチングでもあります。この電卓で提案側を切り替えると、多くの場合、結果が変化します。

提案者の戦略的誠実性

ゲール＝シャプレーの下では、提案者は嗜好を偽る動機がありません。真実を伝えることが支配戦略となります。一方で、受容者は戦略的に嗜好を偽ることで利益を得られる場合があります。米国の研修医市場で学生側が提案者として設計されている理由の一つがこれです。

地方病院定理 (Rural Hospitals Theorem)

マッチングされないエージェントの集合は、すべての安定マッチングにおいて同一です。したがって、サイズが不均衡なインスタンス（このツールの範囲外）であっても、どの安定解でも同じ人がマッチングされないまま残ります。

入力形式

この電卓は、メンバー1人につき1行の形式を想定しています。名前の後にコロンを置き、その後にカンマで区切った完全な嗜好順位リストを記述します。

要件:

• 両方のグループのメンバー数が完全に一致している必要があります。
• 各メンバーは相手グループの全員をランク付けする必要があります（部分的なリストは不可）。
• 名前には文字、数字、アンダースコア、ハイフン、スペース、および一般的なUnicode文字を使用できます。
• 高速なインタラクティブアニメーションのため、各側最大 15 名まで対応しています。

この電卓の使い方

1. グループAの嗜好を入力: 左側のテキストエリアに、1人1行で完全なランキングを入力します。
2. グループBの嗜好を入力: 右側のテキストエリアに、同じ形式で入力します。
3. 提案側を選択: グループAまたはグループBを選択します。両方を試して、A最適とB最適の結果を比較してみてください。
4. 「安定マッチングを解決」をクリック: 電卓がゲール＝シャプレーを実行し、安定したペア、統計、アニメーション、および安定性の証明を生成します。
5. アニメーションを確認: 再生 / ステップ / リセットのコントロールを使用して、すべてのプロポーズ、受諾、交代、拒絶を順番に確認できます。
6. ヒートマップを調査: 各セルに順位が表示されます。黄色の枠線のセルが最終的なマッチングです。これらのセルがどの位置にあるかを見ることで、各側の「満足度」を確認できます。

実行例 — 古典的な3×3

男性: Alex, Bryan, Chris。女性: Bea, Claire, Diana。嗜好:

男性が提案する設定でゲール＝シャプレーを実行すると、第1ラウンドで Alex–Bea, Bryan–Claire, Chris–Diana が成立します（各男性の第1希望が、その男性を第1希望としない女性と一致し、衝突が発生しません）。このマッチングは安定しています。どの男女ペアも、現在のパートナーを解消して相手を選ぶ方が得になることはないため、ブロッキングペアは存在しません。

実社会での応用

ロイド・シャプレーがノーベル賞を受賞した理由

2012年、スウェーデン王立科学アカデミーは、ノーベル経済学賞を、理論の功績に対してロイド・シャプレー（故デビッド・ゲールと共に）に、そして理論を米国の研修医マッチングや腎臓交換ネットワークの再設計などの実市場に適用した功績に対してアルヴィン・ロスに授与しました。授賞理由は「安定配分理論と市場設計の実践」でした。

よくある質問

安定結婚問題とは何ですか？

安定結婚問題とは、同人数の2つのグループがあり、各メンバーが他方のグループの全メンバーを好みの順にランク付けしている場合、どの2人も現在のパートナーよりもお互いを好んで今のペアを解消することがないように全員をペアリングできるかという問題です。このようなペアリングを安定マッチングと呼びます。ゲール＝シャプレーアルゴリズムはこの問題をO(n²)の時間で解決し、常に安定マッチングを見つけます。

ゲール＝シャプレーアルゴリズムはどのように機能しますか？

ゲール＝シャプレーの保留受容アルゴリズムはラウンド制で進みます。各ラウンドで、現在婚約していない各提案者が、まだ自分を拒絶していない中で最も順位の高い受容者にプロポーズします。各受容者は、これまでに受けた中で最高のプロポーズを暫定的に受け入れ、それ以外を拒絶します。追い出された提案者は再び自由の身となります。すべての提案者が婚約した時点でアルゴリズムは終了し、これは最大n²回のプロポーズで発生します。

安定マッチングは唯一のものですか？

いいえ、安定マッチングのインスタンスには複数の安定マッチングが存在し得ます。しかし、片方の側が提案する場合、ゲール＝シャプレーは常に提案者最適安定マッチングを生成します。つまり、すべての提案者が、あらゆる安定マッチングの中で得られる最高のパートナーを得ることになります。対称的に、これは相手側にとっては受容者最悪マッチングとなります。提案側を入れ替えると、多くの場合異なる安定マッチングが得られます。

ブロッキングペアとは何ですか？

ブロッキングペアとは、現在はマッチングされていないペア(a, b)において、aが現在のパートナーよりもbを好み、かつbも現在のパートナーよりもaを好んでいる状態のペアを指します。ブロッキングペアが存在する場合、その二人はお互いとペアを組むことを望むため、マッチングは不安定になります。安定マッチングにはブロッキングペアが存在しません。この電卓は解決後に自動的にこれを検証します。

安定マッチングの実社会での応用例は何ですか？

ゲール＝シャプレーアルゴリズムは、米国の医学生を研修先に割り当てる全米研修医マッチングプログラム、ボストンやニューヨークの学校選択システム、数カ国での大学入試、臓器提供者の腎臓交換チェーン、ルームメイト割り当てシステムなどで活用されています。ロイド・シャプレーとアルヴィン・ロスは、この業績の一部により2012年にノーベル経済学賞を受賞しました。

両方のグループは同じサイズである必要がありますか？

古典的な安定結婚問題の定式化では、はい、必要です。両側が同じメンバー数を持ち、それぞれが相手側の完全なランキングを提供する必要があります。不完全なリストを持つ安定マッチングや病院研修医問題などの不均衡なバリエーションも存在しますが、修正されたアルゴリズムが必要です。この電卓は等しいサイズと完全な嗜好リストを強制します。

参考文献

• 安定結婚問題 — Wikipedia
• ゲール＝シャプレーアルゴリズム — Wikipedia
• 全米研修医マッチングプログラム — Wikipedia (英語)
• 2012年ノーベル経済学賞 — シャプレー & ロス