少数のエージェントタイプのための改善されたMMS近似

我々は、エージェントが少数のタイプにグループ化され、各タイプ内のエージェントが同一の評価を持つ設定における最大最小共有（MMS）公正基準の下での不可分財の公正な分配について研究する。単一タイプの特別な場合では、正確なMMS割り当てが常に存在することが保証される。しかし、二つ以上の異なるエージェントタイプでは、正確なMMS割り当てが常に存在するわけではなく、近似-MMS割り当ての存在を確立することに焦点が移る。過去十年にわたる一連の研究により、最も知られている近似保証は34 + 33836である。本論文では、エージェントが二つまたは三つのタイプにグループ化される設定における近似保証を改善する。これは多くの実用的な設定で発生するシナリオである。具体的には、二つのエージェントタイプのための45-MMS割り当てと、三つのエージェントタイプのための1621-MMS割り当てを保証する新しいアルゴリズムを提案する。我々のアプローチは、主要タイプのMMS分割を利用し、すべてのタイプに対して公正性の保証を改善するように適応する。