[1D3-OS-28b] 複雑化社会における意思決定・合意形成のためのAI技術(2)

[1D3-OS-28b-02] 対称性を満たすM凸集合の和集合で表現される制約を扱うマッチングメカニズムの提案

張 語哲¹、〇八尋 健太郎¹、Barrot Nathanael²、横尾 真¹ (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より優れていることを評価実験により示す．