Asymptotic existence of fair divisions for groups

DOI10.1016/J.MATHSOCSCI.2017.05.006zbMATH Open1415.91182DBLPjournals/mss/ManurangsiS17arXiv1706.08219OpenAlexW2730072800WikidataQ56388119 ScholiaQ56388119MaRDI QIDQ1680744FDOQ1680744

Warut Suksompong, Pasin Manurangsi

Publication date: 16 November 2017

Published in: Mathematical Social Sciences (Search for Journal in Brave)

Abstract: The problem of dividing resources fairly occurs in many practical situations and is therefore an important topic of study in economics. In this paper, we investigate envy-free divisions in the setting where there are multiple players in each interested party. While all players in a party share the same set of resources, each player has her own preferences. Under additive valuations drawn randomly from probability distributions, we show that when all groups contain an equal number of players, a welfare-maximizing allocation is likely to be envy-free if the number of items exceeds the total number of players by a logarithmic factor. On the other hand, an envy-free allocation is unlikely to exist if the number of items is less than the total number of players. In addition, we show that a simple truthful mechanism, namely the random assignment mechanism, yields an allocation that satisfies the weaker notion of approximate envy-freeness with high probability.

Full work available at URL: https://arxiv.org/abs/1706.08219

Recommendations

• Closing gaps in asymptotic fair division
• When do envy-free allocations exist?
• Asymptotic existence of proportionally fair allocations
• Almost envy-freeness in group resource allocation
• Almost envy-freeness with general valuations

zbMATH Keywords

envy-free divisionsfair divisions for groupsmultiple players

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Asymptotic existence of proportionally fair allocations
• Approximation Algorithms for Computing Maximin Share Allocations
• Noise stability of functions with low influences: invariance and optimality
• How to Cut A Cake Fairly
• Bidding for envy-freeness: a procedural approach to \(n\)-player fair-division problems
• How to Cut a Cake Fairly
• The undercut procedure: an algorithm for the envy-free division of indivisible items
• Two-person fair division of indivisible items: an efficient envy-free algorithm
• Approximate maximin shares for groups of agents

Cited In (14)

• Fair cake-cutting among families
• Closing Gaps in Asymptotic Fair Division
• Fairness for multi-self agents
• Efficient Fair Division with Minimal Sharing
• Consensus Halving for Sets of Items
• Fair division with allocator's preference
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• Almost envy-freeness in group resource allocation
• Democratic fair allocation of indivisible goods
• Fairly allocating contiguous blocks of indivisible items
• When Do Envy-Free Allocations Exist?
• Approximate maximin shares for groups of agents
• Maximum Nash welfare and other stories about EFX
• Computing a small agreeable set of indivisible items

This page was built for publication: Asymptotic existence of fair divisions for groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680744)