Improved Weighted Maximin Share Guarantees for Indivisible Chores

Abstract

We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share (\MMS) context. While constant-\MMS\ allocations 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 proved that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee. We prove the existence of a $\frac{54}{5}$-$\WMMS$ assignment using a combinatorial layered moving-knife algorithm.\footnote{For concurrent and independent work by Li, Wang, and Xing~\cite{li2025constant}, see the \hyperref[remark:parallel-work]{remark on parallel work} in the introduction.} For every fixed $\epsilon >0$, this yields a $(\frac{54}{5}+\epsilon )$-$\WMMS$ assignment in polynomial time. Using a faster estimate of the weighted maximin shares instead gives a $\frac{108}{5}\cdot (1+\epsilon )$-$\WMMS$ assignment in almost linear time. We also develop a chore-oblivious analysis that guarantees\linebreak $\WMMS$ approximation factors of approximately $2.06447$, $2.475855$, and $2.732051$ for three, four, and five agents, respectively.