組合せ最適化にもとづく安定マッチングの理論と応用

点击翻译按钮获取中文摘要

安定マッチングモデルは，研修医配属システムや学校選択制度などに応用をもつ数理モデルであり，経済学や数学，計算機科学といった様々な方面から研究されている．本研究では，組合せ最適化を用いたアプローチにより，安定マッチング理論における以下の成果を得た．１．多対一の安定マッチング問題では，研修医と病院になぞらえられる二つの集合間で，各主体の選好を考慮した“安定な”マッチングを見つけることを考える．各病院が割当人数に上限しかもたない場合には安定マッチングの存在が保証できるが，下限ももつ場合には保証できない． 安定マッチングをもたない問題例に対しては，その緩和である envy-free マッチングを発見することが，代替策として考えられる．本研究では，下限付き多対一安定マッチングモデルにおける envy-free マッチングの存在性について考察した．そして，基本的な設定および，マトロイド的構造を持った拡張モデルに対し，効率的に envy-free マッチングの存在判定をするアルゴリズムを設計した．また，より一般的なモデルにおける存在性判定の計算困難性(NP困難性)を示した．２．昨年度の研究では，ポリマトロイドという構造上の安定マッチングを算出する初の強多項式時間アルゴリズムを設計した．本年度の研究では，そのアルゴリズムの出力が単に安定であるだけでなく，多数存在し得る安定解の中で，ある種の最適性を満たすものであるということを示した．また，安定マッチングを数学的に拡張した概念(半順序対のカーネル)を用いて，リスト優モジュラ彩色という組合せ的問題に対して，彩色の存在を保証するリスト長の特徴付けを与えた．