On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
We study the problem of allocating a set of indivisible goods to a set of agents having additive preferences. We introduce two new important complexity results concerning efficiency and fairness in resource allocation problems: we prove that the problem o
- PDF / 272,263 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 88 Downloads / 179 Views
Abstract. We study the problem of allocating a set of indivisible goods to a set of agents having additive preferences. We introduce two new important complexity results concerning efficiency and fairness in resource allocation problems: we prove that the problem of deciding whether a given allocation is Pareto-optimal is coNP-complete, and that the problem of deciding whether there is a Pareto-efficient and envy-free allocation is Σ2p -complete.
1
Introduction
The problem of allocating a set of indivisible goods to a set of agents arises in a wide range of applications including, among others, auctions, divorce settlements, frequency allocation, airport traffic management, fair and efficient exploitation of Earth Observation Satellites [1]. In many such real-world problems, one needs to find efficient and fair solutions, where an efficient solution can be seen informally as ensuring the greatest possible satisfaction to the agents, and where fairness refers to the need for compromises between the agents’ (often antagonistic) objectives. In this paper, we study the resource allocation problem from the point of view of computational complexity. We restrict our setting to additive preferences. In other words, the preferences of each agent are represented by a set of weights w(o), standing for the utility (or satisfaction) she enjoys for each single object o. The utility of an agent for a subset of objects S is then given by the sum of the weights of all the objects o in S. Moreover, we restrict our study to two particular definitions of efficiency and fairness: Pareto-efficiency (or Pareto-optimality) and envy-freeness. Paretoefficient allocations are such that we cannot increase the satisfaction of an agent without strictly decreasing the satisfaction of another agent. An allocation is envy-free if and only if each agent likes her share at least as much as the share of any other agent. In this paper, we introduce two new complexity results concerning the resource allocation problem with additive preferences. Even if the setting seems F. Rossi and A. Tsoukis (Eds.): ADT 2009, LNAI 5783, pp. 98–110, 2009. c Springer-Verlag Berlin Heidelberg 2009
On the Complexity of Efficiency and Envy-Freeness in Fair Division
99
restrictive, we advocate that the particular problems we address are important enough to justify an extensive study for the following reasons. Firstly, one of the most natural ways of (compactly) modeling cardinal preferences over sets of objects (or more generally over combinatorial domains) is to suppose that they are additive. Notice that this goes far beyond resource allocation: matching problems, weighted path in a graph, valued constraints satisfaction problems, etc. Secondly, Pareto-efficiency is one the most prominent notion of efficiency used in collective decision making problems. Thirdly, envy-freeness is a key concept in the literature about resource allocation (see e.g. [2]), as it provides an elegant way of encoding the notion of fairness and does not require, contrary to Rawlsian egalitarianism, the interpersona
Data Loading...
