About: 安定結婚問題

安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。 安定結婚問題は人の男性と人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable matching）という。 下図に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。 「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。 全ての例題について、安定マッチングは必ず存在する。それを見つける O(N2) 時間アルゴリズムが存在することも知られている（下を参照）。