# fair_division_through_information_withholding__c656f13e.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

Fair Division Through Information Withholding

Hadi Hosseini,1 Sujoy Sikdar,2 Rohit Vaish,3 Hejun Wang,3 Lirong Xia3

1Rochester Institute of Technology, 2Washington University St. Louis, 3Rensselaer Polytechnic Institute hho@cs.rit.edu, sujoy@wustl.edu, {vaishr2, wangj38}@rpi.edu, xial@cs.rpi.edu

Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and deﬁne a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envyfreeness can be achieved by withholding only a small number of goods overall. We show that ﬁnding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and realworld preference data show that existing algorithms for ﬁnding EF1 allocations withhold a close-to-optimal amount of information.

1 Introduction

When dividing discrete objects, one often strives for a fairness notion called envy-freeness (Foley 1967), under which no agent prefers the allocation of another agent to its own. Such outcomes might not exist in general (even with only two agents and a single indivisible good), motivating the need for approximations. Among the many approximations of envy-freeness proposed in the literature (Lipton et al. 2004; Budish 2011; Nguyen and Rothe 2014; Caragiannis et al. 2016), the one that has found impressive practical appeal is envy-freeness up to one good (EF1). In an EF1 allocation, agent a can envy agent b as long as there is some good in b s bundle whose removal makes the envy go away. It is known that an EF1 allocation always exists and can be computed in polynomial time (Markakis 2017). On closer scrutiny, however, we ﬁnd that EF1 is not as strong as one might think: In the worst case, an EF1 allocation could entail the (hypothetical) removal of every good, because the elimination of each agent s envy may require the removal of a different good. To see this, consider an in-

Copyright c 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

stance with six goods g1, . . . , g6 and three agents a1, a2, a3 whose (additive) valuations are as follows:

g1 g2 g3 g4 g5 g6 a1 1 1 4 1 1 4 a2 1 4 1 1 4 1 a3 4 1 1 4 1 1

Observe that the allocation shown via circled goods is EF1, since any pairwise envy can be addressed by removing an underlined good. However, each pair of agents requires the removal of a different good (e.g., a1 s envy towards a2 is addressed by removing g3 whereas a3 s envy towards a2 is addressed by removing g4, and so on), resulting in a weak approximation overall (since all goods need to be removed over all pairs of agents). The above example shows that EF1, on its own, is too coarse to distinguish between allocations that remove a large number of goods (such as the one with circled entries) and those that remove only a few (such as the one with underlined entries, which, in fact, is envy-free). This limitation highlights the need for a fairness notion that (a) can distinguish between allocations in terms of their aggregate approximation, and (b) retains the up to one good style approximation of EF1 that has proven to be practically useful (Goldman and Procaccia 2014). Our work aims to ﬁll this important gap. We propose a new fairness notion called envy-freeness up to k hidden goods (HEF-k), deﬁned as follows: Say there are n agents, m goods, and an allocation A = (A1, . . . , An). Suppose there is a set S of k goods (called the hidden set) such that each agent i withholds the goods in Ai S (i.e., the hidden goods owned by i) and only discloses the goods in Ai \ S to the other agents. Any other agent h = i only observes the goods disclosed by i (i.e., those in Ai \ S), and its valuation for i s bundle is therefore vh(Ai \ S) instead of vh(Ai). Additionally, agent h s valuation for its own bundle is vh(Ah) (and not vh(Ah \ S)) because it can observe its own hidden goods. If, under the disclosed allocation, no agent prefers the bundle of any other agent (i.e., if vh(Ah) vh(Ai \ S) for every pair of agents i, h), then we say that A is envy-free up to k hidden goods (HEF-k). In

other words, by withholding the information about S, allocation A can be made free of envy. Notice how HEF-k addresses the previous concerns: Like EF1, HEF-k is a relaxation of envy-freeness that is deﬁned in terms of the number of goods. However, unlike EF1, HEFk offers a precise quantiﬁcation of the extent of information that must be withheld in order to achieve envy-freeness. Clearly, any allocation can be made envy-free by hiding all the goods (i.e., if k = m). The real strength of HEF-k lies in k being small; indeed, an HEF-0 allocation is envy-free. As we will demonstrate below, there are natural settings that admit HEF-k allocations with a small k (i.e., hide only a small number of goods) even when (exact) envy-freeness is unlikely.

Information Withholding is Meaningful in Practice. To understand the usefulness of HEF-k, we generated a synthetic dataset where we varied the number of agents n from 5 to 10, and the number of goods m from 5 to 20 (we ignore the cases where m < n). For every ﬁxed n and m, we generated 100 instances with binary valuations. Speciﬁcally, for every agent i and every good j, the valuation vi,j is drawn i.i.d. from Bernoulli(0.7). Figure 1a shows the heatmap of the number of instances out of 100 that do not admit envyfree outcomes. Figure 1b shows the heatmap of the number of goods that must be hidden in the worst-case. That is, the color of each cell denotes the smallest k such that each of the corresponding 100 instances admits some HEF-k allocation.

(a) Heatmap of the fraction of instances that are not envy-free.

(b) Heatmap of the number of goods that must be hidden.

Figure 1: In both ﬁgures, each cell corresponds to 100 instances with binary valuations for a ﬁxed number of goods m (on X-axis) and a ﬁxed number of agents n (on Y-axis).

It is evident from Figure 1 that even in the regime where envy-free outcomes are unlikely (in particular, the redcolored cells in Figure 1a), there exist HEF-k allocations with k 3 (the light blue-colored cells in Figure 1b). This observation, along with the foregoing discussion, shows that fairness through information withholding is a wellmotivated approach towards approximate envy-freeness that yields promising existence results in practice.

Our Contributions We make contributions on three fronts. On the conceptual side, we propose a novel fairness notion called HEF-k as a ﬁne-grained generalization of envyfreeness in terms of aggregate approximation. Our theoretical results (Section 4) show that computing HEF-k allocations is computationally hard even for highly restricted classes of valuations (Theorem 1 and Corollary 1). We show a similar result when HEF-k is coupled with

Pareto optimality (Theorem 2). We also provide an alternative proof of NP-completeness of determining the existence of an envy-free allocation for binary valuations (Proposition 3).

Our experiments show that HEF-k allocations with a small k often exist, even when envy-free allocations do not (Figure 1). We also compare several known algorithms for computing EF1 allocations on synthetic and real-world preference data, and ﬁnd that the round-robin algorithm and a recent algorithm of Barman, Krishnamurthy, and Vaish (2018) withhold close-to-optimal amount of information, often hiding no more than three goods (Section 5).

2 Related Work An emerging line of work in the fair division literature considers relaxations of envy-freeness by limiting the information available to the agents. Notably, Aziz et al. (2018) consider a setting where each agent is aware only of its own bundle and has no knowledge about the allocations of the other agents. They propose the notion of epistemic envy-freeness (EEF) under which each agent believes that an envy-free allocation of the remaining goods among the other agents is possible. Note that in EEF, each agent might consider a different hypothetical assignment of the remaining goods, and each of these could be signiﬁcantly different from the actual underlying allocation. By contrast, under HEF-k, each agent evaluates its valuation with respect to the same (underlying) allocation. Chen and Shah (2017) study a related model where agents have probabilistic beliefs about the allocations of the other agents, and envy is deﬁned in expectation. Chan et al. (2019) study a setting similar to Aziz et al. (2018) wherein each agent is unaware of the allocations of the other agents, with the guarantee that it does not get the worst bundle. Another related line of work considers settings where the agents constitute a social network and can only observe the allocations of their neighbors (Abebe, Kleinberg, and Parkes 2017; Bei, Qiao, and Zhang 2017; Chevaleyre, Endriss, and Maudet 2017; Aziz et al. 2018; Beynier et al. 2018; Bredereck, Kaczmarczyk, and Niedermeier 2018). These works place an informational constraint on the set of agents, whereas our model restricts the set of revealed goods per agent. Several other forms of fairness approximations have been proposed recently, such as by introducing side payments (Halpern and Shah 2019), permitting sharing of some goods (Sandomirskiy and Segal-Halevi 2019), or donating a small fraction of goods (Caragiannis, Gravin, and Huang 2019).

3 Preliminaries Problem instance An instance I = [n], [m], V of the fair division problem is deﬁned by a set of n N agents [n] = {1, 2, . . . , n}, a set of m N goods [m] = {1, 2, . . . , m}, and a valuation proﬁle V = {v1, v2, . . . , vn} that speciﬁes the preferences of every agent i [n] over each subset of the goods in [m] via a valuation function vi : 2[m] N {0}. Notice that each agent s valuation

for any subset of goods is assumed to be a non-negative integer. We will assume that the valuation functions are additive, i.e., for any i [n] and G [m], vi(G) :=

j G vi({j}), where vi( ) = 0. We will write vi,j instead of vi({j}) for a singleton good j [m]. We say that an instance has binary valuations if for every i [n] and every j [m], vi,j {0, 1}.

Allocation An allocation A := (A1, . . . , An) refers to an n-partition of the set of goods [m], where Ai [m] is the bundle allocated to agent i. Given an allocation A, the utility of agent i [n] for the bundle Ai is vi(Ai) =

Deﬁnition 1 (Envy-freeness). An allocation A is envy-free (EF) if for every pair of agents i, h [n], vi(Ai) vi(Ah). An allocation A is envy-free up to one good (EF1) if for every pair of agents i, h [n] such that Ah = , there exists some good j Ah such that vi(Ai) vi(Ah \ {j}). An allocation A is strongly envy-free up to one good (s EF1) if for every agent h [n] such that Ah = , there exists a good gh Ah such that for all i [n], vi(Ai) vi(Ah \ {gh}). The notions of EF, EF1, and s EF1 are due to Foley (1967), Budish (2011), and Conitzer et al. (2019), respectively.1

Deﬁnition 2 (Envy-freeness with hidden goods). An allocation A is said to be envy-free up to k hidden goods (HEF-k) if there exists a set S [m] of at most k goods such that for every pair of agents i, h [n], we have vi(Ai) vi(Ah \ S). An allocation A is envy-free up to k uniformly hidden goods (u HEF-k) if there exists a set S [m] of at most k goods satisfying |S Ai| 1 for every i [n] such that for every pair of agents i, h [n], we have vi(Ai) vi(Ah \ S). We say that allocation A hides the goods in S and reveals the remaining goods. Notice that a u HEF-k allocation is also HEF-k but the converse is not necessarily true. Indeed, in Proposition 2, we will present an instance that, for some k N, admits an HEF-k allocation but no u HEF-k allocation.

Remark 1. It follows from the deﬁnitions that an allocation is EF if and only if it is HEF-0. It is also easy to verify that an allocation is s EF1 if and only if it is u HEF-n. This is because the unique hidden good for every agent is also the one that is (hypothetically) removed under s EF1. Additionally, as discussed in Section 1, an EF1 allocation might not be u HEF-k for any k n. We say that allocation A is HEF with respect to set S if A becomes envy-free after hiding the goods in S, i.e., for every pair of agents i, h [n], we have vi(Ai) vi(Ah \ S). We say that k goods must be hidden under A if A is HEF with respect to some set S such that |S| = k, and there is no set S with |S | < k such that A is HEF with respect to S .

Deﬁnition 3 (Pareto optimality). An allocation A is Pareto dominated by another allocation B if vi(Bi) vi(Ai) for every agent i [n] with at least one of the inequalities being strict. A Pareto optimal (PO) allocation is one that is not Pareto dominated by any other allocation.

1A slightly weaker notion than EF1 was previously studied by Lipton et al. (2004). However, their algorithm can be shown to compute an EF1 allocation.

Deﬁnition 4 (EF1 algorithms). We will now describe four known algorithms for ﬁnding EF1 allocations that are relevant to our work.

Round-robin algorithm (Round Robin): Fix a permutation σ of the agents. The Round Robin algorithm cycles through the agents according to σ. In each round, an agent gets its favorite good from the pool of remaining goods.

Envy-graph algorithm (Envy Graph): This algorithm, proposed by Lipton et al. (2004), works as follows: In each step, one of the remaining goods is assigned to an agent that is not envied by any other agent. The existence of such an agent is guaranteed by resolving cyclic envy relations (if any exists) in a combinatorial structure called the envy-graph of an allocation.

Fisher market-based algorithm (Alg-EF1+PO): This algorithm, due to Barman, Krishnamurthy, and Vaish (2018), uses local search and price-rise subroutines in a Fisher market associated with the fair division instance, and returns an EF1 and PO allocation. The bound on running time of this algorithm is pseudopolynomial (a polynomial in vi,j instead of log vi,j).

Maximum Nash Welfare solution (MNW): The Nash social welfare of an allocation A is deﬁned as NSW(A) := i [n] vi(Ai) 1/n . The MNW algorithm computes an allocation with the highest Nash social welfare (called a Nash optimal allocation). Caragiannis et al. (2016) showed that a Nash optimal allocation is both EF1 and PO. Remark 2. Conitzer et al. (2019) observed that Round Robin, Alg-EF1+PO, and MNW algorithms all satisfy s EF1. It is easy to see that Envy Graph algorithm is also s EF1. However, note that among the above algorithms, only MNW and Alg-EF1+PO are known to also satisfy PO.2 The allocations computed by all four algorithms have the property that there exists some agent that is not envied by any other agent. Indeed, MNW and Alg-EF1+PO are both PO and therefore cannot have cyclic envy relations, and Round Robin and Envy Graph algorithms have this property by design. For such an agent (not necessarily the same agent for all four algorithms), no good needs to be removed under s EF1. Therefore, from Remark 1, all these algorithms are also envy-free up to n 1 uniformly hidden goods, or u HEF-(n 1).

Proposition 1. Given an instance with additive valuations, a u HEF-(n 1) allocation always exists and can be computed in polynomial time, and a u HEF-(n 1) + PO allocation always exists and can be computed in pseudopolynomial time. Remark 3. Note that for any k < n 1, an HEF-k allocation might fail to exist. Indeed, with n agents that have identical and positive valuations for m = n 1 goods, some agent will surely miss out and force the allocation to hide all n 1 (i.e., k + 1 or more) goods. Therefore, the bound in Proposition 1 for u HEF-k (and hence, for HEF-k) is tight in terms of k.

2It is also known that Round Robin and Envy Graph fail to satisfy PO; see, e.g., (Conitzer, Freeman, and Shah 2017).

Relevant Computational Problems Deﬁnition 5 formalizes the decision problem of whether a given instance admits an HEF-k allocation.

Deﬁnition 5 (HEF-k-EXISTENCE). Given an instance I, does there exist an allocation A and a set S [m] of at most k goods such that A is HEF w.r.t. S?

Notice that a certiﬁcate for HEF-k-EXISTENCE consists of an allocation A as well as a set S of at most k hidden goods. Another relevant computational question involves checking whether a given allocation A is HEF with respect to some set S [m] of at most k goods.

Deﬁnition 6 (HEF-k-VERIFICATION). Given an instance I and an allocation A, does there exist a set S [m] of k goods such that A is HEF w.r.t. S?

For additive valuations, both HEF-k-EXISTENCE and HEF-k-VERIFICATION are in NP. The next problem pertains to the existence of envy-free allocations.

Deﬁnition 7 (EF-EXISTENCE). Given an instance I, does there exist an envy-free allocation for I?

EF-EXISTENCE is known to be NP-complete (Lipton et al. 2004). From Remark 1, it follows that HEF-k EXISTENCE is NP-complete when k = 0 for additive valuations.

4 Theoretical Results We will now present our theoretical results concerning the existence and computation of HEF-k and u HEF-k allocations. We ﬁrst show that u HEF-k is a strictly more demanding notion than HEF-k (Proposition 2).

Proposition 2. There exists an instance I that, for some ﬁxed k N, admits an HEF-k allocation but no u HEF-k allocation.

Proof. Consider the fair division instance I with ﬁve agents a1, . . . , a5 and six goods g1, . . . , g6 shown in Table 1. Observe that the allocation A = (A1, . . . , A5) with A1 = {g1, g2}, A2 = {g3}, A3 = {g4}, A4 = {g5}, A5 = {g6} satisﬁes HEF-2 with respect to the set S = {g1, g2}.

g1 g2 g3 g4 g5 g6 a1 1 1 2 0 0 0 a2 1 1 2 0 0 0 a3 10 10 1 1 1 1 a4 10 10 1 1 1 1 a5 10 10 1 1 1 1

Table 1: The instance used in the proof of Proposition 2.

We will show that I does not admit a u HEF-2 allocation. Suppose, for contradiction, that there exists an allocation B satisfying u HEF-2. Then, B must hide g1 and g2 (otherwise, at least one of a3, a4 or a5 will envy the owner(s) of these goods). Thus, in particular, the good g3 must be revealed by B. Assume, without loss of generality, that g3 is not assigned to a1 in B (otherwise, a similar argument can be carried out for a2). Then, B must assign both g1 and g2 to a1 (so that a1

does not envy the owner of g3). However, this violates the one-hidden-good-per-agent property of u HEF-k, which is a contradiction.

Recall from Section 3 that HEF-k-EXISTENCE is NPcomplete when k = 0. This still leaves open the question whether HEF-k-EXISTENCE is NP-complete for any ﬁxed k N. Our next result (Theorem 1) shows that this is indeed the case, even under the restricted setting of identical valuations (i.e., for every j [m], vi,j = vh,j for every i, h [n]).

Theorem 1 (Hardness of HEF-k-EXISTENCE). For any ﬁxed k N, HEF-k-EXISTENCE is NP-complete even for identical valuations.

Proof. We will show a reduction from PARTITION, which is known to be NP-complete (Garey and Johnson 1979). An instance of PARTITION consists of a multiset X = {x1, x2, . . . , xn} with xi N for all i [n]. The goal is to determine whether there exists Y X such that

xi X\Y xi = T, where T := 1

xi X xi. We will construct a fair division instance with k+3 agents a1, . . . , ak+3 and n + k + 1 goods. The goods are classiﬁed into n + 1 main goods g1, . . . , gn+1 and k dummy goods d1, . . . , dk. The (identical) valuations are deﬁned as follows: Every agent values the goods g1, . . . , gn at x1, . . . , xn respectively; the good gn+1 at T, and each dummy good at 4T. ( ) Suppose Y is a solution of PARTITION. Then, an HEF-k allocation can be constructed as follows: Assign the main goods corresponding to the set Y to agent a1 and those corresponding to X \ Y to agent a2. The good gn+1 is assigned to agent a3. Each of the remaining k agents is assigned a unique dummy good. Note that every agent in the set {a1, a2, a3} envies every agent in the set {a4, . . . , ak+3}, and these are the only pairs of agents with non-zero envy. Therefore, the allocation can be made envy-free by hiding the k dummy goods, i.e., the allocation is HEF with respect to the set {d1, . . . , dk}. ( ) Now suppose there exists an HEF-k allocation A. Since there are k dummy goods and k +3 agents, there must exist at least three agents that do not receive any dummy good in A. Without loss of generality, let these agents be a1, a2 and a3 (otherwise, we can reindex). We claim that all dummy goods must be hidden under A. Indeed, agent a1 does not receive any dummy good, and therefore its maximum possible valuation can be v(g1 gn+1) = 3T < v(dj) for any dummy good dj. If some dummy good dj is not hidden, then a1 will envy the owner of dj, contradicting HEF-k. Therefore, all dummy goods must be hidden, and since there are k such goods, these are the only ones that can be hidden. The above observation implies that the good gn+1 must be revealed by A. Furthermore, gn+1 must be assigned to one of a1, a2 or a3 (otherwise, by pigeonhole principle, one of these agents will have valuation at most 2T

3 and will envy the owner of gn+1). If gn+1 is assigned to a3, then the remaining main goods g1, . . . , gn must be divided between a1 and a2

such that v(A1) T and v(A2) T. This gives a partition of the set X.

Another commonly used preference restriction is that of binary valuations (i.e., for every i [n] and j [m], vi,j {0, 1}). We note that even under this restriction, HEFk-EXISTENCE remains NP-complete when k = 0 (Corollary 1). This observation follows from a result of Aziz et al. (2015), who showed that determining the existence of an envy-free allocation is NP-complete even for binary valuations (Proposition 3). We provide an alternative proof of this statement in the full version of the paper (Hosseini et al. 2019).

Proposition 3 (Aziz et al. 2015; Theorem 11). EFEXISTENCE is NP-complete even for binary valuations.

Corollary 1. For k = 0, HEF-k-EXISTENCE is NPcomplete even for binary valuations.

Proposition 3 is also useful in establishing the computational hardness of ﬁnding an HEF-k+PO allocation. Note that unlike Corollary 1, Theorem 2 holds for any ﬁxed k N.

Theorem 2 (Hardness of HEF-k+PO). Given any instance I with binary valuations and any ﬁxed k N {0}, it is NPhard to determine if I admits an allocation that is envy-free up to k hidden goods (HEF-k) and Pareto optimal (PO).

Proof. (Sketch) Starting from any instance of EFEXISTENCE with binary valuations (Proposition 3), we add to it k new goods and k + 1 new agents such that all new goods are approved by all new agents (and no one else). Also, the new agents have zero value for the existing goods. In the forward direction, an arbitrary allocation of new goods among the new agents works. In the reverse direction, PO forces each new (respectively, existing) good to be assigned among new (respectively, existing) agents only. The imbalance between new agents and new goods means that all (and only) the new goods must be hidden. Then, the restriction of the HEF-k allocation to the existing agents/goods gives the desired EF allocation.

We will now proceed to analyzing the computational complexity of HEF-k-VERIFICATION. Here, we show a hardness-of-approximation result (Theorem 3). Note that HEF-k-VERIFICATION is stated as a decision problem. However, one can consider an approximation version of this problem as follows: A c-approximation algorithm for HEF-k-VERIFICATION is one that, given any fair division instance, computes a set of goods of size at most c kopt, where kopt is the size of the smallest hidden set for the given instance. Under this deﬁnition, Theorem 3 can be interpreted as follows: Given any ε > 0, there is no polynomialtime (1 ε). ln E-approximation algorithm for HEF-k VERIFICATION, unless P=NP.

Theorem 3 (HEF-k-VERIFICATION inapproximability). Given any ε > 0, it is NP-hard to approximate HEF-k VERIFICATION to within (1 ε) ln E even for binary valuations, where E is the sum of all non-negative pairwise envy values in the given allocation.

Proof. We will show a reduction from HITTING SET. An instance of HITTING SET consists of a ﬁnite set X = {x1, . . . , xp}, a collection F = {F1, . . . , Fq} of subsets of X, and some k N. The goal is to determine whether there exists Y X, |Y | k that intersects every member of F (i.e., for every F F, Y F = ). It is known that given any ε > 0, it is NP-hard to approximate HITTING SET to within a factor (1 ε) ln |F| (Dinur and Steurer 2014). We will construct a fair division instance with n = q + 1 agents and m = p + q i=1(|Fi| 1) goods. The agents are classiﬁed into q dummy agents a1, . . . , aq and one main agent aq+1. The goods are classiﬁed into p main goods g1, . . . , gp and q distinct sets of dummy goods, where the ith set consists of the goods f i 1, . . . , f i |Fi| 1. The valuations are as follows: The main agent approves all the main goods, i.e., for all j [p], vq+1({gj}) = 1. Each dummy agent ai approves the dummy goods in the ith set as well as those main goods that intersect with Fi, i.e., for every i [q], vi({f i j}) = 1 for all j [|Fi| 1], and vi({gj}) = 1 whenever xj Fi. All other valuations are set to 0. The input allocation A = (A1, . . . , Aq+1) is deﬁned as follows: The main agent aq+1 is assigned all the main goods, i.e., Aq+1 := {g1, . . . , gp}. For every i [q], the dummy agent ai is assigned the |Fi| 1 dummy goods in the ith set, i.e., Ai := {f i 1, . . . , f i |Fi| 1}. Note that in the allocation A, each dummy agent envies the main agent by one approved good, and these are the only pairs of agents with envy. Finally, given any allocation A, we deﬁne the aggregate envy in A as the sum of all non-negative pairwise envy values, i.e.,

i =h max{0, vi(Ah) vi(Ai)}.

( ) Suppose Y X, |Y | k is solution of the HITTING SET instance. We claim that the allocation A is HEF with respect to the set S := {gj : xj Y } with |S| k. Indeed, since S is induced by a hitting set, each dummy agent approves at least one good in S. Therefore, by hiding the goods in S, the envy from the dummy agents can be eliminated. ( ) Now suppose there exists S [m], |S| k such that A is HEF with respect to S. Then, for every i [q], the set S must contain at least one good that is approved by the dummy agent ai (otherwise A will not be envy-free after hiding the goods in S). It is easy to see that the set Y := {xj : gj S} constitutes the desired hitting set of cardinality at most k. Finally, to show the hardness-of-approximation, notice that the aggregate envy in A is q because each dummy agent envies the main agent by one unit of utility. The claim now follows by substituting |F| = q = E in the inapproximability result of HITTING SET stated above.

Our next result (Theorem 4) provides an approximation algorithm that (nearly) matches the hardness-ofapproximation result in Theorem 3. We remark that the algorithm in Theorem 4 applies to any instance with additive and possibly non-binary valuations.

ALGORITHM 1: Greedy Approximation Algorithm for HEF-k-VERIFICATION Input: An instance [n], [m], V and an allocation A. Output: A set S [m].

Initialize S = . while f(S) 1 do

Set j arg maxj [m]\S f(S) f(S {j}) tiebreak lexicographically Update S S {j } return S

Theorem 4 (Approximation algorithm). There is a polynomial-time algorithm that, given as input any instance of HEF-k-VERIFICATION, ﬁnds a set S [m] with |S| kopt ln E + 1 such that the given allocation is HEF with respect to S. Here, E and kopt denote the aggregate envy and the number of goods that must be hidden under the given allocation, respectively.

The proof of Theorem 4 is available in the full version (Hosseini et al. 2019), but a brief idea is as follows: For any set S [m], deﬁne the residual envy function f : 2[m] R so that f(S) is the aggregate envy in allocation A after hiding the goods in S. That is,

i =h max{0, vi(Ah \ S) vi(Ai)}.

The relevant observation is that f is supermodular. Given this observation, the approximation guarantee in Theorem 4 can be obtained by the standard greedy algorithm for submodular maximization, or, equivalently, supermodular minimization (Nemhauser, Wolsey, and Fisher 1978); see Algorithm 1.

5 Experimental Results

We have seen that the worst-case computational results for HEF-k, even in highly restricted settings, are largely negative (Section 4). In this section, we will examine whether the known algorithms for computing approximately envy-free allocations in particular, the four EF1 algorithms described in Deﬁnition 4 in Section 3 can provide meaningful approximations to HEF-k in practice. Recall from Remark 2 that all four discussed algorithms Round Robin, MNW, Alg-EF1+PO, and Envy Graph satisfy u HEF-(n 1). We evaluate each algorithm in terms of (a) its regret (deﬁned below), and (b) the number of goods that the algorithm must hide. Given an instance I and an allocation A, let κ(A, I) denote the number of goods that must be hidden under A. The regret of allocation A is the number of extra goods that must be hidden under A compared to the optimal. That is, reg(A, I) := κ(A, I) min B κ(B, I). Similarly, given an algorithm ALG, the regret of ALG is given by reg(ALG(I), I), where ALG(I) is the allocation returned by ALG for the input instance I. Note that the regret can be large due to the suboptimality of an algorithm, but also due to the size of the instance. To negate the effect of the latter,

we normalize the regret value by n 1, which is the worstcase upper bound on the number of hidden goods for all four algorithms of interest.

Experiments on Synthetic Data The setup for synthetic experiments is similar to that used in Figure 1. Speciﬁcally, the number of agents, n, is varied from 5 to 10, and the number of goods, m, is varied from 5 to 20 (we ignore the cases where m < n). For every ﬁxed n and m, we generated 100 instances with binary valuations drawn i.i.d. from Bernoulli distribution with parameter 0.7 (i.e., vi,j Ber(0.7)). Table 2 shows the heatmaps of the normalized regret (averaged over 100 instances) and the number of goods that must be hidden (averaged over non-EF instances, i.e., whenever k 1) for all four algorithms.3 It is clear that Alg-EF1+PO and Round Robin algorithms have a superior performance than MNW and Envy Graph. In particular, both Alg-EF1+PO and Round Robin have small normalized regret, suggesting that they hide close-to-optimal number of goods. Additionally, the number of hidden goods itself is small for these algorithms (in most cases, no more than three goods need to be hidden), suggesting that the worst-case bound of n 1 is unlikely to arise in practice. Overall, our experiments suggest that Alg-EF1+PO and Round Robin can achieve useful approximations to HEF-k in practice, especially in comparison to MNW and Envy Graph.4

Experiments on Real-World Data For experiments with real-world data, we use the data from the popular fair division website Spliddit (Goldman and Procaccia 2014). The Spliddit data has 2212 instances in total, where the number of agents n varies between 3 and 10, and the number of goods m n varies between 3 and 93. Unlike the synthetic data, the distribution of instances here is rather uneven (see the full version online); in fact, 1821 of the 2212 instances have n = 3 agents and m = 6 goods. Therefore, instead of using heatmaps, we compare the algorithms in terms of their normalized regret (averaged over the entire dataset) and the cumulative distribution function of the hidden goods (see Figure 2). Figure 2 presents an interesting twist: MNW is now the best performing algorithm, closely followed by Round Robin and Alg-EF1+PO. For any ﬁxed k, the fraction of instances for which these three algorithms compute an HEF-k allocation is also nearly identical. As can be observed, these algorithms almost never need to hide more than three goods. By contrast, Envy Graph has the largest regret and signiﬁcantly worse cumulative performance. Therefore, once again, Alg-EF1+PO and Round Robin algorithms perform competitively with the optimal solution, making them attractive options for achieving fair outcomes without withholding too much information.

3The full version (Hosseini et al. 2019) provides additional results for vi,j Ber(0.7), and vi,j Ber(0.5). 4In the full version of the paper (Hosseini et al. 2019), we provide two families of instances where the normalized worst-case regret of MNW is large.

Normalized average-case regret Alg-EF1+PO Round Robin MNW Envy Graph

Number of goods that must be hidden on average (averaged over non-EF instances only) Alg-EF1+PO Round Robin MNW Envy Graph

Table 2: Results for synthetic data.

$ Y H U D H F D V H Q R U P D H G U H U H W

5 R X Q G 5 R E Q

( Q Y U D S"

$ ( ) % 3 2

1 X P E H U R I G G H Q R R G V

) U D F W R Q R I Q V W D Q F H V

( ) 0 1# 5 R X Q G 5 R E Q ( Q Y&' U D S $* ( ) + 3 2

Figure 2: Results for Spliddit data.

6 Future Work

The asymptotic existence of envy-free allocations has been studied by Dickerson et al. (2014) and Manurangsi and Suksompong (2019). Analyzing the asymptotic behavior of HEF-k allocations is an interesting direction for future work. Exploring the connection with other recently proposed relaxations that involve discarding goods (Caragiannis, Gravin, and Huang 2019) or sharing a small subset of goods (Sandomirskiy and Segal-Halevi 2019) might also be interesting.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. We are grateful to Ariel Procaccia and Nisarg Shah for sharing with us the data from Spliddit, and to Haris Aziz for bringing to our attention the proof of EF-EXISTENCE for binary valuations in (Aziz et al. 2015). RV thanks Rupert Freeman, Nick Gravin, and Neeldhara Misra for very helpful discussions and several useful suggestions for improving the presentation of the paper. LX acknowledges NSF #1453542 and #1716333, and HH acknowledges NSF #1850076 for support.

Abebe, R.; Kleinberg, J.; and Parkes, D. C. 2017. Fair Division via Social Comparison. In Proceedings of the 16th

Conference on Autonomous Agents and Multiagent Systems, 281 289. Aziz, H.; Gaspers, S.; Mackenzie, S.; and Walsh, T. 2015. Fair Assignment of Indivisible Objects under Ordinal Preferences. Artiﬁcial Intelligence 227:71 92. Aziz, H.; Bouveret, S.; Caragiannis, I.; Giagkousi, I.; and Lang, J. 2018. Knowledge, Fairness, and Social Constraints. In Thirty-Second AAAI Conference on Artiﬁcial Intelligence, 4638 4645. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018. Finding Fair and Efﬁcient Allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, 557 574. Bei, X.; Qiao, Y.; and Zhang, S. 2017. Networked Fairness in Cake Cutting. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, 3632 3638. Beynier, A.; Chevaleyre, Y.; Gourv es, L.; Lesca, J.; Maudet, N.; and Wilczynski, A. 2018. Local Envy-Freeness in House Allocation Problems. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 292 300. Bredereck, R.; Kaczmarczyk, A.; and Niedermeier, R. 2018. Envy-Free Allocations Respecting Social Networks. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 283 291. Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy 119(6):1061 1103. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation, 305 322. Caragiannis, I.; Gravin, N.; and Huang, X. 2019. Envy Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019

ACM Conference on Economics and Computation, 527 545. ACM. Chan, H.; Chen, J.; Li, B.; and Wu, X. 2019. Maximin Aware Allocations of Indivisible Goods. In Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence, 137 143. Chen, Y., and Shah, N. 2017. Ignorance is Often Bliss: Envy with Incomplete Information. Technical report. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2017. Distributed Fair Allocation of Indivisible Goods. Artiﬁcial Intelligence 242:1 22. Conitzer, V.; Freeman, R.; Shah, N.; and Vaughan, J. W. 2019. Group Fairness for Indivisible Good Allocation. In Thirty-Third AAAI Conference on Artiﬁcial Intelligence, 1853 1860. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proceedings of the 2017 ACM Conference on Economics and Computation, 629 646. ACM. Dickerson, J. P.; Goldman, J.; Karp, J.; Procaccia, A. D.; and Sandholm, T. 2014. The Computational Rise and Fall of Fairness. In Proceedings of the Twenty-Eighth AAAI Conference on Artiﬁcial Intelligence, 1405 1411. Dinur, I., and Steurer, D. 2014. Analytical Approach to Parallel Repetition. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, 624 633. Foley, D. 1967. Resource Allocation and the Public Sector. Yale Economic Essays 45 98. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Goldman, J., and Procaccia, A. D. 2014. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges 13(2):41 46. Halpern, D., and Shah, N. 2019. Fair Division with Subsidy. In International Symposium on Algorithmic Game Theory, 374 389. Springer. Hosseini, H.; Sikdar, S.; Vaish, R.; Wang, J.; and Xia, L. 2019. Fair Division through Information Withholding. ar Xiv preprint ar Xiv:1907.02583. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, 125 131. Manurangsi, P., and Suksompong, W. 2019. When Do Envy Free Allocations Exist? In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 33, 2109 2116. Markakis, E. 2017. Approximation algorithms and hardness results for fair division with indivisible goods. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 12, 231 247. Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An Analysis of Approximations for Maximizing Submodular Set Functions I. Mathematical Programming 14(1):265 294.

Nguyen, T. T., and Rothe, J. 2014. Minimizing Envy and Maximizing Average Nash Social Welfare in the Allocation of Indivisible Goods. Discrete Applied Mathematics 179:54 68. Sandomirskiy, F., and Segal-Halevi, E. 2019. Fair Division with Minimal Sharing. ar Xiv preprint ar Xiv:1908.01669.