Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals

概要

We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals

# 概要
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound…

# 原典
https://arxiv.org/abs/2611.04884

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。