Gale-Shapleyアルゴリズム
- 提唱者
- David Gale, Lloyd Shapley
- 年
- 1962
- 種類
- algorithm
- 系統
- Game-theoretic
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Gale-Shapleyアルゴリズムは、安定結婚問題(stable marriage problem)を解決します。これは、2つのグループ(例:研修医と病院、学生と学校)をマッチングする際に、どのペアも割り当てられたパートナーよりも互いを好むことがないようにする方法です。David GaleとLloyd Shapleyによって1962年に導入されたこのアルゴリズムは、繰り延べ受諾(deferred acceptance)プロセスを通じて多項式時間で安定したマッチングを保証します。このプロセスでは、一方の側が順次提案し、もう一方の側が応答し、より良い選択肢が現れると選択を修正します。
手法の背後にある直感
医師と病院のマッチングを想像してください。このアルゴリズムは椅子取りゲームのように機能します。各医師は最も希望する病院に提案し、各病院は利用可能な最良の医師を仮に受け入れます。病院はより良い提案を受け取ると、選択を修正し、以前の受け入れを拒否する可能性があります。拒否された医師は、次に希望する病院に提案します。このプロセスは、どの医師もそれ以上提案したくなくなり、どの病院も現在のマッチングを交換したくなくなるまで続きます。結果は安定しています。どの医師と病院のペアも、割り当てられたパートナーよりも互いにマッチングされることを好むことはありません。
歴史学
David GaleとLloyd Shapleyは1962年に安定結婚問題の解決策を発表し、二面市場では常に安定したマッチングが存在することを証明しました。彼らのアルゴリズムは、マッチング理論に関する膨大な文献を生み出し、医学、教育、労働市場にわたる応用があります。2012年、Alvin Rothは、マッチング理論を実際の市場設計に応用した実験的および理論的研究によりノーベル経済学賞を受賞し、Gale-Shapleyフレームワークの実用的な重要性を裏付けました。
使うべき場面
安定性が重要となる二面市場のマッチングにGale-Shapleyアルゴリズムを適用します。例えば、研修医の配置、学生の学校割り当て、腎臓交換、労働市場のマッチング、オンラインデーティング市場などです。割り当て後にマッチングが崩壊する可能性のあるマッチングの不安定性(ブロッキングペア)のリスクがある場合に使用します。このアルゴリズムは、一方の側が戦略的優位性を持って最初に動ける場合に理想的です。
限界と注意点
- パレート最適ではない:マッチングが総福祉を最大化しない可能性があり、パートナーを交換することで全員が利益を得られるブロッキングペアが存在する可能性がある
- 戦略的脆弱性:提案側は選好を偽ることで利益を得られる可能性があるが、応答側は正直である
- 非対称性:結果は、どちらの側が最初に提案するかに大きく依存する
- 制約を扱わない:アルゴリズムの変更なしに、複雑な選好(例:カップル、地域選好)を組み込むことは困難である
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 安定性の保証:最終的なマッチングにはブロッキングペアが存在しない
- 多項式時間:O(n^2)の複雑さで、大規模な集団にも効率的
- シンプルな実装:透明な選好収集により、実際に実行しやすい
- 戦略的インセンティブ:提案側には戦略的優位性があり、後の提案よりも早い提案を好む
- 普遍的な適用性:凸性や推移性を仮定することなく、あらゆる選好プロファイルに機能する
応用
- 研修医マッチング:NRMPを介して医学生と病院の研修プログラムをペアリングする
- 学校選択:選好と定員制約に基づいて生徒を公立学校に割り当てる
- 腎臓交換:臓器提供者とレシピエントをマッチングし、適合する移植を最大化する
- 求人市場マッチング:二面労働市場で求職者と雇用主を結びつける
- オンラインデーティング:デーティングプラットフォームでユーザーをマッチングし、マッチングの安定性とユーザー満足度を向上させる
使い方
使い方
両グループの全個人について、相手側に対する順位付けを表す選好リストを作成します。
各ラウンドで、提案側のマッチングされていない各個人は、まだ提案していない相手側の最も上位の個人に提案します。
受諾側の各個人は、マッチングされていない場合、または提案者が現在のパートナーよりも上位にランク付けされている場合、その提案を仮に受け入れます。この場合、以前の婚約は取り消されます。
アルゴリズムは、全員がマッチングされ、それ以上の提案が発生しなくなったときに停止し、安定したマッチングが生成されます。
よくある落とし穴
- 安定性のみが公平性や福祉に十分であると仮定すること。安定したマッチングは一方の側に大きく偏る可能性がある。
- 安定性を最適性と混同すること。安定したマッチングは必ずしも福祉を最大化するわけではない。
- 提案側の戦略的優位性を見落とすこと。提案側のメンバーは、より上位のパートナーとマッチングされる傾向がある。
- アルゴリズムが完全な選好リストを前提としていることを忘れること。不完全な選好には修正が必要である。
よくある質問
マッチングにおいて安定性が重要なのはなぜですか?
安定性がなければ、マッチングされたペアは後で、割り当てられたパートナーよりも互いを好むことに気づき、マッチングを破棄するインセンティブが生じる可能性があります。安定したマッチングは、そのようなブロッキングペアを防ぎ、再交渉なしにマッチングが持続することを保証します。
Gale-Shapleyアルゴリズムは常に同じマッチングを生成しますか?
いいえ。異なる選好リストや提案順序は、異なる安定したマッチングを生み出す可能性があります。しかし、常に「男性最適」な安定したマッチング(すべての提案者にとって最良)と「女性最適」な安定したマッチング(すべての応答者にとって最良)が存在します。
Gale-Shapleyはグループに対する選好(例:カップル)をどのように扱いますか?
標準的なアルゴリズムは、カップルやその他の制約を直接扱いません。カップルアルゴリズムのような拡張機能は存在しますが、より複雑であり、すべての選好プロファイルに対して安定性を保証するとは限りません。