Size versus fairness in the assignment problem

Anna Bogomolnaia and Herve Moulin

Games and Economic Behavior, 2015, vol. 90, issue C, 119-127

Abstract: When not all objects are acceptable to all agents, maximizing the number of objects actually assigned is an important design concern. We compute the guaranteed size ratio of the Probabilistic Serial mechanism, i.e., the worst ratio of the actual expected size to the maximal feasible size. It converges decreasingly to 1−1e≃63.2% as the maximal size increases. It is the best ratio of any Envy-Free assignment mechanism.

Keywords: Envy-freeness; Random assignment; Probabilistic serial (search for similar items in EconPapers)
JEL-codes: D63 D70 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825615000251
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:gamebe:v:90:y:2015:i:c:p:119-127

DOI: 10.1016/j.geb.2014.11.006

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().