男女平等安定マッチング問題に対する近似アルゴリズム

概要

論文の詳細を見る
安定結婚問題は,GaleとShapleyによって提案されたマッチングの問題である.任意の例題について,解が存在し,それを見つける多項式時間が存在することが知られている.しかし,このアルゴリズムによって得られるマッチングは「男性最適」,つまり,男性にとっては好ましいが女性にとっては好ましくないマッチングである(逆に,男女の役割を入れ替えれば,女性最適なマッチングになる).GusfieldとIrvingによって提案された男女平等安定マッチング問題は,男女両者にとって「公平な」安定マッチングを求める,つまり,男性側の不満足度の和が女性側の不満足度の和になるべく近づくような安定マッチングを求める問題である.この問題は,強NP困難であることが知られている.本稿では,男女平等安定マッチング問題に対して,ほぼ最適な解を求める多項式時間アルゴリズムを与える.さらに,評価指標を一つ増やして,男女平等(sex-equality)の観点でほぼ最適なもののうち,全体の公平さ(egalitarian)が最小の安定マッチングを求める問題を考える.我々は,この問題がNP困難であることを示し,この問題に対して近似度が2より良い多項式時間アルゴリズムを構築した.
2008-03-03