Papers for

workforce management software developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improving fairness limits in dividing difficult tasks by weight

Improving the Bounds on Approximating Weighted Maximin Share for Chores

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]$.

Sun 11 OctComputer Science and Game TheoryArtificial Intelligence
The gist
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.
Open → 2610.15520v1