MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results

The theory of the fair allocation investigates how to allocate items to a set of agents under some fairness notion, where different agents may have different valuation functions on the items. The spirit of the fair allocation problem is to achieve a desired outcome for individuals and the whole community simultaneously, which motivates several important problems in mathematics and computer science. The goods allocation problem with positive valuation functions has received extensive studies [18, 10, 9, 20]. However, in some scenarios in real life, the items to be allocated may have disutility, i.e., the valuation functions are negative, such as troublesome jobs, household chores, or debt. For this case, the problem is called the chores allocation problem [3]. Seemingly, the problem of chores allocation is similar to the well-studied goods allocation problem as we can reduce the former to the latter by setting all valuation functions as their negative counterparts. However, many properties of the problem may change and not be applicable under this reduction. Thus, most results for goods allocation cannot be trivially extended to chores allocation [3, 4, 14, 2, 23].

There are several fairness notions for allocations, such as envy-free (EF) [18], proportionality (PROP) [22], maximin share (MMS) [10], and so on. In this paper, we consider the MMS fairness notion where the MMS value is the best possible guarantee that an agent can expect when he divides the items into several bundles but picks after all other agents. Moreover, we study MMS allocations of chores on graphs with connectivity constraints in which chores are embedded on a graph and each bundle assigned to an agent is required to be connected [5, 15, 8, 19, 7]. The connectivity requirements for chores capture the scenarios such as the allocation for energy conservation and emission reduction obligations between countries where the feature of geographical adjacency is natural, crop harvesting task allocation problem or clean work arrangement in the street where arranging a task with continuous geographical location is more convenient to set and use tools, and so on. Note that MMS allocation may not always exist. It is also meaningful to study the approximate $\alpha$-MMS allocation: whether each agent can always get $\alpha$ fraction of his MMS guarantee in the allocation.

Let $A=\{1,\dots,n\}$ be a set of $n$ agents and $C=\{c_{1},\dots,c_{m}\}$ be a set of $m$ chores. There is an undirected graph $G=(C,E)$ with vertices being chores in $C$. For each agent $i\in A$, there is a disutility function on chores $u_{i}:C\rightarrow\mathbb{R}_{\leq 0}$, where the functions $u_{i}$ are additive, i.e., $u_{i}(C^{\prime})=\sum_{c\in C^{\prime}}u_{i}(c)$ holds for any subset of chores $C^{\prime}\subseteq C$. The whole disutility function profile for all agents is denoted by $U=\{u_{1},\dots,u_{n}\}$.

Let $k$ be a positive integer. Let $P^{k}:[k]\to 2^{C}$ be a $k$-partition of $C$ such that $\cup_{i\in[k]}P^{k}(i)=C$ and $P^{k}(i)\cap P^{k}(j)=\varnothing$ for any different $i,j\in[k]$, where $[k]=\{1,\dots,k\}$ and the set $P^{k}(i)$ is called the $i$th bundle in the $k$-partition. A $k$-partition $P^{k}$ is valid if the induced subgraph $G[P^{k}(i)]$ is connected for each $i\in[k]$. Let $\mathcal{P}^{k}$ denote the set of all valid $k$-partitions. An allocation of $C$ is defined as a valid $n$-partition $\pi:A\rightarrow 2^{C}$.

We mainly consider the Maximin share (MMS) criterion for the allocation of chores. Given a graph $G$ and a positive integer $k$, for each $i\in A$, we define the MMS value of agent $i$ as follows when the chores in $G$ are allocated to $k$ agents

For simplification, we use $mms_{i}^{k}$ and $mms_{i}$ to denote $mms_{i}^{k}(G)$ and $mms_{i}^{n}$, respectively.

For any constant $\alpha\geq 1$. An $n$-partition $P$ of $G$ is called an $\alpha$-MMS_i split for agent $i$ if each bundle $b\in P$ induces a connected subgraph and $u_{i}(b)\geq\alpha\times mms_{i}$. When $\alpha=1$, we simply call it an MMS_i split. We say a valid allocation $\pi$ is an $\alpha$-MMS allocation if $u_{i}(\pi(i))\geq\alpha\times mms_{i}$ for each agent $i\in A$. When $\alpha=1$, we simply call it an MMS allocation.

We focus on the existence of MMS (or $\alpha$-MMS) allocations of chores on graphs and algorithms to find them if they exist. Our algorithms may need to use the MMS value for each agent. We show that when the graph is a tree or a cycle, the MMS value for each agent can be easily computed. The algorithms are modified from the algorithms for goods in [8] and the detailed proof can be found in Appendix A.

As mentioned in the introduction, MMS allocations of goods on trees always exist and can be computed in polynomial time [8]. The algorithm uses the idea of the last-diminisher method for proportionality cuttings of divisible cake [21].

We first review the allocation procedure for goods. First, let one agent take a sub rooted tree as $T$ (the original tree is rooted by taking an arbitrary vertex as the root); second, each other agent, in order, replaces $T$ with a sub rooted tree $T^{\prime}$ of it if he thinks $T$ is too much and does nothing if he thinks the current subtree $T$ is not enough or just right; third, the last agent who modifies $T$ gets the bundle $T$. Note that after deleting $T$ from the original tree $G$, the remaining part is still a connected tree. The same procedure is then applied to allocate the remaining tree to the remaining agents. This algorithm is not exactly the algorithm for allocating goods on trees in [8]. Both algorithms use the idea of the last-diminisher method and we just present a simplified version.

For chores, agents do not want to get more burdens. The corresponding last-diminisher method will be different: each agent may want to expand the current bundle if he thinks the current bundle of burdens is too light. At first glance, we can also assign the last expanded bundle to the last agent who expands it. However, the expanding operation will cause trouble on trees. After expanding the current bundle (a subtree) by including some vertices to it, the remaining graph after deleting the new bundle may not be connected (not be a connected tree anymore). This may change the property of the problem. Specifically, we give an example in Figure 1 to show that after expanding a rooted subtree the remaining part may not be connected. The current subtree $T$ is the subtree rooted as $v_{3}$, which contains three vertices $\{v_{3},v_{6},v_{7}\}$. An agent may include two vertices $v_{1}$ and $v_{2}$ to the subtree $T$. However, after adding them, $T$ is not a rooted subtree and the remaining graph after deleting $T$ is not connected. For this case, we can not guarantee the existence of allocations to the remaining $n-1$ agents even if the original allocations to the $n$ agents exist.

It turns out that chores allocation on trees become much harder. We show that chores allocation on some special trees always exists and can be found in polynomial time. Our algorithms will use a technique, called the group-satisfied method, which can be regarded as an extension of the last-diminisher method. In an allocation procedure of the group-satisfied method, we will assign $k^{\prime}$ bundles to $k^{\prime}$ agents together such that the remaining $n-k^{\prime}$ agents ‘agree with’ this allocation and the remaining objects still form a connected tree. Here ‘agree’ means that the agent thinks in the new instance his MMS value will not decrease. The group-satisfied method will iteratively apply this allocation procedure until all objects are assigned to agents. If in each allocation procedure only one bundle is assigned to one agent, then the group-satisfied method becomes the last-diminisher method. Before introducing the group-satisfied method in detail, we first define some concepts.

Recall that a partial allocation is valid if each bundle of chores in the allocation induces a connected graph.

Given a valid partial allocation $\pi^{\prime}:A^{\prime}\rightarrow 2^{C^{\prime}}$. To check whether $\pi^{\prime}$ is group-satisfied we need to check whether all agents are satisfied with it. For an agent in $A^{\prime}$, it is easy to check since we only need to compute the disutility of the bundle assigned to him. For an agent $i\in A\setminus A^{\prime}$, we use the following sufficient condition to guarantee their requirements,

A subclass of trees satisfying a certain property $\Pi$ is called Property-$\Pi$ graphs. For example, the class of paths is trees having the property: having no vertices of degree $\geq 3$. In this paper, we will consider several Property-$\Pi$ graphs, such as paths, trees with only one vertex of degree $\geq 3$, trees with depth 3, and so on. We have the following important lemma that will widely be used in our proofs.

Next, we show how to use Lemma 4.4 to find feasible allocations. We first consider the simple case of paths.

Now we consider trees with depth at most 3 and show how to use the group-satisfied method to solve the allocation problem on these trees. Let $r$ be the root of the tree $G$. If the depth of the tree is 2, then the tree is a star. For this case, we consider the MMS${}_{i_{0}}$ split $P_{i_{0}}$ of an arbitrary agent $i_{0}$ and let agent $i_{0}$ take the bundle containing the root. Note that all other $n-1$ bundles in $P_{i_{0}}$ contain only one chore in one leaf of the tree. We arbitrarily assign the $n-1$ chores to the other $n-1$ agents, since the value of every single chore will not less than the MMS value of each agent. This will be an MMS allocation. Next, we assume that the depth of $G$ is 3.

In the algorithm, we also first consider the MMS${}_{i_{0}}$ split $P_{i_{0}}$ of an arbitrary agent $i_{0}$ and denote the bundle containing the root by $p_{r}$. In the graph $G^{\prime}=G-p_{r}$ after deleting $p_{r}$, each connected component is either a star or a single vertex. Let $C=\{c_{1},c_{2},\dots,c_{p}\}$ be the set of stars in $G^{\prime}$. Each star in $C$ is a rooted subtree of $G$. We will show that we can always find a group-satisfied allocation.

Case 1: There is a star $c_{q}\in C$ that is $x$-perfect for some integer $x$. Assume that agent $i$ $x$-splits star $c_{q}$. We consider the $x$-partition of $c_{q}$ by agent $i$ and assign the bundle containing the center vertex of $c_{q}$ to agent $i$ and assign the left $x-1$ chores to arbitrary $x-1$ agents. All the $x$ agents are satisfied with this allocation. By Lemma 4.7, we know that this allocation of $c_{q}$ to the $x$ agents is group-satisfied.

Case 2: All stars in $C$ are $x$-super for different integers $x$. Assume that $c_{i}$ is $x_{i}$-super for $1\leq i\leq p$. In this case, we will use a matching technique to show that there is either a group-satisfied allocation to allocate some stars in $C$ or a group-satisfied allocation to allocate the whole graph $G$.

We construct an auxiliary bipartite graph $H=(V_{1},V_{2},E_{H})$. The vertex set $V_{1}$ contains $|C|+1$ vertices. Each star in $C$ is corresponding to a vertex in $V_{1}$ and the last vertex in $V_{1}$ is corresponding to the bundle $p_{r}$ in $P_{i_{0}}$, i.e., $V_{1}=C\cup\{p_{r}\}$. The vertex set $V_{2}$ is corresponding to the agent set $A$, i.e., $V_{2}=A$. A vertex in $c_{j}\in C$ is adjacent to a vertex $i\in V_{2}$ if and only if the corresponding agent $i$ is a dominator of the subtree $c_{j}$, i.e., $i\in D(c_{j})$. The vertex $p_{r}\in V_{1}$ is only adjacent to vertex $i_{0}\in V_{2}$. See Figure 3 for an illustration of the construction of the auxiliary graph $H$.

We use a standard matching algorithm to find a maximum matching $M_{H}$ between $V_{1}$ and $V_{2}$ in $H$.

Case 2.1: All vertices in $V_{1}$ are matched in $M_{H}$. For this case, we will show that we can find a group-satisfied allocation to allocate the whole graph $G$ according to the matching $M_{H}$. First of all, the vertex $p_{r}\in V_{1}$ can only be matched with $i_{0}\in V_{2}$ since $p_{r}$ is only adjacent to $i_{0}$ in $H$. So we assign the bundle $p_{r}$ to agent $i_{0}$. Next, we consider other edges in the matching $M_{H}$. Assume that $c_{j}\in C$ is matched with $i_{j}\in V_{2}$. Then agent $i_{j}$ is a dominator of the subtree $c_{j}$. We consider an $x_{j}$-partition of $c_{j}$ by agent $i_{j}$ and assign the bundle containing the center vertex to agent $i_{j}$. All other bundles left are bundles of a single chore. For each vertex in $c_{j}\in C$, we do the above allocation. Then we can allocate $|M_{H}|=|C|+1$ bundles to $|M_{H}|$ different agents since $M_{H}$ is a matching. After this, the remaining chores will form an independent set. We assign each remaining chore to a remaining agent. This is the algorithm.

Case 2.2: Some vertices in $V_{1}$ are not in the matching $M_{H}$. In this case, we will show that we can find a group-satisfied allocation to allocate a subset of stars at $C$. Our algorithm will use the following concept crown.

The following lemma gives a condition for the existence of the crown structure.

For Case 2.2, the size of the matching $M_{H}$ is less than the size of $V_{1}$, and then the condition of Lemma 5.3 holds. By Lemma 5.3, we can find a crown $(V^{\prime}_{1},V^{\prime}_{2})$ in polynomial time. Then we execute the group-satisfied allocation according to the crown $(V^{\prime}_{1},V^{\prime}_{2})$ by Lemma 5.4.

The main steps of our algorithm to compute MMS allocations of chores on trees with depth 3 are described as Algorithm 1.

A graph is a spider if it is a tree having only one vertex of degree $\geq 3$. We will also use the group-satisfied method to show the existence of MMS allocations of chores in spiders.

The vertex of degree $\geq 3$ in a spider is called the center. A degree-1 vertex in a spider is called a leaf. The path from a leaf to the center is called a branch of the spider and the number of edges in a branch is the length of the branch.

In this section, we assume that the input graph $G$ is a spider, and use $r$ to denote the center and use $B_{i}$ to denote the branch between the center and a leaf $f_{i}$. We also consider the tree as a rooted tree with the root being the center $r$.

Similar to the algorithm for trees with depth 3, the algorithm will also use Lemma 4.7 and Lemma 4.8 to construct group-satisfied partial allocations based on $x$-perfect and $x$-super subtrees.

The above lemma provides a way to find group-satisfied allocations for a special case. Our algorithm iteratively applies the operation in the proof of Lemma 6.1 until we get a spider such that each branch of it is contained in one bundle in the MMS_j split of an agent $j$. The following part of the algorithm is similar to the algorithm for trees with depth 3.

We consider the MMS${}_{j_{0}}$ split $P_{j_{0}}$ of an arbitrary agent $j_{0}$ and denote the bundle containing the root by $p_{r}$. In graph $G^{\prime}=G-p_{r}$, each connected component is a path. Let $C=\{c_{1},c_{2},\dots,c_{p}\}$ be the set of these paths. Each path in $C$ is 1-super because the whole branch is contained in a bundle in the MMS_j split of some agent $j$.

We also construct an auxiliary bipartite graph $H=(V_{1},V_{2},E_{H})$. Set $V_{1}$ contains $|C|+1$ vertices, which are corresponding to the $|C|$ paths in $C$ and the bundle $p_{r}$. Each vertex in $V_{2}$ is corresponding to an agent in $A$ and we simply denote $V_{2}$ by $A$. A vertex $j\in V_{2}$ is adjacent to a vertex $c\in C$ in $H$ if and only if the corresponding agent $j\in A$ is a dominator of $c$. Vertex $p_{r}\in V_{1}$ is only adjacent to $j_{0}\in A$. We compute a maximum matching $M_{H}$ between $V_{1}$ and $V_{2}$ in $H$.

Case 1: $|M_{H}|=|V_{1}|$. We allocate the whole graph to the $n$ agents according to the matching $M_{H}$. The bundle $c$ corresponding to a vertex in $V_{1}$ will be assigned to agent $i$ if they are matched in $M_{H}$. It is easy to see that all chores will be allocated to agents, and all agents are satisfied with the allocation. The allocation is group-satisfied.

Case 2: $|M_{H}|<|V_{1}|$. By Lemma 5.3, we can find a crown $(V^{\prime}_{1},V^{\prime}_{2})$ in polynomial time. We allocate the chores to agents according to the algorithm in the proof of the following lemma.

All the above results imply that

Next, we consider the case where the chores are on a simple cycle. Different from trees, MMS allocations of chores on cycles may not exist. We will give an example to show the nonexistence of MMS allocations even to only three agents. We will show how we find the example later.

In the example in Table 1, we are going to allocate nine chores on a cycle to three agents. The chores appear on the cycle are in the same order as that in the table. The numbers in the table are the disutilities of the chores for the agents. The MMS value of each agent is $-1$. For any four consecutive chores, the disutility for any agent is at most $-\frac{7}{6}$. If an $\alpha$-MMS allocation with $\alpha<\frac{7}{6}$ exists, then it would split the cycle into three bundles of three consecutive chores. There are only three ways to split it. It is easy to check that none of the three partitions yields an $\alpha$-MMS allocation with $\alpha<\frac{7}{6}$. Thus, no $\alpha$-MMS allocation with $\alpha<\frac{7}{6}$ exists for this instance.

On the other hand, ${\frac{3}{2}}$-MMS allocations of chores on cycles always exist. The simple observation of the ${\frac{1}{2}}$-MMS allocations of goods on cycles in [19] can get the corresponding result for chores.