Assigning a Small Agreeable Set of Indivisible Items to Multiple Players

1 Introduction

Consider the following assignment problem with aspects of fair division as well as social choice: A group of agents are going together on a road trip, and they have to collectively agree upon a subset of items to bring with them in a bag that can hold a limited number of items. Naturally, the agents have different interests on different items, but they always like a set at least as much as any subset of it. The set of items included in the bag should be selected in such a way that any agent weakly prefers it to the set of items left at home. How large does the bag need to be in order to guarantee that there always exists such a subset-an agreeable subset-that fits within it? And how can we efficiently compute an agreeable subset?

Our notion of agreeability is closely related to envyfreeness, a well-studied notion in fair division [Bouveret and Lemaˆıtre, 2014; Brams et al., 2012a; Chevaleyre et al., 2006; Cohler et al., 2011; Kash et al., 2013], and variants of agreeability have been considered in the literature [Aziz et al., 2015; Bouveret et al., 2010; Brams et al., 2012b]. An envyfree allocation is one in which every player weakly prefers her bundle to that of any other player. Both agreeability and envy-freeness involve players being happy if their allocation is at least as good as some other allocation(s). In previous work on fair division, each allocation is typically assigned to a single player, and the player compares the allocation that she receives with the allocations that other players receive. A novelty in our setting is the introduction of a social choice aspect to the allocation problem, i.e., we assign the same subset of items to multiple players with possibly wildly differing preferences. This corresponds to the social choice framework of aggregating individual preferences to reach a collective decision for the whole group [Arrow et al., 2002; Brandt et al., 2016]. 1 However, the envy-freeness condition is one-directional in our setting-there is no envy associated to the unassigned set of items. Our setting can also be seen as a multiagent knapsack problem in which every item has the same size and the agreeability condition is imposed, and it bears a resemblance to the consensus halving and necklace bisection problems [Alon and West, 1986; Simmons and Su, 2003].

For an arbitrary number of players, we derive tight upper bounds on the size for which a subset of that size that is agreeable to all players always exists when preferences are monotonic. Remarkably, even if the subset of items needs to be allocated to several players, the number of extra items that we might need to choose in order to accommodate all of them is quite small, i.e., half an item per additional player. We then present polynomial-time algorithms that compute an agreeable subset of approximately half of the items when there are two or three players and preferences are responsive. Our results translate to a 2-approximation on the individual welfare of every player when preferences are subadditive.

The assumptions that we make on the players' preferences, monotonicity and responsiveness, are practical in a broad range of settings. Monotonicity says that a player cannot be worse off whenever an item is added to her set, while the stronger notion of responsiveness says that a player 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. These assumptions are common in the literature 2 and have been made, for example, in [Brams and Fishburn, 2000; Brams et al., 2012b; Aziz, 2015; Lipton et al., 2004], with the latter two only assuming monotonicity. For our existence results we will only assume monotonicity, and we will assume responsiveness for our algorithms.

1 In fact, fair division can also be viewed as a social choice problem in the sense that a collective decision, concerning the allocation of the resources to the different players, has to be reached.

2 For a comprehensive treatment of properties concerning the ranking of sets of objects, we refer to [Barbera et al., 2004].

Even though the need to assign as many as half of the items even for two or three players might not seem that impressive at first glance, the reader should bear in mind that the conditions that we impose on the valuations functions are not many. For instance, monotonicity and responsiveness are generalizations of additivity, a very common assumption on preferences (e.g., [Dickerson et al., 2014]). Since we consider very general valuation functions, it is natural that the size of the selected set is relatively large. Indeed, in the simple case where we want to assign items to a single player whose preference only depends on the number of items and who prefers more items than less, we already need to assign to her at least half of the items. In this light, our result that we only need to assign half an item extra in the worst case for each additional player is quite intriguing.

An important issue when we discuss algorithms for computing desirable allocations is how we represent the players' preferences. Since preferences on subsets, unlike preferences on single items, might not have a succinct representation, this would already disallow algorithms that run in polynomial time in the number of players and the number of items if the algorithm were required to read the whole preference input. To circumvent this problem, we instead assume the existence of a preference oracle. In particular, we allow the algorithm to make a polynomial number of queries to the preference oracle. In each query, the algorithm can specify a player and two subsets of items to the preference oracle, and the oracle reveals the preference of that player between the two subsets. The use of the oracle model is common in computer science and in artificial intelligence in particular [Armstrong et al., 2012; Jain et al., 2011; McMahan et al., 2003].

2 Definitions and notation

In this section, we introduce the setting and give definitions and notation that we will use throughout this paper.

We consider n players, numbered 1↪ 2↪ ▷ ▷ ▷ ↪ n, who must collectively choose a subset of the set S = ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xm♦ of m indivisible items. Denote by S the set of all subsets of S. Each player 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 abuse notation and write x ⌫ y to mean ¶x♦ ⌫ ¶y♦.

Next, we define two properties of preferences that we will consider in the paper. Both properties are standard in the literature. The first property, monotonicity, says roughly that "more is better", i.e., a player cannot be worse off whenever an item is added to her set.

Definition 1. A preference ⌫ on S is monotonic if T [¶x♦ ⌫ T for all T ✓ S.

Note that if x 2 T , then T [ ¶x♦ ⌫ T always holds, so we only need to check when x 2 S∩T .

We will assume throughout most of the paper that preferences are monotonic. Monotonicity is a natural assumption in a broad range of situations. In particular, it implies free disposal of items, i.e., every item is considered to be of nonnegative value to each player.

The next property, responsiveness, says that a player 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. While stronger than monotonicity, responsiveness is still a reasonable assumption in many settings.

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

• ÷ ⌫ is monotonic;

Given two sets T1 = ¶xi1 ↪ xi2 ↪ ▷ ▷ ▷ ↪ xik ♦ with i1 < i2 < · · · < ik and T2 = ¶xj1 ↪ xj2 ↪ ▷ ▷ ▷ ↪ xjk ♦ with j1 < j2 < · · · < jk, T1 is said to lexicographically dominate T2 if the following two statements hold for some l 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ k♦:

• ÷ T∩¶y♦ [ ¶x♦ ⌫ T for all T ✓ S and x↪ y such that x ⌫ y, x 62 T and y 2 T .

For instance, one can check that the set ¶x1↪ x3↪ x5↪ x8♦ lexicographically dominates the set ¶x1↪ x3↪ x6↪ x7♦, while the set ¶x4↪ x5♦ does not lexicographically dominate the set ¶x3↪ x10♦.

We now consider two examples of preferences.

Example 1. Consider the preference ⌫1 on S defined as follows. For distinct subsets T1↪ T2 ✓ S, we have T1 ≻1 T2 if one of the following two conditions holds:

• ÷ ♣T1♣ > ♣T2♣;

For instance, when m = 3, the preference ⌫1 is given by ¶x1↪ x2↪ x3♦ ≻1 ¶x1↪ x2♦ ≻1 ¶x1↪ x3♦ ≻1 ¶x2↪ x3♦ ≻1 ¶x1♦ ≻1 ¶x2♦ ≻1 ¶x3♦ ≻1 ;.

• ÷ ♣T1♣ = ♣T2♣ and T1 lexicographically dominates T2.

Example 2. Consider the preference ⌫2 on S defined as follows. For distinct subsets T1↪ T2 ✓ S, we have T1 ≻2 T2 if one of the following three conditions holds:

• ÷ x1 2 T1 and x1 62 T2;
• ÷ x1 2 T1↪ T2 or x1 62 T1↪ T2, and ♣T1♣ = ♣T2♣ and T1 lexicographically dominates T2.
• ÷ x1 2 T1↪ T2 or x1 62 T1↪ T2, and ♣T1♣ > ♣T2♣;

For instance, when m = 3, the preference ⌫2 is given by ¶x1↪ x2↪ x3♦ ≻2 ¶x1↪ x2♦ ≻2 ¶x1↪ x3♦ ≻2 ¶x1♦ ≻2 ¶x2↪ x3♦ ≻2 ¶x2♦ ≻2 ¶x3♦ ≻2 ;.

One can check that the preferences in Examples 1 and 2 are both monotonic and responsive. Moreover, they share the same preference on the single items in S, i.e., x1 ≻ x2 ≻ · · · ≻ xm.

Definition 3. Player i regards a subset T ✓ S as agreeable if T ⌫i -T .

Next, we define the notion of agreeability. We denote the complement of a set T by -T := S∩T .

When preferences are monotonic, agreeability also implies that the player does not prefer any subset of the complement to her current set. That is, we have T ⌫i U for any U ✓ -T .

We now define two properties of subsets of items based on the preference on single items. In general, we will use ⌫ to denote the preference on S and ⌫sing to denote the preference on the single items in S. The first property, possible agreeability, says that a subset is "strictly agreeable" for some responsive preference consistent with the preference on single items.

Definition 4. Fix a preference ⌫sing on the single items in S. A subset T ✓ S is possibly agreeable with respect to ⌫sing if there exists a responsive preference ⌫ on S consistent with ⌫sing such that T ≻ -T.

The next property, necessary agreeability, concerns the situation in which a subset is agreeable for any responsive preference consistent with the preference on single items.

Definition 5. Fix a preference ⌫sing on the single items in S. A subset T ✓ S is necessarily agreeable with respect to ⌫sing if T ⌫ -T for any responsive preference ⌫ on S consistent with ⌫sing .

We now make a connection to the model in which every player has a cardinal utility for each subset of items. A utility function f is a function that maps any subset of items to a nonnegative real number. We assume that utility functions are monotonic, i.e., f(T1)  f(T2) for all subsets of items T1 ✓ T2. A utility function f is said to be additive if f(T1 [ T2) = f(T1) + f(T2) for all disjoint subsets of items T1 and T2, and is said to be subadditive if f(T1 [ T2)  f(T1) + f(T2) for all subsets of items T1 and T2. Any nonnegative monotonic additive utility function is also subadditive. Subadditive utility functions have been widely considered in the literature [Feige, 2009; Bhawalkar and Roughgarden, 2011].

When the preferences of the players are given by subadditive utility functions, a subset that a player regards as agreeable also gives the player a utility of at least 1◁2 of the utility that the player obtains from the whole set S of items. Indeed, for any such subset T we have f(S) = f(T [-T)  f(T)+f(-T)  2f(T), which implies that f(T) ≥ 12 f(S). Hence our results concerning subsets that are agreeable to every player also translate to a 2-approximation on the individual welfare of every player when preferences are subadditive.

3 Possibly and necessarily agreeable subsets

In this section, we investigate possibly and necessarily agreeable subsets and provide characterizations for such sets. The characterizations will later be useful in the analyses of our algorithms for computing an agreeable subset when there are two or three players. The following proposition shows a relationship between the two classes of subsets.

Proposition 1. Fix a preference ⌫sing on the single items in S. A subset T ✓ S is possibly agreeable with respect to ⌫sing if and only if -T is not necessarily agreeable with respect to ⌫sing .

Proof. Suppose first that T is possibly agreeable with respect to ⌫sing . By definition, there exists a responsive preference ⌫ on S consistent with ⌫sing such that T ≻ -T . This means that -T ⌫ T does not hold for the responsive preference ⌫. Hence -T is not necessarily agreeable with respect to ⌫sing . The converse can be shown similarly.

We now characterize possibly and necessarily agreeable subsets.

Proposition 2. Fix a preference ⌫sing on the single items in S with x1 ⌫sing x2 ⌫sing · · · ⌫sing xm. Let T ✓ S, and define Ik = ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xk♦ for all k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦.

(b) If T is possibly agreeable with respect to ⌫sing , then ♣Ik \ T ♣ > k2 for some k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦. The converse also holds if the preference ⌫sing is strict.

(a) If ♣Ik \ T♣ ≥ k2 for all k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦, then T is necessarily agreeable with respect to ⌫sing . The converse also holds if the preference ⌫sing is strict.

Proof. (a) Suppose first that ♣Ik \ T♣ ≥ k2 for all k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ m♦. Since ♣Im\T ♣ ≥ m2 , we have that ♣T ♣ ≥ ♣-T ♣. Let T 0 ✓ T be the subset consisting of the ♣ -T ♣ elements of T with the smallest indices.

Define a bijective function f : T 0 ! -T as follows: Given the element xk 2 T with the smallest index for which f(xk) is not yet defined, we define f(xk) to be the element in -T with the smallest index that has not occurred in the range of f so far. Since ♣Ik \ T♣ ≥ k2 for all k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦, the function f maps each element xk to another element xl with l > k. Hence T is necessarily agreeable with respect to ⌫sing .

(b) Suppose first that T is possibly agreeable with respect to ⌫sing . By Proposition 1, -T is not necessarily agreeable with respect to ⌫0 . Part (a) implies that ♣Ik \ -T♣ < k2 for some k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦. It follows that ♣Ik \T♣ > k2 for this value of k.

Now, suppose that the preference ⌫sing is strict, and that ♣Ik\T ♣ < k2 for some k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ m♦. Since the (b k2 c+1)- th element of -T has a smaller index than the (b k2 c + 1)-th element of T (if the latter element exists at all), there exists a responsive preference ⌫ on S consistent with ⌫sing such that -T ≻ T. Hence T is not necessarily agreeable with respect to ⌫sing .

When the preference ⌫sing is strict, the converse can be shown similarly to the converse of part (a).

4 Two players

In this section, we assume that there are two players and consider the problem of choosing a small subset that is agreeable to both players. We show that if preferences are monotonic, we can choose a subset of approximately half of the items that is agreeable to both players. Moreover, if we are given the preferences on the single items of the two players, we can choose a subset of approximately half of the items that is necessarily agreeable with respect to both preferences, and we present a polynomial-time algorithm to do so.

For arbitrary preferences that are not monotonic, the task of choosing any subset that is agreeable to two players might not be possible. Indeed, suppose that preferences are strict, and that the preference of one player is exactly the reverse of that of the other player. Then any subset is not agreeable for one of the players.

Nevertheless, when we impose the light assumption of monotonicity on the preferences, the following proposition shows that we can choose a subset of approximately half of the items that is agreeable to both players. Even though the proposition will later be generalized by Theorem 2, the proof of Theorem 2 relies crucially on a theorem best known as Kneser's conjecture, which we use as a black box. We believe that a direct proof of Proposition 3 may well be useful both for understanding and for applying the result.

Proposition 3. Assume that there are two players with monotonic preferences on S. There exists a subset T ✓ S such that ♣T ♣  ⌃ m+1 2 ⌥ and T is agreeable to both players. Moreover, there exist monotonic preferences for which the bound d m+1 2 e is tight.

Proof. Denote by ⌫1 and ⌫2 the preferences on S of the two players.

Assume first that m = 2k + 1 is odd. Suppose for contradiction that no subset of size at most k + 1 is agreeable to both players. Let T ✓ S be such that ♣T♣ = k. We begin by proving the following claim.

Claim: If T ≻1 -T, then T [ ¶x♦∩¶x0 ♦ ≻1 -T∩¶x♦ [ ¶x0 ♦ for any x 2 -T and x0 2 T .

We now use our claim to obtain the desired contradiction. Assume without loss of generality that ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xk♦ ≻1 ¶xk+1↪ xk+2↪ ▷ ▷ ▷ ↪ x2k+1♦. Applying our claim repeatedly to move elements between the two sets, we find that ¶xk+1↪ x2↪ ▷ ▷ ▷ ↪ xk♦ ≻1 ¶x1↪ xk+2↪ ▷ ▷ ▷ ↪ x2k+1♦, ¶xk+1↪ xk+2↪ x3↪ ▷ ▷ ▷ ↪ xk♦ ≻1 ¶x1↪ x2↪ xk+3↪ ▷ ▷ ▷ ↪ x2k+1♦, and so on, until finally ¶xk+1↪ xk+2↪ ▷ ▷ ▷ ↪ x2k♦ ≻1 ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xk↪ x2k+1♦. By monotonicity of the preferences, we have that ¶xk+1↪ xk+2↪ ▷ ▷ ▷ ↪ x2k+1♦ ≻1 ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xk♦, which contradicts our assumption that ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xk♦ ≻1 ¶xk+1↪ xk+2↪ ▷ ▷ ▷ ↪ x2k+1♦.

Proof of Claim: Suppose that T ≻1 -T, x 2 -T, and x0 2 T. It follows frommonotonicity of the preferences that T [¶x♦ ≻1 -T∩¶x♦. Since no subset of size at most k+1 is agreeable to both players, we have -T∩¶x♦ ≻2 T [ ¶x♦. By monotonicity of the preferences again, we have -T∩¶x♦ [ ¶x0 ♦ ≻2 T [¶x♦∩¶x0 ♦. Hence T [¶x♦∩¶x0 ♦ ≻1 -T∩¶x♦[ ¶x0 ♦, and our claim is proved.

Assume now that m = 2k is even. Let S0 be the set of all elements of S except x1. We know from the case of m odd that there exists a subset T ✓ S0 of size at most k such that T ⌫1 S0 ∩T and T ⌫2 S0 ∩T. Since the players have monotonic preferences, we have that T [ ¶x1♦ ⌫1 S0 ∩T and T [ ¶x1♦ ⌫2 S0 ∩T. This means that the set T [ ¶x1♦ of size k + 1 is our desired subset.

We omit the proof that the bound is tight due to space constraints.

While Proposition 3 shows the existence of a subset of approximately half of the items that is agreeable to both players, it does not show how to obtain such a subset. If preferences are also responsive, it is possible to lift preferences over single items to partial preferences over subsets. The next theorem shows that by considering only preferences over single items, it is possible to find a subset of approximately half of the items that is guaranteed to be agreeable to both players, no matter what the (responsive) preferences are.

Theorem 1. Assume that there are two players with preferences ⌫sing 1 and ⌫sing 2 on the single items in S. There exists a subset T ✓ S such that ♣T ♣  ⌃ m+1 2 ⌥ and T is necessarily agreeable with respect to both ⌫sing 1 and ⌫sing 2 . Moreover, there exist preferences on the single items in S for which the bound d m+1 2 e is tight. We also give a polynomial-time algorithm that finds such a subset T .

Proof. Assume first that m = 2k + 1 is odd, and suppose without loss of generality that x1 ⌫sing 1 x2 ⌫sing 1 · · · ⌫sing 1 x2k+1. One can check using Proposition 2 that the set ¶x1↪ x3↪ x5↪ ▷ ▷ ▷ ↪ x2k+1♦ is necessarily agreeable with respect to ⌫sing 1 . We choose our set T of k + 1 items as follows.

1. We choose x1.
2. Between each of the k pairs of items ¶x2↪ x3♦↪ ¶x4↪ x5♦↪ ▷ ▷ ▷ ↪ ¶x2k↪ x2k+1♦, we choose the item that is preferred according to ⌫sing 2 . If ⌫sing 2 is indifferent between any pair of items, we choose arbitrarily.

Since our set T is at least as good as the set ¶x1↪ x3↪ x5↪ ▷ ▷ ▷ ↪ x2k+1♦ with respect to ⌫sing 1 , and the latter set is necessarily agreeable with respect to ⌫sing 1 , T is also necessarily agreeable with respect to ⌫sing 1 . Moreover, since we choose the item that ⌫sing 2 prefers from each of the sets ¶x2↪ x3♦↪ ¶x4↪ x5♦↪ ▷ ▷ ▷ ↪ ¶x2k↪ x2k+1♦, T is also necessarily agreeable with respect to ⌫sing 2 . Hence T is necessarily agreeable with respect to both ⌫sing 1 and ⌫sing 2 .

Assume now that m = 2k is even. Let S0 be the set of all items of S except x1. We apply the algorithm from the case of m odd to choose a set T ✓ S0 of k items such that T is necessarily agreeable with respect to both ⌫sing 1 and ⌫sing 2 , when the universe considered is S0 . It follows that T [ ¶x1♦ is a subset of k+1 items that is necessarily agreeable with respect to both ⌫sing 1 and ⌫sing 2 , when the universe considered is S.

The tightness of the bound can be shown using players whose preferences are in opposite order of each other; we omit the details due to space constraints.

Since the algorithm in Theorem 1 only considers preferences on single items, it remains efficient even when the number of items is relatively large.

We can generalize the notion of necessary agreeability by defining a subset T ✓ S to be necessarily worth at least 1◁k with respect to ⌫sing for some fixed positive integer k ≥ 2 if the complement -T can be partitioned into k - 1 sets T1↪ T2↪ ▷ ▷ ▷ ↪ Tk-1 so that T ⌫ Ti for all i and any responsive preference ⌫ on S consistent with ⌫sing . Necessary agreeability then corresponds to being necessarily worth at least 1◁2. An algorithm similar to that in Theorem 1 yields a subset T ✓ S such that ♣T♣  ⌃ m+k-1 k ⌥ and T is necessarily worth at least 1◁k with respect to both ⌫sing 1 and⌫sing 2 . This bound is again tight.

5 Three or more players

In this section, we consider the problem of choosing a small subset that is agreeable to multiple players. We generalize Proposition 3 by showing that if preferences are monotonic, we can choose a subset of size approximately half of the number of items plus half of the number of players that is agreeable to all players. Moreover, if there are three players and preferences are also responsive, we present a polynomialtime algorithm for computing such a subset.

We begin with the following lemma.

Lemma 1. The graph with all k-element subsets of ¶1↪ 2↪ ▷ ▷ ▷ ↪ n♦ as vertices and with edges connecting disjoint sets has chromatic number n - 2k + 2 if n ≥ 2k, and 1 otherwise.

Lemma 1 was conjectured by Kneser, and is therefore best known as Kneser's conjecture [Kneser, 1955]. It was first resolved by Lov´asz using topological methods, and was later simplified several times, before Matouˇsek gave a purely combinatorial proof [Lov´asz, 1978; Matouˇsek, 2004]. The lemma will play a crucial role in our next theorem.

Proposition 3 shows that if there are two players, we can choose a subset of approximately half of the items that is agreeable to both players. It is natural to ask what happens when there are more than two players. Given that the preferences of the players can differ wildly, it is perhaps surprising that the price we need to pay is only approximately half an item for each additional player, as the following theorem shows.

Theorem 2. Assume that there are n players with monotonic preferences on S. There exists a subset T ✓ S such that ♣T ♣  min (⌃ m+n-1 2 ⌥ ↪m) and T is agreeable to all n players. Moreover, there exist monotonic preferences for which the bound min (d m+n-1 2 e↪m) is tight.

Proof. Let k = d m+n-1 2 e. If k ≥ m, the set S of all items has size m = min(k↪m) and is agreeable to all n players since preferences are monotonic. Assume from now on that k < m, and consider the graph G with all (m- k)-element subsets of ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xm♦ as vertices and with edges connecting disjoint sets. If all n players weakly prefer S∩T to T for some (m- k)-element subset T ✓ S, then S∩T is our desired subset of size k.

Suppose now that for any (m- k)-element subset T ✓ S, there exists a player who strictly prefers T to S∩T . We color the vertices of G with n colors 1↪ 2↪ ▷ ▷ ▷ ↪ n in the following way. For each vertex v of G corresponding to a set T, we color it with the color corresponding to a player who strictly prefers T to S∩T. If there is more than one such player, choose one arbitrarily.

By Lemma 1, the chromatic number of G is m- 2(mk) + 2 = 2k - m + 2 ≥ n + 1. Since we colored G with n colors, there exist two adjacent vertices sharing the same color, say, T1 and T2. This means that T1 ≻i S∩T1 and T2 ≻i S∩T2 for some player i. Since T1 and T2 are disjoint, we have T1 ✓ S∩T2 and T2 ✓ S∩T1. Monotonicity of preferences now implies that S∩T1 ⌫i T2 ≻i S∩T2 ⌫i T1, a contradiction to T1 ≻i S∩T1. This case is thus impossible, which implies that we can always find our desired subset T .

The tightness of the bound can be shown by having all but one players prefer any set with a particular distinct item to any without that item, and the last player preferring any set with a larger number of the remaining items than any with a smaller number. We omit the details due to space constraints.

We again ask the question of how to obtain a subset whose existence is guaranteed by Theorem 2. The following theorem provides a polynomial-time algorithm in the case of three players with responsive preferences. Since preferences on subsets, unlike preferences on single items, might not have a succinct representation, we assume that the algorithm is allowed to make a polynomial number of queries to a preference oracle. In each query, the algorithm can specify a player and two subsets of items to the preference oracle, and the oracle reveals the preference of that player between the two subsets.

The algorithm presented in the theorem is weaker than the one for two players in Theorem 1 in that it relies not only on preferences on single items but also on preferences on subsets.

Theorem 3. Assume that there are three players with responsive preferences ⌫1, ⌫2, and ⌫3 on S. There exists a subset T ✓ S such that ♣T♣  ⌃ m2 ⌥ + 1 and T is agreeable for all three players. Moreover, there exist responsive preferences for which the bound d m2 e + 1 is tight. We also give a polynomial-time algorithm that finds such a subset T .

Proof. The existence of a subset T ✓ S such that ♣T♣  d m2 e+1 and T is agreeable for all three players follows from Theorem 2. The tightness of the bound also follows, since one can make the preferences used to show tightness in Theorem 2 responsive. Next, we give an algorithm to find such a subset T .

Assume first that m = 2k is even. Suppose without loss of generality that x2k-1 is the most preferred item according to ⌫1, x2k is the most preferred item besides x2k-1 according to ⌫2, and that among the remaining 2k - 2 items, the preference ⌫1 ranks them as x1 ⌫1 x2 ⌫1 · · · ⌫1 x2k-2. One can check using Proposition 2 that the set

¶x2k-1↪ x2↪ x4↪ x6↪ ▷ ▷ ▷ ↪ x2k-2↪ x2k♦ is agreeable to player 1. Let A = ¶x1↪ x2↪ ▷ ▷ ▷ ↪ x2k-2♦, and consider the pairs (x1↪ x2)↪ (x3↪ x4)↪ ▷ ▷ ▷ ↪ (x2k-3↪ x2k-2). Let B be a set of k-1 elements containing an item from each pair that is less preferred by ⌫2 than its pair. If ⌫2 prefers the two items in some pair equally, we choose an arbitrary item from that pair.

While A∩B ⌫2 B, we remove an element from B that is less preferred by ⌫2 than its pair, and insert its pair into B. Since the preference is responsive and there are finitely many items, we eventually reach a point where B ⌫2 A∩B. We consider two cases.

Case 1: We have not performed any insertion into or removal from B. By definition of B, we have that A∩B ⌫2 B, and therefore A∩B ⇠2 B. Since preferences are monotonic, it follows that A∩B [ ¶x2k♦ ⌫2 B and B [ ¶x2k♦ ⌫2 A∩B.

Case 2: We have performed some insertion into or removal from B. Suppose that our last insertion was on x2i-1 and our last removal was on x2i. Let C = A∩(B [ ¶x2i♦) [ ¶x2i-1♦ and D = B∩¶x2i-1♦ [ ¶x2i♦. We have that C ≻2 D and B ⌫2 A∩B, and it follows from the monotonicity of preferences that C [ ¶x2k♦ ⌫2 D and B [ ¶x2k♦ ⌫2 A∩B. We will show that at least one of D[ ¶x2k♦ ⌫2 C and A∩B [ ¶x2k♦ ⌫2 B holds.

In both Cases 1 and 2, we can find a subset E ✓ A of k - 1 elements containing an item from each of the pairs (x1↪ x2)↪ (x3↪ x4)↪ ▷ ▷ ▷ ↪ (x2k-3↪ x2k-2) such that E [ ¶x2k♦ ⌫2 A∩E and A∩E [ ¶x2k♦ ⌫2 E. This set E will be crucial in the description of our algorithm.

Suppose for contradiction that C ≻2 D [ ¶x2k♦ and B ≻2 A∩B[¶x2k♦. Then by the responsiveness of preferences, we have C ≻2 D [ ¶x2k♦ ⌫2 B ≻2 A∩B [ ¶x2k♦ ≻2 C, a contradiction. Hence at least one of D [ ¶x2k♦ ⌫2 C and A∩B [ ¶x2k♦ ⌫2 B holds.

We choose our set T of k + 1 items as follows.

1. We include x2k-1 and x2k in T.
2. We include in T either E or A∩E according to which one player 3 prefers. (If player 3 is indifferent between the two sets, we choose one of them arbitrarily.)

Next, we claim that our chosen set T is agreeable for all three players. We prove the claim separately for each of the players.

• ÷ From the perspective of player 1, the worst set T we could have chosen is ¶x2k-1↪ x2↪ x4↪ x6↪ ▷ ▷ ▷ ↪ x2k-2↪ x2k♦. Since this set is agreeable to player 1 and preferences are responsive, our set T is agreeable to player 1.
• ÷ Since E [ ¶x2k♦ ⌫2 A∩E and A∩E [ ¶x2k♦ ⌫2 E and we include the remaining item x2k-1, T is also agreeable for player 2.
• ÷ Since we choose the set E or A∩E that player 3 prefers and we include both of the remaining items x2k-1 and x2k, T is also agreeable for player 3.

Hence T is agreeable for all three players, as desired. This concludes the case m even.

Assume now that m = 2k + 1 is odd. Let S0 be the set of all items of S except x1. We apply the algorithm from the case of m even to choose a set T ✓ S0 of k + 1 items such that T is agreeable for all three players, when the universe considered is S0 . It follows that T [¶x1♦ is a subset of k+2 items that is agreeable for all three players, when the universe considered is S.

Even though the algorithm in Theorem 3 also relies on preferences on subsets, the number of subsets involved in the algorithm is only linear in the number of items, hence the algorithm remains efficient even when the number of items is relatively large.

One may ask whether we may restrict the algorithm in Theorem 3 to rely only on preferences on single items similarly to the case of two players. The following example shows that the answer is negative. In particular, a necessarily agreeable subset of size at most min (⌃ m+n-1 2 ⌥ ↪m) does not always exist.

Example 3. Suppose that there are six items x1↪ ▷ ▷ ▷ ↪ x6, and consider the following preferences ⌫1↪⌫2↪⌫3 of three players on the single items:

If we had access to the preferences on subsets, the algorithm in Theorem 3 would yield a subset of ⌃ 62 ⌥ + 1 = 4 items that is agreeable to all three players. However, to obtain a necessarily agreeable subset, we need to include all of x1↪ x2↪ x3 as they are most preferred by at least one player. Moreover, choosing only one of x4↪ x5↪ x6 does not yield a necessarily agreeable subset for the player who ranks that item fourth. Hence a necessarily agreeable subset contains at least five items.

6 FutureWork

Our work suggests a number of possible future directions. With the polynomial-time algorithms for two and three players in mind, a natural question to ask is whether we can similarly obtain efficient algorithms for more players. The algorithm for three players is already quite involved, so one might suspect that the problem is intractable for larger numbers of players. If that were to be the case, it would be useful to have a confirmation by means of a hardness result, even for some fixed large number of players. Since the problem is a search problem in which we know that a solution always exists, the problem would not be NP-hard, but could potentially be hard with respect to some subclass of TFNP such as PPAD or PLS. One could also ask about the NP-hardness of deciding the existence of an agreeable subset of some smaller size for which there is no guarantee of existence.

Since the algorithm in Theorem 3 relies on preferences on subsets, we can consider a different setting in which we are not given access to preferences on subsets but only to preferences on single items. In this setting, we need to choose a subset that is necessarily agreeable to all three players, and as Example 3 shows, this may well force us to choose more items than we need to in the case where we have access to preferences on subsets. We can ask how many items we need to choose in the worst case, and whether there exists an efficient algorithm to compute those items. Of course, the same question can be asked for the corresponding setting with more players as well.

An interesting related question that goes beyond our setting is the following: When is it possible to obtain an envy-free allocation between two (or more) parties if there are multiple players in each party, possibly with wildly differing preferences? To the best of our knowledge, the fair-division literature has so far only focused on settings in which each party consists of a single player. Whether we can come up with an algorithm along the lines of the undercut procedure [Brams et al., 2012b] to find an envy-free allocation in the multipleplayer setting when one exists is an appealing direction that we leave for future research.