# democratic_fair_allocation_of_indivisible_goods__cd672ca8.pdf

Democratic Fair Allocation of Indivisible Goods

Erel Segal-Halevi1, Warut Suksompong2

1 Department of Computer Science, Ariel University 2 Department of Computer Science, Stanford University erelsgl@gmail.com, warut@cs.stanford.edu

We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group s share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. Our protocols approximate both envy-freeness and maximin-share fairness. As an example, for two groups of agents with additive valuations, our protocol yields an allocation that is envy-free up to one good and gives at least half of the maximin share to at least half of the agents in each group.

1 Introduction Fair division is the study of how to allocate resources among agents with different preferences so that agents perceive the resulting allocation as fair. This problem occurs in a wide range of situations, from negotiating over international interests and reaching divorce settlements [Brams and Taylor, 1996] to dividing household tasks and sharing apartment rent [Goldman and Procaccia, 2014]. Two kinds of fairness criteria are common in the literature. The first, envy-freeness (EF), means that each agent finds her share at least as good as the share of any other agent. When allocating indivisible goods, envy-freeness is sometimes unattainable (consider two agents quarreling over a single good), so it is often relaxed to envy-freeness up to one good (EF1), which is always attainable [Lipton et al., 2004; Budish, 2011]. The second kind, maximin share fairness, means that each agent finds his share at least as good as his maximin share (MMS), which is the best share he can secure by dividing the goods into n parts and getting the worst part, where n is the number of agents. Again, with indivisible

goods MMS fairness cannot be guaranteed, but at least a constant fraction of the MMS can [Procaccia and Wang, 2014]. Most works on fair division involve individual agents, each of whom has individual preferences. But in reality, resources often have to be allocated among groups of agents, such as families or states. A good allocated to a group is shared among the group members and all of them derive full utility from the good. For example, when dividing real estate among families, all members of a family enjoy their allocated house and backyard. In international negotiations, the divided rights and settled outcomes are enjoyed by all citizens of a country. When resources are allocated between different buildings of a university, all occupants of a building benefit from the whiteboards and open space allocated to their building. However, different group members may have different preferences. The same share can be perceived as fair by one member and unfair by another member of the same group. Ideally, we would like to find an allocation considered fair by all agents in all groups. However, two recent works show that this unanimous fairness might be too strong to be practical. (a) Suksompong [2018] shows that when allocating indivisible goods among groups, there might be no allocation that is unanimously EF1. Moreover, there might be no division that gives all agents a positive fraction of their MMS. This impossibility occurs even for two groups of three agents. (b) Segal-Halevi and Nitzan [2015] show that when allocating a divisible good ( cake ) among groups, there might be no division that is unanimously envy-free and gives each group a single connected piece, or even a constant number of connected pieces. In contrast, with individual agents a connected envy-free division always exists [Stromquist, 1980]. What do groups do when they cannot attain unanimity? In democratic societies, they use some kind of voting. The premise of voting is that it is impossible to satisfy everyone, so we should try to satisfy as many members as possible. Based on this observation, we say that a division is h-democratic fair, for some fairness notion and for some h [0, 1], if at least a fraction h of the agents in each group believe it is fair. In this paper we focus on allocating indivisible goods. We would like h, the fraction of happy agents, to be as large as possible. We thus pose the following question:

Given a fairness notion, what is the largest h such that an h-democratic fair allocation of indivisible goods can always be found?

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

We study democratic fairness under three different assumptions on the agents valuations. In the most general case, the agents can have arbitrary monotonic valuations on bundles of goods. A more common assumption in the literature is that agents valuations are additive (the value of a bundle is the sum of the value of its goods). We also study a special case of additive valuations in which agents valuations are binary (each agent has a set of desired goods and her utility equals the number of desired goods allocated to her group).

1.1 Overview of Our Results Initially (Section 3) we consider two groups with binary agents. We study a relaxation of envy-freeness that we call envy-freeness up to c goods (EFc), a generalization of EF1. One might expect to have a trade-off curve where a larger c corresponds to a larger h. However, we find that the actual trade-off curve is degenerate: for every constant c, it is possible to guarantee 1/2-democratic EFc and the 1/2 is tight. The same holds for MMS fairness. To get a more flexible trade-off curve, we study a generalization of MMS called 1out-of-c-MMS, which is the best share an agent can secure by dividing the goods into c subsets and receiving the worst one. We prove that for every integer c 2, 1-out-of-c MMS can be guaranteed to at least 1 1/2c 1 and at most 1 1/c22c+1 of the agents in both groups. Our positive results are attained by an efficient roundrobin protocol where each group in turn picks a good using weighted approval voting with carefully calculated weights. We believe this weighted voting scheme can be interesting in its own right as a way to make fair group decisions. Next (Section 4) we consider two groups whose agents have arbitrary monotonic valuations. We present an efficient protocol that guarantees EF1 to at least 1/2 of the agents in each group (which is tight even for binary agents). When all agents are additive, this protocol guarantees 1/2 of the MMS to 1/2 of the agents. This is tight: one cannot guarantee more than 1/2 of the MMS to more than 1/3 of the agents. Moreover, a positive fraction of the MMS can be guaranteed to at least 3/5 and at most 2/3 of the agents in both groups. Finally (Section 5), we present two generalizations of our results to k 3 groups. The first generalization has stronger fairness guarantees: when all valuations are binary, it guarantees to 1/k of the agents in all groups both EF1 and MMS (the 1/k is tight for EF1). When valuations are additive, it guarantees an additive approximation to EF and MMS. However, the run-time of the protocol might be exponential. The second generalization uses a polynomial-time protocol but has weaker guarantees: when all valuations are binary, it guarantees MMS to 1/k of the agents, and when valuations are additive, it guarantees an additive approximation to MMS. Some of our results and open questions are summarized in Table 1.

1.2 Related Work The group resource allocation problem is relatively new. We already mentioned the impossibility result of Suksompong [2018], which is for worst-case agents utilities. On the other hand, if the agents utilities are drawn at random from probability distributions, Manurangsi and Suksompong [2017a] showed that a unanimously envy-free alloca-

tion exists with high probability as the number of agents and goods grows. In our terminology, unanimous fairness is called 1-democratic-fairness. The term democratic fairness already appears in [Segal Halevi and Nitzan, 2015]; however, they use it in the narrower sense that at least 1/2 of the agents in each group must be satisfied. In our terminology this is called 1/2-democratic fairness. Hence, our democratic fairness notion generalizes existing notions of group fairness. A related model, in which a subset of public goods is allocated to a single group of agents but the rest of the goods remain unallocated, has also been studied [Manurangsi and Suksompong, 2017b; Suksompong, 2016]. MMS fairness was introduced by Budish [2011] based on earlier concepts by Moulin [1990]. Budish also considered its relaxation to 1-out-of-(n + 1) MMS. The notion 1-out-ofc MMS is a special case of l-out-of-d MMS, recently defined by Babaioff et al. [2017]. Our group-fairness notions differ from those defined, e.g., by Todo et al. [2011]. In their setting, goods are divided among individuals. The challenge comes from the requirement to eliminate envy, not only between individuals, but also between subsets of agents. In our setting, the challenge is that the goods are divided among groups. A share that is desirable for some group members might be undesirable for other members of the same group. This motivates the use of social choice techniques such as having each group vote on which good to pick.

2 Preliminaries

There is a set G = {g1, . . . , gm} of goods. A bundle is a subset of G. There is a set A of agents. The agents are partitioned into k groups A1, . . . , Ak with n1, . . . , nk agents, respectively. Let aij denote the jth agent in group Ai. Each agent aij has a nonnegative utility uij(G ) for each G G. For any agent aij, denote by uij,max := maxl=1,...,m uij(gl) the maximum utility of the agent for any single good. Denote by uij = (uij(g1), . . . , uij(gm)) the utility vector of agent aij for single goods. The agents utility functions are monotonic, i.e., uij(G ) uij(G ) for every G G G and every agent aij. A subclass of monotonic utilities is the class of additive utilities, i.e., for every bundle G G and every agent aij A, we have uij(G ) = P g G uij(g). Sometimes we will study a special case of additive utilities in which utilities are binary, i.e., each agent either approves or disapproves each good. Since we will not engage in interpersonal comparison of utilities, we may assume without loss of generality that in this case uij(g) {0, 1} for each i, j, g. We allocate a bundle Gi G to each group Ai. All goods should be allocated. The goods are treated as public goods within each group, i.e., for every group i, the utility of every agent aij is uij(Gi). We refer to a setting with agents partitioned into groups, goods and utility functions as an instance. We now define the fairness notions considered in this paper. We begin by defining what it means for an allocation to be fair for a specific agent. We start with envy-freeness.

Definition 2.1. Given an agent aij and an integer c 0, an allocation is called envy-free up to c goods (EFc) for aij if for

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Happy h | Share q Positive (0, 1/2] (1/2, 1] EFc for any constant c 1 (0, 1/3]

Yes (Thm. 4.4) Yes (Cor. 4.2) Bin: Yes (Thm. 3.6), Add: ? Yes (Thm. 4.1) (1/3, 1/2] Bin: Yes ( ), Add: No ( ) (1/2, 3/5] ? Bin: ?, Add: No (Prop. 4.3) No (Prop. 3.4) (3/5, 2/3] ? (2/3, 1] No (Prop. 3.1)

Table 1: Summary of results for two groups with Binary and Additive agents. For each range of h, q (0, 1], the table shows whether there always exists an allocation that gives at least a fraction h of the agents in each group at least a fraction q of their maximin share. For EFc, the results hold for monotonic valuations too. The arrows refer to the directions pointed to in the table. The table is clearer when viewed in color.

every i there is a set Ci Gi with |Ci | c such that

uij(Gi) uij(Gi \Ci ).

In other words, one can remove the envy of aij toward group i by removing at most c goods from the group s bundle. An EF0 allocation is also known as envy-free. Next, we define the maximin share concepts. Definition 2.2. Given an agent aij and an integer c 2, the 1-out-of-c maximin share (MMS) of aij is defined as the maximum, over all partitions of G into c sets, of the minimum of the agent s utilities for the sets in the partition:

MMSc ij(G) := max G 1,...,G c min(uij(G 1), . . . , uij(G c)),

where (G 1, . . . , G c) is a partition of G. When c = k (the number of groups), the 1-out-of-k MMS of an agent is simply called his MMS and denoted by MMSij(G). An allocation (G1, . . . , Gk) is said to be: 1-out-of-c MMS-fair for aij, if uij(Gi) MMSc ij(G).

MMS-fair for aij, if uij(Gi) MMSij(G). q-MMS-fair for aij, for some fraction q (0, 1), if uij(Gi) q MMSij(G). positive-MMS-fair if every agent with positive MMS gets positive value: MMSij(G) > 0 uij(Gi) > 0. Note that MMS-fairness implies q-MMS-fairness (for any q), which implies positive-MMS-fairness. The next lemma shows an interesting link between EF1 and MMS-fairness. Lemma 2.3. If an allocation is EF1 for an agent with an additive utility function, then (a) it is also 1/k-MMS-fair for that agent the 1/k is tight; (b) if the agent s utility function is binary, then the allocation is also MMS-fair for that agent.

Proof. Denote by u the utility function of the agent and assume without loss of generality that the agent is in group A1. (a) EF1 implies that in each bundle Gi (for i {1, . . . , k}) there exists a subset Ci with |Ci| 1 such that u(G1) u(Gi\Ci). Summing over all groups gives that k u(G1) u(G\(C2 Ck)). Now, in any partition of G into k bundles, there is at least one bundle that does not contain any good in C2 Ck. This bundle is contained in G\(C2 Ck). Therefore, the MMS is at most u(G\(C2 Ck)) which is at most k u(G1). Therefore, u(G1) is at least 1/k of the MMS. To show that the factor 1/k is tight, assume that there are 2k 1 goods with u(g1) = = u(gk) = 1 and

u(gk+1) = = u(g2k 1) = k. If the agent s group (say, group A1) gets g1 and group i 2 gets {gi, gk+i 1}, the agent gets utility 1 and finds the allocation EF1. However, the MMS is k, as can be seen from the partition ({g1, . . . , gk}, {gk+1}, . . . , {g2k 1}). (b) Suppose the agent s group wins l of the agent s desired goods. EF1 implies that each of the other k 1 groups wins at most l + 1 of the agent s desired goods. Hence the agent has at most kl+k 1 desired goods. Hence the agent s MMS is at most l, so the allocation is MMS-fair for her.

Now we are ready to define our main group fairness notion: Definition 2.4. For any given fairness notion, an allocation (G1, . . . , Gk) is said to be h-democratic fair if it is fair for at least h ni agents in group Ai, for all i {1, . . . , k}. Due to space constraints, some proofs are left to the full version of this paper [Segal-Halevi and Suksompong, 2018].

3 Two Groups with Binary Valuations This section considers the special case in which there are two groups, the agents have additive valuations, and each agent either desires a good (in which case her utility for the good is 1) or does not desire it (in which case her utility is 0). Even in this special case, some fairness guarantees are unattainable. Proposition 3.1. For any h > 2/3, there is a binary instance in which no allocation is h-democratic positive-MMS-fair.

Proof. There are 3 goods. In each group there are 3 members, each of whom has utility 0 for a unique good and utility 1 for each of the other two goods. Each agent has a positive MMS (1), but no allocation gives all agents a positive utility.

We next leverage a combinatorial construction of Erd os to show the limitations of 1-out-of-c MMS-fairness. Lemma 3.2. For any integer c 2, there is an instance with two groups consisting of c22c+1 agents with binary valuations in each group, such that each agent desires c goods but no allocation gives all agents a positive utility.

Proof. Erd os [1964] proved that for any positive integer c, there exists a collection C of c22c+1 subsets of size c of a base set G that does not have property B . This means that no matter how we partition G into two subsets G1 and G2, some subset in C has an empty intersection with G1 or G2. Take the elements of G to be our goods. Each group consists of c22c+1 agents, each of whom desires all goods in a unique subset of goods in C. Then every agent desires c goods, but no allocation gives all agents a positive utility.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Proposition 3.3. For any integer c 2 and h > 1 1/c22c+1, there is a binary instance with two groups in which no allocation is h-democratic 1-out-of-c MMS-fair.

Proof. Consider the instance from Lemma 3.2. The 1-out-ofc MMS of an agent who desires c goods is positive (1), but no allocation gives all agents a positive utility.

If we change the fairness requirement to EFc, then we can satisfy no more than half of the agents in each group.

Proposition 3.4. For any constant integer c 1 and h > 1/2, there is an instance with two groups with binary agents in which no allocation is h-democratic EFc.

Proof. Consider an instance with m = 4l goods and 4l 2l

agents in each group, for some l 1. Each agent desires a unique subset of 2l goods. An allocation is EFc for an agent iff her group receives at least l c/2 of her 2l desired goods. The symmetry between the groups implies that the best fairness guarantee can be attained by giving exactly 2l goods to each group; the symmetry between the goods implies that it does not matter which 2l goods are given to which group. In each such allocation, the number of a group s members who receive exactly j desired goods is 2l j 4l 2l 2l j = 2l j 2. Therefore, the number of a group s members who receive at least l c/2 desired goods is: P2l j=l c/2 2l j 2 = Pl 1 j=l c/2 2l j 2 + 1

2 2l l 2 + 1

2 4l 2l , where the equality fol-

lows from expanding the central binomial coefficient 4l 2l . The fraction of a group s members who think the division is EFc is attained by dividing this expression by 4l 2l . For a constant c, the ratio approaches 1/2 when l .

Our positive results are attained with a protocol we call Round-robin with Weighted Approval Voting (RWAV). The groups take turns picking a single good until all goods are taken. Each group picks its good using a weighted approval voting scheme. The members weights are determined using fiat money. Initially, each group has an account that starts at 0, and each agent also starts with 0. Each agent can pay money to the group account or receive money from the group account. RWAV proceeds as follows.

(a) Initially, each member pays to his group account some amount of fiat money to be calculated later. (b) Whenever it is the group s turn to pick, each member is assigned a positive weight to be calculated later. (c) For each good, the total weight is calculated as the sum of the weights of the members who desire this good. The group picks a good with a maximal total weight. (d) Every member whose desired good was picked by the group pays his weight to the group account. (e) When it is the other group s turn to pick, each member whose desired good was picked by the other group receives his weight from the group account. This rule has one exception: it is not executed for the second group in the first turn of the first group (so that each execution of step (e) is preceded by an execution of step (d)).

We now calculate the weights such that, when the protocol ends, the net payment paid by each happy agent is 1 and by each unhappy agent is 0 (i.e., each unhappy agent got all his money back). An agent s weight will be a function of the number r of his desired goods that remain untaken, and the number s of desired goods that he is missing to be happy. Both r and s of an agent weakly decrease as the protocol runs. An agent becomes happy when s = 0 and unhappy when r < s. Let w(r, s) be the weight of such an agent and B(r, s) the net amount paid by such an agent. Then, r s > 0:

( ) B(r, s) + w(r, s) = B(r 1, s 1) by step (d) B(r, s) w(r, s) = B(r 1, s) by step (e)

This implies the following recurrence relation for B(r, s):

r s > 0 : B(r, s) = B(r 1, s) + B(r 1, s 1)

2 r 0 : B(r, 0) = 1 (happy agents) r < s : B(r, s) = 0 (unhappy agents)

Its solution is (**): r s 0 : B(r, s) = 1

and (***): w(r, s) = B(r, s) B(r 1, s)

To complete the specification of the protocol, we have to calculate the initial payments in step (a). We define a generalized fairness criterion called f(d)-fairness, where f is some integer function. An allocation is f(d)-fair for an agent if the agent s group receives at least f(d) desired goods whenever the agent has d desired goods. Note that EF1 and MMSfairness are both equivalent to d

2 -fairness. Suppose we are interested in f(d)-fairness for some function f. Then, in the first group, an agent with d desired goods has initially r = d and s = f(d). Hence his initial payment should be B(d, f(d)). In the second group, such an agent might have lost a desired good in the first turn of the first group, so r = d 1 and the initial payment is only B(d 1, f(d)), which by (*) is smaller than B(d, f(d)). We are now ready to state the main lemma: Lemma 3.5. For every integer function f(d), it is possible to select weights such that the RWAV protocol attains hdemocratic f(d)-fairness, where:

h = inf d=1,2,... B(d 1, f(d)) = inf d=1,2,... 1 2d 1

Proof. In step (a), each agent pays at least h. Therefore, the initial balance of group i is at least h ni. In step (e) the group pays the total weight of a good, while in step (d) the group receives the total weight of another good. Since the good picked in step (c) has a maximal total weight, the balance of the group weakly increases, so its final balance is at least h ni. By (*), the final balance of each unhappy agent is 0 and of each happy agent 1. Since the total balance of the group plus the agents is 0, there are at least h ni happy agents.

Note that each group can choose its own f(d) and get its own h. As an example, suppose our group follows the egalitarian philosophy and we want to ensure that as many members as possible receive a positive utility. Then we can let

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

f(d) 1. For each d, the initial voting weight of a member with d desired goods is w(d, 1) = 1/2d. As the protocol progresses, the weight of a member whose desired good is taken by our group drops to zero, and the weight of a member whose desired good was taken by the other group is multiplied by 2. Thus the interests of poor agents are prioritized. Lemma 3.5 implies the following positive result.

Theorem 3.6. For every integer c 2, it is possible to select weights such that RWAV attains (1 1/2c 1)-democratic 1out-of-c MMS-fairness.

Proof. Suppose an agent wants d = l c + l goods, for some integers l 1 and l < c. So her 1-out-of-c-MMS is l. We can arbitrarily ignore l of her desired goods and aim to give her a utility of l. Applying Lemma 3.5 with f(lc) = l gives h = infl=1,2,... B(lc 1, l). It remains to prove that for every l, B(lc 1, l) B(c 1, 1) = 1 1/2c 1. The proof is combinatorial; we leave it to the full version.

Our results raise the following open question: what is the maximum fraction of agents that can be guaranteed 1-outof-c-fairness? By Theorem 3.6 it is at least 1 1/2c 1; by Proposition 3.3 it is at most 1 1/c22c+1. An interesting special case of Theorem 3.6 is when c = 2, since with two groups 1-out-of-2 MMS-fairness is equivalent to MMS-fairness, and with binary agents this is also equivalent to EF1. Hence Theorem 3.6 implies that 1/2-democratic EF1 and MMS-fairness are attainable. The fraction 1/2 exactly matches the upper bound in Proposition 3.4. It is interesting that our RWAV protocol gives the following unanimous guarantee that holds for all agents.

Corollary 3.7. For two groups each containing at most n agents with binary valuations, there exists an allocation that is 1-out-of-( log2(n + 1) + 1) MMS-fair for all agents. The O(log n) rate is asymptotically tight.

Proof. Let c = log2(n + 1) + 1, so n 2c 1 1. By Theorem 3.6, we can attain (1 1/2c 1)-democratic 1-out-of-c MMS-fairness. However, (1 1/2c 1)-democratic fairness and unanimous fairness are equivalent when the number of agents in each group is at most 2c 1 1. The tightness of the O(log n) rate follows from the remark after Theorem 3.6.

4 Two Groups with General Valuations

In this section we assume that there are two groups and each agent can have an arbitrary monotonic utility function. We start with a positive result: it is always possible to efficiently allocate goods so that at least half of the agents in each group believe the division is EF1. Despite the simplicity of the protocol, we find the result important since, unlike previous results in this setting [Manurangsi and Suksompong, 2017a; Suksompong, 2018], our result holds for worst-case instances with any number of agents in the groups and very general utility functions.

Theorem 4.1. For two groups with agents with monotonic valuations, 1/2-democratic EF1 is attainable.

Proof. We arrange the goods in a line and process them from left to right. Starting from an empty block, we add one good at a time until the current block is EF1 for at least half of the agents in at least one group. We allocate the current block to one such group, and the remaining goods to the other group. The proof that the protocol is 1/2-democratic EF1 can be found in the full version of this paper.

Theorem 4.1 shows that if the goods lie on a line, we can find a 1/2-democratic EF1 allocation that moreover gives each group a contiguous block on the line. This may be important, for example, if the goods are houses on a street and each group wants to have all its houses in a contiguous block [Bouveret et al., 2017; Suksompong, 2017]. If agents have additive valuations, Lemma 2.3 implies:

Corollary 4.2. For two groups with additive agents, 1/2democratic 1/2-MMS-fairness is attainable.

For EF1, the factor 1/2 in Theorem 4.1 is tight even for binary valuations, as shown in Proposition 3.4. For 1/2-MMSfairness, the factor 1/2 in Corollary 4.2 is almost tight:

Proposition 4.3. For any h > 1/3 and q > 1/2, there is an additive instance with two groups in which no allocation is h-democratic q-MMS-fair.

Proof. Consider an instance with m = 3 goods and n1 = n2 = 3 agents in each group, with utility vectors: ui1 = (2, 1, 1), ui2 = (1, 2, 1), and ui3 = (1, 1, 2) for i = 1, 2. The MMS of every agent is 2. In any allocation, one group receives at most one good, so at most one of its three agents receives utility more than 1. So in that group, at most 1/3 of the agents receive more than 1/2 of their MMS.

A corollary of Proposition 4.3 is that, for every h (1/3, 1/2], the maximum fraction q such that there always exists an h-democratic q-MMS-fair allocation is q = 1/2. What fraction of the agents can be satisfied if we are only interested in positive-MMS-fairness? The upper bound on h in Proposition 3.1 is 2/3 even for binary agents. Below we show a lower bound of 3/5 that holds for additive agents.

Theorem 4.4. For any two groups with additive agents, there exists a 3/5-democratic positive-MMS allocation.

Proof. An agent s maximin share is positive only if the agent has at least two goods with a positive utility. Therefore, for positive-MMS it is sufficient to give an agent at least one of his two best goods. We show that this can be attained for at least 3/5 of the agents in each group. First, convert all valuations to binary by assuming each agent desires only his two most valuable goods (breaking ties arbitrarily). If, in one of the groups, at least 3/5 of the agents desire the same good g, then give g to that group and give all other goods to the other group. The allocation is obviously 3/5democratic positive-MMS. Otherwise, run RWAV with the following initial payments. In the first group, all n1 agents pay B(2, 1) = 3/4. In the second group, there are less than 3 5n2 agents whose desired good was taken; these agents pay B(1, 1) = 1/2 and the others pay B(2, 1) = 3/4. The initial balance of the first group is 3

4n1. Hence, as in the proof of Lemma 3.5, at the end at least 3

4n1 of its members are

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

happy. The initial balance of the second group is at least 3 5n2 1

4 = 3 5n2. Hence, at the end at least 3

5n2 of its members are happy.

5 Three or More Groups In this section we study the most general setting where we allocate goods among any number of groups. When there are two groups, the protocol in Theorem 4.1 is efficient and yields an allocation that is both approximately envy-free and approximately MMS-fair. We present two ways of generalizing the result to multiple groups: one keeps the approximate envy-freeness guarantee but loses computational efficiency, while the other keeps only the approximate MMS-fairness guarantee but also retains compuational efficiency.

5.1 Approximate Envy-freeness The main theorem in this subsection is: Theorem 5.1. When all agents have binary valuations, there exists an allocation that is 1/k-democratic EF1 and 1/kdemocratic MMS-fair. The factor 1/k is tight for EF1. To establish this theorem, we prove two lemmas that may be of independent interest one on cake-cutting and the other on group allocation for agents with additive valuations. The result on cake-cutting generalizes the theorems of Stromquist [1980] and Su [1999], who prove the existence of contiguous envy-free cake allocations for individual agents. We consider a cake modeled as the interval [0, 1]. Each agent aij has a value-density function vij : [0, 1] R 0. The value of an agent for a piece X is Vij(X) = R

x X vij(x)dx. Denoting by Xi the allocation to group i, an allocation is envy-free for an agent aij if Vij(Xi) Vij(Xi ) for every group i . A contiguous allocation is an allocation of the cake in which each group gets a contiguous interval. Lemma 5.2. There always exists a contiguous cake allocation that is 1/k-democratic envy-free. The factor 1/k is tight. The proof of Lemma 5.2 can be found in the full version. The next lemma presents a reduction from approximate envy-free allocation of indivisible goods to envy-free cakecutting. We call this approximation EF-minus-2 . An allocation is EF-minus-2 for agent aij if for every group i , uij(Gi) > uij(Gi ) 2uij,max. The reduction generalizes Theorem 5 of Suksompong [2017]; a similar reduction was used in Theorem 3 of Barrera et al. [2015]. Lemma 5.3. When agents have additive valuations, there always exists a contiguous allocation of indivisible goods that is 1/k-democratic EF-minus-2.

Proof. Given an instance of indivisible goods allocation, we create a cake-cutting instance where the cake is the half-open interval (0, m]. The value-density functions are piecewise constant: for every l {1, . . . , m}, the value-density vij in the half-open interval (l 1, l] equals uij(gl). By Lemma 5.2, there exists a contiguous cake allocation that is envy-free for at least 1/k of the agents in each group. From this allocation we construct an allocation of goods as follows. If point g of the cake is in the interior of a piece, then good g is given to the group owning that piece. Else, point g

is at the boundary between two pieces, and good g is given to the group owning the piece to its left. A group gets good g only if it owns a positive fraction of the interval (g 1, g]. Hence, in the allocation, each group loses strictly less than the value of a good and gains strictly less than the value of a good (relative to its value in the cake division). This means that every agent who believes that the cake allocation is envy-free also believes that the goods allocation is EF-minus-2.

Proof of Theorem 5.1. Suppose an allocation is EF-minus-2 for some agent aij. This means that the agent s envy towards any other group is less than 2uij,max 2. Since the agent has binary valuations, the envy is at most 1, meaning that the allocation is EF1 for that agent. Hence any 1/kdemocratic EF-minus-2 allocation, which is guaranteed to exist by Lemma 5.3, is also 1/k-democratic EF1. By Lemma 2.3 it is also 1/k-democratic MMS-fair. The proof of tightness can be found in the full version.

The cake-cutting protocol of Lemma 5.2 might take infinitely many steps to converge. In fact, there is no finite protocol for contiguous envy-free cake-cutting even for individuals [Stromquist, 2008]. However, the division guaranteed by Lemma 5.3 and Theorem 5.1 can be found in finite time (exponential in the input size) by checking all possible allocations. It is interesting whether a faster algorithm exists.

5.2 Approximate MMS In this subsection, we show that if we weaken our fairness requirement to approximate MMS, it is possible to compute a fair allocation in time polynomial in the input size. Lemma 5.4. When agents have additive valuations, there always exists an allocation such that at least 1/k of the agents aij in each group Ai receive utility at least 1

k uij(G) k 1

k uij,max, and such an allocation can be computed efficiently. This lemma generalizes the corresponding result for the setting with one agent per group by Suksompong [2017]. The factor (k 1)/k is tight even for individual agents.

Proof. We arrange the goods in a line and process them from left to right. Starting from an empty block, we add one good at a time until the current block yields utility at least 1 k uij(G) k 1

k uij,max for at least 1/k of the agents in at least one group. We allocate the current block to one such group and repeat the process with the remaining k 1 groups. It is clear that this algorithm can be implemented efficiently. The proof of correctness is similar to that of the corresponding result for the setting with one agent per group [Suksompong, 2017]; we leave it to the full version of this paper.

It is clear by definition that the MMS of any agent aij is at most 1

k uij(G). Lemma 5.4 therefore implies the following: Theorem 5.5. When agents have additive valuations, there always exists an allocation such that at least 1/k of the agents aij in each group Ai receive utility at least MMSij(G) k 1

k uij,max, and such an allocation can be computed efficiently. For binary valuations, if we change the stopping condition in Lemma 5.4 to be when the current block yields the MMS for at least 1/k of the agents in some group, we get:

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Theorem 5.6. When agents have binary valuations, there always exists a 1/k-democratic MMS-fair allocation, and such an allocation can be computed efficiently.

6 Discussion and Future Work

For two groups, we have a comprehensive understanding of possible democratic fairness guarantees. We have a complete characterization of possible envy-freeness approximations, and upper and lower bounds for maximin-share-fairness approximations. Some remaining gaps are shown in Table 1; closing them raises interesting combinatorial challenges. For k 3 groups, the challenges are much greater. Currently all our fairness guarantees are to 1/k of the agents in all groups. From a practical perspective, it may be important in some settings to give fairness guarantees to at least half of the agents in all groups. Preliminary numerical calculations indicate that the RWAV protocol can be modified to provide such guarantees; establishing the guarantees theoretically is an avenue for future work. From an algorithmic perspective, it is interesting whether there exists a polynomial-time algorithm that guarantees EF1 to any positive fraction of the agents. A possible concern about democratic fairness is that it completely leaves aside a fraction of the agents in each group. As Lemma 3.2 shows, it might be inevitable to leave some agents with zero utility. In these cases, the goal of an egalitarianist is to minimize the fraction of such poor agents. While the weighting scheme used by our RWAV protocol indeed prioritizes the interests of poor agents (see the example after Lemma 3.5), it may be interesting to develop an algorithm that directly minimizes the maximum fraction of poor agents across all groups.

Acknowledgments

We are grateful to Fedor Petrov, Arnaud Mortier, Darij Grinberg, Michael Korn, Kevin P. Costello, Nick Gill, Jack D Aurizio, Leon Bloy and anonymous referees of IJCAIECAI 2018 and COMSOC 2018 for their helpful comments.

References [Babaioff et al., 2017] Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. Competitive equilibria with indivisible goods and generic budgets. Co RR, abs/1703.08150, 2017. [Barrera et al., 2015] Roberto Barrera, Kathryn Nyman, Amanda Ruiz, Francis Edward Su, and Yan Zhang. Discrete envy-free division of necklaces and maps. Co RR, abs/1510.02132, 2015. [Bouveret et al., 2017] Sylvain Bouveret, Katar ına Cechl arov a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In IJCAI, pages 135 141, 2017. [Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. A procedure for divorce settlements. Meditation Quarterly, 13(3):191 205, 1996. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium

from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Erd os, 1964] Paul Erd os. On a combinatorial problem. II. Acta Mathematica Academiae Scientiarum Hungarica, 15(3 4):445 447, 1964. [Goldman and Procaccia, 2014] Jonathan Goldman and Ariel D. Procaccia. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2), 2014. [Lipton et al., 2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In EC, 2004. [Manurangsi and Suksompong, 2017a] Pasin Manurangsi and Warut Suksompong. Asymptotic existence of fair divisions for groups. Mathematical Social Sciences, 89:100 108, 2017. [Manurangsi and Suksompong, 2017b] Pasin Manurangsi and Warut Suksompong. Computing an approximately optimal agreeable set of items. In IJCAI, 2017. [Moulin, 1990] Herv e Moulin. Uniform externalities: Two axioms for fair allocation. Journal of Public Economics, 43(3):305 326, 1990. [Procaccia and Wang, 2014] Ariel D. Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. In EC, pages 675 692, 2014. [Segal-Halevi and Nitzan, 2015] Erel Segal-Halevi and Shmuel Nitzan. Fair cake-cutting among families. Co RR, abs/1510.03903, 2015. [Segal-Halevi and Suksompong, 2018] Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods. Co RR, abs/1709.02564, 2018. [Stromquist, 1980] Walter Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640 644, 1980. [Stromquist, 2008] Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols. Electronic Journal of Combinatorics, 15:#R11, 2008. [Su, 1999] Francis Edward Su. Rental harmony: Sperner s lemma in fair division. The American Mathematical Monthly, 106(10):930 942, 1999. [Suksompong, 2016] Warut Suksompong. Assigning a small agreeable set of indivisible items to multiple players. In IJCAI, pages 489 495, 2016. [Suksompong, 2017] Warut Suksompong. Fairly allocating contiguous blocks of indivisible items. In SAGT, pages 333 344, 2017. [Suksompong, 2018] Warut Suksompong. Approximate maximin shares for groups of agents. Mathematical Social Sciences, 92:40 47, 2018. [Todo et al., 2011] Taiki Todo, Runcong Li, Xuemei Hu, Takayuki Mouri, Atsushi Iwasaki, and Makoto Yokoo. Generalizing envy-freeness toward group of agents. In IJCAI, pages 386 392, 2011.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)