# 安定結婚問題 ## 定義 **安定結婚問題(Stable Marriage Problem)**は、同数の男性集合と女性集合があり、各人が相手全員に対する選好順位(preference list)を持つとき、全員を一夫一婦で結婚させ、かつ**不良カップル(rogue couple)**——互いに現在の配偶者より好み合う、結婚していない男女の組——が一切生じないようにする問題である。不良カップルを含まないマッチングを**安定マッチング(stable matching)**と呼ぶ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.6) 安定マッチングは常に存在し、**Mating Ritual**(**Gale–Shapley アルゴリズム**)がそれを構成的に与える。手続きは日々繰り返される: (1) 朝、各男性は自分のリストの最上位の女性にセレナーデする(**求婚者、suitor**になる)。(2) 午後、複数の求婚者を持つ女性は最も好む1人だけを残し、他は永久に断る。(3) 夕方、断られた男性はその女性を自分のリストから消す。全女性の求婚者が高々1人になった日に終了し、その相手と結婚する。ある人にとって、ある安定マッチングで結婚しうる相手を**実行可能な配偶者(feasible spouse)**と呼び、実行可能な配偶者のうち最も好む相手を**最適配偶者(optimal spouse)**、最も好まない相手を**最悪配偶者(pessimal spouse)**と呼ぶ。Mating Ritual は、全ての男性をその最適配偶者と、全ての女性をその最悪配偶者と結婚させる。すなわちこのアルゴリズムは求婚する側(男性)に構造的に有利である。1962年の D. Gale と L. S. Shapley の論文で発表され、それに先立ち米国の National Resident Matching Program(NRMP)が研修医と病院のマッチングに同種の手続きを用いていた。Shapley はこの功績で2012年ノーベル経済学賞を受賞した。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.6.1〜§11.6.5) ## 横断的知見 （2ソース目以降に積み増す。現時点では第11章単独の導入のため、複数ソース間の横断的な観察はまだ記録できていない。） ## 未解決の問い - 本章は性別を区別しない「バディ・マッチング(buddy matching、全員が対等な立場で相互にペアを組む)」では安定なマッチングが存在しない反例があると述べる(演習11.22、図11.26)。二部構造(男女の区別)が安定性の存在にどう本質的に効いているのか、一般グラフの安定マッチング理論(Irving のアルゴリズムなど)は本章の範囲外で確認が必要。 - Mating Ritual は Akamai のWebトラフィック割り当てにも応用されると本章は述べるが、詳細なアルゴリズム設計(選好関数の定義、分散実行の方法)は本章からは分からない。関連する通信ネットワーク・分散システムのソースが入れば横断的知見として積み増す。 ## 関連 - 概念: [[マッチング]] / [[単純グラフ]] - 実体: [[Akamai]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 11.