Size versus fairness in the assignment problem

• 成果类型: Article
• 署名作者: Bogomolnaia, Anna; Moulin, Herve
• 署名单位: University of Glasgow
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.11.006
• 发表日期: 2015
• 页码: 119-127
• 关键词: Envy-freeness; random assignment; probabilistic serial

摘要

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 - 1/e similar or equal to 63.2% as the maximal size increases. It is the best ratio of any Envy-Free assignment mechanism. (C) 2015 Elsevier Inc. All rights reserved.