Improving fairness limits in dividing difficult tasks by weight
Improving the Bounds on Approximating Weighted Maximin Share for Chores
Computer Science and Game TheoryArtificial Intelligence
Summary
The paper looks at how to fairly divide difficult or undesirable tasks (called chores) among people who have different levels of responsibility or importance (weights). The fairness measure used is called weighted maximin share (WMMS), and the authors show every scenario can be fairly divided within about four times this measure. They also provide an efficient method to find such a division when the problem details are given in binary numbers. Additionally, they prove that this fairness factor cannot be improved beyond a certain natural limit related to the number e, tightening previous known boundaries.
What this means in practice
- •For resource allocation teams: Use the improved approximation bound and polynomial-time algorithm to fairly distribute undesirable tasks when individuals have different importance levels.
- •For workforce management software developers: Incorporate the algorithm to assign chores fairly based on weighted responsibilities in scheduling and task management tools.
Authors
Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
Abstract
We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.