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

基于组合优化的稳定匹配理论与应用

基本信息

批准号：
15J09039
负责人：
横井優
金额：
$ 1.09万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2015
资助国家：
日本
起止时间：
2015-04-24 至 2017-03-31
项目状态：
已结题

项目摘要

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

稳定匹配模型是一种在医学培训分配系统和学校选择系统中都有应用的数学模型，并且已经从经济学、数学和计算机科学等各个领域进行了研究。在本研究中，我们使用组合优化方法在稳定匹配理论中获得了以下结果。 1.在多对一的稳定匹配问题中，我们考虑找到一个“稳定”的匹配，考虑到每个受试者在两组之间的偏好，这可以与住院医生和医院进行比较。如果每个医院只有分配人数的上限，则可以保证稳定匹配的存在，但如果每个医院也有下限，则不能保证稳定匹配的存在。对于不具有稳定匹配的问题示例，另一种解决方案是找到无嫉妒匹配，这是对其的放松。在本研究中，我们考虑了具有下界的多对一稳定匹配模型中无嫉妒匹配的存在。然后，我们设计了一种算法，可以有效地确定基本设置和具有拟阵结构的扩展模型是否存在无嫉妒匹配。我们还展示了在更通用的模型中确定存在性的计算难度（NP 难度）。 2.在去年的研究中，我们设计了第一个强多项式时间算法来计算聚合物结构的稳定匹配。在今年的研究中，我们表明算法的输出不仅是稳定的，而且在许多可能的稳定解中满足某种最优性。此外，使用稳定匹配的数学扩展（部分有序对的内核），我们给出了列表长度的表征，保证了列表超模着色的组合问题的着色的存在。