{'fraction_non_alphanumeric': 0.05299442235401088, 'fraction_numerical': 0.016040821311764625, 'mean_word_length': 3.6184895017235976, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Communication Complexity of Discrete Fair Division

We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.


Introduction
Fair division studies the problem of distributing resources among competing players in a "fair" way, where each player has equal claim to the resources. There are many different notions of fairness, with the two most prominent being envy-freeness and proportionality. An allocation is envy-free (EF) if each player's value for her own bundle is at least as much as her value for any other player's bundle. An allocation is proportional (Prop) if each player's value for her bundle is at least 1/n of her value for the entire set of items, where n is the number of players.
In discrete fair division, the resources consist of indivisible items: each item must go to a single player and cannot be split among players. Unfortunately, neither envy-freeness nor proportionality can be guaranteed in this setting. Consider two players and a single item: one must receive the item while the other receives nothing, so the allocation is neither envy-free nor proportional. We study the problem of finding an envy-free (or proportional) allocation, or showing that none exists.
We also consider approximate versions of these properties: for c ∈ [0, 1], an allocation is c-EF if each player's value for her own bundle is at least c times her value for any other player's bundle, and an allocation is c-Prop if each player's value for her bundle is at least c/n of her value for the entire set of items. Thus 1-EF and 1-Prop are standard envy-freeness and proportionality, respectively. The same counterexample of two players and a single item shows that these approximate properties also cannot be guaranteed for any c > 0. 1 From a computational complexity viewpoint, this problem is hard even when player valuations are additive, meaning that a player's value for a set of items is the sum of her values for the individual items. For two players with identical additive valuations, determining whether a 1-EF or 1-Prop exists is NP-hard, via a simple reduction from the partition problem [3].
It is arguably even more natural to study fair division from a communication complexity perspective, where there is no centralized authority and each player initially knows only her own preferences.
When players have combinatorial valuations, their values for a bundle cannot just be decomposed into their values for the individual items. 2 In particular, for m items, a combinatorial valuation may contain 2 m different values. The primary question is to determine whether players need to exchange an exponential amount of information to compute a fair allocation, or whether the problem can be solved using only polynomial communication. This question has not been studied previously, despite the rich literature on communication complexity in combinatorial auctions (e.g. [22,21,12]).
Our paper can also be thought of as formally studying the difficulty of eliciting different classes of valuations from a fair division standpoint. Additive valuations are typically used in practice (for example on the non-profit website Spliddit [15]) because each player need only report one value for each item to specify the entire valuation. Richer combinatorial valuations allow for more expressiveness, but may be more difficult to elicit. Our work formally studies the tradeoffs between these factors.

Our results
We study the following question: "Given n players and m items, a fairness property P ∈ {EF, Prop}, and a constant c ∈ [0, 1], how much communication is required to either find a c-P allocation, or show that none exists?" 3 We are primarily interested in whether this can be done with communication polynomial in m. The answer to this question will depend on n, P , and c. We also consider when player valuations are restricted to be submodular or subadditive, as well as deterministic vs. randomized protocols.
All in all, we give a full characterization of the communication complexity for every combination of the following five parameters: One of our results (Section 7) shows that there is no hope for a polynomial communication protocol for more than two players: exponential communication is required for every n > 2, for either P ∈ {EF, Prop}, for any c > 0, even for submodular valuations, and even for randomized protocols. The (very important) two-player case is surprisingly rich, however, with multiple phenomena occurring across different valuation classes and constants c. The results for two players in the deterministic setting are summarized in Table 1. It is also surprising that there is such a chasm between the twoand three-player cases; for example, there is no analogous chasm for maximizing the social welfare in combinatorial auctions.
Furthermore, in contrast to combinatorial auctions, the two-player setting is fundamental in fair division. Indeed, the first known mention of fair division is in the Bible, when Abraham and Lot use the cut-and-choose method to divide a piece of land. In modern day, one of the primary applications of fair division for indivisible items is divorce settlements, which is fundamentally a two-player setting. Fair Outcomes Inc. 4 , a commercial fair division website, only allows for two players. Other applications of fair division, such as dividing an inheritance and international border disputes, are also often two player settings. Unless otherwise mentioned, we assume that n = 2 throughout the paper.  Table 1: A summary of our results for the two-player deterministic setting. For both c-EF and c-Prop, we characterize exactly when the problem is easy (i.e., can be solved with communication polynomial in the number of items) and hard (i.e., requires exponential communication). We note that the protocol for Theorem 4.1 has communication cost exponential in 1 1−c , and the corresponding lower bound (Theorem 6.1) rules out a protocol with communication cost polynomial in 1 1−c . See Section 1.1.2 for additional discussion.
c ≤ 1 in the special case of subadditive (and hence also submodular) valuations. This resolves the randomized setting.
Finally, we briefly consider the maximin share property in Section 10, and prove exponential lower bounds in that setting as well.

Ideas behind our protocols
Since the problem is always hard when n > 2, all of our upper bounds are in the two-player setting. All of our positive results require the following condition: for any partition of the items into two bundles A 1 and A 2 , each player must be happy with at least one of A 1 and A 2 . This is always true for envy-freeness: a player is always happy with whichever of A 1 and A 2 she has maximum value for (she could be happy with both bundles if they have equal value to her). This is not satisfied for proportionality in general, for example if a player has value zero for each of A 1 and A 2 , but positive value for A 1 ∪ A 2 . However, it is satisfied for subadditive valuations.
All of our deterministic protocols have the same first step: if there is any allocation where player 1 would be happy to receive either bundle, she specifies that allocation to player 2, and player 2 selects her preferred bundle. Player 2 is guaranteed to be happy with at least one of the bundles by the above condition, and player 1 is happy with either bundle in this allocation, so she is happy as well.
The key to the analysis is what happens when there is no allocation such that player 1 is happy with either bundle. It will turn out that the absence of such an allocation implies certain structure in the valuations. The exact structure, and the way the structure is exploited, depends on the setting (valuation class, property P , and constant c).
For example, consider the case of subadditive valuations and 1 2 -EF. We show that if there is no allocation where player 1 is happy with either bundle, then there must exist a single item that player 1 values more than the rest of the items combined. Then player 1 can simply specify that item to player 2. If player 2 is happy with the rest of the items, we have found a satisfactory allocation. Otherwise, there is no satisfactory allocation, since player 1 and player 2 both care about that particular item more than the rest of the items combined.
Furthermore, this protocol gives an additional guarantee. If a c-P allocation is not returned, the protocol will return the fairest allocation possible, i.e., a c ′ -P allocation where no allocation is c ′′ -P for any c ′′ > c ′ . For brevity, we will use c * to refer to the maximum c ′ such that a c ′ -P allocation exists. 6 If player 2 determines that a c-P allocation does not exist, then there is a single item g that both players care about more than all of the other items together. One player will have to not receive item g, and the protocol gives g to the player who will be most unhappy otherwise. This yields a c * -P allocation. In fact, all of our deterministic protocols give this guarantee, although slightly more work is required to achieve it in other settings.

Minimal bundles
The reasoning described above is actually a special case of analyzing what we call minimal bundles. We say that a bundle is minimal for some player if that player is happy with the bundle, but is not happy with any strict subset of that bundle. 7 The minimal bundles represent the most a player is willing to compromise. If a player does not receive one of her minimal bundles (or a superset thereof), she cannot be happy, by definition. On the other hand, if a player receives one of her minimal bundles (or a superset thereof), she is guaranteed to be happy. 8 Thus it is both necessary and sufficient for each player to receive one of her minimal bundles (or a superset thereof). By this reasoning, it is sufficient for player 1 to specify all of her minimal bundles to player 2: player 2 can then determine if there is an allocation which satisfies her (player 2), while still giving player 1 one of player 1's minimal bundles.
The general Minimal Bundle Protocol (Protocol 2) is as follows. If there is an allocation where player 1 is happy with either bundle, she specifies that allocation to player 2, and we are done. Otherwise, player 1 specifies all of her minimal bundles to player 2, who searches for a satisfactory allocation. If player 2 fails to find one, she declares that no satisfactory allocation exists. There is a final step that is used to guarantee that a c * -P allocation is returned if no c-P allocation is found; this will be described later.
The key is proving that the number of minimal bundles is polynomial in m, and this analysis varies based on the context. For example, for subadditive valuations and 1 2 -EF, we discussed above how if there is no allocation where player 1 is happy with either bundle, there must be a single item g that she values more than all of the other items together. This means that player 1 has a single minimal bundle: {g}.
We also use the protocol to give a PAS for EF in the submodular setting: we show that for every fixed c < 1, the number of minimal bundles is at most 2(m + 1) 8 1−c , and thus the protocol uses polynomial communication for any fixed c. The analysis for this case is technically involved and involves constructing what we call the "minimal bundle graph" for player 1's valuation. The vertices in this graph are the minimal bundles, and two vertices share an edge if the corresponding bundles overlap by exactly one item (it will be impossible for two minimal bundles to overlap by more than one item). For some of these edges, moving the overlapping item between bundles will cause a large change in value: these special edges will play an important role. We will show that the only way to have a large number of minimal bundles is for there to be a large number of these special edges, but submodularity will imply an upper bound on how many special edges can be incident on a single vertex, and hence an upper bound on the total number of special edges.
The Minimal Bundle Protocol is correct for any valuation class, property P , or constant c. However, in some contexts, the number of minimal bundles may be exponential. Our lower bound constructions all involve valuations with an exponential number of minimal bundles. 6 It is possible that c * = 0 (for example, in the case of two players and one item), but our protocol at least certifies that this is the best possible. 7 A similar notion of "minimal bundles" features prominently in [4]. 8 We assume monotonicity: adding items to a bundle cannot decrease its value.

Related work
Fair division has a long history, and a full survey of this field is outside of the scope of this paper: see e.g. [6,5,18] for further background. There are several approaches for handling the fundamental asymmetry of indivisible items, where neither envy-freeness or proportionality can be guaranteed. One natural question is whether there are other compelling properties that can be guaranteed [23,10,8,17]. Another possibility is to allow for randomized allocations and search for allocations that are fair in expectation [2,9].
Although EF and Prop allocations do not always exist, they often do. For example, [11] showed that when the number of items is at least a logarithmic factor larger than the number of players, envy-free allocations are likely to exist. If a fully envy-free or proportional allocation does exist in a particular instance, it may be preferable to choose that allocation before resorting to weaker properties or randomization. In this paper, we address the question of determining whether a c-EF or a c-Prop allocation exists, and if so, finding one.
Communication complexity was first studied by [25]. The paper most relevant to our work is [22], which shows that maximizing social welfare requires exponential communication, even for two players with submodular valuations. Furthermore, they show that for general valuations, any constant factor approximation of the social welfare requires exponential communication to compute. Although they do not mention envy-freeness, proportionality, or fair division, some of their arguments can be adapted to prove exponential lower bounds for some (but not all) of the cases that we study.
A recent and complementary line of work is presented in [7]. They study the communication complexity of fair division with divisible goods (also known as "cake cutting"), where each resource can be divided into arbitrarily small pieces. Their paper complements ours with no overlap. Together, our papers give a comprehensive picture of the communication complexity of fair division in both the indivisible and divisible models.
The organization of the rest of the paper is as follows. Section 2 formally presents the model. Section 3 presents our 1-Prop protocol for submodular valuations. In Section 4, we discuss the PAS for 1-EF for submodular valuations. Section 5 describes our general lower bound approach, and proves a lemma that we will use to prove lower bounds later on in a standardized way. Section 6 uses that lemma to prove hardness for 1-EF for submodular valuations, which shows that the PAS from Section 4 is optimal. Section 7 shows that the problem is always hard for more than two players, even for submodular valuations and even in the randomized setting. The rest of the paper is focused on resolving the two player case. Section 8 presents the upper and lower bounds for subadditive valuations. Section 9 considers general valuations, and also handles the randomized two player setting. Table 1 will be complete after this section. Finally, we consider the maximin share property (to be defined later) in Section 10.

Model
We formally introduce the discrete fair division model in Section 2.1, and the communication complexity model in Section 2.2.

Fair division
Let [k] denote the set {1...k}. Let N = [n] be the set of players, and let M be the set of items, where |M | = m. We assume throughout the paper that items are indivisible, meaning that an item cannot be split among multiple players. Player i's value for each subset of M is specified by a valuation v i : 2 M → R ≥0 . We refer to a subset of M as a bundle.
We assume throughout the paper that valuations obey monotonicity (adding items to a bundle cannot decrease the value of the bundle) and normalization (v i (∅) = 0), and that v i (M ) > 0. We refer to set of the valuations constrained only by these three properties as "general valuations".
There are many commonly studied subclasses of valuations, such as subadditive and submodular. A valuation v is subadditive if for all bundles S and Every submodular valuation is subadditive, but not every subadditive valuation is submodular. Thus a problem that is hard for subadditive valuations may become tractable if valuations are restricted to be submodular. Similarly, problems that are hard for general valuations may be easier for subadditive valuations.
An allocation is a partition of M into n disjoint subsets (A 1 , A 2 ...A n ), where A i is the bundle allocated to player i. The goal is to find a "fair" allocation. The two most prominent fairness notions for indivisible items are envy-freeness and proportionality. Envy-freeness states that no player strictly prefers another player's bundle to her own, and proportionality states that every player receives at least 1/n of her value for the entire set of items. We can also define approximate versions of these properties: Thus 1-EF is standard envy-freeness, and 1-Prop is standard proportionality. We will say that a player is (c, P )-happy with an allocation A if property c-P is satisfied from her viewpoint. Specifically, when P = EF, we will say that player i is (c, P )-happy with allocation A if v i (A i ) ≥ c·v i (A j ) for all j. For P = Prop, we will say a player i is (c, P )-happy if v i (A i ) ≥ c n v i (M ). We will typically leave P implicit, and just say that player i is c-happy. We sometimes also leave c implicit, and just say that player i is happy.
A instance of Fair Division consists of a set of players N , a set of items M , player valuations (v 1 ...v n ), a fairness property P ∈ {EF, Prop}, and a constant c ∈ [0, 1]. The goal is to find an allocation satisfying c-P , or show that none exists.

Two players
We use the following additional terminology when n = 2. For a player i, we will use i to denote the other player. For an allocation A = (A 1 , A 2 ), let A be the allocation (A 2 , A 1 ). Also, when n = 2, knowing player i's bundle uniquely determines the overall allocation, since player i simply has every item not in player i's bundle. Therefore, with slight abuse of notation, we say that player i is c-happy with bundle S if player i is c-happy with the allocation A where A i = S and A i = M \S.

Communication complexity
We assume that each player knows only her own valuation v i , and does not know anything about other players' valuations. In order to solve an instance of Fair Division, players will need to exchange information about their valuations. We assume that all players know N, M, P , and c. Since there 2 m subsets of M , specifying a bundle requires m bits. We will use v size to refer to the number of bits required to represent a value v i (S). We assume that v size is polynomial in m, otherwise sending even a single value would rule out a polynomial communication protocol.
A (deterministic) protocol Γ specifies which player should speak (and what she should say) as a function of the messages sent so far, and terminates when a player declares that an allocation A satisfies c-P , or when a player declares that no c-P allocation exists. For fixed N, M, P , and c, we define the communication cost of a protocol Γ to be the maximum number of bits Γ sends across all player valuations v 1 ...v n . Formally, let C Γ (N, M, (v 1 ...v n ), P, c) be the number of bits that Γ communicates when run on the fair division instance (N, M, (v 1 ...v n ), P, c). Then the communication We define the deterministic communication complexity D(n, m, P, c) as the minimum communication cost of any protocol Γ which correctly solves Fair Division for n players, m items, property P and constant c. Formally, where Γ ranges over all correct deterministic protocols.
In a randomized protocol Γ R , each player also has access to an infinite stream of random bits. The protocol should correctly solve Fair Division with probability 2/3 (say) over these random bits. Like the deterministic setting, the communication cost of Γ R is the number of bits Γ R communicates for a worst-case choice of v 1 ...v n . We can similarly define the randomized communication complexity R(n, m, P, c) as the minimum communication cost of any randomized protocol Γ R which correctly solves Fair Division with probability at least 2/3. Formally, R(n, m, P, c) = min where Γ R ranges over all correct randomized protocols. If valuations are restricted to be subadditive or submodular, the problem may become easier, so D(n, m, P, c) and R(n, m, P, c) may be affected. We use D subadd (n, m, P, c) and D submod (n, m, P, c) to denote the deterministic communication complexity when valuations are restricted to be subadditive and submodular, respectively (and similarly for R subadd (n, m, P, c) and R submod (n, m, P, c)). The following relationships are immediate, for all n, m, P, and c: R(n, m,P, c) ≤ D(n, m, P, c) D submod (n, m, P, c) ≤ D subadd (n, m, P, c) ≤ D(n, m, P, c) R submod (n, m, P, c) ≤ R subadd (n, m, P, c) ≤ R(n, m, P, c) Another factor that may affect the communication complexity is how the players gain access to random bits. In the public-coin model, the players can also see other players' streams of random bits; in the private-coin model, each player sees only her own stream. This distinction is not significant in our setting, however, due to the following theorem by [19]. Thus we will assume all randomized protocols to be public-coin for the rest of the paper. Finally, we mention the multiparty (i.e., n > 2) communication complexity model. There is more than one such model: for example, do players communicate in a peer-to-peer fashion, or is each message broadcast for all of the players to see? We discuss in Section 7 how this turns out not to matter in our setting.

An upper bound for 1-Prop with submodular valuations
This section presents our first result: a deterministic protocol for 1-Prop, when there are two players, and when valuations are submodular. The protocol will communicate just m + 1 values and a single bundle. Our protocol either finds a 1-Prop allocation or a c * -Prop allocation. Recall that c * is the maximum c such that a c-P allocation exists. 9 We prove the following theorem: It will be important that the following condition is satisfied in this setting: Condition 3.1. For every allocation A, each player is happy with at least one of A and A.
Recall that for an allocation A = (A 1 , A 2 ), A = (A 2 , A 1 ). This condition is satisfied for proportionality with subadditive valuations (and hence also satisfied for submodular valuations): for all c ∈ [0, 1]. Thus player i is always happy if she receives the bundle arg max v i (A 1 ), v i (A 2 ) . Also, we assume in this section that v 1 (M ) = 1, without loss of generality: were this not the case, we could simply rescale v 1 as needed. Let M = (g 1 , g 2 ...g m ) be an arbitrary ordering of the items. Consider starting from the empty set and adding the items in M one at a time in this order. We define δ M k as player 1's marginal value of adding g k in this process: The protocol is as follows. The first step is common to all of our deterministic protocols: player 1 checks if there is an allocation A where she is happy with both A and A. If so, player 2 can choose whichever she prefers, and we are done by Condition 3.1. If this fails, the following condition is satisfied:

Condition 3.2. There is no allocation A for which player 1 is happy with both A and A.
In this case, player 1 sends the values (δ M 1 , δ M 2 ...δ M m ) to player 2. For every bundle S, player 2 needs to be able to figure out whether player 1 likes S or M \S. To do this, player 2 simply pretends that player 1's valuation is additive where δ M k is the value of item g k . Formally, let χ(S) = g k ∈S δ M k : player 2 pretends that v 1 (S) = χ(S). This will not be a perfect estimate of v 1 , of course, but player 2 does not need to know the exact value of v 1 (S): she only needs to know whether player 1 is happy with S.
Lemma 3.1 shows that this actually works: assuming Condition 3.2, v 1 (S) ≥ 1/2 if and only if χ(S) ≥ 1/2. We informally argue why this is case. Crucially, submodularity implies that χ(S) will be an underestimate of so player 1 is happy with S. Then by Condition 3.2, we know that player 1 is not happy with M \S. Therefore, for any bundle S, player 2 can correctly use χ as a proxy for v 1 to determine which of S and M \S player 1 is happy with. Thus χ is sufficient for her to determine whether or not a 1-Prop allocation exists, and if so, find one. This lemma is the heart of Protocol 1.
Step 4, S * (v i ), and c i (S * (v i )) are necessary only for finding a c * -Prop allocation if no 1-Prop allocation is found. For a bundle S and property P , let Although this section considers only proportionality, we allow for either P ∈ {EF, Prop} in our definitions, since we will use this terminology again in later sections. We will typically leave P implicit and write c i (S).
For each player i, we define a special bundle In words, S * (v i ) the bundle that player i is the most happy with, out of all of the bundles she is not fully happy (i.e., c-happy) with. It will be useful for the analysis to define δ S i for an arbitrary bundle S. First, let Proof. We first claim that for any bundle S and any item and for all k and S. Therefore for any bundle S, Protocol 1 Protocol for two players with submodular valuations to either find a 1-Prop allocation or a c * -Prop allocation.
Private inputs: v 1 , v 2 Public inputs: the ordering of M = {g 1 , g 2 ...g m } 1. If there exists an allocation A where player 1 is happy with both A and A, player 1 sends that allocation to player 2. If player 2 is happy with A, she declares that A is 1-Prop, otherwise she declares that A is 1-Prop.

Player 2 first checks if there exists any bundle
Since χ(M \S) < 1/2, we have χ(S) ≥ 1/2. , c 1 (S * (v 1 )) requires a single value to communicate. Thus in this case, m + 1 values and one bundle are communicated, so the communication cost is (m + 1)v size + m. Therefore the communication cost bound is satisfied.
It remains to prove correctness. Suppose the protocol terminates in step 1. By Condition 3.1, player 2 is happy with at least one of A and A. Therefore player 2 is happy with whichever of A and A she declares to be 1-Prop. Player 1 is happy with both A and A, so she is also happy. Therefore if the protocol terminates in step 1, the declared allocation is in fact 1-Prop.
Suppose the protocol does not terminate in step 1. We assume Condition 3.2 for the remainder of the proof. Suppose player 2 declares that (S, M \S) is 1-Prop in step 3: then So suppose the protocol does not terminate until step 4. We first claim that no 1-Prop allocation exists. Suppose that a 1-Prop allocation A does exist: then v i (A i ) ≥ 1/2 for both i. Since the protocol did not terminate in step 1, we have Condition 3.2. Thus by Lemma 3.1, χ( so the protocol should have terminated in step 3, which is a contradiction. Therefore no 1-Prop allocation exists. It remains to show that we return a c * -Prop allocation in this case. Let i = arg max i ′ ∈{1,2} c i ′ (S * (v i ′ )) as computed by player 2 in step 4. Let A be the allocation returned by the protocol in this case: )-happy with A by definition, and we claim that player i is 1-happy with A. If i were not 1-happy with A, then she must be 1-happy with A by Condition 3.1. Furthermore, Since player i is not 1-happy with A, she must be 1-happy with A also by Condition 3.1. But then both players are 1-happy with A, which is a contradiction.
. We know that player i cannot be happier than c i (S * (v i ))-happy without being 1-happy, so player i must be 1-happy with A ′ . That implies that player 2 is not 1-happy with A ′ , since no allocation makes both players 1-happy in this case. But then the happiest player i can be is c i (S * (v i )), and c i (S * (v i )) ≤ c i (S * (v i )) by assumption. Thus for any allocation, there is a player who is at most c i (S * (v i ))-happy. Therefore no allocation is c-Prop for any c > c i (S * (v i )).

PAS for EF with submodular valuations
In this section, we prove our other positive result for specifically submodular valuations: a deterministic protocol for c-EF when c < 1, and when there are two players. This is our most technically involved result. We prove the following theorem: Theorem 4.1. For two players with submodular valuations and any c < 1, Protocol 2 has communication cost at most 2m(m + 1) 8 1−c + 2v size , and either returns a c-EF allocation or a c * -EF allocation. This also implies that This constitutes a polynomial-communication approximation scheme (PAS): the communication cost approaches infinity exponentially as c goes to 1, but for any fixed constant c < 1, it is polynomial in m. 10 We use much of the same terminology from Section 3: in particular, c P i (A), S * (v i ), S ≤k , and δ S k . Also, recall the following condition: This is satisfied for c-EF for any c ∈ [0, 1], even for general valuations: Our PAS protocol will use the minimal bundle analysis discussed in Section 1.2. For a fixed constant c, we say that a bundle S is minimal for a particular player if that player is c-happy with S, but for all g ∈ S, she is not c-happy with S\{g}. We use S to denote the set of player 1's minimal bundles: each S ∈ S is a minimal bundle for player 1. Also, in this section, we assume that v 1 (M ) = 1.

The protocol
We now describe Protocol 2, also known as the Minimal Bundle Protocol. Although we only consider envy-freeness in this section, we define Protocol 2 for either P ∈ {EF, Prop}. We will use this same protocol in Section 8.1 to prove upper bounds for both envy-freeness and proportionality in the subadditive case.
First, if there is an allocation A where player 1 is happy with both A and A, we are done: player 2 chooses her favorite of A and A, and she is guaranteed to be happy with at least one them by Condition 3.1. If there is no such allocation A, player 1 sends the set S of all of her minimal bundles to the other player. We will prove that in our setting, the number of minimal bundles sent in step 2 must be polynomial in m. Specifically, we will show that |S| < 2(m + 1) The minimal bundles represent the most player 1 is willing to compromise while still being happy: she does not require anything more than a minimal bundle, but she is not happy with any strict subset of any of her minimal bundles. In this way, receiving a minimal bundle is both necessary and sufficient for player 1 to be happy. Using this reasoning, we will show that knowing S is sufficient for player 2 to find a c-P allocation or show that none exists. Finally, step 4 is identical to that of Protocol 1, and is used to find a c * -P allocation when no c-P allocation exists.

Correctness
We now formally prove the correctness of Protocol 2. We will prove a few helpful lemmas before proving the main correctness lemma (Lemma 4.4). Proof. The only two steps that can declare an allocation to be c-P are steps 1 and 3. Suppose the protocol declares an allocation to be c-P in step 1. Then by assumption, there exists an allocation A where player 1 is happy with both A and A. If player 2 declares A to be c-P , then both players Protocol 2 Protocol for two players to either find a c-P allocation or a c * -P allocation.
Public inputs: P, c 1. If there exists an allocation A where player 1 is happy with both A and A, player 1 sends that allocation to player 2. If player 2 is happy with A, she declares that A is c-P , otherwise she declares that A is c-P .
2. If there is no such allocation A, player 1 sends the set S of her minimal bundles to player 2. She also sends the bundle S * (v 1 ) and the value c 1 (S * (v 1 )).
3. Player 2 first checks if there exists a bundle S ∈ S where player 2 is happy with M \S. If so, she declares that (S, M \S) is c-P .
are happy with A, and the claim is satisfied. If player 2 declares A to be c-P , then she was not happy with A. By Condition 3.1, player 2 is happy with A. Thus A is c-P in this case, so the lemma is satisfied if the protocol terminates in step 1. Suppose the protocol declares an allocation to be c-P in step 3. Then the allocation declared can be written as (S, M \S) for some S ∈ S. Since S is minimal, player 1 is happy with S by assumption, and player 2 only declares an allocation to be c-P in this step if she is happy with it. Thus the lemma is satisfied in this case as well. Proof. ( =⇒ ) Suppose player 1 is happy with bundle S. If S is minimal, we are done, so assume S is not minimal. Then there exists g ∈ S where player 1 is happy with S\{g}. If S\{g} is not minimal, there again exists some g ′ ∈ S\{g} that we can remove, and this process can be repeated until we obtain some minimal subset of S.
( ⇐= ) Suppose there exists a minimal bundle T where T ⊆ S. Then by monotonicity, v 1 (S) ≥ v 1 (T ). Since T is minimal, player 1 is happy with T . If P = Prop, this is sufficient to show that player 1 is happy with S. If P = EF, it is also necessary to note that v 1 (M \S) ≤ v 1 (M \T ), again by monotonicity. Thus the claim holds for both P ∈ {EF, Prop}. Proof. If no c-P allocation exists, the protocol does not declare any allocation to be c-P by Lemma 4.1. Thus assume a c-P allocation A exists. Then player 1 is happy with A 1 , so by Lemma 4.2, there exists S ∈ S where S ⊆ A 1 . Then A 2 ⊆ M \S, so by monotonicity, player 2 is happy with M \S. Thus if the protocol has not already terminated, player 2 will declare will declare (S, M \S) to be c-P . Then by Lemma 4.1, the declared allocation is in fact c-P , so the claim is satisfied in this case.
If the protocol terminated before player 2 considered S in step 3, the protocol declared some other allocation to be c-P , and the declared allocation is again c-P by Lemma 4.1 in this case. Thus the claim is satisfied in both cases.
Finally, we show that the protocol correctly returns a c * -P allocation if no c-P allocation exists. Recall the definitions of S * (v i ) and c(S): c i (S) is the maximum c ′ ≤ 1 where player i is c ′ -happy with S, and S * (v i ) = arg max S⊆M : c i (S)<c c i (S). In words, S * (v i ) is the bundle that makes player i the most happy, out of all the bundles that do not make her c-happy. For P = EF, . Lemma 4.4. Protocol 2 either returns a c-P allocation or a c * -P allocation.
Proof. If a c-P allocation exists, Lemma 4.3 implies that the protocol correctly returns one, so the claim is satisfied in this case.
Suppose no c-P allocation exists: then the protocol does not declare an allocation to be c-P , again by Lemma 4.3. Thus the protocol does not terminate until step 4.
as computed by player 2 in step 4. Let A be the allocation returned by the protocol in this case: . We know that player i cannot be happier than c i (S * (v i ))-happy without being c-happy, so player i must be c-happy with A ′ . That implies that player 2 is not chappy with A ′ , since no allocation makes both players c-happy in this case. But then the happiest player i can be is c i (S * (v i )), and c i (S * (v i )) ≤ c i (S * (v i )) by assumption. Thus for any allocation, there is a player who is at most c i (S * (v i ))-happy. Therefore c * = c i (S * (v i )).

Communication cost
It remains to bound the communication cost. This will primarily consist of proving an upper bound on the number of minimal bundles player 1 sends to player 2. We will go through a series of helpful lemmas before proving the final theorem.
The upper bound on the number of minimal bundles will depend on there being no allocation A for which player 1 is happy with both A and A: recall that if there is such an allocation, then Protocol 2 terminates after step 1 and does not even send the set of minimal bundles S. This condition was defined in Section 3.

Condition 3.2. There is no allocation A for which player 1 is happy with both A and A.
Let ∆(S, g) be player 1's marginal value for adding item g to bundle S. Formally, ∆(S, . The idea behind Lemma 4.5 is the following. Because of Condition 3.2, we have c · v 1 (S) > v 1 (M \S) whenever player 1 is happy with S. If S is minimal, then moving any g ∈ S to M \S will invert this inequality: v 1 (S\{g}) < c · v 1 (M \S) ∪ {g} . Lemma 4.5 uses this to show that at least one of ∆(S\{g}, g) and ∆(M \S, g) has to be fairly large. Proof. Since S is minimal, for every good g ∈ S, we know that player 1 is not happy with S\{g}.
We also know that player 1 is happy with S. Thus by Condition 3.2, player 1 is not happy with M \S, so v 1 (M \S) < c · v 1 (S). Adding this to the above equation yields where the last step follows from submodularity (actually just subadditivity).
Since v 1 (M ) = 1 by assumption, we have Next, we define the a directed graph G = (V, E) which we call the minimal bundle graph. The vertex set V is the set of minimal bundles. With slight abuse of notation, we will use S and T to refer both to minimal bundles and to the corresponding vertices in V . We define the edge set E by The next three lemmas establish some useful properties of the minimal bundle graph. Proof. Suppose g ∈ T : then S ⊆ M \T . Since S is minimal, player 1 is happy with S. Thus by monotonicity, player 1 is also happy with M \T . But player 1 is also happy with T , because T is minimal. This contradicts Condition 3.2, so we must have g ∈ T .  The next lemma is because there are |S| items in S that we could move to M \S. The proof uses Lemma 4.7 to show that each of them will yield a different minimal bundle T , so this constitutes |S| distinct edges (S, T ).
Lemma 4.9. The out-degree of each bundle S ∈ V is at least |S|.
Proof. Let S = {g 1 , g 2 ...g |S| }. We first claim that for all g j ∈ S, there exists T j ∈ V where T j ⊆ (M \S) ∪ {g j }. Consider some g j ∈ S. Because S is minimal, we know that player 1 is not happy with S\{g j }. Therefore player 1 must be happy with (M \S) ∪ {g j }. Then by Lemma 4.2, By Lemma 4.7, g j = g(S, T j ) is unique. Thus for all g ∈ S where g = g(S, T j ), we have g ∈ T j . This implies that each T j is distinct. Thus (S, T 1 ), (S, T 2 )...(S, T |S| ) are all distinct edges in E, so the out-degree of S is at least |S|.
Next, we define a set of edges E + ⊆ E by This is the set of "special edges" alluded to in Section 1.2.
The informal argument for the next lemma is as follows. By Lemma 4.8, we have (S, T ) ∈ E if and only if (T, S) ∈ E. Then Lemma 4.5 (combined with submodularity) implies that at least one of ∆(S\{g(S, T )}, g(S, T )) ≥ α and ∆(T \{g(S, T )}, g(S, T )) ≥ α is true, so at least one of (S, T ) and (T, S) must be in E + .  We are now ready to prove the final theorem. Recall the following definitions from Section 3: Proof. Correctness of Protocol 2 follows from Lemma 4.4, so it remains only to bound the communication cost.
So at least half of the minimal bundles have size more than β. Let G = (V, E) be the minimal bundle graph. Then by Lemma 4.9, at least half of the minimal bundles in V have out-degree more than β. Therefore |E| > β|V |/2. Then by Lemma 4.10, |E + | > β|V |/4 = |V |/α.
For a bundle S, let X S + be the set of out-edges from S that are in E + . Formally, and we can define the corresponding goods by g(X S + ) = {g ∈ S | ∆(S\{g}, g) ≥ α}. We next show that there must exist a minimal bundle S ∈ V where |X S + | > 1/α. Suppose that |X S + | ≤ 1/α for all S ∈ V : then |E + | ≤ |V |/α which contradicts |E + | > |V |/α. Therefore there exists some bundle S with |X S + | > 1/α. By definitions, we have Because S ≤k−1 ⊆ S and g k ∈ S ≤k−1 , we have S ≤k−1 ⊆ S\{g k }. Therefore by submodularity, 11 But v 1 (M ) = 1, so this is a contradiction. Therefore the number of minimal bundles is less than 2(m + 1)  Player 1 also sends c i (S * (v 1 )). By definition of c EF i , c i (S * (v 1 )) can be expressed as the ratio of two values, each of which takes v size bits to communicate. Therefore the total communication cost is 2m(m + 1) 8 1−c + 2v size as required.
We will show formally in Section 6 that Theorem 4.1 is tight, meaning that exponential communication can be required when c = 1. To see why the minimal bundle argument fails for c = 1, consider an additive (and hence submodular) valuation over an even number of items, where the value of each item is one. Then a bundle is minimal if and only if it contains exactly half the items, and there are exponential number of such bundles.

Lower bound approach
In Section 6, we will prove a lower bound that matches the PAS from Section 4. Before we do that, we describe our general lower bound approach in this section. All of our lower bounds will rely on reductions from two well-known problems in communication complexity: determining whether two bit strings are equal, and determining whether two bit strings are disjoint. Let x i denote the bit string held by player i, and let x ij denote the jth bit of x i . An input (x 1 , x 2 ) is a no-instance of the Equality problem if and only if there exists j where x 1j = x 2j . An input (x 1 , x 2 ) is a no-instance of the Disjointness problem if and only if there exists j where x 1j = x 2j = 1. The following lemma states that Disjointness is hard in the randomized setting (and thus also in the deterministic setting). The following well-known lemma states that Equality is hard in the deterministic setting.

Lemma 5.2. Any deterministic protocol which solves Equality for bit strings of length ℓ has communication cost at least ℓ.
Perhaps surprisingly, Equality admits a constant communication randomized protocol, due to [25].

Lemma 5.3 ([25]). There exists a randomized protocol which solves Equality and has communication cost O(1).
The protocol for Lemma 5.3 asks each player to compute the inner product mod 2 of her bit string and a random string. The protocol then compares those inner products. The Principle of Deferred Decisions can be used to show that this protocol arrives at the correct answer with probability at least 75%. Lemma 5.3 will be a key element of our randomized upper bound in Section 9.3.
All of our lower bounds have the following structure. Given two bit strings x 1 and x 2 of length ℓ = Ω( 2k k ), we construct a corresponding instance of Fair Division with O(k) items. In the two player case, each index in the bit strings will correspond to a possible allocation that gives each player k items.
Our constructed instance will have that a property that a c-P allocation exists if and only if (x 1 , x 2 ) is a no-instance 12 of Equality (for a deterministic lower bound), or a no-instance of Disjointness (for a randomized lower bound). Thus if there existed a protocol for Fair Division with communication cost less than Ω( 2k k ), it could also be used to solve Equality or Disjointness in communication less than Ω(ℓ). This is impossible according to Lemmas 5.1 and 5.2, so any protocol for Fair Division requires exponential communication.
Using this framework, all that is needed to prove a lower bound for a particular set of parameters (property P , constant c, and a valuation class) is: 1. Given bit strings x 1 and x 2 of length Ω( 2k k ), define how to construct a corresponding instance of Fair Division with O(k) items.
2. Show that a c-P allocation exists in the constructed instance if and only if (x 1 , x 2 ) is a no-instance of Equality or Disjointness.
3. Show that the valuations in the constructed instance of Fair Division are of the desired valuation class.
More specifically, our Fair Division instance will have two players and 2k items. Valuations will be constructed such that a player will never be happy if she receives fewer than k items, so both players will have to receive exactly k items. There are 2k k allocations which give each player k items, and this gives rise to the exponential communication lower bound.
In fact, we can do this in a very standardized way for the two player deterministic case. Given bit strings of length 1 2 2k k , we define a list of allocations T = (T 1 , T 2 ...T |T | ) where each T j = (T j1 , T j2 ) ∈ T is an allocation giving each player k items: |T j1 | = |T j2 | = k. It is important that T does not contain every such allocation: in particular, for any allocation A ∈ T , A ∈ T . 13 The allocations in T appear in an arbitrary (but known) order. Note that |T | = 1 2 2k k . Lemma 5.4 states that under this approach, all that is necessary to complete the lower bound is to construct valuations satisfying three particular properties. The exact way valuations are constructed will depend on what class we wish them to belong to (general, subadditive, or submodular). We only prove the lemma for the c-EF in the two player deterministic setting. A similar result is possible for other settings, but this is only setting where we prove enough different lower bounds to make it worth having a separate lemma.
For a bit string x i , let x i denote the string obtained by flipping every bit: x ij = x ij for all j. We will define two new bit strings, y 1 and y 2 , by y 1 = x 1 and y 2 = x 2 . Also, recall that for a player i, i denotes the other player.
The lemma relies on three conditions. Condition 5.1 states that neither player is happy with any bundle containing fewer than k items: then any c-P allocation must either be A or A for some A ∈ T . Condition 5.2 states that player i is unhappy receiving T ji when y ij = 1 (and happy receiving T ji ). Condition 5.3 states that player i is unhappy receiving T ji when y ij = 0 (and happy receiving T ji ). Thus we want to find an index j where either y 1j = y 2j = 1, in which case the allocation (T j1 , T j2 ) is c-P , or where y 1j = y 2j = 0, in which case the allocation (T j2 , T j1 ) is c-P . Therefore we are looking for an index where y 1j = y 2j , which is equivalent to x 1j = x 2j . This is exactly the Equality problem.

Condition 5.2. Whenever y
Then any deterministic protocol which finds a c-EF allocation for two players requires exponential communication. Specifically, Proof. We reduce from Equality. Given bit strings x 1 and x 2 of length 1 2 2k k for some integer k, we construct the following instance of Fair Division. Let N, M, (y 1 , y 2 ), and T be as defined in the statement of Lemma 5.4. Also assume that v 1 and v 2 satisfy Conditions 5.1, 5.2, and 5.3.
Suppose that (x 1 , x 2 ) is a no-instance of Equality: then there exists j where x 1j = x 2j . Therefore y 1j = y 2j . If y 1j = y 2j = 1, then by Condition 5.2, for both i. Thus the allocation T j is c-EF, because each player i receives T ji . If y 1j = y 2j = 0, then by Condition 5.3, for both i. Thus the allocation T j is c-EF, because each player i receives T ji . Therefore if (x 1 , x 2 ) is a no-instance of Equality, there exists an allocation satisfying c-EF. Suppose that (x 1 , x 2 ) is a yes-instance of Equality: then for every j, y 1j = y 2j . For any allocation A where |A i | < k for some i, we have v i (A i ) < c · v i (A i ) by Condition 5.1. Thus A cannot be c-EF whenever |A i | < k for some i. Now consider an arbitrary allocation A where |A 1 | = |A 2 | = k. For any such allocation, there must exist j where either A = T j , or A = T j . Since y 1j = y 2j , there exists a player i where y ij = 0, and y ij = 1. Then by Condition 5.
where i = i represents the player other than i.
Therefore neither player is happy with bundle T ji . But since either A = T j or A = T j , there must be a player who receives T ji , is hence is not happy. Thus no allocation where |A 1 | = |A 2 | = k can be c-EF, no allocation is c-EF.
This lemma will be useful in a variety of settings. In the next section, we will use this lemma to prove a lower bound for 1-EF that matches the PAS from Section 4.

1-EF is hard for submodular valuations
In this section, we use the general approach described in Section 5 to show that 1-EF requires exponential communication, even for two players with submodular valuations. This shows that the PAS for this setting from Section 4 is the best we can hope for.
Formally, Section 4 showed that D submod (2, m, EF, c) is polynomial in m when c < 1. We now show that D submod (2, m, EF, c) is exponential when c = 1. Section 3 showed that D submod (2, m, Prop, c) is polynomial for any c, so there is no lower bound necessary there. Thus this section resolves the deterministic submodular case for two players.
. This satisfies Condition 5.1. Suppose y ij = 1 for some i, j: Recall that Section 4 gave a PAS for this setting, where for any fixed c, communication at most 2(m + 1) 8 1−c is required. In a fully polynomial-communication approximation scheme (FPAS), the dependence in 1 1−c is required to be polynomial. The PAS from Section 4 is not an FPAS, since the dependence on 1 1−c is exponential. The above proof of Theorem 6.1 actually shows that for any c > 3k−1 3k = 3m−2 3m , exponential communication is required. This does not contradict the PAS from Section 4, because 3m−2 3m is not a fixed constant (it depends on m). However, this does rule out the possibility of an FPAS. To see this, suppose an FPAS existed, and consider some c > 3m−2 3m . Then the FPAS would have communication cost polynomial in 1 1−c . We have so the communication cost is polynomial of m. But the proof of Theorem 6.1 shows communication exponential in m is required, which is a contradiction. Finally, we note that the proof of Theorem 6.1 can easily be adapted to prove exponential lower bounds on the communication complexity of maximizing Nash welfare (the product of player utilities) or egalitarian welfare (the minimum player utility).

Everything is hard for more than two players
In this section, we show that Fair Division requires an exponential amount of communication whenever there are more than two players: even when randomization is allowed, even for submodular valuations, and for any c > 0. This will allow us to focus on the two player setting for the rest of the paper.
Before proving the theorems, we discuss the multiparty (i.e., n > 2) communication complexity model. As mentioned in Section 2, there is more than one such model. This will turn out not to matter in our setting. The reason is that our lower bounds will hold even when only player 1 and player 2 have private valuations, and the valuations of all other players are public information. One can think of the other players as not really being agents, and just being a (publicly known) part of the input. Thus we never actually consider multiparty communication. In this way, the theorem that we are really proving is that when there are more than two Fair Division players, the problem is hard in the two-party communication complexity model.
We first prove hardness for envy-freeness, and then reduce envy-freeness to proportionality. Recall that Disjointness has randomized communication complexity Ω(ℓ), where ℓ is the length of the bit strings (Lemma 5.1). Proof. We reduce from Disjointness. Given bit strings x 1 and x 2 of length 2k k , we construct a fair division instance as follows. Although there will be more than two players, there are only two bit strings. Let player 1 hold x 1 and player 2 hold x 2 , and the other players will have no bit strings. Let if |S| < k and g 3 ∈ S kc if |S| > k and g 3 ∈ S (k − 1 2 )c if |S| = k and g 3 ∈ S and S ∩ M 2 = ∅ kc if ∃j S = T ji where x ij = 1 and g 3 ∈ S (k − 1 2 )c if ∃j S = T ji where x ij = 0 and g 3 ∈ S Every allocation giving each player k items occurs in T exactly once. Thus when |S| = k and S ⊂ M 1 , exactly one of the last two cases occurs, and any such j must be unique. For i > 2, v i (S) is given by Suppose that (x 1 , x 2 ) is a yes-instance of Disjointness: then for every j, there exists i where x ij = 0. Suppose that a c-Prop allocation A = (A 1 , A 2 ) exists. We first claim that for every i > 2, g i ∈ A i : if not, v i (A i ) = 0, so player i will envy whichever player receives g i . Thus Suppose a player i ≤ 2 receives strictly fewer than k items in A i : then v i (A i ) < kc, since none of those items can be g 3 . This is a contradiction, so we have |A 1 | = |A 2 | = k. Since T contains all of the allocations which give each player k items, there must exist j where A i = T ji for both i, and v i (A i ) ≥ kc. But that implies that x 1j = x 2j = 1, which is a contradiction. Therefore no allocation is c-Prop. It remains to show that the valuations are submodular. For i > 2, v i is trivially submodular. We now we examine v i (S ∪ {g}) − v i (S) for i ≤ 2, any bundle S, and any item g ∈ S where Therefore the submodularity condition is satisfied when g 3 ∈ S ∪ {g}.
There are two remaining cases: when g 3 ∈ S, or when g = g 3 . For g 3 ∈ S, v i (S ∪{g})−v i (S) = 0 for all S and g, so the condition is satisfied in this case.
We now prove hardness for proportionality for more than two players, by reducing from envyfreeness. Proof. We reduce from Disjointness. Given an input (x 1 , x 2 ), we define v i as in the proof of Theorem 7.1, except using c/n instead of c. That is, if |S| < k and g 3 ∈ S kc/n if |S| > k and g 3 ∈ S (k − 1 2 )c/n if |S| = k and g 3 ∈ S and S ∩ M 2 = ∅ kc/n if ∃j S = T ji where x ij = 1 and g 3 ∈ S (k − 1 2 )c/n if ∃j S = T ji where x ij = 0 and g 3 ∈ S It was shown in the proof of Theorem 7.1 that these valuations are submodular. Theorem 7.1 implies that Ω( 2k k ) communication is required to determine whether a c n -EF allocation exists under these valuations. We will show that under these valuations, an allocation is c-Prop if and only if it is c n -EF. This will imply that determining whether a c-Prop allocation exists is just as hard as whether a c n -EF allocation exists. In order for an allocation A to be c n -EF or c-Prop, we must have v i (A i ) > 0 for all i. Thus assume g i ∈ A i for all i > 2, and we need only consider i ≤ 2.
Suppose an allocation A is c-Prop: for all i ′ . Therefore A is c n -EF. Suppose an allocation A is c n -EF: then for all i and This resolves the n > 2 case for all combinations of other parameters, so we will assume that n = 2 for the remainder of the paper.

Subadditive valuations
In this section, we consider the deterministic setting for two players with subadditive valuations. In Section 8.1, we use the Minimal Bundle Protocol from Section 4 to show that c-EF for c ≤ 1/2 and c-Prop for c ≤ 2/3 require only polynomial communication. This is the same protocol that yielded the PAS for EF with submodular valuations, but the communication cost analysis will be different. In Section 8.2, we show that this is tight, by giving an exponential lower bound for c-EF and c-Prop when c exceeds 1/2 and 2/3, respectively.

Upper bounds
In this section, we prove that when players have subadditive valuations, the Minimal Bundle Protocol (Protocol 2) can be used to solve Fair Division for 1 2 -EF and 2 3 -Prop with polynomial communication. In fact, we will show that if a satisfactory allocation is not found in step 1, there must exist a single item g where v 1 ({g}) > v 1 (M \{g}). This will imply that the only minimal bundle is {g}. Protocol 2 is restated here for the convenience of the reader. Protocol 2 Protocol for two players to either find a c-P allocation or a c * -P allocation.
Private inputs: v 1 , v 2 Public inputs: P, c 1. If there exists an allocation A where player 1 is happy with both A and A, player 1 sends that allocation to player 2. If player 2 is happy with A, she declares that A is c-P , otherwise she declares that A is c-P .
2. If there is no such allocation A, player 1 sends the set S of her minimal bundles to player 2. She also sends the bundle S * (v 1 ) and the value c 1 (S * (v 1 )).
3. Player 2 first checks if there exists a bundle S ∈ S where player 2 is happy with M \S. If so, she declares that (S, M \S) is c-P .
4. If not, player 2 computes S * (v 2 ) and i = arg In Section 4, we proved correctness of this protocol for any setting, so it remains only to prove the communication cost bound for this setting.
Let α ∈ (0, 1] be some constant. Let η P (α) be the maximum c ≤ 1 for which any allocation A is guaranteed to be c-P , given v i (A i ) ≥ αv i (A i ) for both i. For example, η EF (α) = α. We will write η P (α) = η(α) and leave P implicit. Lemma 8.1 is strongest for α = 1/2, but we find it insightful to prove the theorem for any α ≤ 1/2. Also, recall that Condition 3.1 is satisfied for c-Prop with subadditive valuations, for any c: for any allocation A, each player must be happy with at least one of A and A. Thus communicating c 1 (S * (v 1 )) requires 2v size bits. The only other information transmitted is the bundle S * (v 1 ) and S. Communicating S * (v 1 ) requires m bits, and S requires |S|m bits. Thus the communication cost of the protocol is m(|S| + 1) + 2v size It remains to show that if the protocol does not terminate in step 1, |S| = 1.
By Condition 3.1, for every allocation A, player 1 is happy with at least one of A and A. Thus |S| ≥ 1, so let S be a minimal bundle in S. Since player 1 is happy with S, we know that she is not happy with M \S, or the protocol would have terminated in step 1. Suppose αv 1 (S) ≤ v 1 (M \S): then player 1 is η(α)-happy with M \S. Since c = η(α), this means player 1 is happy with M \S, which is a contradiction. Therefore αv 1 (S) > v 1 (M \S). This also implies that v 1 (S) > 0.
Also, since S is minimal, player 1 is not happy with S\{g} for all g ∈ S. Therefore player 1 is happy with (M \S)∪{g} for all g ∈ S. By the same argument as above, we have αv 1 (M \S)∪{g}) > v 1 (S\{g}).
Since v i (S) > 0, S must be nonempty, so let g be an arbitrary item in S. By subadditivity of v 1 , we have where the final step is due to 0 < α ≤ 1/2. Thus player 1 is η(α)-happy with the bundle {g} by definition. Since the protocol did not terminate in step 1, player 1 must not be happy with M \{g}. Therefore player i is happy with a bundle S if and only if g ∈ S, and so the only minimal bundle is {g}.  for any c ≤ η P (1/2).
Proof. Run Protocol 2 to either find a η P (1/2)-P allocation, or to find a c ′ -P allocation where c ′ is the best possible. If a η P (1/2)-P allocation exists, then a c-P allocation exists, since c ≤ η P (1/2). If a c * -P allocation is returned where c * < η P (1/2), then by definition of c * , a c-P allocation exists if and only if c * ≥ c.
Since η P rop (1/2) ≥ 2/3, any 1 2 -EF A allocation is also 2 3 -Prop. However, a c ′ -EF allocation where c ′ is the maximum possible EF approximation ratio does not necessarily achieve the maximum possible approximation ratio for Prop. Consider the case where M = {g 1 , g 2 } and the players valuations are given by and v i (∅) = 0 for both i. There is no 1 2 -EF allocation or 2 3 -Prop allocation in this instance. The allocation achieving the maximum EF approximation ratio is A = ({g 2 }, {g 1 }) which is 2 7 -EF. On the other hand, the allocation achieving the maximum Prop approximation ratio is A, which is 1 2 -Prop.

Lower bounds
In this section, we show that 1 2 -EF and 2 3 -Prop are the best we can do deterministically for two players with subadditive valuations. We first prove that c-EF is hard for any c > 1/2, and then show that the same construction also proves hardness for c-Prop when c > 2/3. We will use Lemma 5.4, which gives a standardized way to prove deterministic lower bounds for EF for two players. Recall that a list of allocations T = (T 1 , T 2 ...) is defined where each T j = (T j1 , T j2 ) is an allocation giving each player k items. Also, for every such allocation A, exactly one of A and A appears in T . All that is needed to complete the reduction is to show how to construct valuations v 1 , v 2 such that the following conditions are satisfied: When |S| = k, S falls under exactly one of the last four cases in the definition of v i .
If |S| < k, we have |M \S| > k, so v i (S) ≤ 1 and v i (M \S) ≥ 2. Thus for any c > 1/2, v i (S) < c · v i (M \S), so Condition 5.1 is met. Suppose y ij = 1 for some i, j: then v i (T ji ) = 1 and v i (T ji ) = 2, so again v i (S) < c · v i (M \S) for any c > 1/2. Suppose y ij = 0 for some i, j: then similarly, v i (T ji ) = 1 < c · 2 = c · v i (T ji ) for any c > 1/2. Thus Condition 5.3 is satisfied as well.
It remains to show that v i is subadditive for both i. Specifically, we need to show that for any S and T , v i (S) + v i (T ) ≥ v i (S ∪ T ). If either S = ∅ or T = ∅, this trivially holds, so suppose |S| > 0 and |T | > 0. We proceed by case analysis.
Case 1: Since v i (S) ≥ 1 and v i (T ) ≥ 1, it remains to show that at least one of v i (S) ≥ 2 and v i (T ) ≥ 2 is true. Since S ∪ T = M in this case, we have M \S ⊆ T . Observe that under these valuations, for any allocation Since v i only takes on integer values in this proof, if v i (S) > 1, we have v i (S) ≥ 2. Thus at least one of v i (S) ≥ 2 and v i (T ) ≥ 2 is true, so the claim is satisfied in this case. Thus v i is subadditive for both i.
To prove hardness for proportionality, we reduce from envy-freeness. whether a c ′ -EF allocation exists under these valuations. We will show that under these valuations, for any c > 2/3 and any c ′ > 1/2, an allocation A is c-Prop if and only if is c ′ -EF: thus the lower bound of Theorem 8.5 will apply to c-Prop for c > 1/2 as well. 15 Suppose an allocation A is c ′ -EF for some c ′ > 1/2: Thus v i (A i ) must be strictly greater than 1. Since these valuations only take on integer values, this implies that for every c > 2/3, so A is c-Prop for every c > 2/3. Now suppose that A is c-Prop for some c > 2/3: > 1 for both i. Thus we again have v i (A i ) ≥ 2 for both i, since these valuations only take on integer values. This also implies that |A i | > 0 for both i, which means that |A i | < 2k for both i.
for any c ′ > 1/2. Therefore A is c ′ -EF for every c ′ > 1/2. Theorems 8.5 and 8.6 resolve the deterministic subadditive case. We now move on to general valuations, and give the last few results we need to complete Table 1.

General valuations
This section covers the remaining settings for envy-freeness and proportionality. In Section 9.1, we show that c-Prop is hard for general valuations for any c > 0, in both the randomized and deterministic settings. Section 9.2 gives a similar lower bound for c-EF for any c > 0, but only for deterministic protocols. In Section 9.3, we show that there actually exists an efficient randomized protocol for c-EF for any c ∈ [0, 1]. We also show that this protocol works for proportionality in the subadditive case, again for any c ∈ [0, 1]. These results conclude our study of envy-freeness and proportionality.
Exactly one of the last two cases occur when |S| = k, and any such j is unique.
Suppose that (x 1 , x 2 ) is a no-instance of Disjointness: then there exists j where x 1j = x 2j = 1. Consider the allocation T j = (T j1 , T j2 ). Then for both Suppose that (x 1 , x 2 ) is a yes-instance of Disjointness: then for every j, there exists i where · v i (M ) > 0 for both i. Suppose a player i receives strictly more than k items in A i : then the other player receives strictly fewer than k items, and has value zero, which is impossible. Thus |A 1 | = |A 2 | = k. Since T contains all of the allocations which give each player k items, there must exist j where A i = T ji for both i. But that implies that x 1j = x 2j = 1, which is a contradiction. Therefore no allocation is c-Prop.
We will see in Section 9.3 that this leads to an efficient randomized protocol for c-EF, for any c ∈ [0, 1].

Envy-freeness deterministic lower bound
In this section we prove that for general valuations, c-EF is hard in the deterministic setting for any c > 0. We will use Lemma 5.4; recall that we need only show how to construct valuations that satisfy the following conditions: Recall that for every allocation A which gives each player k items, T (as defined by Lemma 5.4) contains exactly one of A and A. Thus if |S| = k, S falls under exactly one of the last four cases in the definition of v i .
If |S| < k, we have |M \S| > k, so v i (S) = 0 < c = c · v i (M \S). This satisfies Condition 5.1. Suppose y ij = 1 for some i, j: then v i (T ji ) = 0 < c = c · v i (T ji ), so Condition 5.2 is satisfied. Suppose y ij = 0 for some i, j: then similarly, v i (T ji ) = 0 < c = c · v i (T ji ). Thus Condition 5.3 is satisfied as well.

A randomized upper bound
Although c-EF is hard for general valuations in the deterministic setting, it admits an efficient randomized protocol for any c ≤ 1. Fundamentally, this is because the randomized communication complexity of Equality is constant, while its deterministic complexity is the length of the string. Our deterministic lower bound in Section 9.2 was based on a reduction from Equality: in this section, we reduce to Equality.
Our protocol will actually be much more general than just c-EF. For example, it will also work for c-Prop for subadditive valuations, for any c ∈ [0, 1]. More generally, it solves Fair Division with two players when (c, P ) satisfies two conditions: Condition 3.1. For every allocation A, each player is happy with at least one of A and A.
Condition 9.1. Whether player i is happy does not depend on any valuation other than v i .
All of the fairness properties we consider satisfy Condition 9.1. The c-EF property satisfies Condition 3.1 for any c ≤ 1. As mentioned before, c-Prop satisfies this for any c ≤ 1 for subadditive valuations.
Despite being hard in the deterministic setting, Equality admits an efficient randomized protocol (Lemma 5.3), as described in Section 5. This protocol (let us call it Γ EQ ) enables the Fair Division randomized protocol that we present in this section.
The standard Equality problem is a decision problem, but Fair Division is a search problem: we must output a satisfactory allocation if one exists. The search version of Equality is to determine whether two bit strings are equal, and if they are not, to return an index where they differ. The protocol uses a binary search approach. The players first use Γ EQ to check if their strings are equal. If so, the protocol terminates. If not, the players split their strings into a left half and a right half. They again use Γ EQ to check if their left halves are equal: if they are not, the players recurse on the left half, otherwise they recurse on the right half. This process continues until players isolate a single bit which differs in their bit strings 16 .
Since Γ EQ is a randomized protocol, it may return an incorrect answer with probability up to 1/3 (say) each time it is run. If we use Γ EQ many times, as required by the above binary search argument, the probability Γ EQ returns the correct answer every time may be less than 2/3, which is unacceptable. This makes the protocol a sort of "noisy binary" search. This can be done with total communication O(log ℓ log log ℓ) using a standard Chernoff bound argument, but [13] shows how this can be done with total communication just O(log ℓ). We refer to protocol from Lemma 9.1 as Γ EQS .
We now present our randomized protocol (Protocol 3). Let T = (T 1 , T 2 ...) be a list of every possible allocation (not just those with bundles of a fixed size) in an arbitrary order. Condition 9.1 is necessary for Protocol 3 to be well-defined (step 1 in particular), but will not appear in the proof of Theorem 9.3.
The protocol uses a similar construction to the previous lower bounds in that players have exponentially long bit strings, with each index representing a possible allocation, and where y ij = 1 if player i is happy with T j . Similarly to the Equality lower bounds, an index where y 1j = y 2j implies the existence of a c-P allocation: if y 1j = y 2j = 1, both players are happy with that allocation, and if y 1j = y 2j = 0, both players are happy with the reverse allocation by Condition 3.1. This is made formal by the following theorem:

Maximin share
Finally, we consider a different fairness property: maximin share. A player's maximin share (MMS) is the maximum value as she could guarantee herself if she gets to divide the items into n bundles, but chooses last. An allocation A is c-MMS for c ∈ [0, 1] if each player receives at least a c-fraction of her MMS. We use "MMS" to refer to both each player's maxmin share and the fairness property itself. Formally, where A ′ ranges over all possible allocations.
In this section, we prove exponential lower bounds for MMS in two settings: for general valuations and any c > 0, and for submodular valuations when c = 1. Both lower bounds hold even for two players, and for randomized protocols. Both lower bounds will rely on reductions from Disjointness.

Lower bound for general valuations and any c > 0
In this section we show that for general valuations, c-MMS is hard for any c > 0, even for randomized protocols and even if there are only two players. We will reduce from 1-Prop, which we know to be hard in this setting (randomized, n = 2, general valuations) from Theorem 9.1. We say that an allocation A is over a set of items M to mean that A 1 ∪ A 2 = M . Also, we say that an allocation A is c-Prop for valuations v 1 , v 2 if v i (A i ) ≥ 1 2 v i (M ) for both i. Since we will be reducing between two different Fair Division instances, we will be dealing with allocations over different sets of items and different sets of valuations. We will create a second instance of Fair Division as follows. Add four items g 1 , g 2 , g 3 , g 4 , let X = {g 1 , g 2 , g 3 , g 4 }, and define M ′ = M ∪ X. Let Y 1 = {g 1 , g 2 }, Y 2 = {g 3 , g 4 }, Z 1 = {g 1 , g 3 }, and if Z 1 ⊆ S or Z 2 ⊆ S min(v 2 (S\X), cα 2 ) if {g 2 , g 3 } ⊆ S and g 1 , g 4 ∈ S 0 otherwise We first claim that each player i's MMS is exactly α i . Since c ≤ 1, we have v ′ i (A ′ i ) ≤ α i for all i and for every allocation A ′ over M ′ . Thus each player's MMS is at most α i . In the partition (Y 1 , Y 2 ∪ M ), player 1 has value α 1 for both bundles, so player 1's MMS is at least α 1 . Similarly, player 2 has value α 2 for both bundles in the partition (Z 1 , Z 2 ∪ M ). Thus each player i's MMS is exactly α i . Therefore For all j and j ′ , we have Y j ∩ Z j ′ = ∅. Thus if player 1 receives Y 1 or Y 2 : then player 2 player 2 cannot receive Z 1 or Z 2 . Furthermore, player 2 cannot receives {g 2 , g 3 }, so v ′ 2 (A ′ 2 ) = 0, which is a contradiction. Therefore player 1 cannot receive either Y 1 or Y 2 . Similarly, if player 2 receives Z 1 and Z 2 , player 1 will have value 0. Thus player 2 does not receive Z 1 or Z 2 .

Lower bound for submodular valuations and c = 1
We now show that even for two players with submodular valuations, 1-MMS is hard. This does not hold for c-MMS for any c: in fact, a 1 3 -MMS is guaranteed to exist for submodular valuations [14]. . One exception: none of (Y 1 , Z 1 ), (Z 1 , Y 1 ), (Y 2 , Z 2 ), or (Z 2 , Y 2 ) appear in T .
Player i's valuation is given by: These valuations are submodular by the same argument as in the proof of Theorem 6.1. Observe that when |S| = k, exactly one of the last four cases occur.
Since v i (S) ≤ 3k for all S, player i's MMS is at most 3k. For both i, (Y i , Z i ) is a valid allocation. Furthermore, player i has value 3k for both bundles in that allocation. Thus each player i's MMS is at least 3k, so both players' MMS are exactly 3k.
Suppose that (x 1 , x 2 ) is a no-instance of Disjointness: then there exists j where x 1j = x 2j = 1. Consider the allocation T j = (T j1 , T j2 ). Then for both i, v i (T ji ) = 3k, so the allocation T j satisfies 1-MMS.
Suppose that (x 1 , x 2 ) is a yes-instance of Disjointness: then for every j, there exists i where x ij = 0. Suppose a 1-MMS allocation A exists. We first claim that for both i, A = (Y i , Z i ) and A = (Z i , Y i ) for both i. This is because player i will have value 3k − 1, which is less than her MMS. Suppose there is a player i where |A i | < k: then v i (A i ) < 3k, which is impossible. Thus Therefore there exists j where A = T j . But since (x 1 , x 2 ) is a yes-instance of Disjointness, there exists i where x ij = 0, so v i (T ji ) = 3k − 1. This is a contradiction, so no 1-MMS allocation exists.

Conclusion
In this paper, we proposed a simple model for the communication complexity of fair division, and solved it completely, for every combination of five parameters: number of players, valuation class, fairness property P , constant c, and deterministic vs. randomized complexity.
More broadly, communication complexity is an example of topic that has been well-studied in algorithmic game theory but not in fair division, despite having a natural fair division analog. We wonder if there are other such topics.