Asymptotic Analysis of Weighted Fair Division
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912585232678912 |
|---|---|
| author | Manurangsi, Pasin Suksompong, Warut Yokoyama, Tomohiko |
| author_facet | Manurangsi, Pasin Suksompong, Warut Yokoyama, Tomohiko |
| contents | Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if $m$ items are divided among $n$ agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that $m = Ω(n\log n/\log\log n)$, generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of $m = n/(1-μ)$ for the transition from non-existence to existence, where $μ\in (0,1)$ denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if $m = ω(\sqrt{r})$, where $r$ denotes the ratio between the two weights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21728 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic Analysis of Weighted Fair Division Manurangsi, Pasin Suksompong, Warut Yokoyama, Tomohiko Computer Science and Game Theory Discrete Mathematics Probability Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if $m$ items are divided among $n$ agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that $m = Ω(n\log n/\log\log n)$, generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of $m = n/(1-μ)$ for the transition from non-existence to existence, where $μ\in (0,1)$ denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if $m = ω(\sqrt{r})$, where $r$ denotes the ratio between the two weights. |
| title | Asymptotic Analysis of Weighted Fair Division |
| topic | Computer Science and Game Theory Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2504.21728 |