Behavioural economists have shown that people are often averse to inequality and will make choices to avoid unequal outcomes. In this paper, we consider how to allocate indivisible goods fairly to agents with additive utilities, so as to minimize inequality. We consider how this interacts with axiomatic properties such as envy-freeness, Pareto efficiency and strategy-proofness. We also consider the computational complexity of computing allocations minimizing inequality. Unfortunately, this is computationally intractable in general so we consider several tractable mechanisms that minimize greedily the inequality. Finally, we run experiments to explore the performance of these mechanisms.
Endriss has formulated the task of reducing inequality as a combinatorial optimisation problem @cite_19 . In particular, he studied the problem of deciding if there exists an inequality reducing improvement such as a Pigou-Dalton or Lorenz transfer. The complexity of such decision problems depends on the language used to represent the (possibly non-additive) utilities. He also provided a modular mixed integer programming formulation that returns an allocation to minimize inequality measures such as the Gini and Hoover indices when utilities are specified with the XOR-language. Schneckenburger, Dorn and Endriss @cite_6 consider allocating indivisible goods to minimize inequality as measured by the Atkinson index. They demonstrated that a sequence of local deals would converge on a globally optimal allocation with the minimum Atkinson index possible, but that the number of agents and items involved in such deals could not be bounded. For the Gini index, they conjectured that such convergence would be very challenging if not impossible to achieve.
@cite_19 @cite_6
2949121341 2126307323 2620964349 1995275762
We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procacciafirst (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1- @math allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a @math - @math allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a @math - @math allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of ! to a @math factor in the additive setting. The main idea for our @math - @math allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time. Combinatorial allocation problems require allocating items to players in a way that maximizes the total utility. Two such problems received attention recently, and were addressed using the same linear programming (LP) relaxation. In the Maximum Submodular Welfare (SMW) problem, utility functions of players are submodular, and for this case Dobzinski and Schapira [SODA 2006] showed an approximation ratio of 1 - 1 e. In the Generalized Assignment Problem (GAP) utility functions are linear but players also have capacity constraints. GAP admits a (1 - 1 e)- approximation as well, as shown by Fleischer, Goemans, Mirrokni and Sviridenko [SODA 2006]. In both cases, the approximation ratio was in fact shown for a more general version of the problem, for which improving 1 - 1 e is NPhard. In this paper, we show how to improve the 1 - 1 e approximation ratio, both for SMW and for GAP. A common theme in both improvements is the use of a new and optimal Fair Contention Resolution technique. However, each of the improvements involves a different rounding procedure for the above mentioned LP. In addition, we prove APX-hardness results for SMW (such results were known for GAP). An important feature of our hardness results is that they apply even in very restricted settings, e.g. when every player has nonzero utility only for a constant number of items. We analyse the problem of finding an allocation of resources in a multiagent system that is as fair as possible in terms of minimising inequality between the utility levels enjoyed by the individual agents. We use the well-known Atkinson index to measure inequality and we focus on the distributed approach to multiagent resource allocation, where new allocations emerge as the result of a sequence of local deals between groups of agents agreeing on an exchange of some of the items in their possession. Our results show that it is possible to design systems that provide theoretical guarantees for optimal outcomes that minimise inequality, but also that in practice there are significant computational hurdles to be overcome: finding an optimal allocation is computationally intractable---independently of the approach chosen---and large numbers of potentially highly complex deals may be required under the distributed approach. From a methodological point of view, while much work in multiagent resource allocation relies on combinatorial arguments, here we use insights from basic calculus. We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least half that of the value of the fractional solution. This approximation ratio of 1 2 improves over an Ω(1 log m) ratio of Dobzinski, Nisan and Schapira [STOC 2005]. We also show an approximation ratio of 1 - 1 e when utility functions are fractionally subadditive. A result similar to this last result was previously obtained by Dobzinski and Schapira [Soda 2006], but via a different rounding technique that requires the use of a so called "XOS oracle".The randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players. This allows us to suggest new incentive compatible mechanisms for combinatorial auctions, extending previous work of Lavi and Swamy [FOCS 2005].