Asymptotic Analysis of Weighted Fair Division
Asymptotic Analysis of Weighted Fair Division
Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 3979-3987.
https://doi.org/10.24963/ijcai.2025/443
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.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Agent-based and Multi-agent Systems: MAS: Resource allocation
