Computing an Approximately Optimal Agreeable Set of Items

1 Introduction

A typical resource allocation problem involves dividing a set of resources among interested agents. We are often concerned with the efficiency of the allocation, e.g., achieving high social welfare or ensuring that there is no other allocation that would make every agent better off than in the current allocation. Another important issue is the fairness of the allocation. For example, we might want the resulting allocation to be envy-free, meaning that every agent regards her bundle as the best among the bundles in the allocation [Foley, 1967; Varian, 1974], or proportional, meaning that every agent obtains at least her proportionally fair share [Steinhaus, 1948]. A common feature of such problems is that one agent's gain is another agent's loss: the setting inherently puts the agents in conflict with one another, and our task is to try to resolve this conflict as best we can according to our objectives.

We consider a variant of the resource allocation problem where instead of the agents being pitted against one another, they belong to one and the same group. We will collectively allocate a subset of items to this group, and our goal is to make this subset "agreeable" to all agents. Agreeability can be thought of as a minimal desirability condition: While an agent may be able to find other subsets of items that she personally prefers, the current set is still acceptable for her and

Warut Suksompong

Stanford University warut@cs.stanford.edu

she can agree with the allocation of the set to the group. Without further constraints, the problem described so far would be trivial, since we could simply allocate the whole set of items to the agents. We therefore impose a constraint that the allocated subset should be small. This constraint on size is reasonable in a variety of settings. For instance, the agents could be going together on a trip and there is limited space in the luggage. Alternatively, they could be receiving some items in a resource allocation setting where the preferences of the other groups are not known or are given lower priority, perhaps because the groups have not arrived or are placed lower in a team competition, so we want the subset to be agreeable to the first group while leaving as many items as possible to the remaining groups.

The problem of allocating a small agreeable subset of items was first studied by Suksompong, who defined the notion of agreeability based on the fairness notion of envy-freeness [Suksompong, 2016]. A subset of items is said to be agreeable to an agent if the agent likes it at least as much as the complement set. Agreeability, or minor variants thereof, has been considered in the context of fair division, where each group consists of a single agent [Bouveret et al., 2010; Brams et al., 2012; Aziz et al., 2015]. In the example of agents going together on a trip, a subset of items that they take is agreeable if they weakly prefer it to the complement subset of items left at home. In the resource allocation example, assuming that we allocate resources between two groups, a subset is agreeable to the first group if no agent in the group would rather switch to the second group. Suksompong showed a tight upper bound on the number of items that may need to be included in the set in order for it to be agreeable to all agents. In particular, for every additional agent, the worst-case bound increases by approximately half an item. This result is rather surprising, since agents can have very different preferences on the items, and yet we only need to pay a relatively mild cost for each extra agent to keep agreeability satisfied for the whole group. When there are two or three agents, Suksompong also gave polynomial-time algorithms that compute an agreeable subset whose size matches the worst-case bound.

While Suksompong's results are quite intriguing, some important issues were left unaddressed by his work. Firstly, in many instances, an agreeable subset of smallest size is much smaller than the worst-case bound over all instances with that number of agents and items. Indeed, an extreme example is when there is a single item that every agent likes better than all of the remaining items combined. In this case, it suffices to allocate that item. This results in a much smaller set than the worst-case bound, which is at least half of the items for any number of agents. Secondly, even if we were content with finding a subset that matches the worst-case bound, we might not be able to compute it efficiently, thus rendering the existence result impractical when the number of agents or items is large. A related issue is that of eliciting the preferences on subsets of items from the agents. Since there are an exponential number of subsets, the burden on the agents to determine their preferences and the amount of information that they need to submit to our algorithm is potentially huge. This issue can be circumvented by relying on preferences over single items or allowing the algorithm to query the agents' preferences on a need-to-know basis, as is the case for Suksompong's polynomial time algorithm for two and three agents, respectively. 1

In this paper, we address all of these issues and investigate the problem of computing an agreeable subset of approximately optimal size for a given instance, as opposed to one whose size is close to the worst-case bound over all instances with that number of agents and items. We tackle the problem using several models that are well-studied in the literature and present computationally efficient algorithms for computing an agreeable subset of approximately optimal size in each of them. Moreover, in all of the models we show that our approximation bounds are virtually tight.

In Section 3, we assume that we only have access to the agents' ordinal preferences on single items rather than subsets of items. Models of this type offer the advantage that the associated algorithms are often simple to implement and the agents do not need to give away or even determine their entire utility functions; such models have therefore received widespread attention [Kohler and Chandrasekaran, 1971; Bouveret et al., 2010; Aziz et al., 2015]. With only the ordinal preferences on single items in hand, however, most of the time we cannot tell whether a certain subset is agreeable to an agent or not. Nevertheless, by assuming that preferences are responsive, we can extend preferences on single items to partial preferences on subsets. We show that for any constant number of agents, there exists a subset of m2 +o(m) items that is always agreeable as long as the full responsive preferences are consistent with the rankings over single items. Since a necessarily agreeable subset always consists of at least m2 items even for one agent, this bound is essentially tight. We also present a simple randomized algorithm and a deterministic algorithm, both running in polynomial time, to compute such a subset.

Next, in Section 4, we consider general preferences using the value oracle model [Feige et al., 2011], where the preferences of the agents are represented by utility functions and we are allowed to query the utility of an agent for any subset. We exhibit an efficient approximation algorithm with approximation ratio O(mln lnm/ lnm) in this model. While this may not seem impressive since the trivial algorithm that always outputs the whole set of items already achieves approximation ratio O(m), we also show that our ratio is essentially the best we can hope for. In particular, there does not exist a polynomial time algorithm with approximation ratio o(m/ lnm).

1 Note that if the algorithm elicits the whole preference relations from the agents, this elicitation step alone already prevents the algorithm from running in time polynomial in the number of items.

Finally, in Section 5, we assume that the agents are endowed with additive utility functions. Additivity provides a reasonable tradeoff between simplicity and expressiveness; it is commonly assumed in the literature, especially recently [Amanatidis et al., 2015; Bouveret and Lemaˆıtre, 2016; Caragiannis et al., 2016]. We show that under additive valuations, it is NP-hard to decide whether there exists an agreeable set containing exactly half of the items even where there are only two agents. On the other hand, using results on covering integer programs, we demonstrate the existence of an O(ln n)-approximation algorithm for computing a minimum size agreeable set. Moreover, we show that this is tight: It is NP-hard to approximate the problem to within a factor of (1 - δ) ln n for any δ > 0.

2 Preliminaries

Let N = {1, 2, . . . , n} denote the set of agents, and S = {x1, x2, . . . , xm} the set of items. The agents in N will be collectively allocated a subset of items in S. Denote by S the set of all subsets of S. Each agent i is endowed with a preference relation ⪰i, a reflexive, complete, and transitive ordering over S. Let ≻i denote the strict part and ∼i the indifference part of the relation ⪰i. For items x and y, we will sometimes write x ⪰ y to mean {x} ⪰ {y}. We assume throughout the paper that preferences are monotonic, i.e., T ∪ {x} ⪰ T for all T ⊆ S and x ∈ S.

We are interested in when a set of items is agreeable to an agent. To this end, we must precisely define what agreeability means. The notion of agreeability, defined by Suksompong [Suksompong, 2016], is based on the fairness concept of envy-freeness. A subset is considered to be agreeable to an agent if the agent likes it at least as much as the complement set. Put differently, if the complement set is allocated to another agent, then the former agent does not envy the latter.

Definition 1. A subset T ⊆ S of items is said to be agreeable to agent i if T ⪰i S\T.

Next, we define a property of preferences called responsiveness, which says that an agent cannot be worse off whenever an item is added to her set or replaced by another item that she weakly prefers to the original item. Responsiveness is a reasonable assumption in many settings and has been widely studied in the literature [Brams and Fishburn, 2000; Brams et al., 2012].

Definition 2. A preference ⪰ on S is called responsive if it satisfies the following two conditions:

• T ∪ {x} ⪰ T for all T ⊆ S and x ∈ S (monotonicity);
• T\{y} ∪ {x} ⪰ T for all T ⊆ S and x, y ∈ S such that x ⪰ y, x ̸∈ T and y ∈ T .

When preferences are responsive, it sometimes suffices to know an agent's preference on single items (i.e., the restriction of ⪰i to subsets consisting of single items) in order to deduce that the agent regards a subset as agreeable. This intuition is formalized in the next definition.

Definition 3. Fix a preference ⪰sing on single items in S. A subset T ⊆ S is necessarily agreeable with respect to ⪰sing if T ⪰ S\T for any responsive preference ⪰ on S consistent with ⪰sing .

The following characterization of necessary agreeability will be useful for our results in Section 3.

Lemma 1 ([Suksompong, 2016]). Fix a preference ⪰sing on single items in S with

Let T ⊆ S, and define Ik = {x1, x2, . . . , xk} for all k ∈ {1, 2, . . . ,m}. If

for all k ∈ {1, 2, . . . ,m}, then T is necessarily agreeable with respect to ⪰sing . The converse also holds if the preference ⪰sing is strict.

3 Ordinal Preferences on Single Items

In this section, we assume that we only have at our disposal the agents' ordinal preferences on single items. We are interested in computing a small necessarily agreeable subset that is consistent with these preferences. If we had access to the agents' preferences over all subsets of items, it is known that we could always find a subset of size ⌊ m+n 2 ⌋ that is agreeable to all n agents [Suksompong, 2016]. It is not clear, however, how much extra "penalty" we have to pay for the information restriction that we are imposing. It could be, for example, that with three agents there exist preferences for which we have to include up to 2m 3 or 3m 4 items in a necessarily agreeable subset. We show that this is in fact not the case-there always exists a necessarily agreeable subset of size m2 +O(√mlog logm) as long as the number of agents is constant.

For the proof of our first result, we will require the law of the iterated logarithm, which gives a bound for the fluctuations of a random walk.

Lemma 2 (Law of the iterated logarithm [Khintchine, 1924; Kolmogoroff, 1929]). Let X1,X2, . . . be independent and identically distributed random variables with mean 0 and variance 1. Let Sn := X1 + · · · +Xn. Then

almost surely.

Theorem 1. If the number of agents is constant, then there exists a subset of size m2 +O(√mlog logm) that is necessarily agreeable with respect to the preferences on single items of all agents.

We remark that when there are two agents, Suksompong's algorithm computes a necessarily agreeable subset of size ⌊ m2 ⌋ + 1, which is also the optimal bound for an agreeable subset for two agents even if we know their full preferences.

Proof. Let X1,X2, . . . ,Xm be independent random variables taking values 1 or -1. We will take Xi = 1 to mean that item xi is included in our subset, and Xi = -1 to mean that it is excluded from the subset.

Consider an arbitrary agent j. Suppose that she ranks the single items as

Using Lemma 1, we find that our subset is necessarily agreeable for the agent if

for all 1 ≤ i ≤ m.

Let Sj i :=Xσj(1)+· · ·+Xσj(i), and independently set each Xi to be 1 or -1 with probability 1 2 each. Lemma 2 implies that for large enough k (and m), we have Sj i ≤ 2√i log log i (and by symmetry, -Sj i ≥ -2√i log log i) for all i ≥ k with high probability. This means that for large enough m, |Sj i | ≤ 2√mlog logm for all 1 ≤ i ≤ m with high probability as well.

Since n is constant, by the union bound we find that for sufficiently large m, we can initialize the random variables X1, . . . ,Xm so that |Sj i | ≤ 2√m log log m for all 1 ≤ i ≤ m and all j. We will modify the choice of Xi's slightly. For each agent, include her most preferred √mlog logm items that have so far been excluded. Thus, we have Sj i ≥ 0 for all 1 ≤ i ≤ m and all j, and our selected subset includes at most

Theorem 1 yields a simple randomized polynomial time algorithm that finds a necessarily agreeable subset for multiple agents by first choosing independently and uniformly at random whether to include each item, and then modifying the selection by including the most preferred √m log log m items of each agent that have been excluded.

Next, we present a deterministic polynomial time algorithm that finds a necessarily agreeable subset of size m/2 + o(m) for all agents. We will need the following classical result in combinatorics.

Lemma 3 ([Erd˝os and Szekeres, 1935]). Any sequence of at least (r - 1)(s - 1) + 1 distinct real numbers contains either an increasing subsequence of length r or a decreasing subsequence of length s.

Theorem 2. If the number of agents is constant, then there exists a deterministic algorithm, running in time polynomial in the number of items, that computes a subset of size m2 + o(m) that is necessarily agreeable with respect to the preferences on single items of all agents.

Proof. We first observe that when there are m items and two agents whose preferences on these items are the opposite of each other, we can choose a subset of size at most m2 +1 that is necessarily agreeable to both agents. To see this, suppose that the preferences on single items of the two agents are

and

If m is odd, it suffices to choose items x1, x3, x5, . . . , xm, while if m is even, it suffices to choose items x1, x3, x5, . . . , xm-1 along with item xm.

Now, consider our group of n agents. Assume without loss of generality that the preference on single items of agent 1 is

Using Lemma 3, from the preference on single items of agent 2, we can find either an increasing subsequence or a decreasing subsequence of length √m on the indices of the items. Applying Lemma 3 again, we find a subsequence of this subsequence of length m1/4 that is either increasing or decreasing in the preference on single items of agent 3. Proceeding in this manner, we find a subsequence of m1/2n-1 items whose indices appear either in that order or in the reverse order in every agent's preference on single items. By our observation above, we can choose a subset of at most 1 2 m1/2n-1 +1 items that is necessarily agreeable for every agent with respect to this set of m1/2n-1 items.

Let t := 2n-1 . Note that if a set A of items is necessarily agreeable when the universe of items is taken to be B ⊇ A, and another set C of items is necessarily agreeable with respect to the same preference on single items when the universe of items is D ⊇ C disjoint from B, then A ∪ C is necessarily agreeable with respect to that preference when the universe of items is B ∪D. To obtain our necessarily agreeable subset for all agents, we proceed as follows. When there are k items left, we choose a subset of k 1t items as above. Within that subset, we choose a subset of at most 12 k 1t + 1 items that is necessarily agreeable for all agents with respect to the k 1t items, and we remove the k 1t items from consideration. In the first step, we decrease the number of items by a factor of 1 - 1/m(t-1)/t , and this factor only decreases in subsequent steps. Hence the number of steps is at most

which implies that our chosen subset exceeds half of the items by o(m) items. Moreover, since each step involves finding a longest increasing or decreasing subsequence from a list of length at most m for a constant number of agents, the algorithm runs in polynomial time.

Although the algorithm in Theorem 2 has the advantage of being deterministic, the expected number of repetitions of the randomized algorithm in Theorem 1 is very low; in fact, this value is roughly 1 since the algorithm succeeds with high probability. Therefore, we think that the algorithm from Theorem 1 should be preferred in general due to its speed and ease of implementation as well as its superior guarantee.

4 General Preferences

While our algorithms from the previous section always find an agreeable set of size at most m2 + o(m), it is unclear how small this set is compared to the optimal if we have information beyond preferences on single items. In other words, our results so far do not yield any guarantee on the approximation ratio beyond the obvious O(m) upper bound for arbitrary preferences over subsets of items. The goal of this section is to explore the possibilities and limitations of achieving better approximation ratios in this general setting.

Before we move on to our results, let us be more precise about the model we are working with. First, since each agent's preference is reflexive, complete and transitive, there is a utility function ui : S → [0, 1] such that T ⪰i T ′ if and only if ui(T ) ≥ ui(T ′ ); for convenience, we work with these utility functions instead of working directly with the preferences themselves. Since the number of subsets in S is exponentially large, the utility functions take exponential space to write down. Hence, it is undesirable to include them as part of the input. Instead, we will work with the value oracle model [Feige et al., 2011], in which the algorithm can query u1(T), . . . , un(T) for each subset T ⊆ S. 2 Finally, we note that we do not assume responsiveness of the agents' preferences in this section.

Our first result is a simple polynomial time approximation algorithm with approximation ratio O(mln lnm/ lnm). Even though this approximation guarantee is only Ω(lnm/ ln lnm) better than the obvious O(m) bound, we will see later that this is almost the best one can hope for in polynomial time.

Theorem 3. For any constant ε > 0, there exists a deterministic (εm ln ln m/ ln m)-approximation algorithm for finding a minimum size agreeable set that runs in time polynomial in the number of agents and items.

Our algorithm works as follows. First, we query the agents' utilities on (lnm/ ln lnm)-size subsets T1, . . . , Tpoly(m), which are to be specified. If any of these subsets are agreeable, then we output one such subset. Otherwise, we output the whole set S.

To argue about the approximation ratio of the algorithm, we need to show that, if there is a small agreeable subset T ∗ ⊆ S (of size O(lnm/ ln lnm)), then at least one of T1, . . . , Tpoly(m) is agreeable. A sufficient condition for this is that every subset T ⊆ S of small size is contained in at least one Ti. A similar question has been studied before in combinatorics under the name covering design [Gordon et al., 1996]. Here we will use a construction by Rees et al., stated formally below.

Lemma 4 ([Rees et al., 1999]). For any set S with |S| = m and any positive integers p, q such that pq ≤ m, there exists a deterministic algorithm that outputs subsets T1, . . . , T(⌈m/p⌉ q ) ⊆ S of size pq such that, for any subset T ⊆ S of size at most q, T is contained in Ti for some i. Moreover, the running time of the algorithm is polynomial in m and (⌈m/p⌉ q ).

2 When a polynomial number of queries are allowed, it is not hard to see that the value oracle model can be simulated with the preference oracle model (e.g., [Suksompong, 2016]), in which the algorithm is allowed to query the relative preference of an agent between any two subsets, and vice-versa.

We give a short proof of Lemma 4, which is taken from Rees et al.'s work but modified with the desired range of the parameters.

Proof of Lemma 4. First, partition S into ⌈m/p⌉ parts S1, . . . , S⌈m/p⌉ where each part is of size at most p. Each set Ti is simply a union of q different Sj's. Note that if the union is of size smaller than pq, we can simply add arbitrary elements of S into it to make its size exactly pq. Clearly, there are (⌈m/p⌉ q ) such unions and T1, . . . , T(⌈m/p⌉ q ) satisfy the properties required in the theorem.

With this lemma in place, we are ready to prove Theorem 3.

Proof of Theorem 3. Our algorithm starts by evoking the algorithm from Lemma 4 with q = ⌊ln m/(ε ln ln m)⌋ and p = ⌊εmln lnm/(q lnm)⌋ to produce subsets T1, . . . , Tℓ ⊆ S of size pq where ℓ = (⌈m/p⌉ q ). For each i = 1, . . . , ℓ, we query u1(Ti), . . . , un(Ti), u1(S\Ti), . . . , un(S\Ti) to check whether Ti is agreeable. If any Ti is agreeable, we output it. Otherwise, output the whole set S. Clearly, the output set is always agreeable.

Moreover, observe that, from our choice of p, q, we have

which is polynomial in m. Hence, the running time of our algorithm is polynomial in m and n.

To prove the algorithm's approximation guarantee, let us consider two cases. First, if the optimal agreeable set has size more than q, then since we output a set of size at most m, we obtain an approximation ratio of at most m/(q + 1) ≤ εm ln ln m/ ln m.

On the other hand, if the optimal agreeable set T ∗ has size at most q, then by construction, there exists i such that T ∗ ⊆ Ti. Since T ∗ is agreeable, Ti is also agreeable. Hence, our output set has size pq ≤ εmln lnm/ lnm, which implies an approximation ratio of εm ln lnm/ lnm as well.

While our algorithm may seem rather naive, we will show next that its approximation guarantee is, up to O(ln lnm) factor, essentially the best one can hope for, even when there is only one agent:

Theorem 4. For every constant c > 0 and every sufficiently large m (depending on c), there is no (possibly randomized and adaptive) algorithm that makes at most mc/8 queries and always outputs an agreeable set with expected size at most m/(c lnm) times the optimum, even when there is only one agent.

In other words, the above theorem implies that there is no polynomial time algorithm with approximation ratio o(m/ lnm). We note here that our lower bound is information-theoretic and is not based on any computational complexity assumptions. Moreover, it rules out any algorithm that makes a polynomial number of queries, not only those that run in polynomial time.

To prove Theorem 4, we define two functions g, fT ∗ : S → [0, 1], where T ∗ is a randomly chosen subset of S of size ⌊c lnm/4⌋. On the one hand, we let g(T) = 1 if |T | ≥ m/2, and g(T) = 0 otherwise. On the other hand, we let fT ∗(T) = 1 if |T| ≥ m/2 or T ∗ ⊆ T, and fT ∗(T) = 0 otherwise. That is, fT ∗ is g together with a planted solution T ∗ . The key idea of the proof is that it is unlikely that an algorithm A can distinguish between g and fT ∗ using at most mc/8 queries. As a result, if A is presented with fT ∗, with constant probability it must output an agreeable set of g, which is of size at least m/2. However, the optimal agreeable set for fT ∗ has size only ⌊c lnm/4⌋. Therefore, the expected size of the output of A is more than m/(c lnm) times the optimum. The details of the proof can be found in the full version of this paper [Manurangsi and Suksompong, 2017].

5 Additive Utilities

In this section, we assume that the agents' preferences are represented by additive utility functions. Each agent i has some nonnegative utility ui(xj) for item xj, and ui(T) = ∑x∈T ui(x) for any i ∈ N and any subset of items T ⊆ S.

Clearly, the problem of deciding whether there exists an agreeable set of a certain size is in NP. Moreover, the following theorem shows that it is indeed NP-complete, even when there are two agents with additive utility functions.

Theorem 5. Even when there are two agents with additive utility functions, it is NP-hard to decide whether there is an agreeable set of size exactly m2 .

Proof. We will reduce from the following problem called BALANCED 2-PARTITION: given a multiset A of nonnegative integers, decide whether there exists a subset B ⊆ A such that |B| = |A \ B| = |A|/2 and ∑a∈B a = ∑a∈A\B a = ∑a∈A a/2.

Like the well-known 2-PARTITION where the cardinality constraint is not included, BALANCED 2-PARTITION is NPhard. We leave the proof to the full version [Manurangsi and Suksompong, 2017].

The reduction from BALANCED 2-PARTITION proceeds as follows. Let a1, . . . , a|A| be the elements of A. The set S contains |A| items x1, . . . , x|A|, each associated with an element of A. The utility function is then defined by u1(xi) = ai and u2(xi) = M - ai where M = ∑a∈A a. We will next show that this reduction is indeed a valid reduction.

(YES Case) Suppose that there exists B ⊆ A such that |B| = |A|/2 and ∑a∈B a = ∑a∈A a/2. We can simply pick T to be all the items corresponding to the elements in B. It is obvious that T has size |A|/2 = m/2 and that T is agreeable.

(NO Case) We prove the contrapositive; suppose that there is an agreeable subset T ⊆ S of size m/2. Let B be the corresponding elements in A of all the items in T. Since T is agreeable, ∑x∈T ui(x) ≥ ∑x∈S\T ui(x) for i ∈ {1, 2}. When i = 1, this implies that ∑a∈B a ≥ ∑a∈A a/2. Moreover, when i = 2, using the fact that |T| = m/2, we have

∑a∈B a ≤ ∑a∈A a/2. Thus, ∑a∈B a = ∑a∈A a/2. Finally, note that |B| = m/2 = |A|/2. Hence, A is a YES instance for BALANCED 2-PARTITION.

Theorem 5 shows that the problem is weakly NP-hard even when there are two agents. Nevertheless, when the number of agents is constant, there exists a pseudo-polynomial time dynamic programming algorithm for computing an optimal agreeable set. In particular, the problem is not strongly NPhard for a constant number of agents. On the other hand, when the number of agents is not fixed, the problem becomes strongly NP-hard. In other words, there is no pseudopolynomial time algorithm for this variation unless P=NP. We formally describe these results and their proofs in the full version of this paper [Manurangsi and Suksompong, 2017].

Given that finding an agreeable set of minimum size is NPhard, it is natural to attempt to find an approximation algorithm for the problem. When the utilities are additive, this turns out to be closely related to approximating the classical problem SET COVER. In SET COVER, we are given a ground set U and a collection C of subsets of U. The goal is to select a minimum number of subsets whose union is the entire U.

SET COVER was one of the first problems shown to be NPhard in Karp's seminal paper [Karp, 1972]. Since then, its approximability has been intensely studied and has, by now, been well understood. A simple greedy algorithm is known to yield a (ln |U| + 1)-approximation for the problem [Johnson, 1974; Lov´asz, 1975]. On the other hand, a long line of work in hardness of approximation [Lund and Yannakakis, 1994; Raz and Safra, 1997; Feige, 1998; Alon et al., 2006; Moshkovitz, 2015] culminates in Dinur and Steurer's work, in which a (1 - ε) ln |U| ratio NP-hardness of approximation for SET COVER was proved for every constant ε > 0 [Dinur and Steurer, 2014].

The first connection we will make between SET COVER and approximating minimum size agreeable set is on the negative side-we will show that any inapproximability result of SET COVER can be translated to that of approximating minimum size agreeable set as well. To do so, we will first state Dinur and Steurer's result more precisely.

Lemma 5 ([Dinur and Steurer, 2014]). For every constant ε > 0, there is a polynomial time reduction from any 3SAT formula φ to a SET COVER instance (U, C) and f(U) = poly(|U|) such that

• (Completeness) if φ is satisfiable, the optimum of (U, C) is at most f(U).
• (Soundness) if φ is unsatisfiable, the optimum of (U, C) is at least ((1 - ε) ln |U|)f(U).

We are now ready to prove hardness of approximation for minimum size agreeable set.

Theorem 6. For any constant δ > 0, it is NP-hard to approximate minimum size agreeable set to within a factor (1 - δ) ln n of the optimum.

Proof. Let ε = δ/2. Given a 3SAT formula φ, we first use Dinur-Steurer reduction to produce a SET COVER instance (U, C). Let there be |U| agents, each of whom is associated with each element of U; it is convenient to think of the set of agents as simply N = U. As for the items, let there be one item for each subset C ∈ C and additionally let there be one special item called t; in other words, S = C ∪ {t}.

The utility for each a ∈ U is then defined by

We show next that this reduction indeed gives the desired inapproximability result.

(Completeness) If φ is satisfiable, then there are f(|U|) subsets from C that together cover U. We can take T to contain all these subsets and the special item t. Clearly, T has size f(|U|) + 1 and is agreeable.

(Soundness) If φ is unsatisfiable, then any set cover of (S, C) contains at least ((1 - ε) ln |U|)f(|U|) subsets. Consider any agreeable set T. For each a ∈ U, from our choice of ua(t), T must include at least one subset that contains a. In other words, T \ {t} is a set cover of (S, C). Hence, |T| must also be at least ((1 - ε) ln |U|)f(|U|).

Thus, it is NP-hard to approximate minimum size agreeable set to within ((1-ε) ln |U|)f(|U|) f (|U |)+1 of the optimum. This ratio is at least (1-δ) ln n when the number of agents, n = |U|, is sufficiently large.

Unlike the above inapproximability result, it is unclear how algorithms for SET COVER can be used to approximate minimum size agreeable set. Fortunately, our problem is in fact a special case of a generalization of SET COVER called COVERING INTEGER PROGRAM (CIP), which can be written as follows:

where c, u ∈ Rm and A ∈ Rn×m are given as input.

The problem of finding a minimum size agreeable set can then be formulated in this form simply by setting c, u and A as follows.

Similarly to SET COVER, approximability of CIP has been well studied; specifically, the problem is known to be approximable to within O(lnn) of the optimum in polynomial time [Kolliopoulos and Young, 2005]. This immediately implies an O(ln n)-approximation algorithm for finding a minimum size agreeable set as well:

Theorem 7. When the agents' utility functions are additive, there is a polynomial time O(lnn)-approximation algorithm for finding a minimum size agreeable set.