Designing Truthful Mechanisms for Asymptotic Fair Division

We study the problem of fairly allocating a set of m goods among n agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint distribution. Prior works have shown that if this distribution is well-behaved, then an envy-free allocation exists with high probability when m = Ω(n log n) (Dickerson et al. [13]). Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, this requirement improves to m = Ω(n log n/ log log n), which is tight (Manurangsi and Suksompong [23]). However, these results rely on non-strategyproof mechanisms, such as maximumwelfare allocation or the round-robin algorithm, limiting their applicability in settings with strategic agents. In this work, we extend the theory to a broader, more realistic class of joint value distributions, allowing for correlations among agents, atomicity, and unequal probabilities of having the highest value for an item. We show that envy-free allocations continue to exist with a high probability when m = Ω(n log n). More importantly, we give a new randomized mechanism that is truthful in expectation, efficiently implementable in polynomial time, and outputs envy-free allocations with high probability, answering an open question posed by Manurangsi and Suksompong [21] . We further extend our mechanism to settings with asymptotic weighted fair division and multiple agent types and good types, proving new results in each case.