Democratic Fair Allocation of Indivisible Goods

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?

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/c2 2c+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 RelatedWork

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 allocation 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 [SegalHalevi 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,...,muij(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′ ) = ∑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 every i′ there is a set Ci′ ⊆ Gi′ with |Ci′ | ≤ c such that

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:

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) ≥MMScij (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 3members, 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 c2 2c+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 c2 2c+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 c2 2c+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.

Proposition 3.3. For any integer c ≥ 2 and h > 1 - 1/c2 2c+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 fromLemma 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: ∑2l j=l-⌊c/2⌋ (2l j )2 = ∑l-1 j=l-⌊c/2⌋ (2l j )2 + 1 2 (2l l )2 + 12 (4l 2l), where the equality follows 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:

This implies the following recurrence relation for B(r, 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 ⌊ d2 ⌋-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:

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 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/c2 2c+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 35 n2 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 4 n1. Hence, as in the proof of Lemma 3.5, at the end at least 3 4 n1 of its members are happy. The initial balance of the second group is at least 35 n2 · 12 + 25 n2 · 34 = 35 n2. Hence, at the end at least 35 n2 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) = ∫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 1k ·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 1k · 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 1k · 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 groupAi 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:

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 FutureWork

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.