Fair Allocation of Indivisible Goods and Chores

1 Introduction

Consider a group of students who are assigned to a certain set of coursework tasks. Students may have subjective views regarding how enjoyable each task is. For some people, solving a mathematical problem may be fulfilling and rewarding. For others, it may be nothing but torture. A student who gets more cumbersome chores may be compensated by giving her some valued goods so that she does not feel hard done by.

This example can be viewed as an instance of a classic fair division problem. The agents have di�erent preferences over the items and we want to allocate the items to agents as fair as possible. The twist we consider is that whether an agent has positive or negative utility for an item is subjective. Our setting is general enough to encapsulate two well-studied settings: (1) "good allocation" where agents have positive utilities for the items and (2) "chore allocation" in which agents have negative utilities for the items. Our setting also covers (3) "allocation of objective goods and chores" where the items can be partitioned into chores (that yield negative utility for all agents) and goods (that yield positive utility for all agents). Setting (3) covers several scenarios where an agent could be compensated by some goods for doing some chores.

In this paper, we suggest a very simple yet general model of allocation of indivisible items that properly includes chore and good allocation. For this model, we present some case studies that highlight that whereas some existence and computational results can be extended to our general model, in other cases the combination of good and chore allocation poses interesting challenges not faced in subsettings. Our central technical contributions are several new e�cient algorithms for finding fair allocations. In particular:

• � We first formalize fairness concepts for the general setting. Some fairness concepts directly extend from the setting of good allocation to our setting. Other fairness concepts such as "envy-freeness up to one item" (EF1) and "proportionality up to one item" (PROP1) need to be generalized appropriately.
• � We then show a careful generalization of the decentralized round robin algorithm that finds an EF1 allocation when utilities are additive.
• � We also present a di�erent polynomial-time algorithm that always returns an EF1 allocation even when the agents' utility functions are arbitrary (not necessarily additive).
• � Turning our attention to an e�cient and fair allocation, we show that for the case of two agents, there exists a polynomial-time algorithm that finds an EF1 and Pareto-optimal (PO) allocation for our setting. The algorithm can be viewed as an interesting generalization of the Adjusted Winner rule [Brams and Taylor, 1996a; 1996b] that is designed for divisible goods.
• � If we weaken EF1 to PROP1, then we show that there exists an allocation that is not only PROP1 but is also contiguous (assuming that items are placed in a line). We further give a polynomial-time algorithm that finds such allocation.

1.1 RelatedWork

Fair allocation of indivisible items is a central problem in several fields including computer science and economics [Aziz et al., 2015; Brams and Taylor, 1996a; Bouveret et al., 2016; Lipton et al., 2004]. There are several established notions of fairness, including envy-freeness and proportionality.

The idea of envy-freeness up to one good was implicit in the paper by Lipton et al. [2004]. Today, it has become a wellstudied fairness concept in its own right [Budish, 2011]. Caragiannis et al. [2016] further popularized it, showing that a natural modification of the Nash welfare maximizing rule satisfies EF1 and PO for the case of goods. Barman et al. [2018] recently presented a pseudo-polynomial-time algorithm for computing an allocation that is PO and EF1 for goods. EFX (envy-freeness up to an extreme item) was introduced by Caragiannis et al. [2016].

Aziz [2016] noted that the work on multi-agent chore allocation is less developed than that of goods and that results from one to the other may not necessarily carry over. Barman and Murthy [2017] presented a better approximation algorithm. Caragiannis et al. [2012] studied the e�ciency loss in order to achieve several fair allocations in the context of both good and chore divisions. Allocation of a mixture of goods and chores has received recent attention in the context for divisible items [Bogomolnaia et al., 2019; 2017]. Here, we focus on indivisible items.

Full version. The full version of the paper is available on arXiv [Aziz et al., 2018].

2 Our Model and Fairness Concepts

We now define a fair division problem of indivisible items where agents may have both positive and negative utilities. For a natural number s 2 N, we write [s] = f1; 2; : : : ; sg. An instance is a triple I = (N; O; U) where

• � N = [n] is a set of agents,
• � O = fo1; o2; : : : ; omg is a set of indivisible items, and
• � U is an n-tuple of utility functions ui : O!R.

We note that under this model, an item can be a good for one agent (i.e., ui(o) > 0) but a chore for another agent (i.e., uj(o) < 0). For X � O, we write ui(X) := P o2X ui(o); we assume that the utilities in this paper are additive unless specified otherwise. Each subset X � O is referred to as a bundle of items. An allocation � is a function � : N ! 2 O assigning each agent a di�erent bundle of items, i.e., for every pair of distinct agents i; j 2 N, �(i) \ �( j) = ;; it is said to be complete if S i2N �(i) = O.

We first observe that the definitions of standard fairness concepts can be naturally extended to this general model. The most classical fairness principle is envy-freeness, requiring that agents do not envy each other. Specifically, given an allocation �, we say that i envies j if ui(�(i)) < ui(�( j)). An allocation � is envy-free (EF) if no agent envies the other agents. Another appealing notion of fairness is proportionality which guarantees each agent an 1=n fraction of her utility for the whole items. Formally, an allocation � is proportional (PROP) if each agent i 2 N receives a bundle �(i) of value at least her proportional fair share ui(O)=n. The following implication, which is well-known for the case of goods, holds in our setting as well.

Proposition 1 An envy-free complete allocation satisfies proportionality.

A simple example of one good with two agents already suggests the impossibility in achieving envy-freeness and proportionality. The recent literature on indivisible allocation has, thereby, focused on approximation of these fairness concepts. A prominent relaxation of envy-freeness, introduced by Budish [2011], is envy-freeness up to one good (EF1), which requires that an agent's envy towards another bundle can be eliminated by removing some good from the envied bundle. We will present a generalized definition for EF1 that have only been considered in the context of good allocation: the envy can diminish by removing either one "good" from the other's bundle or one "chore" from their own bundle.

Definition 1 (EF1) An allocation � is envy-free up to one item (EF1) if for all i; j 2 N, either i does not envy j, or there is an item o 2 �(i)[�( j) such that ui(�(i)nfog) � ui(�( j)nfog).

Obviously, envy-freeness implies EF1. Conitzer et al. [2017] introduced a novel relaxation of proportionality, which they called PROP1. In the context of good allocation, this fairness relaxation is a weakening of both EF1 and proportionality, requiring that each agent gets her proportional fair share if she obtains one additional good from the others' bundles. Now we will extend this definition to our setting: under our definition, each agent receives her proportional fair share by obtaining an additional good or removing some chore from her bundle.

Definition 2 (PROP1) An allocation � satisfies proportionality up to one item (PROP1) if for each agent i 2 N,

• � ui(�(i)) � ui(O)=n; or
• � ui(�(i)) + ui(o) � ui(O)=n for some o 2 O n �(i); or
• � ui(�(i)) � ui(o) � ui(O)=n for some o 2 �(i).

It can be easily verified that EF1 implies PROP1. See the online appendix for an illustration of relations between fairness concepts introduced above.

Proposition 2 An EF1 complete allocation satisfies PROP1.

Besides fairness, we will also consider an e�ciency criterion. The most commonly used e�ciency concept is Paretooptimality. Given an allocation �, another allocation � 0 is a Pareto-improvement of � if ui(� 0 (i)) � ui(�(i)) for all i 2 N and u j(� 0 ( j)) > uj(�( j)) for some j 2 N. We say that an allocation � is Pareto-optimal (PO) if there is no allocation that is a Pareto-improvement of �.

3 Finding an EF1 Allocation

In this section, we focus on EF1, a very permissive fairness concept that admits a polynomial-time algorithm in the case of good allocation. We will present two algorithms which appropriately generalize the known algorithms for finding an EF1 allocation of goods, the round robin rule and the envygraph algorithm [Lipton et al., 2004], to our setting.

3.1 Double Round Robin Algorithm

Consider a round robin rule in which agents take turns, and choose their most preferred unallocated item. The round robin rule finds an EF1 allocation if all the items are goods (see e.g., Caragiannis et al. [2016]). By a very similar argument, it can be shown that the algorithm also finds an EF1 allocation if all the items are chores. However, we will show that the round robin rule already fails to find an EF1 allocation if we have some items that are goods and others that are chores.

Proposition 3 The round robin rule does not satisfy EF1.

Proof: Suppose there are two agents and four items with identical utilities described in Table 1. Consider the order, in

which Alice chooses the only good and then the remaining chores of equal value are allocated accordingly. In that case, Alice gets one a high value good and one chore, whereas Bob gets two chores. So even if one item is removed from the bundles of Alice or Bob, Bob will still remain envious. �

Nevertheless, a careful adaptation of the round robin method to our setting, which we call the double round robin algorithm, constructs an EF1 allocation. In essence, the algorithm will apply the round robin method twice: clockwise and anticlockwise. In the first phase, the round-robin algorithm allocates to agents chores, i.e., the items for which each agent has non-positive utility, while in the second phase, the reversed round-robin algorithm allocates to agents the remaining goods, in the opposite order starting with the agent who is worst o� in the first phase. Intuitively, each agent i may envy agent j who comes earlier than her at the end of one phase, but i does not envy j with respect to the items allocated in the other round; hence the envy of i towards j can be bounded up to one item. We formalize the idea in Algorithm 1; see Figure 1 for an illustration.

In the following, for an allocation � and a bundle X, we say that i envies j with respect to X if ui(�(i) \ X) < ui(�( j) \ X).

Algorithm 1 Double Round Robin Algorithm

Input: An instance I = (N;O;U) Output: An allocation �

• 1 Partition O into O + = fo 2 O j 9i 2 N s.t. ui(o) > 0g, O � = fo 2 O j 8i 2 N; ui(o) � 0g. Suppose jO � j = an � k for some integer a and k 2 f0; ; : : : ; n � 1g.
• 2 Create k dummy chores for which each agent has utility 0, and add them to O � . (Hence jO � j = an.)
• 3 Let the agents come in a round robin sequence (1; 2; : : : ; n) � and pick their most preferred item in O � until all items in O � are allocated.
• 4 Let the agents come in a round robin sequence (n; n � 1; : : : ; 1) � and pick their most preferred item in O + until all items in O + are allocated. If an agent has no available item which gives her strictly positive utility, she does not get a real item but pretends to pick a dummy one for which she has utility 0.
• 5 Remove the dummy items from the current allocation � and return the resulting allocation � � .

Theorem 1 The double round robin algorithm (Algorithm 1) returns an EF1 complete allocation in O(maxfm 2 ;mng) time.

Proof: We note that the algorithm ensures that all agents receive the same number of chores, by introducing k virtual chores. Now let � be the output of Algorithm 1. To see that � satisfies EF1, consider any pair of two agents i and j where i < j. We will show that by removing one item, these agents do not envy each other.

First, consider i's envy for j. We first observe that for the k-th item in O � allocated to i is weakly preferred by i than the k-th item in O � allocated to j. Hence, agent i does not envy j with respect to O � . As for the goods allocation, agent i may envy agent j with respect to O + , which implies that j picks at least one more item from O + . But if the first item o � picked by j from O + is removed from j's bundle, then the envy will diminish, i.e., i does not envy j with respect to O + n fo � g. The reason is that for each item in O + n fo � g picked by j there is a corresponding item picked by i before j's turn that is at least as preferred by i. Thus ui(�(i)) � ui(�( j) n fo � g).

Second, consider j's envy for i. Similarly, agent j does not envy agent i with respect to O + because he takes the first pick among i and j; that is, for every item in o 2 O + \�(i) such that uj(o) > 0, agent j picks a corresponding item before i that she weakly prefers. As for the items in O � , let o � be the last item fromO � chosen by j. Then, for each item o 2 O � nfo � g picked by i, there is a corresponding item picked by j before i that j weakly prefers to o, which implies j does not envy i with respect to O � n fo � g. Thus uj(�( j) n fo � g) � uj(�(i)).

In either case, agents do not envy each other up to one item. We conclude that � is EF1 and so does the final allocation � � as removing dummy items does not a�ect the utilities of each agent. It remains to analyze the running time of Algorithm 1. Line 1 requires O(mn) time as each item needs to be examined by all agents. Lines 3 and 4 require O(m 2 ) time as there are at most m iterations, and for each iteration, each agent considers at most m candidates. Thus, the total running time can be bounded by O(maxfm 2 ;mng), which completes the proof. �

3.2 Generalized Envy Graph Algorithm

Algorithm 1 is designed for additive utilities. We construct another algorithm (Algorithm 2) that finds an EF1 allocation for arbitrary utility functions ui : 2 O ! R (not necessarily additive). The algorithm is based on a generalization of an algorithm presented by Lipton et al. [2004] for finding an EF1 allocation for goods. For an allocation �, the envy-graph G(�) is a directed graph where the vertices is given by the set of agents N, and there is an arc from i to j if and only if i envies j. For each directed cycle C = fi1; i2; : : : ; ikg of the envy graph G(�) where i j envies i j+1 for each j 2 [k] and ik+1 = i1, we may implement an exchange over the cycle, and define the resulting allocation �C as follows:

A source of a directed graph is a vertex with no incoming arcs, whereas a sink is a vertex with no outgoing arcs. Given an allocation �, the marginal utility of an item o 2 O n �(i) to an agent i 2 N is defined as �i(�; o) := ui(�(i)[fog)�ui(�(i)):

Theorem 2 Suppose that we are given an oracle access to the utility functions ui : 2 O ! R of all agents i 2 N. Then the generalized envy-graph algorithm (Algorithm 2) finds an EF1 complete allocation in O(mn 3 ).

Proof: We will prove by induction that each time a new item is allocated and a while loop of Algorithm 2 is executed, the envy-graph G(�) is acyclic and the allocation � is EF1. The base case clearly holds since the initial allocation corresponds to the null allocation. Suppose that k�1 items have been allocated and we want to allocate the k-th item o. If N + , ;, then let G + be the envy graph induced by N + . Since by the induction hypothesis, the envy-graph is acyclic, which means that G + is acyclic as well. Hence, at least one agent i � has no incoming arc towards i � in G + and the algorithm can give i � item o. Since no agent envied agent i � before, even if some agent now envies agent i � , the allocation � satisfies EF1. If N + = ;, then we know that all the agents have negative marginal utility for item o. Since by the induction hypothesis, the envy graph G(�) is acyclic, and thus at least one agent i � has no out-degree, which follows that we can give i � item o. Since i � envied no one before, even if i � envies other agents now, the allocation � satisfies EF1.

We now focus on the while loop in the algorithm whereby envy cycles are removed by exchanging allocations along the cycle. After exchanging bundles over cycle C, we observe that the agents in the cycle improve their utility and the envy towards each agent in C is still bounded up to one good as the set of bundles does not change. Hence, the resulting allocation �C still satisfies EF1. Further, by removing one cycle, we note that each agent in the cycle has her out-degree decreased by one. Furthermore no agent outside the cycle has her outdegree changed. Hence, after a linear number of cycles removed, the graph has no more envy-cycle and hence is acyclic. Similarly to [Lipton et al., 2004], the running time of the algorithm can be bounded by O(mn 3 ). �

Theorem 2 also applies when we consider oracles that compare agents' ordinal preferences over bundles of items.

Algorithm 2 Generalized Envy Graph Algorithm

Input: An instance I = (N;O;U)

Output: An allocation �

• 1 Initialize allocation �(i) = ; for all i 2 N
• 2 for o 2 O do
• 3 Let N + be the set of agents i who have a nonnegative marginal utility �i(�; o) � 0.
• 4 if N + , ; then
• 5 Choose a source i � 2 N + in the graph G(�) induced by N + .
• 6 else

7

Choose a sink i � 2 N in G(�).

• 8 Update �(i � ) �(i � ) [ fog.
• 9 while G(�) contains a directed cycle C do
• 10 Update � �C.

4 Finding an EF1 and POAllocation

We move on the the next question as to whether fairness is achievable together with e�ciency. In the context of goods allocation where agents have non-negative additive utilities, Caragiannis et al. [2016] proved that an outcome that maximizes the Nash welfare (i.e., the product of utilities) satisfies EF1 and Pareto-optimality simultaneously. The question regarding whether a Pareto-optimal and EF1 allocation exists for chores is unresolved. If one starts from an EF1 allocation and finds Pareto improvements, one runs into two challenges. First, Pareto improvements may not necessarily preserve EF1. Second, finding Pareto improvements is NP-hard [Aziz et al., 2016; de Keijzer et al., 2009]. Even if we ignore the second challenge, the question regarding the existence of a Paretooptimal and EF1 allocation for chores is open.

Next we show that the problem of finding an EF1 and Pareto-optimal allocation is completely resolved for the restricted but important case of two agents. Our algorithm can be viewed as a discrete version of the well-known Adjusted Winner (AW) rule [Brams and Taylor, 1996a; 1996b]. Just like AW, our algorithm is Pareto-optimal and EF1. In contrast to AW that is designed for goods, our algorithm can handle both goods and chores.

Theorem 3 For two agents, a Pareto-optimal and EF1 complete allocation always exists and can be computed in polynomial time.

Proof: The algorithm begins by giving each subjective item to the agent who considers it as a good; that is, for each item o 2 O allocate o to agent i if ui(o) � 0 and uj(o) < 0 where j 2 N n fig. So, in the following, let us assume that there is no item for which each agent has utility 0. Also we assume that we have objective items only, i.e., for each item o 2 O, either o is a good (ui(o) > 0 for each i 2 N); or o is a chore (ui(o) < 0 for each i 2 N). Now we call one of the two agents winner (denoted by w) and another loser (denoted by ').

• (i) Initially, all goods are allocated to the winner and all chores to the loser.
• (ii) We sort the items in terms of ju'(o)j=juw(o)j (monotone non-increasing order), and consider reallocation of the

items according to the ordering (from the left-most to the right-most item).

• (iii) When considering a good, we move it from the winner to the loser. When considering a chore, we move it from the loser to the winner. We stop when we find an EF1 allocation from the point of view of the loser. Note that the loser is envious up to one item of the winner.

We will first prove that at any point of the algorithm, the allocation � is Pareto-optimal, and so is the final allocation � � . Assume towards a contradiction that the allocation � is Pareto-dominated by the allocation � 0 . For each i; j 2 fw; 'g with i , j, we write

• � Gii is the set of goods in �(i) \ � 0 (i);
• � Cii is the set of chores in �(i) \ � 0 (i);
• � Gi j is the set of goods in �(i) \ � 0 ( j);
• � Ci j is the set of chores in �(i) \ � 0 ( j).

Without loss of generality, we assume that, in �, the winner has utility which is at least as high as in � 0 , while the loser is strictly better o�. Taking into account that the bundles of goods Gww and G'' and the bundles of chores Cww and C'' are allocated to the same agent in both allocations, this means

The crucial observation now is that the algorithm considered all items inG'w and Cw' before the items inGw' and C'w in the ordering (this is why the allocation of the items in the first two bundles changes while the allocation of the items in the last two bundles does not). Let � be such that

This definition implies the inequalities,

which, together with inequality (2), yields

a contradiction. The last inequality follows by (1) and by the fact that � is non-negative.

Now observe that at the final allocation � � , at most one agent envies the other: if the loser still envies the winner and the winner also envies the loser, then exchanging the bundles would result in a Pareto improvement, a contradiction. Thus, � � is EF1 when the loser envies the winner at � � . Consider when at � � the loser does not envy the winner but the winner envies the loser. Let � 0 be the previous allocation just before the final transfer, and X = � 0 (w)\� � (w) and Y = � 0 (')\� � ('). By construction, the loser envies the winner more than one item at � 0 , which implies u'(Y) < u'(X). Suppose towards a contradiction that the winner envies the loser more than one item at � � , which implies uw(X) < uw(Y). If g is the last good that has been moved from the winner to the loser, then allocating X to ' and Y [ fgg to w would be a Pareto-improvement of � 0 , a contradiction. Similarly, if c is the last chore that has been moved from the loser to the winner, then allocating X [ fcg to ' and Y to w would be a Pareto-improvement of � 0 , a contradiction. Hence, the winner envies the loser up to one item; we conclude that � � is EF1. �

The following example illustrates the generalized AW.

Example 4 Consider two agents, Alice and Bob, and five items with the additive utilities specified in Table ?? where the grey circles correspond to goods and the white circles correspond to chores. The generalized AW initially allocates

the goods to Alice and the chores to Bob. Then, it transfers the first good from Alice to Bob and moves the second chore from Bob to Alice. After moving the third good from Alice to Bob, Bob stops being envious up to one item. Hence the final allocation gives the items 2 and 4 to Alice and the rest to Bob.

A natural question is whether PO and EF1 allocation exists for three agents with general additive utilities; we leave this as an interesting open question. We note that Pareto-optimality by itself is easy to achieve, by taking a permutation of agents and applying a variant of 'serial dictatorship'.

Proposition 4 A Pareto-optimal allocation can be computed in linear time.

5 Finding a Contiguous PROP1 Allocation

We saw that an EF1 allocation always exists for subjective goods/chores. If we weaken EF1 to PROP1, one can achieve another requirement besides fairness, that is, connectivity. Specifically, we will consider a situation when the items are placed on a path, and each agent gets a connected bundle of the path. Finding a connected set of items is relevant in many scenarios, in particular when the items have a spatial or temporal structure. For example, the items can be a set of rooms in a corridor and agents will often value being allocated a contiguous chunk of rooms (see e.g., [Bouveret et al., 2017]).

We will show that a connected PROP1 allocation exists and can be found e�ciently. Bil´o et al. [2018] recently consider related questions regarding EF1 allocations of goods. Without loss of generality, we assume that the path is given by a sequence of items (o1; o2; : : : ; om). We first prove a result for the case of cake cutting that is of independent interest. In the following, a mixed cake is the interval [0;m]. Each agent i 2 N has a value density function ˆui, which maps a subinterval of the cake to a real value, where i has uniform utility ui(oj) for the interval [ j � 1; j] for each j 2 [m]. An allocation of a mixed cake assigns each agent a disjoint sub-interval of the cake where the union of the intervals equals the entire cake [0;m]; it satisfies proportionality if each agent i gets an interval of value at least the proportional fair share ui(O)=n.

Theorem 5 A contiguous proportional allocation of a mixed cake exists and can be computed in polynomial time.

Proof sketch: Let N + be the set of agents with strictly positive total value for O. We combine the moving-knife algorithms for goods and chores. First, if there is an agent who has positive proportional fair share, i.e., N + , ;, we apply the moving-knife algorithm only to the agents in N + . Our algorithm moves a knife from left to right, and agents shout whenever the left part of the cake has a value of exactly the proportional fair share. The first agent j who shouts is allocated to the left bundle [0; x j], and the algorithm recurs on the remaining instance. Second, if no agent has positive proportional fair share, our algorithm moves a knife from right to left, and agents shout whenever the left part of the cake has value exactly proportional fair share. Again, the first agent j who shouts is allocated to the left bundle [0; xj], and the algorithm recurs on the remaining instance.

We will prove by induction on jNj that the allocation of a mixed cake produced by the algorithm satisfies the following:

• � if N + , ;, then each agent in N + receives an interval of value at least proportional fair share and each agent not in N + receives an empty piece; and
• � if N + = ;, then each agent receives an interval of value at least proportional fair share.

The claim is clearly true when jNj = 1. Suppose that A returns a proportional allocation of a mixed cake with desired properties when jNj = k � 1; we will prove it for jNj = k.

Suppose that some agent has positive proportional fair share, i.e., N + , ;. If jN + j = 1, the claim is trivial; thus assume otherwise. Clearly, a shouter j receives an interval of value at least the proportional fair share. Further, all other agents in N + have value at most the proportional fair share for the left piece [0; xj]. Indeed, if some agent i 2 N + values the left piece greater than the proportional fair share, then i would have shouted when the knife reaches before xj by the continuity of ˆui, and ˆui([0; xj]) > ˆui([0; 0]), contradicting the minimality of xj. Thus, the remaining agents in N + have at least (n � 1) � ˆui([0;m])=n value for [xj;m]. By the induction hypothesis, each agent in N + gets an interval of value at least proportional fair share, and the rest gets an empty piece.

Suppose that no agent has positive proportional fair share. Again, if some agent i values [0; xj] greater than the proportional fair share, then i would have shouted when the knife reaches before xj by the continuity of ˆui and ˆui([0; xj]) > ˆui([0; m]), contradicting the maximality of x j. Thus all the remaining agents have have at least (n � 1) � ˆui([0;m])=n value for [x j; m], and hence by the induction hypothesis each agent gets an interval of value at least proportional fair share. �

The theorem stated above also applies to a general cakecutting model in which information about agent's utility function over an interval can be inferred by a series of queries. We note that a contiguous envy-free allocation of a mixed cake is known to exist only when the number of agents is four or a prime number [Segal-Halevi, 2018; Meunier and Zerbib,

2018]. A fractional proportional allocation can be then used to achieve a contiguous PROP1 division of indivisible items.

Theorem 6 A connected PROP1 allocation of a path always exists and can be computed in polynomial time.

We note that our PROP1 existence result extends to any traceable graph that admits a Hamiltonian path: we can run our algorithm on the Hamiltonian path and the resulting output can be easily seen to satisfy both contiguity and PROP1.

6 Discussion

In this paper, we formally studied fair allocation when the items are a combination of subjective goods and chores. Our work paves the way for detailed examination of allocation of goods/chores, and opens up an interesting line of research, with many problems left open to explore. In particular, there are further fairness concepts that could be studied from both existence and complexity issues, most notably envy-freeness up to the least valued item (EFX) [Caragiannis et al., 2016]. In our setting, one can define an allocation � to be EFX if for any pair of agents i; j, the following two hold:

• (i) 8o 2 �(i) s.t. ui(o) < 0: ui(�(i) n fog) � ui(�( j)); and
• (ii) 8o 2 �( j) s.t. ui(o) > 0: ui(�(i)) � ui(�( j) n fog).

That is, i's envy towards j can be eliminated by either removing i's least valuable good from j's bundle or removing i's favorite chore from i's bundle. Caragiannis et al. [2016] mentioned the following 'enigmatic' problem: does an EFX allocation exist for goods? It would be intriguing to investigate the same question for subjective or objective goods/chores.

Conitzer et al. [2017] proposed a fairness concept called Round Robin Share that can be achieved together with Paretooptimality. In our context, RRS can be formalized as follows. Given an instance I = (N;O;U), consider the round robin sequence in which all agents have the same utilities as agent i. In that case, the minimum utility achieved by any of the agents is RRSi(I). Formally for each agent i, we order the items in a non-increasing order of her utilities, i.e., ui(o (1) ) � ui(o (2) ) � � � � ui(o (m) ); the round robin share for i is given by RRSi(I) = minj2[n] Pp�1 k=0 ui(o ( j+k�n) ) where p = bm=nc. An allocation satisfies RRS if each agent i gets utility at least RRSi(I). It would be then very natural to ask what is the computational complexity of finding an allocation satisfying both properties.

Finally, recent works of Bouveret et al. [2017] and Bil´o et al. [2018] showed that a contiguous allocation satisfying several fairness notions, such as MMS and EF1, is guaranteed to exist for some restricted domains. It remains open whether similar results can be obtained in fair division of indivisible goods and chores.

Acknowledgements

We thank the reviewers at IJCAI-19 for helpful feedback. Ayumi Igarashi is supported by the KAKENHI Grant-in-Aid for JSPS Fellows number 18J00997. Haris Aziz is supported by a UNSW Scientia Fellowship. Toby Walsh is funded by the European Research Council under the Horizon 2020 Programme via AMPLify 670077.