On fair division of a homogeneous good

• 成果类型: Article
• 署名作者: Feige, Uriel; Tennenholtz, Moshe
• 署名单位: Weizmann Institute of Science; Technion Israel Institute of Technology
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.02.009
• 发表日期: 2014
• 页码: 305-321
• 关键词: fairness; fair share; Bin packing; Random allocations

摘要

We consider the problem of dividing a homogeneous divisible good among n players. Each player holds a private non-negative utility function that depends only on the amount of the good that he receives. We define the fair share of a player P to be the average utility that a player could receive if all players had the same utility function as P. We present a randomized allocation mechanism in which every player has a dominant strategy for maximizing his expected utility. Every player that follows his dominant strategy is guaranteed to receive an expected utility of at least n/(2n - 1) of his fair share. This is best possible in the sense that there is a collection of utility functions with respect to which no allocation mechanism can guarantee a larger fraction of the fair share. In interesting special cases our allocation mechanism does offer a larger fraction of the fair share. (C) 2014 Published by Elsevier Inc.