Asymptotic existence of fair divisions for groups |
| |
| Institution: | 1. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, USA;2. Department of Computer Science, Stanford University, USA;1. Department of Economics, University of Oregon, Eugene, OR 97403-1285, USA;2. Department of Economics, Vanderbilt University, Nashville, TN 37235, USA;1. Department of Economics, University of Calgary, 2500 University Dr., Calgary, AB, T2N 1N4, Canada;2. Department of Economics, University of Warwick, United Kingdom;3. University of Illinois, 1407 W. Gregory Dr., Urbana, IL 61801, United States;1. Hungarian Academy of Sciences, Institute for Computer Science and Control (MTA-SZTAKI), Budapest, Hungary;2. Department of Computer Science and Egerváry Research Group (MTA-ELTE), Eötvös University, Pázmány Péter sétány 1/C, Budapest, Hungary;1. Department of Computer Science, University of Oxford, United Kingdom;2. Department of Computer Science, Ariel University, Israel;3. School of Computing, National University of Singapore, Singapore;1. Department of Economics, Aomori Public University, 153-4, Yamazaki, Goshizawa, Aomori 030-0196, Japan;2. Department of Economics, Ryutsu Keizai University, 120, Ryugasaki, Ibaraki 301-8555, Japan;3. Faculty of Economics, Keio University, 2-15-45, Mita, Minato-ku, Tokyo 108-8345, Japan;4. School of Political Science and Economics, Waseda University, 1-6-1, Nishi-Waseda, Shinjuku-ku, Tokyo 169-8050, Japan |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
