Fair Assignment of Indivisible Chores to Asymmetric Agents

We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (MMS) context. While constant-MMS allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an n-WMMS (weighted MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an O(log n)-WMMS assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-WMMS guarantee.footnoteWe prove the existence of a 20-WMMS assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.