FOCS Conference 2025 Conference Paper
Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
- Xiaolin Bu
- Biaoshuai Tao
We study the problem of fairly and truthfully allocating m indivisible items to n agents with additive preferences. Specifically, we consider truthful mechanisms outputting allocations that satisfy $\mathrm{EF}_{-v}^{+u}$, where, in an $\mathrm{EF}_{-v}^{+u}$ allocation, for any pair of agents i and j, agent i will not envy agent j if u items were added to i ‘s bundle and v items were removed from j ‘s bundle. Previous work easily indicates that, when restricted to deterministic mechanisms, truthfulness will lead to a poor guarantee of fairness: even with two agents, for any u and $v, \mathrm{EF}_{-v}^{+u}$ cannot be guaranteed by truthful mechanisms when the number of items is large enough. In this work, we focus on randomized mechanisms, where we consider ex-ante truthfulness and ex-post fairness. For two agents, we present a truthful mechanism that achieves $\mathrm{EF}_{-1}^{+0}$ (i. e. , the well-studied fairness notion EF1). For three agents, we present a truthful mechanism that achieves $\mathrm{EF}_{-1}^{+1}$. For n agents in general, we show that there exists a truthful mechanism that achieves $\mathrm{EF}_{-O(\sqrt{n})}^{+0}$. We further consider fair and truthful mechanisms that also satisfy the standard efficiency guarantee: Pareto-optimality. We provide a mechanism that simultaneously achieves truthfulness, EF1, and Pareto-optimality for bi-valued utilities (where agents’ valuation on each item is either p or q for some $p\gt q \geq 0$). For tri-valued utilities (where agents’ valuations on each item belong to $\{p, q, r\}$ for some $p\gt q\gt r \geq 0$) and any $u, v$, we show that truthfulness is incompatible with $\mathbf{E F}_{-v}^{+u}$ and Pareto-optimality even for two agents.