Fair allocation of combinations of indivisible goods and chores
Haris Aziz Ioannis Caragiannis Ayumi Igarashi Toby Walsh





Fair allocation of combinations of indivisible goods and chores        





H. Aziz UNSW Sydney and Data61 CSIRO, Australia

haris.aziz@unsw.edu.au           

           I. Caragiannis Aarhus University, Denmark

iannis@cs.au.dk           

           A. Igarashi^* (corresponding author) National Institute of Informatics, Japan

ayumi_igarashi@nii.ac.jp           

           T. Walsh UNSW Sydney and Data61 CSIRO, Australia

tw@cse.unsw.edu.au           





Fair allocation of indivisible goods and chores



    Haris Aziz Ioannis Caragiannis Ayumi Igarashi^* Toby Walsh

    December 30, 2023
===============================================================




We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are “goods” i.e., they yield positive utility for the agents. There is also some work where the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have positive or negative utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the  complexity of computing such allocations.




§ 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 different preferences over the items and we want to allocate the items to agents as fairly 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” in which agents have positive utilities for the items and (2) “chore allocation” in which agents have negative utilities for the items. The setting we consider also covers a third setting (3) “allocation of objective goods and chores” in which 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 efficient algorithms for finding fair allocations. In particular:

    
  * We 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 show that the round robin sequential allocation algorithm that returns an EF1 allocation for the case of goods does not work in general. Nevertheless, we present a careful generalization of the decentralized round robin algorithm that finds an EF1 allocation when utilities are additive. 
    
  * Turning our attention to an efficient 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  <cit.> that is designed for divisible goods. 
    
  * Weakening EF1 to PROP1, we show that there exists an allocation that is not only PROP1 but also contiguous (assuming that items are placed in a line). We further give a polynomial-time algorithm that finds such an allocation. 




 §.§ Related Work

Fair allocation of indivisible items is a central problem in several fields including computer science and economics <cit.>. Fair allocation has been extensively studied for allocation of divisible goods, commonly known as cake cutting <cit.>. 

There are several established notions of fairness, including envy-freeness and proportionality. 
The recently introduced maximin share (MMS) notion is weaker than envy-freeness and proportionality and has been heavily studied in the computer science literature. <cit.> showed that an MMS allocation of goods may not always exist; on the positive side, there exists a polynomial-time algorithm that returns a 2/3-approximate MMS allocation <cit.>. Subsequent papers have presented simpler <cit.> or even better <cit.> approximation algorithms for MMS allocations. In general, checking whether there exists an envy-free and Pareto-optimal allocation for goods is Σ_2^p-complete <cit.>.

The idea of envy-freeness up to one good (EF1) was implicit in the paper by <cit.>. Today, it has become a well-studied fairness concept in its own right <cit.>. <cit.> further popularized it, showing that a natural modification of the Nash welfare maximizing rule satisfies EF1 and PO for the case of goods. <cit.> recently presented a pseudo-polynomial-time algorithm for computing an allocation that is PO and EF1 for goods. A stronger fairness concept, envy freeness up to the least valued good (EFX), was introduced by <cit.>.

<cit.> noted that the work on multi-agent chore allocation is less developed than that of goods and that results from one may not necessarily carry over to the other. <cit.> considered fair allocation of indivisible chores and showed that there exists a simple polynomial-time algorithm that returns a 2-approximate MMS allocation for chores. <cit.> presented a better approximation algorithm. <cit.> studied the efficiency 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 of divisible items <cit.>. Here, we focus on indivisible items. 




  
Subsequent Work.
Our study of a general setting for goods and chores and our formalization of general definitions for fairness concepts (that apply well to hybrid settings) has spurred further work on the topic. 
In his survey <cit.> discusses the subtle differences between the treatment of goods and chores. 
<cit.> and <cit.> focus on algorithms for computing competitive equilibrium for goods and chores. 
<cit.> consider variations of concepts and algorithms that we propose. <cit.> consider a stronger concept of group envy-freeness for goods and chores. <cit.> focus on our formulation of PROP1 (that is a weakening of proportionality) and propose a polynomial-time algorithm for computing allocations that are PROP1 and Pareto optimal.

<cit.> pointed out that the natural extension of envy-cycle elimination algorithm of <cit.> does not give an EF1 allocation for a mix of goods and chores. 
<cit.> provide further insights into the issue and show that restricting the envy-graph to edges involving maximum envy results in an EF1 allocation for doubly-monotonic valuations that are more general than additive utilities.



§ 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 ∈, we write [s]={1,2,…,s}. 
An instance is a triple I=(N,O,) where


  * N=[n] is a set of agents,

  * O={o_1,o_2,…,o_m} is a set of indivisible items, and

  *  is an n-tuple of utility functions u_i:2^O →. 

Each subset X ⊆ O is referred to as a bundle of items. We may abuse the notation and write u_i(o)= u_i({o}). We note that under this model, an item can be a good for one agent i (i.e., u_i(o)>0) but a chore for another agent j (i.e., u_j(o)<0). We assume that the utilities in this paper are additive, namely, u_i(X)=∑_o ∈ Xu_i(o) for each bundle X ⊆ O. We say that agent i weakly prefers (respectively, strictly prefers) item o to item o' if u_i(o) ≥ u_i(o') (respectively, u_i(o)> u_i(o')). 
An allocation π is a function π N→ 2^O such that ⋃_i ∈ Nπ(i)=O, and π(i) ∩π(j)=∅ for every pair of distinct agents i,j ∈ N.

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 u_i(π(i)) < u_i(π(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 set of items. Formally, an allocation π is proportional (PROP) if each agent i ∈ N receives a bundle π(i) of utility at least her proportional fair share u_i(O)/n. 
The following implication, which is well-known for the case of goods, holds in our setting as well.


For additive utilities, an envy-free allocation satisfies proportionality. 


Suppose that an allocation π is an envy-free allocation. Consider any agent i ∈ N. Then, by envy-freeness, u_i(π(i))≥ u_i(π(j)) for all j∈ N. Thus, by summing up all the inequalities, n· u_i(π(i))≥∑_j∈ Nu_i(π(j))=u_i(O). Hence, each i∈ N receives a bundle of utility at least u_i(O)/n, so π 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 approximations of these fairness concepts. A prominent relaxation of envy-freeness, introduced by <cit.>, 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 of EF1 for our setting:

the envy can disappear 


by removing either one “good" from the other's bundle or one “chore" from their own bundle. Given an allocation π, we say that i envies j by more than one item if i envies j, and u_i(π(i)∖{o})  < u_i(π(j)∖{o}) for any item o ∈π(i) ∪π(j). 
		

An allocation π is envy-free up to one item (EF1) if for all i,j ∈ N, i does not envy j by more than one item.


Obviously, envy-freeness implies EF1. <cit.> introduced a novel relaxation of proportionality, which is referred to as 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. 
			

An allocation π satisfies proportionality up to one item (PROP1) if for each agent i∈ N, 
 

  * u_i(π(i))≥ u_i(O)/n; or

  * u_i(π(i))+u_i(o)≥ u_i(O)/n for some o∈ O∖π(i); or 

  * u_i(π(i))-u_i(o)≥ u_i(O)/n for some o∈π(i). 


			
We can verify that EF1 implies PROP1.  

For additive utilities, an EF1 allocation satisfies PROP1.

		
The claim clearly holds when |N| ≤ 1 or O=∅; thus suppose |N| ≥ 2 and O ≠∅. Consider any allocation π that satisfies EF1, and any agent i ∈ N.

First, consider the case when π(i)=O. If u_i(O) ≥ 0, then it is clear that u_i(π(i))=u_i(O) ≥ u_i(O)/n. If u_i(O) < 0, consider any j ∈ N ∖{i}≠∅. Since π is EF1, there is an item o ∈π(i) such that u_i(π(i))- u_i(o) ≥ u_i(π(j))= u_i(∅)=0.  Thus, u_i(π(i)) -u_i(o) ≥ 0> u_i(O)/n for some o ∈π(i).
    
Next, consider the case when π(i)=∅. If u_i(O) ≤ 0, then it is clear that u_i(π(i))=u_i(∅)=0 ≥ u_i(O)/n. Thus, suppose u_i(O) > 0. Then, by EF1, for every j ∈ N ∖{i}, i does not envy j, or there is an item o ∈π(j) such that u_i(π(i))= u_i(∅) =0 ≥ u_i(π(j))- u_i(o). Let o^* ∈ O be such that o^* ∈_o ∈ Ou_i(o). Note that u_i(o^*)>0 since u_i(O) > 0. Then, u_i(π(i)) + u_i(o^*) ≥ u_i(π(j)) for every j  ∈ N, which implies that u_i(π(i)) + u_i(o^*) ≥ u_i(O)/n. 
    

Finally, consider the case when when O∖π(i) ≠∅ and π(i) ≠∅. Let x=max_o∈ O∖π(i)u_i(o) and y= min_o∈π(i)u_i(o). Since π satisfies EF1, for any agent j ∈ N ∖{i}, 
    
        
  * i does not envy j; or
        
  * there exists an item o ∈π(j) such that u_i(π(i)) ≥ u_i(π(j)) - u_i(o); or 
        
  * there exists an item o ∈π(i) such that u_i(π(i))- u_i(o) ≥ u_i(π(j)),
    
which implies 

    
  * u_i(π(i)) ≥ u_i(π(j)); or
    
  * u_i(π(i)) +x ≥ u_i(π(j)); or 
    
  * u_i(π(i))- y ≥ u_i(π(j)). 

Thus, if i gets bonus utility b^* :=max{x,-y,0} by getting some good or removing some chore, her updated utility is such that u_i(π(i)) + b^* ≥ u_i(π(j)) for any agent j ∈ N ∖{i}. This would imply that 

    n(u_i(π(i))+b^*)≥∑_j∈ N u_i(π(j))=u_i(O),

which implies that u_i(π(i))+b^* ≥ u_i(O)/n. Hence PROP1 is satisfied. 

Figure <ref> illustrates the relations between fairness concepts introduced above.



Besides fairness, we will also consider an efficiency criterion. The most commonly used efficiency concept is Pareto-optimality. Given an allocation π, another allocation π' is a Pareto-improvement of π if u_i(π'(i)) ≥ u_i(π(i)) for all i ∈ N and u_j(π'(j)) > u_j(π(j)) for some j ∈ N. We say that an allocation π is Pareto-optimal (PO) if there is no allocation that is a Pareto-improvement of π.		
	


§ 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. For instance, 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., ). 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. 


The round robin rule does not satisfy EF1.	


Suppose there are two agents and four items with identical utilities described below. 


	
	
		   
		4l
			[scale=0.57, transform shape, every node/.style=minimum size=7mm, inner sep=1.2pt, font=]	
			[draw, circle](2)  at (1.2,0) 1;
			[draw, circle](3)  at (2.4,0) 2;
			[draw, circle](4)  at (3.6,0) 3;
			[draw, circle](5)  at (4.8,0) 4;
			
			

		 

		Alice, Bob:      2     -3     -3     -3  

		


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 the positively valued 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 chores to agents (i.e., the items for which each agent has non-positive utility), while in the second phase, the reversed round-robin algorithm allocates the remaining goods to agents, in the opposite order starting with the agent who chooses last 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 present a formal description of the algorithm in Algorithm <ref>; see Figure <ref> for an illustration. 
			




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


For additive utilities, the double round robin algorithm returns an EF1 allocation in O(max{mlog m,mn}) time.


We note that the algorithm ensures that all agents receive the same number of chores, by introducing k dummy chores. Now let π be the output of Algorithm <ref>. 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. We denote by c^i_t and c^j_t the t-th items allocated to agent i and agent j for t=1,2,…,a in Line <ref>, respectively. We denote by g^i_t and g^j_t the t-th items allocated to agent i and agent j for t=1,2,…,b in Line <ref>, respectively, where b denotes the number of rounds each agent chooses an item (including a dummy item) in Line <ref>. 

First, consider i's envy for j. We first observe that the t-th item c^i_t in O^- allocated to i is weakly preferred by i to the t-th item c^j_t in O^- allocated to j. Hence, agent i does not envy j with respect to O^-. Namely, 

    u_i(π(i) ∩ O^-)= ∑^a_t=1u_i(c^i_t) ≥∑^a_t=1u_i(c^j_t) =u_i(π(j) ∩ O^-).

As for the good allocation, agent i may envy agent j with respect to O^+. But if the first item g^j_1 picked by j from O^+ is removed from j's bundle, then the envy will
disappear,


i.e., i does not envy j with respect to O^+∖{g^j_1}. Namely, 

    u_i(π(i) ∩ O^+)= ∑^b_t=1u_i(g^i_t) ≥∑^b_t=2u_i(g^j_t) = u_i((π(j) ∩ O^+)∖{g^j_1}).

The reason is that for each item g^j_t picked by j where t=2,3,…,b, there is a corresponding item g^i_t-1 picked by i before j's turn that is weakly as preferred by i to g^j_t. Combining (<ref>) and (<ref>) yields u_i(π(i)) ≥ u_i(π(j)∖{g^j_1}).

Second, consider j's envy for i. Similarly to the above, agent j does not envy agent i with respect to O^+ because agent j takes the first pick among i and j; that is, for every item in g^i_t chosen by i, agent j picks an item g^j_t before i that she weakly prefers to g^i_t. Thus, 

    u_j(π(j) ∩ O^+)= ∑^b_t=1u_j(g^j_t) ≥∑^b_t=1u_i(g^i_t) =u_j(π(i) ∩ O^+).

As for the items in O^-, for each item c^i_t picked by i where t=2,3,…,a, there is an item c^j_t-1 picked by j before i that j weakly prefers to c^i_t, which implies that j does not envy i with respect to O^-∖{c^j_a}. Thus 

    u_j(π(j)∖{c^j_a})= ∑^a-1_t=1u_j(c^j_t) ≥∑^a_t=2u_j(c^i_t) ≥∑^a_t=1u_j(c^i_t) = u_j(π(i)).

Note that the last inequality holds since u_j(c^i_1) ≤ 0. Combining (<ref>) and (<ref>) yields u_j(π(j)∖{c^j_a}) ≥ u_j(π(i)).

In either case, agents do not envy each other by more than one item. We conclude that π is EF1 and so does the final allocation π^* as removing dummy items does not affect the utilities of each agent. 

It remains to analyze the running time of Algorithm <ref>. Line <ref> requires O(mn) time as each item needs to be examined by all agents. Lines <ref> and <ref> require O(mlog m) time as there are at most m iterations, and for each iteration, each agent has to choose the most preferred item out of at most m items, which can be done by sorting all the items according to the preference of each agent at the beginning. Thus, the total running time can be bounded by O(max{mlog m,mn}), which completes the proof.
	
		


§ FINDING AN EF1 AND PO ALLOCATION

We move on to the next question as to whether fairness is achievable together with efficiency. In the context of good allocation where agents have non-negative additive utilities, <cit.> 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. Starting from an EF1 allocation and finding Pareto improvements, one runs into two challenges: first, Pareto improvements may not necessarily preserve EF1; second, finding Pareto improvements is NP-hard <cit.>. Even if we ignore the second challenge, the question regarding the existence of a Pareto-optimal 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. The main theorem in this section is stated as follows. 


For two agents with additive utilities, a Pareto-optimal and EF1 allocation always exists and can be computed in O(m^2) time.


Our algorithm for the problem can be viewed as a discrete version of the well-known Adjusted Winner (AW) rule <cit.>. Just like the Adjusted Winner rule, our algorithm finds a Pareto-optimal and EF1 allocation. In contrast to AW, which is designed for goods, our algorithm can handle both goods and chores. 

The algorithm begins by giving each subjective item to the agent who considers it as a good. 
So, in the following, we assume that we have objective items only, i.e., for each item o ∈ O, either o is a good (u_i(o)>0 for each i ∈ N); or o is a chore (u_i(o)<0 for each i ∈ N).
Now we call one of the two agents winner (denoted by w) and another loser (denoted by ℓ). 


  * Initially, all goods are allocated to the winner and all chores to the loser. 

  * We sort the items in terms of |u_ℓ(o)|/|u_w(o)| (monotone non-increasing order), and consider reallocation of the items according to the ordering (from the left-most to the right-most item). 

  * 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 the loser does not envy the winner by more than one item. 

We present a formal description of the algorithm in Algorithm <ref>.




We will first prove that at any point of the algorithm, the allocation π is Pareto-optimal, and so is the final allocation. 

During the execution of Algorithm <ref>, the allocation π is Pareto-optimal at any point after Line <ref>. 


It can be easily verified that the allocation π just after Line <ref> is Pareto-optimal. 
Thus, consider some time step after the algorithm enters the while-loop of Line <ref>. Assume towards a contradiction that π' is a Pareto-improvement of π. We assume without loss of generality that all items in O^*_w remain assigned to w under π' because transferring an item in O^*_w from w to ℓ improve neither the utility of w nor that of ℓ. Likewise, we assume that all items in O^*_ℓ remain assigned to ℓ under π'.

In the following, we call each item o ∈ O^+ a good and item o ∈ O^- a chore. 
For each i,j ∈{ w,ℓ} with i ≠ j, let


  * G_ii be the set of goods in π(i) ∩π'(i);

  * C_ii be the set of chores in π(i) ∩π'(i);

  * G_ij be the set of goods in π(i) ∩π'(j);

  * C_ij be the set of chores in π(i) ∩π'(j).



Consider first the case when in π, the winner has utility which is at least as high as in π', while the loser is strictly better off. Taking into account that the bundles of goods G_ww and G_ℓℓ and the bundles of chores C_ww and C_ℓℓ are allocated to the same agent in both allocations, this means

    u_w(G_ℓ w)+u_w(C_ℓ w)-u_w(G_w ℓ)-u_w(C_w ℓ)    ≥ 0; 
    
    u_ℓ(G_w ℓ)+u_ℓ(C_w ℓ)-u_ℓ(G_ℓ w)-u_ℓ(C_ℓ w)    >0


The crucial observation now is that the algorithm considered all items in G_ℓ w and C_w ℓ before the items in G_w ℓ and C_ℓ w in the ordering. 
Indeed, recall that all the goods are initially assigned to the winner, G_ℓ w⊆π(ℓ), and G_w ℓ⊆π(w). Thus the goods in G_ℓ w are those transferred from the winner w to the loser ℓ in the while-loop of Line <ref>, while the goods in G_w ℓ are those that stay in the winner's bundle. Similarly, recall that all the chores are initially assigned to the loser, C_w ℓ⊆π(w), and C_ℓ w⊆π(ℓ). Thus, the chores in C_w ℓ are those transferred from the loser ℓ to the winner w, while the chores in C_ℓ w are those that stay in the loser's bundle.
Now, let α be such that

    max_o∈ G_w ℓ∪ C_ℓ w|u_ℓ(o)|/|u_w(o)|≤α≤min_o∈ G_ℓ w∪ C_w ℓ|u_ℓ(o)|/|u_w(o)|.

This definition implies the inequalities, 

    u_ℓ(G_w ℓ)≤α u_w(G_w ℓ); 
    u_ℓ(G_ℓ w)≥α u_w(G_ℓ w); 
    
    -u_ℓ(C_w ℓ)≥ -α u_w(C_w ℓ);
    -u_ℓ(C_ℓ w)≤ -α u_w(C_ℓ w),

which, together with inequality (<ref>), yield

    0    < u_ℓ(G_w ℓ) + u_ℓ(C_w ℓ)- u_ℓ(G_ℓ w) - u_ℓ(C_ℓ w) 
       ≤-α(u_w(G_ℓ w)+u_w(C_ℓ w)-u_w(G_w ℓ) - u_w(C_w ℓ))≤ 0,

a contradiction. The last inequality follows by (<ref>) and by the fact that α is non-negative. A similar argument applies when in π, the loser has utility which is at least as high as in π', while the winner is strictly better off. 

We are now ready to prove Theorem <ref>. 


We will prove that the final output π of Algorithm <ref> satisfies EF1. Together with Lemma <ref>, this proves the desired claim. 
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, contradicting Lemma <ref>. 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 π' be the previous allocation just before the final transfer in the while-loop of Line <ref>. Let W=π'(w) ∩π(w) and L=π'(ℓ) ∩π(ℓ). Namely, W (respectively, L) is the set of items in the winner's bundle (respectively, the loser's bundle) excluding the transferred item at π' and π. By construction, the loser envies the winner by more than one item at π', which implies u_ℓ(L) < u_ℓ(W). Suppose towards a contradiction that the winner envies the loser by more than one item at π, which implies u_w(W) < u_w(L).


    
  * If g is the last good that has been moved from the winner to the loser, then allocating W to ℓ and L ∪{g} to w would be a Pareto-improvement of π', a contradiction. 
    
  * If c is the last chore that has been moved from the loser to the winner, then allocating W∪{c} to ℓ and L to w would be a Pareto-improvement of π', a contradiction.

Hence, the winner does not envy the loser by more than one item at π; we conclude that π is EF1.

It remains to analyze the running time of the algorithm. First, the items can be sorted in O(m log m) time. The adjustment process takes O(m^2) time. Each iteration checks the allocation is EF1 from the view point of the loser, which requires at most m comparisons of utilities, and there are at most m iterations. Thus, the number of operations is bounded by O(m^2).

The example below illustrates our discrete adaptation of AW.
[Example of the generalized AW]
Consider two agents, Alice and Bob, and five items with the following additive utilities where the gray circles correspond to goods and the white circles correspond to chores. 


	
	
		   
		7l
			[scale=0.57, transform shape, every node/.style=minimum size=7mm, inner sep=1.3pt, font=]	
			[draw, circle, fill=gray!70](1)  at (1.2,0) 1;
			[draw, circle](2)  at (2.4,0) 2;
			[draw, circle,fill=gray!70](3)  at (3.6,0) 3;
			[draw, circle, fill=gray!70](4)  at (4.8,0) 4;
			[draw, circle](5)  at (6,0) 5;
			[draw, circle](6)  at (7.3,0) 6;
			[draw, circle](7)  at (8.6,0) 7;
			
			

		 

		Alice (winner) :     1     -1     2     1    -2   -4    -6 

		Bob (loser) :      4     -3     6     2     -2     -2      -2

		|u_ℓ(o)|/|u_w(o)|  :      4     3     3     2     1     1/2      1/3

		


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 by more than 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 allocations exist for three or more agents; we leave this an an interesting open question. We remark that Pareto-optimality by itself is easy to achieve in O(nm) time. It suffices to give each item to the agent who values it the most.



§ FINDING A CONNECTED PROP1 ALLOCATION

We saw that there always exists an EF1 allocation for subjective goods and chores. If we weaken EF1 to PROP1, one can achieve one additional requirement besides fairness, that is, connectivity. In this section, we will consider a situation when items are placed on a path, and each agent desires a connected bundle of the path. Finding a connected set of items is important in many scenarios. For example, the items can be a set of rooms in a corridor and the agents could be research groups where each research group wants to get adjacent rooms (see e.g., ). 

We will show that a connected PROP1 allocation exists and can be found efficiently. In what follows, we assume that the path is given by a sequence of items (o_1,o_2,…,o_m). Formally, we say that an allocation π is connected if for each agent i ∈ N, π(i) is connected in the path (o_1,o_2,…,o_m). We will consider a slightly more stringent notion of PROP1: A connected allocation π is PROP1_outer if for each agent i ∈ N, 
 

  * agent i receives a bundle of utility at least her proportional fair share, i.e., u_i(π(i))≥ u_i(O)/n, or

  * u_i(π(i))+u_i(o)≥ u_i(O)/n for some item o∈ O∖π(i) such that π(i) ∪{o} is connected; or 

  * u_i(π(i))-u_i(o)≥ u_i(O)/n for some o∈π(i) such that π(i) ∖{o} is connected. 



We first prove a result for a case of the cake cutting setting that is of independent interest. In the following, a mixed cake is the interval [0,m]. Each agent i ∈ N has a value density function û_i, which maps a subinterval of the cake to a real value, where i has uniform utility u_i(o_j) for the interval [j-1,j] for each j ∈ [m]. The proportional fair share of agent i for a mixed cake [0,m] is given by û_i([0,m])/n.
A contiguous 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 utility at least her proportional fair share.


For additive utilities, a contiguous proportional allocation of a mixed cake exists and can be computed in polynomial time.


Let N^+ be the set of agents with strictly positive total utility for O. 

We combine the moving-knife algorithms for goods and chores as follows. 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 utility of exactly equal to the proportional fair share. The first agent who shouts is allocated the left bundle, and the algorithm recurs on the remaining instance. Second, if no agent has a positive proportional fair share, our algorithm moves a knife from right to left, and agents shout whenever the left part of the cake has utility exactly proportional fair share. Again, the first agent who shouts is allocated the left bundle, and the algorithm recurs on the remaining instance. 



Algorithm <ref> formalizes the idea. To prove its correctness, we will prove by induction on the number of agents |N'| that the allocation of a mixed cake [ℓ,r] produced by  satisfies the following:


  * if N^+ ≠∅, then each agent in N^+ receives an interval of utility at least her proportional fair share û_i([ℓ,r])/|N'| and each agent not in N^+ receives an empty piece; and

  * if N^+ = ∅, then each agent receives an interval of utility at least her proportional fair share û_i([ℓ,r])/|N'|. 

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

Suppose that some agent has positive proportional fair share, i.e., N^+ ≠∅. Note that each agent i not in N^+ has non-positive proportional fair share and gets nothing; thus it suffices to show that the agents in N^+ receive bundles of utility at least her proportional fair share. If |N^+|=1, the claim is trivial; thus assume otherwise. Clearly, agent j receives an interval of utility at least her proportional fair share. Further, all other agents in N^+ have utility at most their proportional fair shares for the left piece [ℓ,x_j]. Indeed, if there is an agent i' ∈ N^+ whose utility for the left piece [ℓ,x_j] is greater than her proportional fair share û_i'([ℓ,r])/k, then i' would have shouted when the knife reaches before x_j by the continuity of û_i', i.e., x_i'<x_j, contradicting the minimality of x_j. Thus, the remaining agents in N^+ have at least (k-1) ·û_i([ℓ,r])/k utility for the rest of the cake [x_j,r]; hence, by the induction hypothesis each agent in N^+ gets an interval of utility at least her proportional fair share, and each of the remaining agents gets an empty piece.

Suppose that no agent has positive proportional fair share. Again, if there is an agent i' whose utility for the left piece [ℓ,x_j] is greater than her proportional fair share û_i'([ℓ,r])/k, then i' would have shouted when the knife reaches before x_j by the continuity of û_i', i.e., x_i'>x_j, contradicting the maximality of x_j. Thus, all the remaining agents have utility at least (k-1) ·û_i([ℓ,r])/k for the rest of the cake [x_j,r], and hence, by the induction hypothesis, each agent gets an interval of utility at least her proportional fair share û_i([ℓ,r])/k. 
It can be easily verified that Algorithm <ref> runs in polynomial time. 


The theorem stated above also applies to a general cake-cutting model in which information about agent's utility function over an interval can be inferred by a series of queries. We note that in contrast with proportionality, the existence of a contiguous envy-free allocation of a mixed cake remains elusive: it is known to exist only when the number n of agents is four or a prime number <cit.>. Next, we show how a fractional proportional allocation can be used to achieve a contiguous PROP1 division of indivisible items. 	


			 

For additive utilities, a connected PROP1_outer allocation of a path always exists and can be computed in polynomial time. 


Given a path (o_1,o_2,…,o_m), consider a mixed cake [0,m] and each agent with a value density function û_i, where i has uniform utility u_i(o_j) for the interval [j-1,j] for each j ∈ [m]. We know that this instance admits a contiguous and proportional allocation π̂ from Theorem <ref>. 
Suppose without loss of generality that under such an allocation π̂, agents 1, 2,…, n receive the 1st, 2nd, …, and n-th bundles from left to right. That is, each agent i=1,2,…,n receives the sub-interval [x_i-1,x_i] of the mixed cake, where 0=x_0 ≤ x_1  ≤…≤ x_n-1≤ x_n=m. Without loss of generality, we also assume that no agent gets the empty bundle under this fractional allocation, i.e., x_i-1< x_i for each i=1,2,…, n.

From left to right, we show how to allocate each item o_j for j=1,2,…,m to construct an integral allocation π. If item o_j is fully contained in some agent's bundle, namely, x_i-1≤  j-1   ≤ j ≤ x_i for some i ∈ N, then we assign each item o_j to agent i. If not, i.e., the item o_j is on the boundary, we allocate it according to the left-most/right-most agents' preferences. Formally, suppose that j-1 ≤ x_ℓ≤ x_ℓ+1≤…≤ x_r ≤ j such that x_ℓ=min{  x_i | x_i ≥ j-1  } and x_r=max{  x_i | x_i ≤ j  }. Then we do the following: 


  * If two agents ℓ and r disagree on the sign of o_j, i.e., min{u_ℓ(o_j), u_r(o_j)} <0 < max{u_ℓ(o_j), u_r(o_j)}, we give the item o_j to the agent i ∈{ℓ,r} who has positive utility for it.

  * If two agents ℓ and r agree on the sign of o_j, i.e., min{u_ℓ(o_j), u_r(o_j)}≥ 0 or max{u_ℓ(o_j), u_r(o_j)} < 0, we allocate the item o_j in such a way that: 


  * the left-agent ℓ takes o_j if both agents have non-negative utility, i.e., min{u_ℓ(o_j), u_r(o_j)}≥ 0;

  * the right-agent r takes o_j if both agents have negative utility, i.e., max{u_ℓ(o_j), u_r(o_j)} < 0.


Note that if there is an agent who gets a fraction of one item only under the proportional fractional division, the agent gets nothing under our final allocation. 

The resulting integral allocation π is PROP1_outer. To see this, take any agent i. Clearly, when one of the knife positions x_i-1 and x_i is integral, the bundle satisfies PROP_outer. Further, if [x_i-1,x_j] ⊆ [j-1,j] for some j ∈ [m], agent i gets utility 1/n by receiving either the item o_j or the empty bundle.
Thus, assume otherwise, i.e., x_i-1,x_i ∉{0,1,…,m} and |x_i-x_i-1|>1. We will show that such an agent gets utility 1/n by either receiving the item next to its bundle or deleting the left-most item of her bundle. Let o_r and o_ℓ be the left and right boundary items where x_i-1∈ (r-1,r) and x_i∈ (ℓ-1,ℓ). Note that we have {o_ℓ+1,o_ℓ+2,…,o_r-1}⊆π(i). 
Consider the following four cases. 

    
  * Both o_ℓ and o_r are goods for i, i.e., min{u_i(o_ℓ),u_i(o_r)}≥ 0. In this case, agent i receives at least o_r. Thus, if o_ℓ∈π(i), agent i obtains utility 1/n. If not, agent i gets utility 1/n by receiving the item o_ℓ. 
    
  * Both o_ℓ and o_r are chores for i, i.e., max{u_i(o_ℓ),u_i(o_r)} < 0. In this case, agent i does not receive o_r. Thus, if o_ℓ∉π(i), agent i obtains utility 1/n. If not, agent i gets utility 1/n by removing the item o_ℓ. 
    
  * The item o_ℓ is a good but o_r is a chore for i, i.e., u_i(o_ℓ) ≥ 0 and u_i(o_r) <0. In this case, agent i does not receive o_r. Thus, if o_ℓ∈π(i), agent i obtains utility 1/n. If not, agent i gets utility 1/n by receiving the item o_ℓ.
    
  * The item o_ℓ is a chore but o_r is a good for i, i.e., u_i(o_ℓ) < 0 and u_i(o_r) ≥ 0. In this case, agent i receives at least o_r. Thus, if o_ℓ∉π(i), agent i obtains utility 1/n. If not, agent i gets utility 1/n by removing the item o_ℓ.

We conclude that π is a connected PROP1_outer allocation. By Theorem <ref>, it is immediate to see that one can compute a connected PROP1_outer allocation in polynomial time.
						 


§ DISCUSSION

In this paper, we have 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.
Perhaps the most intriguing open question as a result of our study is the existence of an EF1 allocation under arbitrary non-monotonic utilities.

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) <cit.>. In our setting, one can define an allocation π to be EFX if for any pair of agents i and j, agent i does not envy agent j, or the following two conditions hold: 








  * ∀ o∈π(i) s.t. u_i(π(i)∖{o})>u_i(π(i)): u_i(π(i)∖{o})≥ u_i(π(j)); and

  * ∀ o∈π(j) s.t. 
u_i(π(j)∖{o})<u_i(π(j))
: u_i(π(i))≥ u_i(π(j)∖{o}).
 

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. 
<cit.> mentioned the following `enigmatic' problem:
does an EFX allocation exist for goods? It would be interesting to investigate the same question for subjective or objective goods/chores under additive utilities.

We also note that while the relationship between Pareto-optimality and most fairness notions is still unclear, <cit.> proposed a fairness concept called round robin share (RRS) that can be achieved together with Pareto-optimality. 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 RRS_i(I). 
An allocation satisfies RRS if each agent i gets utility at least RRS_i(I). It would be then very natural to ask what is the computational complexity of finding an allocation satisfying both properties. 

Finally, recent papers of <cit.> and Bilò et al. (2019) 
showed that a connected allocation satisfying several fairness notions, such as MMS and EF1, is guaranteed to exist for some restricted domains. These existence results crucially rely on the fact that the agents have monotonic valuations, and it remains open whether similar results can be obtained in fair division of indivisible goods and chores.  



§ ACKNOWLEDGEMENTS

We would like to thank <cit.>
and <cit.>
for pointing out an error of the IJCAI version <cit.>. We thank the IJCAI 2019 reviewers and Warut Suksompong for helpful feedback. Ayumi Igarashi is supported by the KAKENHI Grant-in-Aid for JSPS Fellows number 18J00997. Toby Walsh is funded by the European Research Council under the Horizon 2020 Programme via AMPLify 670077.






















plainnat
32


urlstyle

[Aleksandrov and Walsh(2020)]AlWa20a
M. Aleksandrov and T. Walsh.
Two algorithms for additive and fair division of mixed manna.
In KI 2020: Advances in Artificial Intelligence - 43rd German
  Conference on AI, Bamberg, Germany, September 21-25, 2020, Proceedings,
  pages 3–17, 2020.

[Amanatidis et al.(2017)Amanatidis, Markakis, Nikzad, and
  Saberi]AMNS17
G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi.
Approximation algorithms for computing maximin share allocations.
ACM Transactions on Algorithms, 130 (4):0
  52:1–52:28, 2017.

[Aziz(2016)]Aziz16a
H. Aziz.
Computational social choice: Some current and new directions.
In Proceedings of the 25th International Joint Conference on
  Artificial Intelligence (IJCAI), pages 4054–4057, 2016.

[Aziz and Rey(2020)]AzRe20a
H. Aziz and S. Rey.
Almost group envy-free allocation of indivisible goods and chores.
In Proceedings of the 29th International Joint Conference on
  Artificial Intelligence (IJCAI), pages 39–45, 2020.

[Aziz et al.(2016)Aziz, Biro, Lang, Lesca, and Monnot.]ABL+16a
H. Aziz, P. Biro, J. Lang, J. Lesca, and J. Monnot.
Optimal reallocation under additive and ordinal preferences.
In Proceedings of the 15th International Conference on
  Autonomous Agents and Multiagent Systems (AAMAS), pages 402–410, 2016.

[Aziz et al.(2017)Aziz, Rauchecker, Schryen, and Walsh]ARSW17a
H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh.
Algorithms for max-min share fair allocation of indivisible chores.
In Proceedings of the 31st AAAI Conference on Artificial
  Intelligence (AAAI), pages 335–341, 2017.

[Aziz et al.(2019)Aziz, Caragiannis, Igarashi, and Walsh]ijcai2019-8
H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh.
Fair allocation of indivisible goods and chores.
In Proceedings of the 28th International Joint Conference on
  Artificial Intelligence (IJCAI), pages 53–59, 2019.

[Aziz et al.(2020)Aziz, Moulin, and Sandomirskiy]AMS20a
H. Aziz, H. Moulin, and F. Sandomirskiy.
A polynomial-time algorithm for computing a pareto optimal and almost
  proportional allocation.
Operations Research Letters, 480 (5):0
  573–578, 2020.

[Barman and Krishnamurthy(2020)]BK20
S. Barman and S. K. Krishnamurthy.
Approximation algorithms for maximin fair division.
ACM Transactions on Economics and Computation, 80
  (1):0 5:1–5:28, 2020.

[Barman et al.(2018)Barman, Murthy, and Vaish]BMV17a
S. Barman, S. Kumar Krishna Murthy, and R. Vaish.
Finding fair and efficient allocations.
In Proceedings of the 19th ACM Conference on Economics and
  Computation (EC), pages 557–574, 2018.

[Bérczi et al.(2020)Bérczi, Bérczi-Kovács,
  Boros, Gedefa, Kamiyama, Kavitha, Kobayashi, and Makino]brczi2020envyfree
K. Bérczi, E. R. Bérczi-Kovács, E. Boros, F. T. Gedefa,
  N. Kamiyama, T. Kavitha, Y. Kobayashi, and K. Makino.
Envy-free relaxations for goods, chores, and mixed items.
CoRR, abs/2006.04428, 2020.

[Bhaskar et al.(2020)Bhaskar, Sricharan, and Vaish]BSV20a
U. Bhaskar, A. R. Sricharan, and R. Vaish.
On approximate envy-freeness for indivisible chores and mixed
  resources.
CoRR, abs/2012.06788, 2020.

[Bilò et al.(2019)Bilò, Caragiannis, Flammini, Igarashi,
  Monaco, Peters, Vinci, and Zwicker]BCFIMPVZ19
V. Bilò, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters,
  C. Vinci, and W. S. Zwicker.
Almost envy-free allocations with connected bundles.
In Proceedings of the 10th Innovations in Theoretical Computer
  Science Conference (ITCS), pages 14:1–14:21, 2019.

[Bogomolnaia et al.(2017)Bogomolnaia, Moulin, Sandomirskyi, and
  Yanovskaya]BMSY17a
A. Bogomolnaia, H. Moulin, F. Sandomirskyi, and E. Yanovskaya.
Competitive division of a mixed manna.
Econometrica, 850 (6):0 1847–1871, 2017.

[Bogomolnaia et al.(2019)Bogomolnaia, Moulin, Sandomirskyi, and
  Yanovskaya]BMSY16a
A. Bogomolnaia, H. Moulin, F. Sandomirskyi, and E. Yanovskaya.
Dividing goods and bads under additive utilities.
Social Choice and Welfare, 52:0 395–417, 2019.

[Bouveret et al.(2016)Bouveret, Chevaleyre, and Maudet]BCM15a
S. Bouveret, Y. Chevaleyre, and N. Maudet.
Fair allocation of indivisible goods.
In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia,
  editors, Handbook of Computational Social Choice, chapter 12, pages
  284–310. Cambridge University Press, 2016.

[Bouveret et al.(2017)Bouveret, Cechlárová, Elkind,
  Igarashi, and Peters]BCE17a
S. Bouveret, K. Cechlárová, E. Elkind, A. Igarashi, and D. Peters.
Fair division of a graph.
In Proceedings of the 26th International Joint Conference on
  Artificial Intelligence (IJCAI), pages 135–141, 2017.

[Brams and Taylor(1996a)]BT96a
S. J. Brams and A. D. Taylor.
Fair division: From cake-cutting to dispute resolution.
Cambridge University Press, 1996a.

[Brams and Taylor(1996b)]BT96b
S. J. Brams and A. D. Taylor.
A procedure for divorce settlements.
Issue Mediation Quarterly Mediation Quarterly, 130
  (3):0 191–205, 1996b.

[Budish(2011)]Budi11a
E. Budish.
The combinatorial assignment problem: Approximate competitive
  equilibrium from equal incomes.
Journal of Political Economy, 1190 (6):0
  1061–1103, 2011.

[Caragiannis et al.(2012)Caragiannis, Kaklamanis, Kanellopoulos, and
  Kyropoulou]CKKK12
I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou.
The efficiency of fair division.
Theory of Computing Systems, 500 (4):0
  589–610, 2012.

[Caragiannis et al.(2019)Caragiannis, Kurokawa, Moulin, Procaccia,
  Shah, and Wang]CKMPS19
I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.
The unreasonable fairness of maximum Nash welfare.
ACM Transactions on Economics and Computation, 70
  (3):0 12:1–12:32, 2019.

[Chaudhury et al.(2021)Chaudhury, Garg, McGlaughlin, and
  Mehta]CGMM21a
B. R. Chaudhury, J. Garg, P. McGlaughlin, and R. Mehta.
Competitive allocation of a mixed manna.
Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA), 2021.

[Conitzer et al.(2017)Conitzer, Freeman, and Shah]CFS17a
V. Conitzer, R. Freeman, and N. Shah.
Fair public decision making.
In Proceedings of the 18th ACM Conference on Economics and
  Computation (EC), pages 629–646, 2017.

[de Keijzer et al.(2009)de Keijzer, Bouveret, Klos, and
  Zhang]KBKZ09a
B. de Keijzer, S. Bouveret, T. Klos, and Y. Zhang.
On the complexity of efficiency and envy-freeness in fair division of
  indivisible goods with additive preferences.
In Proceedings of the 1st International Conference on
  Algorithmic Decision Theory, pages 98–110, 2009.

[Garg and McGlaughlin(2020)]GaMc20a
J. Garg and P. McGlaughlin.
Computing competitive equilibria with mixed manna.
In Proceedings of the 19th International Conference on
  Autonomous Agents and Multiagent Systems (AAMAS), pages 420–428, 2020.

[Ghodsi et al.(2018)Ghodsi, HajiAghayi, Seddighin, Seddighin, and
  Yami]SGHSY18
M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, and H. Yami.
Fair allocation of indivisible goods: Improvements and
  generalizations.
In Proceedings of the 19th ACM Conference on Economics and
  Computation (EC), pages 539–556, 2018.

[Kurokawa et al.(2018)Kurokawa, Procaccia, and Wang]KPW18
D. Kurokawa, A. D. Procaccia, and J. Wang.
Fair enough: Guaranteeing approximate maximin shares.
Journal of the ACM, 650 (2):0 8:1–8:27,
  2018.

[Lipton et al.(2004)Lipton, Markakis, Mossel, and Saberi]LMMS04a
R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.
On approximately fair allocations of indivisible goods.
In Proceedings of the 5th ACM Conference on Electronic Commerce
  (EC), pages 125–131, 2004.

[Meunier and Zerbib(2018)]MeSh18a
F. Meunier and S. Zerbib.
Envy-free divisions of a partially burnt cake.
CoRR, abs/1804.00449, 2018.

[Moulin(2019)]Moul19a
H. Moulin.
Fair division in the internet age.
Annual Review of Economics, 11:0 1–37, 2019.

[Segal-Halevi(2018)]Halevi2018
E. Segal-Halevi.
Fairly dividing a cake after some parts were burnt in the oven.
In Proceedings of the 17th International Conference on
  Autonomous Agents and Multiagent Systems (AAMAS), pages 1276–1284, 2018.





