\section{Introduction}

\subsection{Background and related research}



Since the introduction of maximin share (MMS) fairness by \citet{budish2011combinatorial}, MMS has been extensively used as a criterion to evaluate the fairness of an allocation when $m$ indivisible items are allocated to $n$ heterogeneous agents.
MMS fairness is traditionally defined for the allocation of goods as a relaxation of proportionality (PROP).
A PROP allocation requires that 
the utility of each agent is no smaller than the average utility when all items are assigned to her.
PROP is too demanding when the items are indivisible since such an allocation does not exist even when there is a single item and two agents: the agent who is not assigned the item has utility 0 which is arbitrarily smaller than her proportionality.
Motivated by this strong impossibility result, \citet{budish2011combinatorial} proposed to use MMS to replace proportionality.
Informally, the maximin share (MMS) of an agent is the maximum value she can guarantee if she is to partition the items into $n$ bundles but is the last one to pick a bundle.
An allocation is MMS fair if every agent's value is no smaller than her MMS.

For the allocation of goods, although MMS significantly weaken the fairness requirement, it is first shown by \citet{DBLP:journals/jacm/KurokawaPW18} that there are instances where no allocation is MMS fair to all agents.
Accordingly, designing (efficient) algorithms to compute approximately MMS fair allocations steps into the center of the filed of algorithmic fair division.
\citet{DBLP:journals/jacm/KurokawaPW18} first proved there exists a $2/3$-approximate MMS fair allocation for additive valuations, and then \citet{DBLP:journals/talg/AmanatidisMNS17} designed a polynomial time algorithm with the same approximation guarantee. 
Later, \citet{DBLP:journals/mor/GhodsiHSSY21} improved the approximation ratio to $3/4$, and \citet{DBLP:journals/ai/GargT21} further improved it to $3/4 + 1/(12n)$.
On the negative side, \citet{DBLP:conf/wine/FeigeST21} proved that no algorithm can ensure better than $39/40$ approximation. Beyond additive valuations, \citet{DBLP:journals/teco/BarmanK20} initiated the study of approximate MMS fair allocation with submodular valuations, and proved that a $0.21$-approximate MMS fair allocation can be computed by the round-robin algorithm.
\citet{DBLP:journals/ai/GhodsiHSSY22} improved the approximation ratio to $1/3$, and moreover, they gave constant and logarithmic approximation guarantees for XOS and subadditive valuations, respectively. 
The approximations for XOS and subadditive valuations are recently improved in \cite{seddighin2022improved}.

As we have seen, the majority of efforts are devoted to indivisible goods, and the parallel problem of tasks (called chores where agents have costs or dis-utilities to complete the received items)  has received less attention. 
\citet{DBLP:conf/aaai/AzizRSW17} first pointed out this issue, and proved that the round-robin algorithm ensures 2 approximation for additive valuations for indivisible chores.  
\citet{DBLP:journals/teco/BarmanK20} and \citet{DBLP:conf/sigecom/HuangL21} respectively improved the approximation ratio to $4/3$ and $11/9$.
Recently, \citet{DBLP:conf/wine/FeigeST21} proved that with additive valuations, no algorithm can beat the approximation of $44/43$.
However, very little is known beyond additive valuations.


Besides MMS fairness, proportionality up to one item (PROP1) and proportionality up to any item (PROPX) are also studied as relaxations of proportionality.
For goods, PROP1 allocations always exist but PROPX allocations may not exist \cite{conf/aaai/BarmanK19, journals/corr/abs-1907-01766, journals/orl/AzizMS20}.
For chores, both PROP1 and PROPX allocations exist and can be found efficiently \cite{moulin2018fair, journals/corr/abs-2103-11849}. 
As far as we know, all the above works assume the valuations are additive, and combinatorial valuations have not been considered yet.



\subsection{Main results}


In this work, we aim at understanding the extent to which MMS fairness, as well as PROPX/PROP1, can be satisfied when the valuations are not additive.
First, it is easy to see that allocating all items to a single agent achieves $n$-approximate proportionality and thus  achieves $n$-approximate MMS fairness.
Surprisingly, we show that $n$-approximation is the best possible even when the valuations are submodular. 
This result exhibits a significant difference between the allocations of chores and goods, since for goods with submodular (even XoS) valuations, we always have constant-approximate MMS fair allocations \citep{DBLP:journals/teco/BarmanK20,DBLP:journals/ai/GhodsiHSSY22}.


\medskip 

\noindent{\bf Result 1}
For any number $n$ of agents, there is an instance with submodular valuations where no allocation can be better than $n$-approximate MMS fair.

\medskip 

Due to this strong impossibility result, we turn to study two concrete settings where the agents have specific combinatorial valuations. 
The first setting deals with a bin packing problem, where the items have sizes and the sizes can be different to different agents.
The agents have bins that can be used to pack the items allocated to them with the goal of using as few bins as possible. 
We call this valuation {\em bin-packing}. 
For bin-packing valuations, we show that no algorithm can be better than 2-approximation, and design a polynomial time algorithm that returns a 2-approximate MMS fair allocation.  
Moreover, the approximation can be improved to $3/2$ when the maximin share gets large.

\medskip 

\noindent{\bf Result 2}
For bin-packing valuations, the best possible approximation of MMS fairness is 2, and an allocation matching this approximation ratio can be found in polynomial time.

\medskip 


The second setting deals with a job scheduling problem, where a set of jobs need to be processed by the agents.
The agents are heterogeneous and thus each job may be of different lengths to different agents.
Each agent controls a set of machines with possibly different speeds.
Upon receiving a set of jobs, an agent's value is determined by the corresponding minimum completion time when processing the jobs using her own machines (i.e., makespan).  
The corresponding valuation is called {\em job-scheduling}.
As will be clear, job-scheduling is a more general setting than additive valuations, which uncovers new research directions for group-wise fairness.

\medskip 

\noindent{\bf Result 3}
For job-scheduling valuations, 
a 2-approximate MMS allocation can be found efficiently.

\medskip 

Finally, we consider PROP1 and PROPX allocations, and show for both bin-packing and job-scheduling valuations, no algorithm can be better than $n$-approximation. 
Thus any allocation algorithm achieves this tight approximation. 




\section{Preliminaries}

For any integer $k\ge 1$, let $[k] = \{1,\ldots,k\}$.
In a fair allocation instance, we have $n$ agents denoted by $N=[n]$ and $m$ items denoted by $M=[m]$.
Each agent $i$ has a valuation function over the items, $v_i:2^M \to {\mathbb{R}}^+\cup \{0\}$.
The items are tasks, and particularly, upon receiving $S \subseteq M$, $v_i(S)$ represents the effort or cost agent $i$ needs to spend on completing the tasks in $S$.
The valuation functions are normalized and monotone, i.e., $v_i(\emptyset) = 0$ and $v_i(S_1) \le v_i(S_2)$ for any $S_1 \subseteq S_2 \subseteq M$.
Note that no bounded approximation can be achieved for general valuation functions, and we provide one such example in the appendix. 
Thus we restrict our attention to the following three classes.
\begin{itemize}
    \item Subadditive: Valuation function $v_i$ is subadditive if for any $S_1,S_2 \subseteq M$, we have
    \[
    v_i(S_1 \cup S_2) \le v_i(S_1) + v_i(S_2). 
    \]
    \item Submodular: Valuation function $v_i$ is submodular if for any $S_1 \subseteq  S_2 \subseteq M$ and $e\in M\setminus S_2$,
    \[
    v_i(S_2 \cup \{e\}) - v_i(S_2) \le v_i(S_1 \cup \{e\} ) - v_i(S_1). 
    \]
    \item Additive: Valuation function $v_i$ is additive if for any $S \subseteq M$, we have
    \[
    v_i(S) = \sum_{j \in S} v_i(\{j\}). 
    \]
\end{itemize}
It is widely known that any additive valuation function is also submodular, and any submodular valuation function is also subadditive.


An allocation $\mathbf{X}=(X_1,\dots,X_n)$ is an $n$-partition of the items where $X_i$ contains the items allocated to agent $i$ such that $X_i \cap X_j = \emptyset$ and $\bigcup_{i\in N} X_i = M$.
For any set $S$ and integer $k$, let $\Pi_k(S)$ be the set of all $k$-partitions of $S$.
Then the maximin share ($\mathsf{MMS}_i$) of agent $i$ is defined as
\[
\mathsf{MMS}_i = \min_{\mathbf{X} \in \Pi_n(M)} \max_{j \in N} v_i(X_j).
\]
Note that the computation of $\mathsf{MMS}_i$ is NP-hard even when the valuations are additive, which can be verified by a reduction from the Partition problem.
Given an $n$-partition of $M$, $\mathbf{X}=(X_1,\dots,X_n)$, if $v_i(X_i) \le \mathsf{MMS}_i$ for all $i$, then $\mathbf{X}$ is called an {\em MMS-defining partition} for agent $i$.
Note that the original definition of $\mathsf{MMS}_i$ for chores is defined with non-positive valuations, where the minimum valued bundle is maximized. 
In this work, to simplify the notions, we choose to use non-negative numbers (representing costs), and thus the definition is equivalently changed to be the maximum valued bundle is minimized.
To be consistent with the literature, we still call it maximin share.

\begin{definition}[$\alpha$-MMS]
An allocation $\mathbf{X} = (X_1,\ldots,X_n)$ is $\alpha$-approximate maximin share ($\alpha$-MMS) fair if $v_i(X_i) \le \alpha \cdot \mathsf{MMS}_i$ for any agent $i\in N$.
The allocation is MMS fair if $\alpha = 1$.
\end{definition}

Given the definition of MMS, we have the following simple property, whose proof is in the appendix. 

\begin{lemma}\label{lem:MMS:bounds}
For any agent $i$ with subadditive valuation $v_i(\cdot)$, we have the following bounds for $\mathsf{MMS}_i$,
\[
\mathsf{MMS}_i \ge \max\big\{ \max_{j \in M} v_i(\{j\}), \frac{1}{n} \cdot v_i(M) \big\}.
\]
\end{lemma}



\section{Submodular valuations}

By Lemma \ref{lem:MMS:bounds}, if the valuations are subadditive, allocating all items to a single agent ensures an approximation of~$n$.
We call this algorithm $\mathsf{All}\text{-}\mathsf{or}\text{-}\mathsf{Nothing}$, which is somewhat the most unfair algorithm.  
Surprisingly, such an unfair algorithm achieves the optimal approximation ratio of MMS even if the valuations are submodular. 

\begin{theorem}\label{thm:submodular:lower}
For any $n \ge 2$, there is an instance with submodular valuations for which no allocation is better than $n$-MMS.
\end{theorem}

\begin{proof}
For any fixed $n \ge 2$, we construct the following instance with $n$ agents and $m = n^n$ items via an $n$-dimensional coordinate system. 
Let each item correspond to a point in the system and
\[
M = \{(x_1, x_2, \ldots, x_n) \mid x_i \in [n] \text{ for all } i \in [n]\}.
\]
For each agent $i \in [n]$, we define $n$ covering planes $\{C_{il}\}_{l\in [n]}$ and for each $l \in [n]$,
\[
C_{il} = \{(x_1, x_2, \ldots, x_n) \mid x_i = l \text{ and } x_j \in [n] \text{ for all } j \in [n] \setminus \{i\}\}.
\]
Note that $\{C_{il}\}_{l\in [n]}$ forms an exact cover of the points in $M$, i.e., $\bigcup_{l} C_{il} = M$ and $C_{il} \cap C_{iz} = \emptyset$ for all $l \neq z$.
For any set of items $S \subseteq M$, $v_i(S)$ equals the minimum number of planes in $\{C_{il}\}_{l\in [n]}$ that can cover $S$.
Therefore, $v_i(S) \in [n]$ for all $S$.
We first show $v_i(\cdot)$ is submodular for every $i$. 
For any $S\subseteq T \subseteq M$ and any $e\in M\setminus T$, if $e$ is not in the same covering plane for any point in $T$, $e$ is not in the same covering plane for any point in $S$.
Thus, $v_i(T\cup\{e\}) - v_i(T) = 1$ implies $v_i(S\cup\{e\}) - v_i(S) = 1$, and accordingly,
\[
v_i(T\cup\{e\}) - v_i(T) \le v_i(S\cup\{e\}) - v_i(S).
\]


Since $\{C_{il}\}_{l\in [n]}$ is an exact cover of $M$, $\mathsf{MMS}_i = 1$ where the MMS defining partition is simply $\{C_{il}\}_{l\in [n]}$.
Then to prove the theorem, it suffices to show that for any allocation of $M$, there is at least one agent whose value is $n$.
For the sake of contradiction, we assume there is an allocation $\mathbf{X}=(X_1,\ldots,X_n)$ where every agent has value at most $n-1$, which means for every agent $i \in [n]$, there exists a plane $C_{il_i}$ with $l_i \in [n]$ such that $X_i \cap C_{il_i} = \emptyset$.
Consider the point $\mathbf{b}=(l_1,l_2,\ldots,l_n)$.
It is clear that $\mathbf{b} \in C_{il_i}$ and thus $\mathbf{b} \notin X_i$ for all $i$.
Hence $\mathbf{b}$ is not allocated to any agent, which is a contradiction with $\mathbf{X}$ being an allocation and thus there must be an agent whose value is $n$.
\end{proof}



\section{Bin packing model}

Although Theorem \ref{thm:submodular:lower} shows that there is no algorithm that can be better than $n$-MMS for all submodular valuations, it does not wipe out the possibility of beating $n$-approximation for specific subadditive valuations.
In this section and the next, we propose two models where agents have concrete combinatorial valuations and design constant-approximate MMS fair algorithms.

The first model encodes a bin packing problem, where the items have sizes and need to be packed into bins by the agents.
Specifically, each item $j \in M$ has size $s_{i,j} \ge 0$ to agent $i$, and note that $j$ may be of different sizes to different agents. For a set of items $S$, $s_i(S)=\sum_{j\in S}s_{i,j}$.
Each agent $i\in N$ has unlimited number of bins with the same capacity $c_i$, where it is assumed that $c_i \ge \max_{j\in M} s_{i,j}$.
Given a set of items $S \subseteq M$, the value of agent~$i$, $v_i(S)$, is determined by the minimum number of bins (with capacity $c_i$) that can pack all items in $S$, which involves solving a classic bin packing problem and thus the computation of $v_i(S)$ is NP-hard. 
Accordingly, $\mathsf{MMS}_i$ is essentially the minimum number $k_i$ such that the items can be partitioned into $n$ bundles and the items in each bundle can be packed into no more than $k_i$ bins.
We have the following simple lemma, whose proof is in the appendix.

\begin{lemma}\label{mmsAndCapacity}
$\mathsf{MMS}_i\cdot c_i \ge \frac{s_i(M)}{n}$ for any $i\in N$
\end{lemma}



We first show the lower bound for the bin-packing model, whose proof is in the appendix.

\begin{theorem}\label{thm:bin:lower}
For the bin-packing model, no algorithm performs better than 2-MMS. 
\end{theorem}


Next, we design an algorithm to compute an allocation that matches the approximation 2,
and thus is the best possible approximation algorithm. Note that although the computation of each $\mathsf{MMS}_i$ and $v_i(S)$ is NP-hard, our algorithm runs in polynomial time without explicitly computing these values.  

We first show that if we can solve the problem for the special case where all agents have the same order of items by ranking their sizes, we can also solve the general case. Similar lemmas have been widely used for designing algorithms to compute MMS fair allocations with additive valuations \cite{DBLP:journals/teco/BarmanK20,DBLP:conf/sigecom/HuangL21}. Although this lemma does not hold for arbitrary subadditive valuations, it holds for the bin-packing model. 


We call a bin-packing instance {\em identical ordering} (IDO) if $s_{i, 1} \ge s_{i, 2}\ge \cdots \ge s_{i, m}$ holds for any $i\in N$.
Note that although the agents have the same order of items by their sizes, the cardinal numbers can still be significantly different.
Given a general bin-packing instance $I = (N, M, \{v_i\}_{i\in N}, \{s_i\}_{i\in N})$, we can construct an IDO instance as follows. First, note that for every agent $i$, there exists a permutation $\sigma_i: M\rightarrow M$ such that for all $j$, $j'\in M$ with $j < j'$, $s_{i, \sigma_i(j)} \ge s_{i, \sigma_i(j')}$. Using these permutations, we can construct the IDO instance by setting $s'_{i, j} = s_{i, \sigma_i(j)}$ for every $i\in N$ and $j\in M$. In other words, for every agent $i$, the size of the $j$-th item in the IDO instance is equal to the $j$-th largest size of items in the original instance. Note that the construction of the IDO instance runs in $O(nm\log m)$ time. Then we have the following lemma whose proof is in the appendix. 



\begin{lemma}\label{lem:IDO}
If there exists an allocation $\mathcal{A}' = (A_1', ..., A_n')$ in the IDO instance $I'$, such that $v_i'(A_i') \le \alpha \cdot \mathsf{MMS}_i$ for all $i\in N$, then there exists an allocation $\mathcal{A} = (A_1, A_2, ..., A_n$) in the original instance $I$ such that $v_i(A_i) \le \alpha \cdot \mathsf{MMS}_i$ for all $i\in N$. Besides, $\mathcal{A}$ can be constructed in polynomial time. 
\end{lemma}








Next, we present the main algorithm (Algorithm \ref{modifiedBagFilling}) that computes $2$-MMS allocations for IDO bin-packing instances. The basic idea is similar to that of the bag filling algorithm, i.e, incrementally adding small items into a bag until the bag is large enough for all the agents, and allocating the bag to one of the agents who are the last to think the bag large enough. 
The major differences include the way we distinguish between small and large items, and the way we initialize and fill the bag. 
In the following, we prove the approximation of 2, and in the appendix, we show how to modify Algorithm \ref{modifiedBagFilling} so that the approximation ratio improves to $(3+\delta)/2$ when MMS values get large.

\begin{theorem}\label{thm:bin:upper}
Algorithm \ref{modifiedBagFilling} returns a $2$-MMS allocation for bin-packing instances in polynomial time.
\end{theorem}

Before the proof of Theorem \ref{thm:bin:upper}, we first introduce some notations and technical lemmas. 
In the bin-packing model, we say an item $j$ is large for an agent $i$ if the size of the item exceeds half the capacity of the agent's bin, i.e., $s_{i,j} > 1/2\cdot c_i$; 
Otherwise, we say item $j$ is small for agent $i$. 
Note that each bin can hold at most one large item, but may hold multiple small items. 
We denote $H$ as the items that are large for some agent, and $L_i$ as the items that are small for agent $i$. Formally, 
\[
H = \{j\in M\mid \exists i\in N: s_{i, j} > \frac{c_i}{2}\}, \quad L_i = \{j\in M\mid s_{i, j} \le \frac{c_i}{2}\}.
\]
Note that $H\cap L_i$ may not be empty since one item may be large for some agents but small for other agents. 
We also split all the items into $\lceil\frac{m}{n}\rceil$ sets, where the first set contains the $n$ largest items, the second set contains the next $n$ largest items, and so on. That is, 
\[
G_i = \{(i-1)n+1, ..., i\cdot n\}\ i\in [1, \lfloor\frac{m}{n}\rfloor], \quad G_{\lceil\frac{m}{n}\rceil} = \{\lfloor\frac{m}{n}\rfloor\cdot n+1, ..., m\}.
\]
Note that the sets $G$s are well-defined since the instances we consider here are identical ordering. 

The algorithm consists of many rounds of bag initialization (Steps \ref{alg1:binInit:start} to \ref{alg1:binInit:end}) and bag filling (Steps \ref{alg1:binFill:start} through \ref{alg1:binFill:end}). 
In the bag initialization procedure, for each $G_i$ that contains large items for some agent, the largest item in it (which must be large for some agent) is put into the bag. 
In this way, for every agent, this initialized bag contains enough but not too much of her large items.
Besides, for some agents, all the items in the bag are large, i.e., those who think the least item is large. 
In the bag filling procedure, whenever an agent who has small items thinks the bag not large enough, the agent will incrementally add her small items into the bag, until the bag is large enough for her or she uses up her small items.
Each round of the algorithm ends when no agent will add items into the bag, i.e., each agent either thinks the bag large enough or has no small items. 
If this happens immediately after the bag is initialized, the bag is given to one of the agents who think all the items in the bag are large. 
Otherwise, the bag is given to the agent who adds the last item into the bag. 



\begin{lemma}\label{bagInit}
The agent who is allocated the bag immediately after the bag is initialized can use no more than $\mathsf{MMS}$ bins to pack all the items in the bag. 
\end{lemma}

\begin{proof
First, recall that in this case, all the items in the bag are large for the agent $i$ who receives the bag. 
From the definition of maximin share, we know that agent $i$ can use $n\cdot \mathsf{MMS}_i$ bins to pack all the items in $M$. 
This implies that there are at most $n\cdot \mathsf{MMS}_i$ large items for agent $i$. 
Therefore, according to the structure of the sets $G$s, we can know that at most $\mathsf{MMS}_i$ large items of agent $i$ are put into the bag, which require no more than $\mathsf{MMS}_i$ bins to pack, thus completing the proof.
\end{proof}

\begin{algorithm}
\caption{2-MMS allocation for IDO bin-packing instance. }\label{modifiedBagFilling}
\textbf{Input: }{An IDO instance over $n$ agents and $m$ indivisible chores with size $s_{i, j}$ for each agent $i\in N$ and chore $j\in M$. The valuation $v_i$ for each agent $i$ is determined by the bin-packing problem, which is non-negative, monotone, and subadditive. }\\
\textbf{Output: }{An allocation $\mathcal{A} = (A_1, A_2, \cdots, A_n)$ such that $v_i(A_i) \le 2\cdot \mathsf{MMS}_i$ for every $i\in N$.} \\
Initialize $R = M$. \\
\While{$|N| > 1$}{
Initialize $Q = N$, $B = \emptyset$, $k = \max\{i\in [1, \lceil\frac{m}{n}\rceil] \mid G_i\cap R\cap H\neq \emptyset\}$. \label{alg1:binInit:start}\\
\For{$i=1$ to $k$}{
    Pick the largest item $g$ in $G_i\cap R$. \\
    $B\leftarrow B\cup \{g\}$, $R\leftarrow R\backslash \{g\}$.
} \label{alg1:binInit:end} 
$Q = \{i\in N \mid B = \emptyset\ or\ \forall j\in B: s_{i, j}\ge \frac{c_i}{2}\}$. \\
\While{$s_i(B)\le \frac{s_i(M)}{n}$ for some agent $i\in N$ and $L_i\cap R\neq \emptyset$ \label{alg1:binFill:start}}{
    Pick an item $g$ in $L_i\cap R$. \label{alg1:pickItem}\\
    $B\leftarrow B\cup \{g\}$, $R\leftarrow R\backslash \{g\}$. \\
    $Q = \{i\}$. \\
    } \label{alg1:binFill:end}
Pick an agent $i$ in $Q$. \\
$A_i \leftarrow B$, $N\leftarrow N\backslash \{i\}$. \\
}
Allocate the remaining items in $R$ to the last agent.
\end{algorithm}

\begin{lemma}\label{bagFill}
The agent who is allocated a bag during the bag filling procedure can use no more than $2\mathsf{MMS}$ bins to pack all the items in the bag.  
\end{lemma}

\begin{proof}
Before proving the lemma, we first show that if the total size of items for an agent $i$ is at most $\frac{s_i(M)}{n}$, the agent can use no more than $2\mathsf{MMS}_i$ bins to pack all the items.
This is because in the worst case where only half capacity of each bin is taken up, the $2\mathsf{MMS}_i$ bins can still hold items with total size of $\mathsf{MMS}_i\cdot c_i$, which is at least $\frac{s_i(M)}{n}$ according to Lemma \ref{mmsAndCapacity}. 
This also implies at least one bin of the $2\mathsf{MMS}_i$ bins is taken up no more than half of its capacity.

Now, we're ready to prove Lemma \ref{bagFill}. There are two cases when the agent $i$ is allocated the bag $B$. 
First, agent $i$ thinks the bag large enough. Denote $g$ as the last item agent $i$ adds into the bag, we have $s_i(B\backslash \{g\}) \le \frac{s_i(M)}{n}$ and $s_i(\{g\}) \le \frac{c_i}{2}$. 
As we've shown, the items in $B\backslash \{g\}$ as well as the item $g$ can be packed into $2\mathsf{MMS}_i$ bins. 
Second, agent $i$ thinks the bag not large enough (i.e., $s_i(B) \le \frac{s_i(M)}{n}$) while she has no small items. 
Clearly, she can also use $2\mathsf{MMS}_i$ bins to pack all the items, which completes the proof. 
\end{proof}


\medskip

Now, we are ready to prove  Theorem \ref{thm:bin:upper}.

\medskip

\begin{proof}[Proof of Theorem \ref{thm:bin:upper}]
Clearly, Algorithm \ref{modifiedBagFilling} runs in polynomial time. 
For all the agents except the last one, Lemma \ref{bagInit} and Lemma \ref{bagFill} have proved that they can use no more than $2\mathsf{MMS}$ bins to pack all the items allocated to them. 
To complete the proof, we now show that the last agent $i$ can use no more than $2\mathsf{MMS}_i$ bins to pack all the remaining items. 

Considering two cases, first, agent $i$ thinks all the bags allocated to other agents are large enough, i.e, $s_i(A_j) > \frac{s_i(M)}{n}$ for all $j\in N\backslash i$.
Denote the remaining items by $M'$, then we have 
\[
s_i(M') = s_i(M) - \sum_{j\in N\backslash i}s_i(A_j) < s_i(M) - (n - 1)\frac{s_i(M)}{n} = \frac{s_i(M)}{n}.
\]
As proved in Lemma \ref{bagFill}, agent $i$ can use no more than $2\mathsf{MMS}_i$ bins to pack all the items in $M'$. 
Second, at least one bag allocated to other agents is not large enough for agent $i$, i.e, $s_i(A_j) \le \frac{s_i(M)}{n}$ for some $j\in N\backslash i$. 
This implies that before $A_j$ is allocated, there is already no small item for agent $i$.
Hence, all the remaining items are large for agent $i$. 
As shown in the proof of Lemma \ref{bagInit}, there are at most $n\cdot \mathsf{MMS}_i$ large items for agent $i$. 
According to the structure of the sets $G$s, we know that at most $\mathsf{MMS}_i$ of these large items are left to the last round.
Therefore, in this case, agent $i$ can use no more than $\mathsf{MMS}_i$ bins to pack all the remaining items. 
\end{proof}

\section{Job scheduling model}

Our second model considers a job scheduling environment, where the items are jobs that need to be processed by the agents.
Similar to the bin packing model, each item $j \in M$ has size $s_{i,j} \ge 0$ to agent $i\in N$. For a set of items $S$, $s_i(S)=\sum_{j\in S}s_{i,j}$. And each agent $i\in N$ exclusively controls a set of $k_i$ machines $P_i=[k_i]$ with possibly different speed $\rho_{i,j}$ for $j\in P_i$.
Without loss of generality, we assume $\rho_{i, 1}\ge \rho_{i, 2}\ge \cdots \ge \rho_{i, k_i}$. 
Upon receiving a set of items $S \subseteq M$, agent $i$'s value $v_i(S)$ is determined by the minimum competition time of processing $S$ using her own machines $P_i$ (i.e., {\em makespan}).
Formally, 
\[
v_i(S) = \min_{(T_1,\ldots,T_{k_i}) \in \Pi_{k_i}(S)} \max_{l\in [k_i]}\frac{\sum_{j\in T_l} s_{i,j}}{\rho_{i,l}}.
\]

Note that the computation of $v_i(S)$ is NP-hard.
Intuitively, the value of $\mathsf{MMS}_i$ is obtained by partitioning the items into $n\cdot k_i$ bundles, and allocating them to $k_i$ different types of machines (with different speeds) where each type has $n$ identical machines so that the makespan is minimized.\footnote{
An alternative way to explain the scheduling model is to view each agent $i$ as a group of $k_i$ small agents and the value of $\mathsf{MMS}_i$ as the {\em collective maximin share} for these $k_i$ small agents in the group.
We believe this notion of collective maximin share is of independent interest as a groupwise fairness notion.
We remark that this notion is different with the groupwise (and pairwise) maximin share defined in \cite{DBLP:conf/aaai/BarmanBMN18} and \cite{DBLP:journals/teco/CaragiannisKMPS19}, where the max-min value is defined for each single agent.
In our definition, however, a set of agents share the same value for the items assigned to them. }
Note that when each agent controls a single machine, i.e., $k_i = 1$ for all $i$, the problem degenerates to the additive valuation case, and thus by \cite{DBLP:conf/wine/FeigeST21} no algorithm can be better than $44/43$-approximation.

\begin{algorithm}
\caption{2-MMS allocation for IDO job-scheduling instance}\label{RRal}
\textbf{Input: }{An IDO instance over $n$ agents and $m$ indivisible jobs with size $s_{i, j}$ for each agent $i\in N$ and job $j\in M$. The valuation $v_i$ for each agent $i$ is determined by the job scheduling problem, which is non-negative, monotone, and subadditive.}\\
\textbf{Output: }{An allocation $\mathcal{A} = (A_1, A_2, ..., A_n)$ such that $v_i(A_i)\le 2\cdot \mathsf{MMS}_i$ for every $i\in N$}.  \\
Initialize allocation $\mathcal{A} = (A_1,..., A_n)$ with $A_i = \emptyset$ for every $i\in N$. \\
\While{$M\neq \emptyset$}{
    \For{$i=1$ to $m$}{
        Pick $g\in \argmax_{g'\in M}s_{i, g'}$. \\
        $A_i\leftarrow A_i\cup \{g\}$, $M\leftarrow M\backslash \{g\}$.
    }
}
\end{algorithm}

Next we focus on the upper bound and prove a result similar with Lemma \ref{lem:IDO} in the bin packing model. 
That is, it suffices for us to design algorithms for the IDO instances where $s_{i, 1} \ge s_{i, 2}\ge \cdots \ge s_{i, m}$ holds for any agent $i$, and the algorithms can be easily converted to handle the general case by the reduction similar to Algorithm \ref{allocationForGeneralInstance} (presented in the appendix).
Since the proof is almost the same as that of Lemma \ref{lem:IDO}, we omit the details to avoid redundancy. 


Now, we can focus on computing approximate MMS allocations for IDO instances of the job scheduling model. We allocate jobs among agents in a round-robin fashion (Algorithm \ref{RRal}): the agents take turns picking the largest job among the remaining jobs until no job is left. The algorithm is quite direct but surprisingly returns us a 2-MMS allocation. The technical contribution here is to show the returned allocation is indeed a 2-MMS allocation. 
That is, for each agent $i$, the makespan of processing the jobs in $A_i$ using her machines doesn't exceed $2\cdot\mathsf{MMS}_i$. 

\begin{theorem}\label{thm:job:upper}
Algorithm \ref{RRal} computes a 2-MMS allocation for every IDO job-scheduling instance in polynomial time.
\end{theorem}

To prove Theorem \ref{thm:job:upper}, we present an algorithm (Algorithm \ref{Machine 2}) for every agent to assign the jobs that Algorithm \ref{RRal} allocates to her among her machines. 
Here, we consider the capacity of a machine instead of its speed. Specifically, for each machine with speed $\rho$, we set the capacity of the machine $c = \tau\cdot \rho$. 
The algorithm assigns as many large jobs as possible to the machines with larger capacities, while ensuring that the workload (i.e., total size of the jobs) on each machine is no more than twice its capacity. 
In this way, the completion time of each machine doesn't exceed $2\tau$. 
Besides, we have the following lemma. 

\begin{algorithm}
\caption{Job scheduling with threshold}
\label{Machine 2}
\textbf{Input: }{A set of jobs $A = \{1, 2, ..., t\}$ with sizes $s_1 \ge s_2 \ge \cdots \ge s_t$, and a set of machines $P = \{1, 2, ..., k\}$ with speeds $\rho_1 \ge \rho_2 \ge \cdots \ge \rho_k$, and a threshold $\tau$.} \\
\textbf{Output: }{An allocation $T = (T_1, T_2, ..., T_k)$}. \\
Initialize $T_i = \emptyset$, $c_i = \tau\cdot \rho_i$ for every $i\in P$, $g = 1$.\\
\For{$i = 1$ to $k$}{
    \While{$s(T_i) + s_g \le 2c_i$ and $A\neq \emptyset$}{
        $T_i\leftarrow T_i\cup \{g\}$, $A\leftarrow A\backslash \{g\}$. \\
        $g \leftarrow g + 1$. 
    }
}
\end{algorithm}

\begin{lemma} \label{jobSche}
For every agent $i$, denote $A_i$ as the jobs that Algorithm \ref{RRal} allocates to her. If $\tau \ge \mathsf{MMS}_i$, Algorithm \ref{Machine 2} assigns all the jobs in $A_i$ among her machines $P_i$. 
\end{lemma}

\begin{proof}[Proof of Lemma \ref{jobSche}]
We will prove the lemma for an agent $i$, an analogous proof can be established for any other agent. 
We assume, for sake of contradiction that $A_i$ is not empty at the end of Algorithm \ref{Machine 2}. We will show that this assumption contradicts the definition of agent $i$'s maximin share. 

For each machine $j$ in $P_i$, the capacity is set to $c_{i, j} = \tau\cdot \rho_{i, j}$, which satisfies $c_{i, j}\ge \mathsf{MMS}_i\cdot \rho_{i, j}$. Besides, $c_{i, 1}\ge c_{i, 2}\ge \cdots \ge c_{i, k_i}$. 
We denote $T = (T_1, T_2, ..., T_{k_i})$ as the allocation returned by Algorithm \ref{Machine 2} and $t_{k_i+1}^*$ as the largest job that is not allocated. 
We use $t_j^*$ to denote the largest job in $T_j$ for $j\in [1, k_i]$, then we can define $T' = (T'_1, T'_2, ..., T'_{k_i})$ where $T'_j = T_j\backslash t_j^*\cup t_{j+1}^*$ for $j\in [1, k_i]$. 
In agent $i$'s {\em MMS-defining partition}, every job $g\in M$ must be assigned to one machine $j$.
This implies that $s_{i, g} \le \mathsf{MMS}_i\cdot \rho_{i, j} \le c_{i, 1}$ for every $g\in M$. 
From Algorithm~\ref{Machine 2}, we know that $s_i(T_1\cup t_2^*) > 2c_{i, 1}$, thus we have $s_i(T'_1) = s_i(T_1\backslash t_1^* \cup t_2^*) > c_{i, 1}$. 

We assume as our induction hypothesis that $s_{i, t_j^*}\le c_{i, j}$ for every $j\in [1, l]$ where $l$ is less than $k_i$. 
Similar to the claim that $s_i(T'_1) > c_{i, 1}$, we have $s_i(T'_j) > c_{i, j}$ for any $j\in [1, l]$. 
Summing up these $l$ inequalities, we have $\sum_{j=1}^{l}s_i(T'_j)>\sum_{j=1}^{l}c_{i,j}$. 
Since Algorithm \ref{RRal} allocates jobs to agents in a round-robin fashion, 
we know that for any job $g$ in $\cup_{j=1}^l T_j'$, 
there are $n$ jobs right before $g$ in $M$ (i.e., jobs $g-n, g-n+1,..., g-1$) that are not smaller than $g$. 
Therefore, denote $S$ as the set of jobs in $M$ that are before job $t_{l+1}^*$, 
we have 
\[
s_i(S) \ge \sum_{g\in \cup_{j=1}^l T_j'}n\cdot s_{i, g} = n\cdot \sum_{j=1}^{l}s_i(T'_j) > n\cdot \sum_{j=1}^l c_{i, j} \ge n\cdot \sum_{j=1}^l \mathsf{MMS}_i\cdot \rho_{i, j}.
\]
By the pigeonhole principle, in agent $i$'s {\em MMS-defining partition}, at least one bundle contains a subset of $S$ with total size greater than $\sum_{j=1}^l \mathsf{MMS}_i\cdot \rho_{i, j}$. 
Therefore, at least one job $g$ in this subset is assigned to a machine $j$ with $j \ge l+1$. Otherwise, the completion time of one of the first $l$ machines must exceed $\mathsf{MMS}_i$, which contradicts the definition of agent $i$'s maximin share. Hence, we have $s_{i, g} \le \mathsf{MMS}_i\cdot \rho_{i, j} \le c_{i, l+1}$. Since any job in $S$ is not smaller than job $t_{l+1}^*$, we have $s_{i, t_{l+1}^*}\le s_{i, g} \le c_{i, l+1}$. 

Therefore, we have $s_{i, t_j^*}\le c_{i, j}$ for every $j\in [1, k_i]$. Similarly, we have $s_i(T'_j) > c_{i, j}$ for every $j\in [1, k_i]$ and $s_i(M) > n\cdot \sum_{j=1}^{k_i}\mathsf{MMS}_i\cdot \rho_{i, j}$. By the pigeonhole principle, in agent $i$'s {\em MMS-defining partition}, the size of at least one bundle exceeds $\sum_{j=1}^{k_i}\mathsf{MMS}_i\cdot \rho_{i, j}$. This contradicts with the definition of maximin share, since the completion time of processing the jobs in such a bundle must exceed $\mathsf{MMS}_i$. 
\end{proof}

\medskip

\begin{proof}[Proof of Theorem \ref{thm:job:upper}]
Clearly, Algorithm \ref{RRal} runs in polynomial time. 
For each agent $i$, we set the threshold $\tau = \mathsf{MMS}_i$. 
Lemma~\ref{jobSche} shows that all the jobs Algorithm \ref{RRal} allocates to agent $i$ can be assigned to her machines. 
Besides, we know from Algorithm \ref{Machine 2} that the completion time of each of agent $i$'s machines doesn't exceed $2\mathsf{MMS}_i$. 
Therefore, $v_i(A_i)\le 2\mathsf{MMS}_i$ holds for every agent $i\in N$, which completes the proof. 
\end{proof}

\paragraph{Remark}
Note that although the proof of Theorem~\ref{thm:job:upper} requires the value of each $\mathsf{MMS}_i$ which is NP-hard to compute, Algorithm \ref{RRal} runs in polynomial time, which means there exists a way for each agent $i$ to complete the jobs allocated to her in $2\cdot\mathsf{MMS}_i$ time.
Actually, we notice that it may not be necessary to obtain the exact value of maximin share for each agent. 
Instead, we can exploit a reasonable upper bound of each $\mathsf{MMS}_i$. 
Similar ideas have been widely applied to designing efficient algorithms for fair allocation of indivisible goods \cite{DBLP:journals/teco/BarmanK20,DBLP:journals/ai/GargT21}. 
Specifically, for each agent $i$, we start by setting the threshold to be less than $\mathsf{MMS}_i$ (e.g., $\tau_{i, 0} = \frac{max_{g\in M}s_i(g)}{\rho_{i, 1}}$). 
Then we (geometrically) increase the threshold by setting $\tau = (1+\delta)\cdot \tau$ and rerun Algorithm \ref{Machine 2}, until no job remains unallocated at the end of Algorithm \ref{Machine 2}. 
Such an algorithm runs in polynomial time since Algorithm \ref{Machine 2} is run for at most $\log_{(1+\delta)}(\frac{\tau_{i, 0}}{\mathsf{MMS}_i})$ times. 
Besides, it guarantees that each agent can complete the jobs allocated to her in $(2+\delta)\cdot \mathsf{MMS}_i$ time. 


\section{Proportionality up to one or any item}
\label{sec:propx}

In this section, we discuss another relaxation for proportionality, ``proportional up to one item'' and ``proportional up to any item'', which are also widely studied for additive valuations.


\begin{definition}[$\alpha$-PROP1 and $\alpha$-PROPX]
An allocation $\mathbf{X} = (X_1, \ldots, X_n)$ is $\alpha$-approximate proportional up to one item ($\alpha$-PROP1) if $v_i(X_i\backslash \{g\})\le \alpha \cdot \frac{v_i(M)}{n}$ for all agents $i\in N$ and some item $g\in X_i$. 
It is $\alpha$-approximate proportional up to any item ($\alpha$-PROPX) if $v_i(X_i\backslash \{g\})\le \alpha \cdot \frac{v_i(M)}{n}$ for all agents $i\in N$ and any item $g\in X_i$. 
The allocation is PROP1 or PROPX if $\alpha = 1$. 
\end{definition}


It is easy to see that a PROPX allocation is also PROP1.
Although exact PROPX and PROP1 allocation is guaranteed to exist for chores with additive valuation, when the valuation is subadditive, no algorithm can be better than $n$-PROP1 or $n$-PROPX. 
Consider an instance with $n$ agents and $n+1$ items. The valuation function is $v_i(S) = 1$ for all agents $i\in N$ and any non-empty subset $S\subseteq M$. Clearly, the valuation function is subadditive since $v_i(S) + v_i(T) \ge v_i(S\cup T)$ for any $S, T\subseteq M$. By the pigeonhole principle, at least one agent $i$ receives two or more items in any allocation of $M$. After removing any item $g\in X_i$, $X_i$ is still not empty. 
That is, $v_i(X_i\backslash \{g\}) = 1 = n\cdot \frac{v_i(M)}{n}$ for any $g \in X_i$.  
This example can be easily extended to the bin-packing and job-scheduling valuations, thus we have the following theorem, whose proof can be seen in the appendix. 

\begin{theorem} \label{thm:propx}
For the bin-packing model and the job-scheduling model, no algorithm performs better than $n$-PROP1 or $n$-PROPX.
\end{theorem}

\section{Conclusion}
In this work, we study the fair allocation problem of allocating indivisible chores when the valuations are subadditive and fairness is measured by MMS. 
We first show that no algorithm can ensure better than $n$-MMS even when the valuations are submodular. 
Then we considered two specific combinatorial valuations, namely, bin packing and job scheduling.
For bin packing valuations, we show that one of the best possible approximation algorithms is bag filling which achieves 2-MMS.
For job scheduling valuations, we show a 2-MMS allocation can be found efficiently, and inherit the lower bound of $44/43$ from additive valuations.
Our work uncovers several future directions. 
One immediate direction is to design better approximation algorithms or lower bound instances for the job scheduling valuations.
In this work, we restricted us on the case of related machines, it is intriguing to consider the general model of unrelated machines.
As we mentioned, the notion of collective maximin share fairness in the job scheduling model can be viewed as a group-wise fairness notion (for both goods and chores), which could be studied of independent interest.
Finally, we can investigate other combinatorial valuations that can better characterize real-world problems.

