Truthful mechanisms achieve fair chore division with constant guarantees
Truthful-in-Expectation MMS Allocations for Chores
Computer Science and Game TheoryData Structures and Algorithms
Summary
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.
What this means in practice
- •For task management software developers: Implement truthful chore division features ensuring fair workload distribution among users with provable fairness guarantees each time.
- •For distributed system designers: Design resource allocation protocols that prevent manipulation while ensuring fairness in workload balancing across agents.
Authors
Zehan Lin, Biaoshuai Tao, Xiaowei Wu, Yuhao Zhang
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.