読者です 読者をやめる 読者になる 読者になる

1.1 安定マッチング

安定マッチング S を求める Gale-Shapley のアルゴリズム:
すべての男性 m ∈ M とすべての女性 s ∈ W は自由な身であると初期設定する

While すべての女性にはプロポーズしていない自由な身の男性 m がいる
  そのような男性 m を選ぶ
  w を m の好意順リストで m がまだプロポーズしていないもっとも好きな女性とする
  m が w にプロポーズする
  If wが自由な身である then
    (m, w) は婚約する
  Else
    w は現在 m'と婚約しているとする
    If w が m より m' が好きである then
      m は自由な身であり続ける
    Else (w は m' より m が好きである)
      (m, w) は婚約する
      m' は自由な身になる
    Endif
  Endif
EndWhile
婚約ペアの集合Sを返す

G-Sアルゴリズムはたかだかn**2回反復して終了する

アルゴリズムの計算時間を上から抑える有効な戦略は,その進捗度測定器(progress measure)を見つける.
各ステップが終了に向かって近づいていることを正確に言い表せるから.

証明

このアルゴリズムは男性がまだプロポーズしていない女性にプロポーズする事になる.
この反復 t の終了時までに, m が w にプロポーズしたペア (m, w) のすべての集合を P (t) とする.
すべての t で P (t+1) のサイズは P (t) より大きくなる事が分かる.
しかし, 男性と女性のペアの総数は高々 n**2 であるので, アルゴリズム全体で P (.) は高々 n**2 しか増加しない

特徴

G-Sアルゴリズムは,プロポーズする側に対しては実現できる最善の安定マッチングをもたらし,
プロポーズを受ける側に対しては実現できる最悪の安定マッチングをもたらすことがわかった.