arXiv preprint ·
Truthful-in-Expectation MMS Allocations for Chores
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
The Double-Edged Sword of Information: Revealed versus Hidden Lotteries in School Choice
Learning to Harvest Without Collapse in a Regenerative Commons: A Lagrangian Framework
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
Regularized policy gradient with learned mixtures of Gaussians for games with continuous actions
Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.