Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913342867636224 |
|---|---|
| author | Bai, Yushi Gölz, Paul |
| author_facet | Bai, Yushi Gölz, Paul |
| contents | We study the problem of allocating $m$ indivisible items to $n$ agents with additive utilities. It is desirable for the allocation to be both fair and efficient, which we formalize through the notions of envy-freeness and Pareto-optimality. While envy-free and Pareto-optimal allocations may not exist for arbitrary utility profiles, previous work has shown that such allocations exist with high probability assuming that all agents' values for all items are independently drawn from a common distribution. In this paper, we consider a generalization of this model where each agent's utilities are drawn independently from a distribution specific to the agent. We show that envy-free and Pareto-optimal allocations are likely to exist in this asymmetric model when $m=Ω\left(n\log n\right)$, which is tight up to a log log gap that also remains open in the symmetric subsetting. Furthermore, these guarantees can be achieved by a polynomial-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_08971 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations Bai, Yushi Gölz, Paul Computer Science and Game Theory 91B32 We study the problem of allocating $m$ indivisible items to $n$ agents with additive utilities. It is desirable for the allocation to be both fair and efficient, which we formalize through the notions of envy-freeness and Pareto-optimality. While envy-free and Pareto-optimal allocations may not exist for arbitrary utility profiles, previous work has shown that such allocations exist with high probability assuming that all agents' values for all items are independently drawn from a common distribution. In this paper, we consider a generalization of this model where each agent's utilities are drawn independently from a distribution specific to the agent. We show that envy-free and Pareto-optimal allocations are likely to exist in this asymmetric model when $m=Ω\left(n\log n\right)$, which is tight up to a log log gap that also remains open in the symmetric subsetting. Furthermore, these guarantees can be achieved by a polynomial-time algorithm. |
| title | Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations |
| topic | Computer Science and Game Theory 91B32 |
| url | https://arxiv.org/abs/2109.08971 |