Fairness and Rank-Weighted Utilitarianism in Resource Allocation
In multiagent resource allocation with indivisible goods, boolean fairness criteria and optimization of inequality-reducing collective utility functions (CUFs) are orthogonal approaches to fairness. We investigate the question of whether the proposed scal
- PDF / 328,042 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 43 Downloads / 200 Views
stract. In multiagent resource allocation with indivisible goods, boolean fairness criteria and optimization of inequality-reducing collective utility functions (CUFs) are orthogonal approaches to fairness. We investigate the question of whether the proposed scale of criteria by Bouveret and Lemaˆıtre [5] applies to nonadditive utility functions and find that only the more demanding part of the scale remains intact for kadditive utility functions. In addition, we show that the min-max fairshare allocation existence problem is NP-hard and that under strict preferences competitive equilibrium from equal incomes does not coincide with envy-freeness and Pareto-optimality. Then we study the approximability of rank-weighted utilitarianism problems. In the special case of rank dictator functions the approximation problem is closely related to the MaxMin-Fairness problem: Approximation and/or hardness results would immediately transfer to the MaxMin-Fairness problem. For general inequality-reducing rank-weighted utilitarianism we show (strong) NP-completeness. Experimentally, we answer the question of how often maximizers of rank-weighted utilitarianism satisfy the max-min fairshare criterion, the weakest fairness criterion according to Bouveret and Lemaˆıtre’s scale. For inequality-reducing weight vectors there is high compatibility. But even for weight vectors that do not imply inequalityreducing CUFs, the Hurwicz weight vectors, we find a high compatibility that decreases as the Hurwicz parameter decreases. Keywords: Fair division · Indivisible goods reduction · Computational complexity
1
·
Fairness
·
Inequality
Introduction
Resource allocation deals with the distribution of goods to agents. We study the case of indivisible goods and cardinal preferences. The quality of allocations can be judged in terms of, e.g., efficiency or fairness. Bouveret and Lemaˆıtre [5] proposed a scale (hierarchy) of criteria for fairness. Starting with the weakest, the max-min fair-share criterion, to the strongest, competitive equilibrium from equal incomes, each criterion becomes more demanding towards an allocation. The approach of optimizing social welfare (see, e.g., the work of Nguyen et al. [19,20]) is orthogonal to the idea of applying fairness criteria, especially c Springer International Publishing Switzerland 2015 T. Walsh (Ed.): ADT 2015, LNAI 9346, pp. 521–536, 2015. DOI: 10.1007/978-3-319-23114-3 31
522
T. Heinen et al.
rank-weighted utilitarianism (see, e.g., the book by Moulin [18] and the book chapter by d’Aspremont and Gevers [11]). A collective utility function maps allocations to numerical values. A rank-weighted utilitarian collective utility function is a weighted utilitarian collective utility function, where the weight depends on the sorted rank of utilities. If the weight decreases for agents with more utility, we have an inequality-reducing collective utility function (e.g., [12,16]). Thus maximizers of rank-weighted utilitarianism can also be considered fair allocations. Rank-weighted utilitarianism is also
Data Loading...
