Fair Division is Hard even for Amicable Agents?

Abstract

We consider the problem of distributing a collection of indivisible objects among agents in a manner that satis es some desirable notions of fairness and e ciency. We allow agents to \share" goods in order to achieve e ciency and fairness goals which may be otherwise impossible to attain. In this context, our goal is to nd allocations that minimize the \amount of sharing". We follow up on recent work demonstrating that nding fair allocations with minimum sharing is tractable when valuations are non-degenerate, a notion which captures scenarios that are \far from identical". This result holds for any xed number of agents. We show that the usefulness of non-degeneracy does not scale to the setting of many agents. In particular, we demonstrate that the problem of nding fractionally Pareto optimal and envy-free allocations is NP-complete even for instances with constant degeneracy and no sharing. We also demonstrate an alterate approach to enumerating distinct consumption graphs for allocations with a small number of sharings.

Keywords

• Fair Division
• Indivisible Items
• NP-completeness

-

The task of fairly distributing indivisible goods among interested agents is challenging already for the simplest possible scenario: one object valued by two or more people. We deal with the case when m objects are to be allocated amongst n agents, respecting certain notions of fairness and e ciency. Every agent attributes a value to each object, stating the extent to which he wants the object. A natural and well-studied notion of fairness is envy-freeness, where everyone values their bundle of objects at least as much as they value others'. Some notion of e ciency are: completeness, which requires all items to be allocated and fractionally Pareto Optimal (fPO), where no agent can be made better o without making another worse o . The opening example already shows that there are instances where no allocation is simultaneously complete and envy-free(EF). This has led to several notions of \workarounds": approximate envy-freeness (e.g, requiring allocations to be envy-free up to the removal of one good [ 2,7 ], or any good [ 3 ], or using hidden goods [ 6 ]), subsidy (introducing money to compensate for envy [ 1 ]), donating items (this involves giving up on completeness, but to a limited extent [ 4 ]), and sharing (wherein we allow for some goods to be shared between agents [ 9,8 ]). Our focus is on the settings, where sharing goods appears to be the most reasonable of all workarounds (for instance, when high valued goods are involved), and the question of interest is to nd allocations that meet our goals of fairness and e ciency with minimum sharing.

In a recent development, Sandomirskiy and Segal-Halevi [ 8 ] show that the case of identical valuation is in fact the \hardest" | they propose a notion of degeneracy(d) which captures the degree of similarity across agent valuations. We refer to the setting of low degeneracy, the ones where valuations are generally dissimilar, hence, less con icting, as a scenario involving amicable agents. One of the key results in [ 8 ] is that nding allocations that are both fPO and EF is tractable for a constant number of amicable agents. In contrast, it was shown that the problem remains NP-hard for instances of high degeneracy. Our Contributions. We investigate the complexity of nding fPO and EF allocations for amicable agents, from the perspective of the number of agents. For example, can the running time be improved to (n + m)O(d), which would increase the realm of tractability to scenarios with any number of agents and constant degeneracy, or more ambitiously, O(2O(d) (m + n)O(1)), which would make the problem tractable for instances with any number of agents and degeneracy logarithmic in (n + m)? Our main contribution here is to show that even the former goal is unlikely to be achievable: when the number of agents is unbounded, the problem of nding allocations that are fPO and EF remains strongly NP-complete for instances with degeneracy one, even for the speci c question of allocations with no sharings. Our result also has consequences for the problem of nding EF allocations, which is weakly NP-complete by a reduction from Partition [ 8 ]. It turns out that the arguments in the reverse direction of our reduction do not require the allocation in question to be fPO, allowing us to obtain a stronger hardness result.

We also revisit the algorithm for nding fPO+EF allocations from [ 8 ]. The algorithm relies on enumerating certain consumption graphs corresponding to fPO allocations that x the sharing structure of a potential solution. We propose an alternate method for generating the relevant consumption graphs that takes advantage of the upper bound on the number of sharings upfront. This leads to a slightly di erent bound that leads to a better exponential term at the cost of a worse polynomial factor. Although the di erence in the bound is not signi cant, we believe our approach lends additional understanding to the structure of class of graphs based on fPO allocations.

Preliminaries

Allocations and Sharing. We use A = fa1, . . . , ang to denote a set of agents and G = fg1, . . . , gmg to denote a collection of objects. A bundle of objects is a vector b = (bj)j2[m] 2 [ 0, 1 ]m, where the component bj represents the portion of gj in the bundle. The total amount of each object is normalized to one. An allocation z is a collection of bundles (zi)i2[n], one for each agent, with the condition that all the objects are fully allocated. Note that an allocation can be identi ed with the matrix z := (zi,j)i2[n],j2[m], where zi,j take values from [ 0,1 ]. If zi,j 6= 1, then the object gj is shared between two or more agents. We de ne total number of sharings as the number of times that an object is shared, i.e: #s?(z) = X j2[m]

fi 2 [n] : zi,j > 0g - 1 .

The matrix v = (vi,j)i2[n],j2[m] is called the valuation matrix.

Value and Utility. For every i 2 [n], j 2 [m], vi,j denotes agent ai's value for the entire object gj. In the setting of additive utilities, the valuations naturally lead us to an utility function over bundles de ned as ui(b) = Pj2[m] vi,j bj. We recall the notion of degeneracy that was proposed in [ 9,8 ]. To this end, we say that two goods gp, gq are valued similarly by a pair of agents i, j if there exists a constant r such that vi,p vj,q = vi,q vj,p = r. If the valuations in question are all non-zero, then the value-ratios of goods gp and gq by the agents i and j equals the constant r. Now, we de ne the similarity between a pair of agents i and j as: sv(i, j) = max r>0 k 2 [m] : vi,k = r vj,k - 1.

Note that the similarity of a pair of agents captures the notion of the largest number of goods that the agents value similarly when considered pairwise. This nally leads us to the notion of degeneracy de ned as d(v) = maxi,j2[n],i6=j sv(i, j). Valuations for which d(v) = 0 are called non-degenerate. Also, note that if any two agents have the same valuations for all goods, then d(v) = m - 1. Fairness and E ciency. An allocation z = (zi)i2[n] is called envy-free (EF) if every agent prefers her bundle to the bundles of others. Formally, for all i, j 2 [n]: ui(zi) > ui(zj). An allocation z is Pareto-dominated by an allocation y if y gives at least the same utility to all agents and strictly more to at least one. An allocation z is fractionally Pareto-optimal (fPO) if no feasible y dominates it. Computational Questions. For the fairness concept EF and an e ciency concept fPO, Minimal Sharing problem is the following. Given (A, G, v, t 2 N) as input, the question is if there exists an allocation where the total number of sharings is at most t.

Hardness for Instances of Constant Degeneracy

We de ne here, a structured version of Satisfiability problem called Linear Near-Exact Satisfiability (LNES), which is known to be NP-complete [ 5 ]. An LNES instance consists of 4p core clauses (p 2 N) and p auxiliary clauses: C = fU1, V1, U01, V10, , Up, Vp, U0p, Vp0g [ fC1, , Cpg. The set of variables consists of p main variables x1, . . . , xp and 4p shadow variables y1, . . . , y4p. Each core clause consists of two literals and 8 i 2 [p], Ui \Vi = fxig and U0i \Vi0 = fxig. Each shadow variable occurs as a positive literal in an auxiliary clause and as a negative literal in a core clause. An auxiliary clause consists of four literals, each corresponding to a positive occurrence of a shadow variable. We will use ui, vi, u0i, and v0i to refer to the shadow variables in the core clauses Ui, Vi, U0 , i and V0, respectively. The LNES problem asks whether, given a set of such i clauses, there exists an assignment of truth values to the variables such that exactly one literal in every core clause and exactly two literals in every auxiliary clause evaluate to true under . The main result of this section is the following: Theorem 1. (EF,fPO)-Minimal Sharing is NP-hard even when restricted to inputs with bounded valuations, degeneracy one, and no sharing. Proof. (Sketch) We reduce from LNES. Let C be an instance of LNES as described above. For each main variable xi we introduce three agents: fai, ai, dig, and the goods fgi, gi, hig. We refer to di as the dummy agent and ai and ai as the key agents associated with xi. Also, we refer to hi as the trigger good and gi and gi as consolation goods. For the shadow variables ui, vi, u0i, v0i, we introduce fnoaullrys,hfaodroewacahgeanutxsialigaernytsc:labuis,eciC,bj,0i,wc0ie ainntdrofoduurceestswenotibaalcgkouopdgs:oroid,ssif,j1r0ia,ns0id. Ffj2i-. Note that our instance consists of 7p agents and 9p goods. Thus the size of the valuation matrix is N := 63 p2. We let L = 4000 p5.

Let w = (wi,j)i2[n],j2[m] denote the (7p 9p) matrix whose entries are given by wi,j = (i - 1) m + j. Intuitively, we can think of these values as being small enough to be negligible, and we will obtain our nal valuation matrix by starting from w and \overwriting" some entries to re ect the fact that certain goods are valued highly by certain agents. This is done to ensure that the nal valuation matrix has low degeneracy, and hence, the agents are amicable. We modify the matrix w as described below. For i 2 [p]: { The dummy agent di has a high value L for the consolation goods gi and gi. Also, they value the four essential goods associated with them at zero. { The rst key agent ai has a somewhat high value L3 for the consolation good gi and the essential goods ri and si, and a high value L for hi. { The second key agent ai has a somewhat high value L3 for the consolation good gi and the essential goods r0i and s0i, and also has a high value L for the trigger good hi. { The shadow agents have a high value L for their associated essential goods and the backup good which represents an auxiliary clause that contains the associated shadow variable. Also, bi (respectively, ci) values the consolation good gi and the essential good si (respectively, ri) at zero. And b0 i (respectively, c0i) values the consolation good gi and the essential good s0i (respectively, r0i) at zero.

The valuation matrix is depicted in the Figure 1. We ask if this instance admits an allocation with zero sharing. Note that the degeneracy of the valuation matrix is indeed one, contributed by the values that shadow agents have for the backup goods. We claim that if there exist an assignment for the LNES instance, then we have an EF and fPO allocation for the above fair division instance, and viceversa. We defer to the detailed arguments in the full version of the paper. tu 4

Concluding Remarks

We demonstrated the hardness of nding fPO+EF allocations even for instances with constant degeneracy, with an unbounded number of agents. We note that running times of the form dO(n) poly(m, n) are \weakly ruled out" because of the hardness result in [ 8 ]. However, all the hardness results combined so far do not rule out the possibility of an algorithm with a running time of cO(d+n) mO(1), which would imply strongly polynomial running times for instances where (d+n) is bounded by O(log m). One framework to rule out such a possibility would be parameterized complexity, where one might attempt demonstrating W-hardness in the combined parameter (n, d). On a related note, we show that instances that have bounded degeneracy and a bounded number of values in the valuation matrix are essentially bounded | we refer the reader to the full version of the paper for a more detailed discussion on bounded valuations as well as remarks on enumerating the consumption graphs.

References

1. Brustle , J. , Dippel , J. , Narayan , V.V. , Suzuki , M. , Vetta , A. : One dollar each eliminates envy . In: Proceedings of the 2020 ACM Conference on Economics and Computation ( 2019 )

2. Budish , E. : The combinatorial assignment problem: approximate competitive equilibrium from equal incomes . In: Proceedings of the Behavioral and Quantitative Game Theory BQGT . p. 74 : 1 . ACM ( 2010 )

3. Caragiannis , I. , Kurokawa , D. , Moulin , H. , Procaccia , A.D. , Shah , N. , Wang , J.: The unreasonable fairness of maximum nash welfare . ACM Trans. Economics and Comput . 7 ( 3 ), 12 :1{ 12 : 32 ( 2019 )

4. Chaudhury , B.R. , Kavitha , T. , Mehlhorn , K. , Sgouritsa , A. : A little charity guarantees almost envy-freeness . In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms , SODA 2020 . pp. 2658 { 2672 . SIAM ( 2020 )

5. Dayal , P. , Misra , N.: Deleting to structured trees . In: International Computing and Combinatorics Conference . pp. 128 { 139 . Springer ( 2019 )

6. Hosseini , H. , Sikdar , S. , Vaish , R. , Wang , J. , Xia , L. : Fair division through information withholding . In: Proceedings of the Thirty-Fourth AAAI Conference on Arti cial Intelligence (AAAI) ( 2020 )

7. Lipton , R.J. , Markakis , E. , Mossel , E. , Saberi , A. : On approximately fair allocations of indivisible goods . In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC) . pp. 125 { 131 . ACM ( 2004 )

8. Sandomirskiy , F. , Segal-Halevi , E. : Fair division with minimal sharing . CoRR abs/ 1908 .01669 ( 2019 ), http://arxiv.org/abs/ 1908 .01669

9. Segal-Halevi , E. : Fair division with bounded sharing . CoRR abs/ 1912 .00459 ( 2019 ), http://arxiv.org/abs/ 1912 .00459