🎎

安定マッチング入門：Gale–ShapleyをRubyで実装して検証する

に公開
Ruby
アルゴリズム
zennfes2025free
tech

はじめに

安定マッチング問題（Stable Marriage Problem）をRubyで実装してみます。
⚠️個人の技術記事なので誤り等があればご容赦ください。

用語と定義

  • 集合 (M={m_1, m_2, ... ,m_n})、(W={w_1, w_2, ... ,w_n})
  • 完全マッチング：全員が1対1でマッチしている
  • ブロッキングペア：マッチングしている既存の相手より、互いに「より好ましい」相手同士のペア
  • 安定マッチング：ブロッキングペアが存在しない完全マッチング

安定マッチング

結婚する男女のマッチングを例に挙げる。男性を(m)、女性を(w)とする。
男性の集合を(M={m_1, m_2, …,m_n})、女性の集合を(W={w_1, w_2, …, w_n})とする。
ここで、ある男性(m)とある女性(w)が結婚することをマッチングと呼び、(M)と(W)の全員が1対1で結ばれている状態を完全マッチングという。
しかし、完全マッチングであっても、それが必ずしも安定とは限らない。
たとえば、男性(m)が現在の相手よりも別の女性(w')を好み、同時に(w')も自分の現在の相手より(m)を好む場合、そのペア((m,w'))が存在するとマッチングは不安定になる。
なぜなら、男女それぞれが自分の中で好みの順位（好意リスト）を持っており、互いにより上位の相手と結びつこうとする傾向があるからである。
このような不安定さを排除し、安定マッチングを成立させる方法として知られているのがGale–Shapleyアルゴリズムである。
ここでは男性提案版の手続きを考える。
まず、男性(m)は自分の好意リストの上から順に、まだプロポーズしていない女性(w)に申し込む。
女性(w)がまだ誰とも婚約していない場合、(m)と(w)は仮婚約を結ぶ。
しかし、すでに(w)が別の男性(m')と仮婚約している場合には、(w)は(m)と(m')のどちらをより好むかを比較する。
もし(w)が(m')を好むなら、現在の婚約を維持し、(m)は自由な身のまま次の候補へ進む。
逆に、(w)が(m)をより好む場合は、既存の婚約((m', w))を破棄し、新たに((m, w))が仮婚約となる。このとき、(m')は自由な男性となり、再び別の女性へプロポーズを行う。
この手続きを、すべての男性が婚約済みになるまで繰り返すことで、どの男女の組み合わせも互いに「乗り換えたい」と思わない、すなわちブロッキングペアの存在しない安定マッチングが得られる。

アルゴリズム（男性提案版 Gale–Shapley）

アルゴリズムを疑似コードで記述します。

while まだ誰にもマッチしていない男性mが存在し、
      かつmが未提案の女性が残っている
  w←mの選好リストで未提案の最上位
  mがwにプロポーズ
  if wがフリーなら
    (m, w) を仮婚約
  else
    いまwはm'と仮婚約中
    if wはm'よりmを好む
      (m, w)を仮婚約に更新し、m'をフリーへ
    else
      mは引き続きフリー（次点へ提案継続）
終了
仮婚約ペアを確定して返す

Rubyで実装

# 例外を投げるヘルパー関数
def assert(cond, msg)
  raise ArgumentError, msg unless cond
end

# 男性提案のGale–Shapley
# m_prefs: Array<Array<Integer>> 長さn（各mの女性の順位：0..n-1の置換）
# w_prefs: Array<Array<Integer>> 長さn（各wの男性の順位：0..n-1の置換）
# return: Array<Integer> men_match[m] = w
def gale_shapley(m_prefs, w_prefs)
  n = m_prefs.length
  assert(w_prefs.length == n, "men and women must have the same size")
  # 検証：各行が0..n-1の置換か
  perm = (0...n).to_a
  n.times do |i|
    assert(m_prefs[i].sort == perm, "m#{i} prefs must be a permutation of 0..#{n-1}")
    assert(w_prefs[i].sort == perm, "w#{i} prefs must be a permutation of 0..#{n-1}")
  end

  # 女性側のランク（低いほど好ましい）
  w_rank = Array.new(n) { Array.new(n) }
  n.times { |w| w_prefs[w].each_with_index { |m, r| w_rank[w][m] = r } }

  next_idx = Array.new(n, 0)          # 各男性の次の提案先インデックス
  engaged_to_w = Array.new(n, nil)    # engaged_to_w[w] = m（nil は空き）
  free_men = (0...n).to_a             # 自由な男性のキュー

  until free_men.empty?
    m = free_men.shift
    assert(next_idx[m] < n, "man #{m} has proposed to everyone (no stable match?)")
    w = m_prefs[m][next_idx[m]]
    next_idx[m] += 1

    if engaged_to_w[w].nil?
      engaged_to_w[w] = m
    else
      m_old = engaged_to_w[w]
      if w_rank[w][m] < w_rank[w][m_old]  # wはmをより好む
        engaged_to_w[w] = m
        free_men << m_old
      else
        free_men << m
      end
    end
  end

  men_match = Array.new(n)
  n.times { |w| men_match[engaged_to_w[w]] = w }
  men_match
end

# 安定性検証：遮断ペアが存在しないか
def stable?(m_prefs, w_prefs, men_match)
  n = m_prefs.length
  return false unless w_prefs.length == n && men_match.length == n

  # 逆マッチ（女性→男性）
  women_match = Array.new(n)
  n.times { |m| women_match[men_match[m]] = m }

  # ランク表
  w_rank = Array.new(n) { Array.new(n) }
  n.times { |w| w_prefs[w].each_with_index { |m, r| w_rank[w][m] = r } }
  m_rank = Array.new(n) { Array.new(n) }
  n.times { |m| m_prefs[m].each_with_index { |w, r| m_rank[m][w] = r } }

  n.times do |m|
    n.times do |w|
      next if w == men_match[m]
      if m_rank[m][w] < m_rank[m][men_match[m]] && w_rank[w][m] < w_rank[w][women_match[w]]
        return false  # 遮断ペア発見
      end
    end
  end
  true
end

# --- デモ ---
if __FILE__ == $0
  names_m = %w[m1 m2 m3]
  names_w = %w[w1 w2 w3]

  m_prefs = [
    [0, 1, 2], # m1: w1 > w2 > w3
    [1, 2, 0], # m2: w2 > w3 > w1
    [1, 0, 2]  # m3: w2 > w1 > w3
  ]
  w_prefs = [
    [1, 0, 2], # w1: m2 > m1 > m3
    [2, 0, 1], # w2: m3 > m1 > m2
    [0, 2, 1]  # w3: m1 > m3 > m2
  ]

  match = gale_shapley(m_prefs, w_prefs)
  puts "Men-optimal matching:"
  match.each_with_index { |w, m| puts "#{names_m[m]} — #{names_w[w]}" }
  puts "Stable? #{stable?(m_prefs, w_prefs, match)}"
end

結果

Men-optimal matching:
m1 — w1
m2 — w3
m3 — w2
Stable? true

応用例

分野・制度名 主体・導入機関 目的・仕組み 出典
医師臨床研修マッチング（JRMP） 医師臨床研修マッチング協議会（Japan Residency Matching Program） 医学生と研修病院を、双方の希望と病院の定員制約に基づいて安定に配属（DA＝受入保留型の考え方を採用）。毎年スケジュールを定めて全国実施。 公式サイト（トップ／結果・中間公表／年次スケジュール）。 (jrmp.jp)
公立高校入試（制度設計の提言・検討） 内閣官房・デジタル行財政改革会議資料、東京大学マーケットデザインセンター（UTMD） 単願制の課題を解くために、出願順位と学校側の優先順位から安定マッチングを出力するDA（生徒提案／学校提案）を提言・解説。自治体設計により実装可否が分かれる。 政策資料PDF／UTMD解説ページ・提言／関連解説。 (Cabinet Office Japan)

まとめ

今回は安定マッチングをRubyで実装してみました。みなさんの学習の補助になれば幸いです。

参考文献

アルゴリズムデザイン Jon Kleinberg 著・ Eva Tardos 著・ 浅野 孝夫 訳・ 浅野 泰仁 訳・ 小野 孝男 訳・ 平田 富夫 訳

Discussion