2025/12/11 by Jugal Garg, Garg, Jugal, Vishnu V. Narayan +2
Economics, Econometrics and Finance · Decision Sciences · #Game Theory and Voting Systems #Auction Theory and Applications #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2512.10892
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=Ω(nlogn) [Dickerson et al., 2014]. Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, this requirement improves to m=Ω(nlogn/loglogn), which is tight [Manurangsi and Suksompong, 2021]. However, these results rely on non-strategyproof mechanisms, such as maximum-welfare 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=Ω(nlogn). 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, 2017]. 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.