2018年度人工知能学会全国大会（第32回）
2018年6月5日〜6月8日鹿児島県鹿児島市（城山観光ホテル）
2018年度人工知能学会全国大会（第32回）
2018年6月5日〜6月8日鹿児島県鹿児島市（城山観光ホテル）
[1D3-OS-28b-02]対称性を満たすM凸集合の和集合で表現される制約を扱うマッチングメカニズムの提案
張 語哲1、〇八尋 健太郎1、Barrot Nathanael2、横尾 真1(1. 九州大学 大学院システム情報科学府、2. 理化学研究所 革新知能統合研究センター AIP)
キーワード：
マッチング問題、戦略的操作不可能性、M凸集合
本論文では，対称性を満たすM凸集合の和集合で表現される制約を新たに導入する．この制約は，M凸集合より広い制約であり，現実のマッチング問題に幅広く応用できる制約である．凸性は和集合で閉じていないので，対称性を満たすM凸集合の和集合は一般にM凸集合ではない．よって，公平性，戦略的操作不可能性を満たし，M凸集合より広い制約のクラスを扱うメカニズムの考察は理論的に意義のある課題である．そこで，人為的に定められた上限を段階的に減少させながら，Deferred Acceptance メカニズム (DA) を繰り返し適用するQuota Reduction Deferred Acceptance メカニズム (QRDA) を新たに提案する．QRDAは公平性，戦略的操作不可能性を満たし，対称性を満たすM凸集合の和集合で表現される制約を扱う．また，QRDAは基準メカニズムであるArtificial Cap Deferred Acceptance メカニズム (ACDA) より学生の満足度が高いことを理論的，実験的に示した上で，非浪費性の観点からもQRDAはACDAより優れていることを評価実験により示す．