講演情報
[2Yin-B-24]遺伝制約下の両方向マッチングにおける公平性と非浪費性の緩和
〇後藤 碧斗1、孫 兆鴻1、横尾 真1、木村 慧1 (1. 九州大学)
キーワード：
マルチエージェント、メカニズムデザイン、両方向マッチング
本論文では，多様性要件や難民の再定住問題などへ応用される遺伝制約下における両方向マッチングについて考える．遺伝制約が課された両方向マッチングでは，公平性および非浪費性を同時に満たすマッチングが必ずしも存在しないことが知られており，既存研究では，いずれか一方の性質を緩和し，もう一方を保証する手法が主に採られてきた。本論文では，既存研究とは異なり，公平性と非浪費性を同時に緩和する手法を提案する．公平性を緩和した概念である College-Envy-Freeness up to k students (CEF-k) および 非浪費性を緩和した概念である Vacant-seat Claim up to l colleges (VC-l) を導入し，CEF-k および戦略的操作不可能性（SP）を満足するメカニズムを提示する．さらに，学生と学校の数が等しく n であるマッチング市場において，ある k に対して，当該 SP メカニズムが，CEF-k と VC-(n-k-1) を満足することを示す．