Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness

We study the problem of fairly and truthfully allocating 𝑚 indivisible items to 𝑛 agents with additive preferences. Specifically, we consider truthful mechanisms outputting allocations that satisfy EF +𝑢 -𝑣 , where, in an EF +𝑢 -𝑣 allocation, for any pair of agents 𝑖 and 𝑗, agent 𝑖 will not envy agent 𝑗 if 𝑢 items were added to 𝑖's bundle and 𝑣 items were removed from 𝑗'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 𝑢 and 𝑣, EF +𝑢 -𝑣 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 EF +0 -1 (i.e., the well-studied fairness notion EF1). For three agents, we present a truthful mechanism that achieves EF +1 -1 . For 𝑛 agents in general, we show that there exists a truthful mechanism that achieves EF +0 -𝑂 ( √ 𝑛) . On the negative side, when considering the stronger notion EF +𝑢 -𝑣 X, we show that it cannot be achieved by any randomized truthful mechanism for any 𝑢, 𝑣, and any fixed number of agents.

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 𝑝 or 𝑞 for some 𝑝 > 𝑞 ≥ 0). For tri-valued utilities (where agents' valuations on each item belong to 𝑝, 𝑞, 𝑟 for some 𝑝 > 𝑞 > 𝑟 ≥ 0) and any 𝑢, 𝑣, we show that truthfulness is incompatible with EF +𝑢 -𝑣 and Pareto-optimality even for two agents.