安定結婚問題

安定結婚問題について

安定結婚問題（Stable Marriage Problem）は、1962年にデイヴィッド・ゲールとロイド・シャープレーによって提唱され、男女のマッチングに関する重要な理論を提供しています。この問題は、n人の男性とk人の女性、そしてそれぞれの参加者が持つ選好リストから成り立っています。選好リストは、各個人が異性全員および独身の自分自身を順位付けしたものです。ここで重要なのは、参加者全員が婚約した場合でも、他の誰かと結婚することが自分の希望に合致するならば、その選択が安定なマッチングであるとされます。このような安定なマッチングには、「ブロッキングペア」が存在しないことが求められます。ブロッキングペアとは、ある婚約者とそのパートナーが互いに他の相手の方が好ましいと感じるようなペアのことです。

安定結婚問題の解決策は、安定マッチングに至ることです。この安定マッチングを見つけるためには、O(N^2)時間で解決できるアルゴリズムが存在することが知られています。その中で有名なものが、ゲール-シャープレー（Gale-Shapley）アルゴリズムです。このアルゴリズムは、参加者全員の選好リストに基づいて、安定なマッチングのペアを導きます。

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

ゲール-シャープレーアルゴリズムは次の手順に基づきます。

1. 初期設定: すべての男性と女性を独身の状態にし、プロポーズを行っていないものとします。

2. プロポーズの繰り返し: 独身の男性がいる限り、以下の操作を繰り返します。
- 男性hは、まだプロポーズしていない女性の中で最も好みの相手dにプロポーズします。
- dが独身の場合、彼女はhと婚約します。
- dが他の男性h'と婚約している場合、
- dがh'の方が好きであれば、hのプロポーズを断ります。
- hの方が好きであれば、h'との婚約を解消し、hと婚約します。

3. 出力: 現在の婚約ペアを安定マッチングとして成果として出力します。

このアルゴリズムの特徴は、男性がプロポーズを行う構造ですが、女性がプロポーズする形式に変えても、結果としては変わらないことがわかっています。男性がプロポーズする場合は、男性にとって最も望ましい安定マッチングを得ることができ、女性がプロポーズする場合は、女性にとって最も望ましい安定マッチングを得ることが可能です。これは、市場参加者が自分の好みに従って安定的な関係を確築できることを示しています。

ゲール-シャープレーアルゴリズムは、任意の例に対して有限回の操作で安定マッチングを導くことができるため、特に注目すべき成果です。この理論に基づいて、ロイド・シャープレーは2012年にノーベル経済学賞を受賞しました。この問題の解決策は、現実の多くの分野においても応用されており、特に市場におけるマッチングやリソース配分に関する問題に利用されています。

参考文献

• - 応用数理計画ハンドブック（朝倉書店）

関連項目

• - 完全被覆問題

外部リンク

• - 『安定マッチングとGale-Shapleyアルゴリズム』 - 高校数学の美しい物語

もう一度検索