[2J5-GS-5] エージェント：

[2J5-GS-5-03] 地域制約下の両方向マッチングにおける新たな公平性・効率性の概念

〇後藤 碧斗¹、孫 兆鴻¹、横尾 真¹ (1. 九州大学)

キーワード：両方向マッチング、制約プログラミング

本論文では，日本の研修医配属などに応用できる地域上限制約下の両方向マッチングについて考える． 両方向マッチングにおいて地域上限制約が課された場合には，公平性かつ非浪費性を満たすマッチングは必ずしも存在しないことが知られている．また，公平性と効率性の間にはトレードオフが存在することが知られおり，一方を向上させるためにはもう一方を緩和する必要がある．本論文では，公平性を緩和した概念 (EF-k, REF-k, SEF-k)，効率性を緩和した概念 (NW-l)を導入する．その後制約プログラミング (CP) を用いて非浪費性と緩和した公平性を満たすアルゴリズム，および公平性と緩和した非浪費性を満たすアルゴリズムを提案する．そして非浪費性を制約したCPに関して緩和した公平性ごとの評価実験を行い，REF-kが最も高い公平性を達成することを明らかにした．また，公平性とNW-lを制約したCPに関して，既存の公平メカニズムFDA，PLDAとの性能比較を行ったところ，CP は FDA よりも優れた性能を示したが，PLDA とは同等の性能を示した．