Designing Truthful Mechanisms for Asymptotic Fair Division
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912758393470976 |
|---|---|
| author | Garg, Jugal Narayan, Vishnu V. Shen, Yuang Eric |
| author_facet | Garg, Jugal Narayan, Vishnu V. Shen, Yuang Eric |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10892 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Designing Truthful Mechanisms for Asymptotic Fair Division Garg, Jugal Narayan, Vishnu V. Shen, Yuang Eric Computer Science and Game Theory 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. |
| title | Designing Truthful Mechanisms for Asymptotic Fair Division |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2512.10892 |