Papers for

task 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.

Truthful mechanisms achieve fair chore division with constant guarantees

Truthful-in-Expectation MMS Allocations for Chores

Abstract: We study truthful-in-expectation (TIE) mechanisms for allocating indivisible chores alongside ex-post maximin share (MMS) guarantees. For goods, Bu and Tao (FOCS 2025) established a (1/n)-approximation for TIE mechanisms, and this was substantially improved by Babaioff, Feige, and Manaker Morag (FOCS 2026), who established an Ω(1/\log n) approximation, where n is the number of agents. The corresponding problem for chores has received less attention. The best-known result is due to Aziz, Li, and Wu (MAPR 2024), who gave a TIE mechanism with an O(\sqrt{\log n}) MMS approximation guarantee that holds only in expectation. They also established a 6/5 lower bound for TIE mechanisms for two agents. In this paper, we present the first TIE mechanism for chores that achieves a constant ex-post MMS approximation guarantee. Specifically, our mechanism guarantees an ex-post ratio of 1.97 for any number of agents n, which improves to 4/3 for n=2 and 3/2 for n=3. On the hardness side, we tighten the two-agent lower bound to 4/3, showing that our mechanism is optimal for n=2. More generally, we establish a lower bound of 13/12 on the ex-post MMS approximation ratio achievable by TIE mechanisms for every n\ge 3.

Mon 28 SeptComputer Science and Game TheoryData Structures and Algorithms
The gist
When people need to divide chores fairly, it can be tricky to make sure everyone is honest about how burdensome tasks are. The authors study ways to split chores so that no one can benefit by lying, and yet everyone gets a share close to what they deserve based on a fairness measure called maximin share (MMS). They create a new method that guarantees fairness not just on average but every time, with a fixed fairness ratio no matter how many people are involved. They also prove this method is the best possible for two people and close to the best for more.
Open → 2609.35280v1