期刊
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
卷 32, 期 6, 页码 741-778出版社
SPRINGER
DOI: 10.1007/s10458-018-9393-0
关键词
Computational social choice; Resource allocation; Fair division; Indivisible goods; Maximin share; Proportional share; Minimax share; Complexity; Approximation
资金
- DFG [RO 1202/14-2]
- Vietnam National Foundation for Science and Technology Development (NAFOSTED Project) [102.01-2015.33]
This paper is concerned with various types of allocation problems in fair division of indivisible goods, aiming at maximin share, proportional share, and minimax share allocations. However, such allocations do not always exist, not even in very simple settings with two or three agents. A natural question is to ask, given a problem instance, what is the largest value c for which there is an allocation such that every agent has utility of at least c times her fair share. We first prove that the decision problem of checking if there exists a minimax share allocation for a given problem instance is -hard when the agents' utility functions are additive. We then show that, for each of the three fairness notions, one can approximate c by a polynomial-time approximation scheme, assuming that the number of agents is fixed. Next, we investigate the restricted cases when utility functions have values in only or are defined based on scoring vectors (Borda and lexicographic vectors), and we obtain several tractability results for these cases. Interestingly, we show that maximin share allocations can always be found efficiently with Borda utilities, which cannot be guaranteed for general additive utilities. In the nonadditive setting, we show that there exists a problem instance for which there is no c-maximin share allocation, for any constant c. We explore a class of symmetric submodular utilities for which there exists a tight We explore a class of symmetric submodular utilities for which there exists a tight 1/2-maximin share allocation, and show how it can be approximated to within a factor of 1/4.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据