2025/04/29 by Pasin Manurangsi, Manurangsi, Pasin, Warut Suksompong +1 · 4 citations
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2504.20704
openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m ≥ 2n, and moreover, m must be at least n+Θ(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = ω(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.