Asymptotic Analysis of Weighted Fair Division

Manurangsi, Pasin; Suksompong, Warut; Yokoyama, Tomohiko

doi:10.24963/ijcai.2025/443

Asymptotic Analysis of Weighted Fair Division

Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3979-3987.

https://doi.org/10.24963/ijcai.2025/443

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division
Agent-based and Multi-agent Systems: MAS: Resource allocation

Abstract

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 = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 - \mu) for the transition from non-existence to existence, where \mu 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 = omega(sqrt{r}), where r denotes the ratio between the two weights.

Pasin Manurangsi, Warut Suksompong, and Tomohiko Yokoyama. 2025. Asymptotic Analysis of Weighted Fair Division. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3979–3987. https://doi.org/10.24963/ijcai.2025/443

@inproceedings{ijcai2025p443,
  title     = {Asymptotic Analysis of Weighted Fair Division},
  author    = {Manurangsi, Pasin and Suksompong, Warut and Yokoyama, Tomohiko},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3979--3987},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/443},
  url       = {https://doi.org/10.24963/ijcai.2025/443},
}

TY  - CPAPER
TI  - Asymptotic Analysis of Weighted Fair Division
AU  - Manurangsi, Pasin
AU  - Suksompong, Warut
AU  - Yokoyama, Tomohiko
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3979
EP  - 3987
DO  - 10.24963/ijcai.2025/443
UR  - https://doi.org/10.24963/ijcai.2025/443
ER  -