An official website of the United States government
We study fair allocation of indivisible goods and chores among agents with lexicographic preferences---a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying envy-freeness up to any item (EFX) could fail to exist for a mixture of objective goods and chores. To our knowledge, this negative result provides the first counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to maximin share (MMS), we show positive existence and computation for any mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-à-vis their goods-only counterparts.
more »
« less
EF2X Exists for Four Agents
We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy between any two agents. The central open problem in this literature, which has proven to be extremely challenging, is regarding the existence of an EFX allocation, i.e., an allocation such that any envy from some agent i toward another agent j would vanish if we were to remove any single good from the bundle allocated to j. Prior work has shown that when the agents’ valuations are additive, which has been the main focus of prior works, an EFX allocation is guaranteed to exist for all instances involving up to three agents. Subsequent work extended this guarantee to more general valuations, like nice-cancelable and MMS-feasible. However, the existence of EFX allocations for instances involving four agents remains open, evenfor additive valuations.We contribute to this literature by focusing on EF2X, a relaxation of EFX which requires that any envy toward some agent would vanish if any two of the goods allocated to that agent were to be removed. Our main result shows that EF2X allocations exist for any instance with four agents, even for the class of cancelable valuations, which is more general than additive. Our proof is constructive, proposing an algorithm that computes such an allocation in pseudo-polynomial time.Furthermore, for instances involving three agents we provide an algorithm that computes an EF2X allocation in polynomial time, in contrast to EFX for which the fastest known algorithm for three agents is only pseudo-polynomial.
more »
« less
- Award ID(s):
- 2047907
- PAR ID:
- 10666090
- Publisher / Repository:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Date Published:
- Journal Name:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Volume:
- 39
- Issue:
- 13
- ISSN:
- 2159-5399
- Page Range / eLocation ID:
- 13555 to 13563
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of distributing a set of indivisible goods among agents with additive valuations in afairmanner. The fairness notion under consideration is envy-freeness up toanygood (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.more » « less
-
We study fair division of indivisible chores among n agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to one/any item (EF1/EFX) and the standard notion of economic efficiency is Pareto optimality (PO). There is a noticeable gap between the results known for both EF1 and EFX in the goods and chores settings. The case of chores turns out to be much more challenging. We reduce this gap by providing slightly relaxed versions of the known results on goods for the chores setting. Interestingly, our algorithms run in polynomial time, unlike their analogous versions in the goods setting.We introduce the concept of k surplus in the chores setting which means that up to k more chores are allocated to the agents and each of them is a copy of an original chore. We present a polynomial-time algorithm which gives EF1 and PO allocations with n-1 surplus.We relax the notion of EFX slightly and define tEFX which requires that the envy from agent i to agent j is removed upon the transfer of any chore from the i's bundle to j's bundle. We give a polynomial-time algorithm that in the chores case for 3 agents returns an allocation which is either proportional or tEFX. Note that proportionality is a very strong criterion in the case of indivisible items, and hence both notions we guarantee are desirable.more » « less
-
We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that EFX allocation exists if we do not allocate at most (n-1) goods. Reducing the number of unallocated goods has emerged as a systematic way to tackle the main question. For example, follow-up works on three- and four-agents cases, respectively, allocated two more unallocated goods through an involved procedure. In this paper, we study the general case and achieve sublinear numbers of unallocated goods. Through a new approach, we show that for every [Formula: see text], there always exists a [Formula: see text]-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We define the notion of rainbow cycle number [Formula: see text] in directed graphs. For all [Formula: see text] is the largest k such that there exists a k-partite graph [Formula: see text], in which each part has at most d vertices (i.e., [Formula: see text] for all [Formula: see text]); for any two parts Viand Vj, each vertex in Vihas an incoming edge from some vertex in Vjand vice versa; and there exists no cycle in G that contains at most one vertex from each part. We show that any upper bound on [Formula: see text] directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on [Formula: see text], yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. Funding: J. Garg was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1942321]. R. Mehta was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1750436].more » « less
-
We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation and a non-constructive proof of the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudopolynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time.We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations.We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1609/aaai.v39i13.33480
