Guaranteed size ratio of ordinally efficient and envy-free mechanisms in the assignment problem

• 成果类型: Article
• 署名作者: Huang, Chao; Tian, Guoqiang
• 署名单位: Nanjing Audit University; Texas A&M University System; Texas A&M University College Station; Shanghai University of Finance & Economics
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2017.07.001
• 发表日期: 2017
• 页码: 1-8
• 关键词: Size of assignment; ordinal efficiency; Envy-freeness

摘要

In the assignment problem where agents can stay unassigned, the size of the assignment is an important consideration for designers. Bogomolnaia and Moulin (2015) show that there is a tension between size and fairness: the guaranteed size ratio of any envy-free mechanism is at most r(m), which converges decreasingly to 1 - 1/e approximate to 63.2% as the maximum size increases. They then ask whether r(m) is also the guaranteed size ratio for any ordinally efficient and envy-free mechanism. We study this issue and show that the lower bound of the guaranteed size ratio of ordinally efficient and envy-free mechanisms converges to 1/2 as the maximum size increases, which means that almost half of the maximum size is wasted at the lower bound. Moreover, the exact lower bound is m+1/2m when the maximum size m is odd. 2017 Elsevier Inc. All rights reserved.