Asymptotic existence of fair divisions for groups

Pasin Manurangsi and Warut Suksompong

Mathematical Social Sciences, 2017, vol. 89, issue C, 100-108

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.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489616301895
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:89:y:2017:i:c:p:100-108

DOI: 10.1016/j.mathsocsci.2017.05.006

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().