{"ID":2830390,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.10892","arxiv_id":"2512.10892","title":"Designing Truthful Mechanisms for Asymptotic Fair Division","abstract":"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., 2014]. 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, 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=Ω(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, 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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.10892","url_pdf":"https://arxiv.org/pdf/2512.10892v1","authors":"[\"Jugal Garg\",\"Vishnu V. Narayan\",\"Yuang Eric Shen\"]","published":"2025-12-11T18:22:27Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}