To Give or Not to Give: Fair Division for Single Minded Valuations

1 Introduction

The question of dividing scarce resources among multiple participants in a way that is fair has remained a pressing question that intrigued humans for a long time, be it for dividing land among citizens 1 or allocating organizational resources to its members. The formal study of fair division as we know it

⇤The full version of the paper can be found on the archive at http://arxiv.org/abs/1602.09088.

We are grateful to Erel Segal-Halevi for useful feedback. The authors aknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61361136003) for the Sino-Danish Center for the Theory of Interactive Computation and from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. A part of this work was done while Simina Brˆanzei and Ruta Mehta were visiting the Simons Institute for the Theory of Computing. Simina Brˆanzei was also supported by ISF grant 1435/14 administered by the Israeli Academy of Sciences and Israel-USA Bi-national Science Foundation (BSF) grant 2014389, as well as the I-CORE Program of the Planning and Budgeting Committee and The Israel Science Foundation.

1 Divide-and-choose is mentioned already in the Bible, in the Book of Genesis (chapter 13)

Ruta Mehta

University of Illinois Urbana-Champaign Champaign, USA

started during World War II with works of Steinhaus, Knaster and Banach [Steinhaus, 1951]. Much of the earlier work focused on one heterogeneous divisible good, i.e. the cake cutting problem [Brams and Taylor, 1996; Robertson and Webb, 1998], while other models and notions of fairness were studied later in a growing body of literature [Moulin, 2004]. Fair division has been recently studied in the computer science community, as problems in resource allocation and fair division in particular are arguably relevant for the design of multiagent systems, including manufacturing and scheduling, airport traffic, and industrial procurement [Chevaleyre et al., 2006; Procaccia, 2013].

Prominent examples of fair division models that surfaced recently in real scenarios include problem of allocating computational resources (e.g. CPU, memory, bandwith) among the users of a system [Ghodsi et al., 2011], or the problem of allocating university courses to students in a way that is fair and efficient. The latter motivated the introduction of a notion of fairness known as A-CEEI [Budish, 2011], which approximates the well known ideal notion of fairness from economics, the competitive equilibrium from equal incomes [Foley, 1967; Varian, 1974]. Othman et al. [2014] studied the complexity of A-CEEI with pessimistic conclusions for general preferences. Nevertheless, the A-CEEI solution is used to allocate courses to students at the Wharton Business School at the University of Pennsylvania.

The largest body of the literature on fair division models for multiple divisible and indivisible goods, including cake cutting, focuses on additive valuations, which capture perfect substitutes, i.e. goods that can replace each other in consumption, such as Pepsi and Coca-Cola. However, many real allocation problems have complementarities in the preferences to various degrees. For example, if the user of a computer system wants to run a specific task, they may need 2 units of CPU and 5 units of RAM. It is not useful if the user gets only 1 unit of CPU but 6 or more units of RAM - they simply cannot run the task because CPU is a bottleneck resource.

An important scenario with complements is that of single minded valuations, where the agent values a particular bundle and nothing less, and anything extra does not add to the value. Such valuations arise naturally, for example assembling a bike requires a set of parts, or an agent's computational task can finish if and only if it is allocated a required bundle of resource. The latter example represents basis for more complex models that take into account the dynamics over time. Due to their immense applicability, there is an extensive body of literature on such single minded valuations in areas such as auctions and exchange markets (see, e.g., [Briest et al., 2005; Nisan et al., 2007; Ledyard, 2007; Robu et al., 2013; Feldman and Lucier, 2014; Feige et al., 2015]), however work on fair division with such valuations is largely missing.

1.1 Our Contribution

We study fair division among single minded agents for three main scenarios, namely multiple divisible goods, cake cutting, and discrete goods. Our main solution concept-the "competitive allocation from equal incomes" (CAEI)-is inspired frommarket equilibria and implements fair outcomes through a pricing mechanism. The CAEI solution can be seen as a relaxation of the standard competitive equilibrium from equal incomes and is a more intuitive notion for discrete resources than the latter. However many of our results, most notably for multiple divisible goods, carry over to the competitive equilibrium from equal incomes solution. The CAEI solution concept is sandwhiched between the competitive equilibrium from equal incomes and envy-freeness, and it prunes (via the prices), the least desirable envy-free allocations. Nevertheless, CAEI exists if and only if envy-free allocations exist in all the fair division models we consider.

For multiple divisible goods and cake cutting we show existence of CAEI, while for discrete goods we give a succinct characterization of instances that admit this solution; then we give an efficient algorithm to find one in all cases. Maximizing social welfare turns out to be NP-hard in general, however we obtain efficient algorithms for a number of settings, (i) divisible and discrete goods when the number of different types of agents is a constant, (ii) cake cutting with contiguous demands and (iii) cake cutting with constant number of agents.

Our results also carry over to valuation models where the agents have a desired target set (e.g. the set of parts of a bike), while having very small positive value (✏) for any bundle that does not contain their desired set. For such scenarios (which are compatible with experimental evidence that people like to accumulate "stuff", even if unneeded), the solution computed is an ✏-CAEI.

2 Background

We begin by presenting the model and solution concept for the most general setting. Let N = ¶1↪ ▷ ▷ ▷ ↪ n♦ be a set of agents and R a set of resources, where R is a compact subset of a Euclidean space. Each agent i is equipped with a valuation function Vi over the resources, such that for each subset S ✓ R, Vi(S) represents the valuation of agent i for bundle S. The goal is to allocate the resources among the agents in a way that is fair.

Agent i is said to be single minded if there exists a bundle Di ✓ R that i cannot be happy without; that is, for any other bundle S ✓ R we have that Vi(S) = 1 if Di ⇢ S and Vi(S) = 0 otherwise.

An allocation x = (x1↪ ▷ ▷ ▷ ↪ xn) is a partition of the set R of resources such that xi ✓ R is the bundle received by agent i, the bundles are not intersecting and add up to the whole space.

Our solution concept-the "competitive allocation from equal incomes" (CAEI)-is inspired frommarket equilibria and implements fair outcomes through a pricing mechanism. More formally, each agent is given an artificial unit of currency by the center. It can be used to acquire goods, and has no intrinsic value. The agent wants to spend its budget to acquire a bundle of items that maximizes its utility. A CAEI outcome is defined as a tuple hp↪ xi, where x is an allocation and p : R ! R+ is an integrable, non-negative price density function, such that for each subset S ✓ R, p(S) = Rx2S p(x)dx. Formally, hp↪ xi is a CAEI solution if and only if:

• ÷ All the resources are allocated: Sni=1 xi = R. ÷ No agent overspends: p(xi)  1 for all i 2 N.
• ÷ For all i 2 N, xi maximizes agent i's utility given prices p and its unit budget.

The difference between the CAEI solution and the competitive equilibrium from equal incomes (CEEI), is that under CEEI, the agents are additionally required to spend all of their budget. Since we are in a fair division setting, neither the center nor the agents have value for the units of currency, thus the requirement of spending all the budgets can be relaxed naturally. More importantly, in several of the scenarios we study, the CEEI solution is not as tractable due to discontinuity of the valuations and/or discrete goods.

Note that every CAEI allocation is envy-free, since if an agent envied another agent's bundle it could just buy it instead, as the endowments are equal; the prices provide a mechanism for indicating the interest level in the different resources. However, since the valuations are discontinuous, CAEI outcomes are not necessarily efficient. Thus our aim will be to compute CAEI allocations with improved welfare guarantees.

The social welfare of an allocation x is the sum of utilities of all the agents: SW(x) = Pni=1 Vi(xi).

3 Multiple Divisible Goods

We now formalize the model with multiple divisible goods and single minded agents. There is a set N = ¶1↪ ▷ ▷ ▷ ↪ n♦ of agents and a set M = ¶1↪ ▷ ▷ ▷ ↪m♦ of goods. W.l.o.g., each good comes in one unit that is infinitely divisible. Each agent i demands a bundle Di = hvi↪1↪ ▷ ▷ ▷ ↪ vi↪mi, where vi↪j 2 [0↪ 1] denotes the fraction required by agent i from good j. The utility of i for a bundle z 2 [0↪ 1]m is Vi(z) = 1 if zj ≥ vi↪j for all j 2 M, and Vi(z) = 0 otherwise. Since every part of a good is equally valued by agents, it suffices to specify its per unit price, i.e., pj 2 R+ for good j.

We first show that the CAEI solution is guaranteed to exist for multiple divisible goods with single minded valuations, and can moreover be computed in polynomial time. All the results in this section apply to the CEEI solution as well, which differs only by requiring that agents exhaust their unit of currency.

Theorem 1. Given a fair division problem with multiple divisible goods and single minded agents, a CAEI solution is guaranteed to exist and can be computed in polynomial time.

Proof. To prove the statement we leverage results on the existence and computation of market equilibria in Fisher markets with Leontief utilities (for background see, e.g., chapter 5 in [Nisan et al., 2007]). Given fair division problem

(N↪M↪D), we consider a Fisher market where the set of buyers is N and the set of items is M. Each buyer i has budget Bi = 1 and Leontief utility described by the vector Di = hvi↪1↪ ▷ ▷ ▷ ↪ vi↪mi, i.e. for any bundle z, ui(z) = minj2M:vi↪j>0 n zj vi↪j o. Fisher markets with Leontief utilities always have exact market equilibria when each item is desired by at least one buyer and each buyer desires at least one item [Maxfield, 1997].

Let (x↪ p) be any such equilibrium, where xi↪j is the fraction received by agent i from good j and pj is the price of good j. Denote the Leontief utility of buyer i in the market by uLi (xi↪ p) = minj2M:vi↪j>0 n xi↪j vi↪j o. We argue the market equilibrium (x↪ p) is a CAEI solution for the fair division problem with single minded agents. To this end, we must show that all the items are allocated, each agent spends no more than a unit, and gets in exchange an optimal bundle at those prices. Clearly the first two requirements are met since (x↪ p) is a market equilibrium in the Fisher market with identical budgets.

We additionally show that each agent gets an optimal bundle in the fair division problem. For every agent i, if the allocation x satisfies the property that xi↪j ≥ vi↪j for all j 2 M, then Vi(xi) = 1 and i gets its demand at these prices. Otherwise, there is an item k with vi↪k > 0 but xi↪k < vi↪k; then agent i does not get its demand, thus Vi(xi) = 0. Since (x↪ p) is a market equilibrium with respect to the Leontief utilities given by v, we have uLi (xi↪ p)  xi↪k vi↪k < 1.

Assume by contradiction that in the fair division problem agent i could afford its demand set at prices p, i.e. 9y 2 [0↪ 1]m with yj ≥ vi↪j 8j 2 M, and p(y)  1. Then in the Fisher market with Leontief utilities, buyer i could also purchase bundle y and get: uLi (y↪ p) = minj:vi↪j>0 n yj vi↪j o ≥ minj:vi↪j>0 n vi↪j vi↪j o = 1 > uLi (xi↪ p), which is a strict imlibrium in the Fisher market. Thus the assumption was false

provement over xi, contradicting that (x↪ p) is a market equiand (x↪ p) is a CAEI.

Finally, Codenotti and Varadarajan (2004) showed that a Fisher market equilibrium can be computed in polynomial time via a convex program formulation, which can be used to compute a CAEI solution for single minded agents.

As the next example illustrates, the solution computed in Theorem 1 is not necessarily optimal.

Example 1. Consider 2 agents and 2 goods, where the demand of agent 1 is D1 = h0▷5↪ 0▷4i and of agent 2 is D2 = h0↪ 0▷6i. The CAEI solution from Theorem 1 prices good 1 at p1 = 0 and good 2 at p2 = 2, and the allocation splits good 2 equally between the two agents. This way agent 2 gets zero utility, while agent 1 gets utility 1 (and some extra good that is of no use). Instead, another possible CAEI solution is to set prices p0 = h1◁3↪ 5◁3i, where agent 2 can now afford a quantity of 0.6 from good 2, and agent 1 still gets its demand. Thus the CAEI solution computed via the Leontief market equilibrium is dominated by another CAEI solution with better welfare.

We show that while maximizing social welfare is in general NP-hard, the problem can be solved in polynomial time when

Algorithm 1: COMPUTE-MAX-CAEI

Data: Agents N = ¶1↪ ▷ ▷ ▷ ↪ n♦, items M = ¶1↪ ▷ ▷ ▷ ↪ m♦, valuations v, types ⌧ Result: Social welfare maximizing CAEI 1 (OPT↪ x⇤ ↪ p⇤ ) (-1↪ NULL↪ NULL) 2 foreach S ✓ T do 3 (m↪ p) SOLVE-OPTIMAL-SUBSET(S↪M) 4 xi↪j = mi↪j pj ↪ 8i 2 N↪ 8j 2M 5 if (SW(x) > OPT) then 6 OPT SW(x) 7 (x⇤ ↪ p⇤ ) (x↪ p) 8 end 9 end 10 return (x⇤ ↪ p⇤ )

the number of types of agents is constant. This allows handling possibly large numbers of agents when their demands fit some standard templates for resource requests.

Theorem 2. Computing a CEEI solution that maximizes social welfare for single minded valuations with divisible goods is NP-hard.

The reduction from the NP-complete problem SET PACKING is deferred to the full version.

Theorem 3. Given a fair division problem with single minded agents and divisible goods, a welfare maximizing CAEI solution can be found in polynomial time for a constant number of agent types.

Proof. We are given a set N = ¶1↪ ▷ ▷ ▷ ↪ n♦ of agents, M of items, valuations D, and T a set of types of agents, such that for each i 2 N, ⌧(i) 2 T represents the type of agent i, and agents with same type have identical valuation (⌧(i) = ⌧ (i0 ) ) vi = vi0 ). Algorithm 1 solves this problem and runs in polynomial time for fixed ♣T ♣.

Procedure SOLVE-OPTIMAL-SUBSET is given as a linear program, where pj is the price of good j, mi↪j is the amount of money spent by agent i on good j, and ✏ is a variable that should be strictly positive in the optimal solution if the set S of agent types can be made simultaneously happy.

The observation underlying the algorithm is that agents of the same type must have identical utilities (but not necessarily identical bundles). The COMPUTE-MAX-CAEI procedure tries to compute a CAEI solution for every set S of types so that agents of type ⌧ 2 S are satisfied, while agents outside S cannot afford their demand. The LP constraints ensure these conditions are met and a positive solution is found if and only if there exists a CAEI solution for the set S. At the end, COMPUTE-MAX-CAEI selects the maximum over all S.

4 Cake Cutting

Next we investigate the cake cutting problem with single minded agents. Cake cutting models the problem of allocating a heterogeneous divisible resource, such as land, time, mineral deposits or computer memory, among agents with different preferences. The "cake" is represented mathematically as the interval [0↪ 1] and the agents have different preferences over the interval. A "piece" of cake A is a union of intervals: A = (I1↪ ▷ ▷ ▷ ↪ Im). The literature on cake cutting has seen very interesting algorithmic developments in recent years (see, e.g., [Kurokawa et al., 2013; Segal-Halevi et al., 2015c; Aziz and Mackenzie, 2016]), all of which are concerned with additive valuations in the one-dimensional model. Among the few exceptions we mention: [Caragiannis et al., 2011] studied fair division with additive valuations constrained by a minimum length requirement (PUML), [Branzei et al., 2013] studied externalities in cake cutting, while [Segal-Halevi et al., 2015a; 2015b], studied cake cutting in two dimensions, where the agents also care about the shape of the pieces that they receive. In earlier work, a different multidimensional model of fair division has been explored under the name of pie-cutting by Brams et al. [Brams et al., 2008], while a very general model of fair resource division has been explored in the works of DallAglio and Maccheroni and of Husseinov and Sagara , who prove the existence of fair and efficient allocations under mild conditions assuming that the valuations are continuous. However, single minded valuations are discontinuous, and so their results do not directly imply ours.

In this paper we focus on single minded agents, and so each agent i will demand a set Di consisting of possibly several disjoint intervals: Di = (Di↪1↪ ▷ ▷ ▷ ↪Di↪mi ). The utility of agent i for a piece of cake A ✓ [0↪ 1] is: Vi(A) = 1 if Di ✓ A and Vi(A) = 0 otherwise.

Examples of single minded agents in cake cutting include cases where the agent requires land that has buildings on it (with some particular functionality) or wants to build a house in a particular location. The case where each single minded agent requires a contiguous piece (i.e., mi = 1) can in fact be mapped to a standard problem known as "interval scheduling" in operations research.

We first show that the CAEI solution always exists and can be computed efficiently in this model.

Theorem 4. A CAEI solution is guaranteed to exist and can be computed in polynomial time in the cake cutting problem with single minded agents.

Proof. For each i 2 N, let Di = (Di↪1↪ ▷ ▷ ▷ ↪Di↪mi ) be the disjoint intervals in its demand set, where Di↪j = [li↪j↪ ri↪j] ✓

[0↪ 1]. Divide each interval Di↪j into two equal pieces, and let Fi↪j = nli↪j↪ li↪j+ri↪j 2 ↪ ri↪j o be the set of points resulting from this partition of Di↪j . Consider the set of all the distinct points thus obtained: P = (Sni=1 Smi j=1 Fi↪j)[¶0↪ 1♦ = ¶q0, q1, ▷ ▷ ▷, qm♦, where 0 = q0 < q1 < ▷ ▷ ▷ < qm = 1. Then we can view every segment Ik = [qk↪ qk+1] delimitated by two consecutive points in P as an indivisible good; moreover, good Ik is in the demand set of each agent i for which [qk↪ qk+1] ⇢ Di. This gives a related allocation problem with m indivisible goods and n agents, where no agent has a demand set consisting of a single good. The latter property follows from the fact that we partitioned each interval Di↪j into two pieces, which are viewed as distinct goods. From [Branzei et al., 2015], a competitive equilibrium from equal incomes is guaranteed to exist and can be computed in polynomial time for every fair division problem with indivisible goods and single minded agents, where no agent has a demand set with only one good; let (x↪ p) be such an allocation and prices.

Then we can compute a CAEI in cake cutting by allocating the intervals in P in the same order (from left to right) as the indivisible goods are allocated under x and setting the price curve of each interval [qk↪ qk+1] uniformly such that it sums up to the price of the corresponding indivisible good.

When the demands are contiguous we can compute a welfare maximizing CAEI in polynomial time. The proof requires a more delicate construction, the details of which are in the full version of the paper (Branzei, Lv, Mehta [2016]).

Theorem 5. A welfare-maximizing CAEI can be computed in polynomial time in cake cutting with single minded agents and contiguous demands. Moreover, when there are no identical agents, the welfare maximizing CAEI coincides with the solution to the pure optimization problem of maximizing welfare.

Proof. The idea is to leverage a connection with the interval scheduling problem [Kleinberg and Tardos, 2005] to first decide the agents that get allocated, and then to construct an asymmetric pricing scheme to implement a price equilibrium.

The interval scheduling problem is as follows. There are n jobs to be run on a supercomputer, where each job i runs from time si to time fi. There are multiple such requests arriving simultaneously, and the goal is to process as many of them as possible, but the computer can only run one job at a time. The question is how to schedule the jobs so that the maximum number of requests is served. The optimal allocation-that maximizes the number of jobs scheduled-is given by a greedy algorithm: Schedule first the job with the earliest finishing time, then remove the jobs intersecting with it, and repeat among the remaining jobs.

This problem can be mapped to cake cutting with single minded agents by considering an agent for each job, i.e. N = ¶1↪ ▷ ▷ ▷ ↪ n♦, and setting the demand of each agent i to the schedule of job i, that is Di = ¶[si↪ fi]♦, where si, fi are normalized in [0↪ 1].

While our aim is to indeed maximize the number of completed jobs, we want to achieve this in a way that is fair. That is, we will compute an allocation of the cake x and a price curve p such that (x↪ p) represent a CAEI solution, where p(x) is the value of the price density function at point x. This can be accomplished by allocating the agents in the same name order that the greedy algorithm allocates the corresponding jobs, with the caveat that if multiple agents have the same finishing time, then the one with the latest starting time must be selected. For each k-th agent that gets selected to receive their full demand, we select two very small intervals at the left and right endpoints of their demand, respectively, and price them (uniformly) to sum up to k · ✏ and 1 - k · ✏, respectively. When there are no identical demands, the agents that don't get served but for which there is an unallocated piece of their demand, can receive a small such piece (at a total price of 1); otherwise, they get nothing (but their demand now has the property that it costs more than 1). This allocation can be done so that the whole cake is divided.

Then to handle identical agents, the algorithm can be modified such that whenever selecting the earliest finishing time and finding multiple agents with the same finish and start time, then take a very small interval at the leftmost point of the unallocated cake and divide it equally among the identified identical agents, setting the price uniformly to sum up to their budgets. Then iterate on the remaining cake. The complete proof is deferred to the full version, while an example with 4 agents is given in Figure 1.

On the other hand, if the demands are not contiguous, then the problem of computing a welfare maximizing CAEI is NPhard. The reduction from SET PACKING is in the full version.

Theorem 6. Given a cake cutting problem with single minded valuations, computing a welfare-maximizing CAEI is NP-hard.

We can also maximize social welfare for discontinuous demands in polynomial time when the number of agents is constant. The idea is to try out every possible set S ✓ N of happy agents, who will receive their required land at a price of one, while the remaining agents split the remaining cake at prices so they cannot afford their demand. Then select the outcome that maximizes welfare among all choices of S.

Theorem 7. Given a cake cutting problem with single minded agents, a welfare maximizing CAEI can be computed in polynomial time when the number of agents is constant.

5 Multiple Discrete Goods

Our setting for discrete goods is as follows. There is a set N = ¶1↪ ▷ ▷ ▷ ↪ n♦ of agents and M = ¶1↪ ▷ ▷ ▷ ↪ n♦ of items, where each item j comes in Qj indivisible copies. Each agent i has a demand set Di ✓ M, and wants a copy of each item j 2 Di; Di is not a multi-set. Without loss of generality, we assume that each type of item is required by some agent. We illustrate the model with an example: there are agents N = ¶1↪ 2♦, items M = ¶1↪ 2↪ 3♦, quantities Q1 = Q3 = 1, Q2 = 2, and demands D1 = ¶1↪ 2♦, D2 = ¶2↪ 3♦.

Next we provide a succinct characterization of the instances that admit a CAEI solution. To this end, a useful notion will be that of over-demand. We say that an item j is over-demanded among a set of agents S if the aggregate demand of the agents in S exceeds the available supply from item j, namely Qj . We illustrate this in the next example.

The goal is to find a set of prices for each item-such that every copy from the same item has an identical price-together with an allocation x such that (x↪ p) is a CAEI solution. In our example, a CAEI solution is attained at: p1 = 0▷5↪ p2 = 0▷5↪ p3 = 0▷5 and x1 = ¶1↪ 2♦, x2 = ¶2↪ 3♦.

Example 1. Consider a market Mwith single minded agents and discrete goods, where M = ¶1↪ 2♦, with quantities Q1 = 2 and Q2 = 4, and agents N = ¶1↪ ▷ ▷ ▷ ↪ 4♦, with demands: D1 = D2 = D3 = ¶1♦, D4 = ¶1↪ 2♦. Then the aggregate demand of the set of agents S = ¶1↪ 2↪ 3♦ with singleton demands, consists of 3 copies of item 1, which exceeds Q1, the available supply from this item. Thus item 1 is over-demanded among S.

The next theorem shows that these are essentially the only instances that don't have a fair outcome. We say that demand of agent i is singleton if ♣Di♣ = 1.

Theorem 8. Given a fair division problem with single minded agents and discrete goods, a CAEI solution exists if and only if there is no set of agents with singleton demands that give rise to an over-demanded item among that set. Moreover, a solution can be computed in polynomial time if it exists.

Proof. Consider Algorithm 2. Clearly, if there is a set of agents S with singleton demands, such that Di = ¶j♦ for some j 2 M and all i 2 S, where ♣S♣ > Qj, then no CAEI can exist. This is because pj  1 causes over-demand, and pj > 1 makes it un-affordable and thereby un-sold.

We claim all other instances admit a CAEI. Algorithm 2 forms a sequence S of active agents, initially containing all the agents sorted in increasing order of ♣Di♣, and then iterates over the item types, at each step searching for an item that is desired by more agents among the active ones (i.e. in S) than there are copies available. If such an item j is found, then j is allocated at a price of pj = 1, one copy to each of the first Qj agents in S that want it. All the active agents that got item j are removed from S, and the algorithm searches for another such over-demanded and unallocated item among the updated set S. Otherwise, when no such item is found, all the goods left are in abundant supply for the agents in S and can be given for a small price (✏) among them. Note that these last agents, which are allocated bundles at a price of ✏ per good, receive not only items that they desire, but in fact all the remaining items.

We argue that the pricing rule ensures that a CAEI is computed. In particular, all the goods are allocated-at latest, the player (or set of players), which receive items in the last round of the algorithm, get all the remaining items. Moreover, the

Algorithm 2: COMPUTE-DISCRETE-CAEI

Input: Agents N = ¶1↪ ▷ ▷ ▷ ↪ n♦, items M = ¶1, ▷ ▷ ▷, m♦, demand sets Di, quantities Qj Output: CAEI (x↪ p), or NULL if none exists 1 for each (j 2M) do 2 if (Qj < card (¶i 2 N ♣ Di = ¶j♦♦)) then 3 return NULL // No solution 4 end 5 end 6 A ; // item types allocated so far 7 S SORT-BY-DEMAND-SET-SIZE(N) // Sort the players in increasing order of demand set size 8 while (9j 2 M ∩ A : OVER-DEMAND(j↪ S) = TRUE) do 9 pj 1; ALLOCATE-OVERDEMAND(j↪ S); A A[ ¶j♦ 10 end 11 ✏ 1◁ ⇣1+ Pmj=1 Qj ⌘ // very small value 12 for each (j 2M ∩ A) do 13 pj ✏; ALLOCATE-REMAINDER(j↪ S); A A[ ¶j♦ 14 end 15 Procedure ALLOCATE-OVERDEMAND(j, S) 16 Q Qj; Sj ¶k 2 S ♣ j 2 Dk♦ // active agents that want item j 17 // Give one copy of j to every active agent that wants it until running out of copies 18 for each (i 2 Sj) do 19 if (Q > 0) then 20 append(xi↪ j); Q Q-1 // Agent i gets a copy of j; decrease the # of copies left 21 S S ∩ ¶i♦ // mark i as inactive 22 end 23 end 24 Procedure ALLOCATE-REMAINDER(j, S) 25 Sj ¶k 2 S ♣ j 2 Dk♦ // active agents that want item j 26 for each (i 2 Sj) do 27 append(xi↪ j) 28 end 29 K Qj - ♣Sj♣ // # of copies of j left unallocated 30 if (K > 0) then 31 ` Sj▷last() // The last player in Sj gets all the additional copies of j 32 append(x`↪ ¶j♦ ⇥ K) 33 end

pricing rule is such that each agent i is allocated all of its bundle at once, regardless of whether xi contains i's required demand set or not. The agents are divided in two categories, namely those who get exactly one item at a price of 1 (Line 9) and those who get multiple items at a price of ✏ (Line 13). In both cases, the pricing rule ensures that the allocation xi costs at most 1. By a case analysis, it can be seen that each agent gets an optimal bundle at the given prices; due to space constraints, this is delegated to the full version.

We illustrate Algorithm 2 on an example.

Example 2. Let N = ¶1,2,3,4,5♦, M = ¶1,2,3,4,5♦, quantities Q1 = 2, Q2 = 4, Q3 = 2, Q4 = 3, Q5 = 2, demands: D1 = ¶1♦, D2 = ¶1,2♦, D3 = ¶1,3♦, D4 = ¶2,3,4♦, D4 = ¶2,3,4,5♦. Only agent 1 has singleton demand ¶1♦ and ♣Q1♣ ≥ 1, so there is a CAEI. Algorithm 2 sorts the agents in increasing order by demand set size and initializes S = (1↪ 2↪ 3↪ 4↪ 5). The search for over-demanded items begins. Item 1 is wanted by 3 agents in S, namely ¶1↪ 2↪ 3♦, but Q1 = 2 < 3; it is over-demanded. Set p1 = 1, x1 = x2 = ¶1♦. Update S S ∩ ¶1↪ 2♦ = ¶3↪ 4↪ 5♦. Next item 3 is over-demanded (wanted by agents 3↪ 4↪ 5 but Q3 = 2). Set p3 = 1 and x3 = x4 = ¶3♦. Update S = ¶5♦. All the items are in sufficient quantities now, give all of them to agent 5 at price ✏ = 1◁14 each.

It is NP-hard to compute a welfare-maximizing CAEI (see [Branzei et al., 2015]), but if we no longer insist on all the items being allocated, then we get a polynomial time algorithm by solving the problem as if the goods were divisible, and then rounding the solution.

Theorem 9. Consider a fair division problem with agents N, m items in quantities Q = (Q1↪ ▷ ▷ ▷ ↪Qm), and demand Di ✓ ¶1↪ ▷ ▷ ▷ ↪m♦ for agent i 2 N. Let T be the types of the agents, where same type agents have the same demand. Then a welfare maximizing CAEI, where all items need not be sold, can be computed in polynomial time if ♣T ♣ is a constant.

6 Discussion

We studied the computation and complexity of the competitive allocation from equal incomes, a method for fair division, for single minded agents for multiple divisible and discrete goods, and cake-cutting. Although a solution can be computed efficiently, social welfare maximizing solutions are hard to compute in general. However, we solved the latter efficiently for several interesting special scenarios. However, cases with constantly many goods, or altogether characterizing easy instances remain unresolved. will be interesting to settle these. We note that our results also work valuation classes where the agents have a desired target set (e.g. the set of parts of a bike), and very small positive value (✏) for any other bundle of goods. For such scenarios, the solution computed is an ✏-CAEI.

In the full version of the paper, we also explain how the CAEI solution can rule out (via the prices) the least desirable envy-free allocations, while remaining envy-free on exactly the same instances where an envy-free solution is guaranteed to exist. On the other hand, the standard CEEI solution is not the right notion for cake cutting or discrete goods; for instance, with discrete goods, even when there exist goods in abundant quantities for everyone, it can be the case that the number of units is "wrong" and cannot result in the exact clearing prescribed by CEEI.

An immediate generalization is that of Leontief valuations, where even existence of succinct characterization of instances that admit CEEI or CAEI in case of discrete goods is not clear, while the bigger question of understanding fair division with complementarities remains a mystery at large.