# Fair Allocation of Indivisible Chores:
Beyond Additive Valuations††thanks: The authors are ordered alphabetically.
Part of this work was done when the second author was a research assistant
with The Hong Kong Polytechnic University.

Bo Li1 Fangxiao Wang2 Yu Zhou1
1Department of Computing, The Hong Kong Polytechnic University, Hong Kong,
China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
2 School of Information and Communication Engineering, UESTC, Chengdu, China
<EMAIL_ADDRESS>
(April 29, 2022)

###### Abstract

In this work, we study the maximin share (MMS) fair allocation of indivisible
chores. For additive valuations, Huang and Lu [EC, 2021] designed an algorithm
to compute a $11/9$-approximate MMS fair allocation, and Feige et al. [WINE,
2021] proved that no algorithm can achieve better than 44/43 approximation.
Beyond additive valuations, unlike the allocation of goods, very little is
known. We first prove that for submodular valuations, in contrast to the
allocation of goods where constant approximations are proved by Barman and
Krishnamurthy [TEAC, 2020] and Ghodsi et al [AIJ, 2022], the best possible
approximation ratio is $n$. We then focus on two concrete settings where the
valuations are combinatorial. In the first setting, agents need to use bins to
pack a set of items where the items may have different sizes to different
agents and the agents want to use as few bins as possible to pack the items
assigned to her. In the second setting, each agent has a set of machines that
can be used to process a set of items, and the objective is to minimize the
makespan of processing the items assigned to her. For both settings, we design
constant approximation algorithms, and show that if the fairness notion is
changed to proportionality up to one/any item, the best approximation ratio is
$n$.

Key Words: Indivisible Chores, Maximin Share Fairness, Subadditive Valuations,
Bin Packing, Job Scheduling.

##  1 Introduction

###  1.1 Background and related research

Since the introduction of maximin share (MMS) fairness by Budish [2011], 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, Budish [2011] 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 Kurokawa et al. [2018] 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. Kurokawa et
al. [2018] first proved there exists a $2/3$-approximate MMS fair allocation
for additive valuations, and then Amanatidis et al. [2017] designed a
polynomial time algorithm with the same approximation guarantee. Later, Ghodsi
et al. [2021] improved the approximation ratio to $3/4$, and Garg and Taki
[2021] further improved it to $3/4+1/(12n)$. On the negative side, Feige et
al. [2021] proved that no algorithm can ensure better than $39/40$
approximation. Beyond additive valuations, Barman and Krishnamurthy [2020]
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. Ghodsi et al. [2022] 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
Seddighin and Seddighin [2022].

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. Aziz et
al. [2017] first pointed out this issue, and proved that the round-robin
algorithm ensures 2 approximation for additive valuations for indivisible
chores. Barman and Krishnamurthy [2020] and Huang and Lu [2021] respectively
improved the approximation ratio to $4/3$ and $11/9$. Recently, Feige et al.
[2021] 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 Barman and Krishnamurthy [2019], Brânzei and
Sandomirskiy [2019], Aziz et al. [2020]. For chores, both PROP1 and PROPX
allocations exist and can be found efficiently Moulin [2018], Li et al.
[2022]. As far as we know, all the above works assume the valuations are
additive, and combinatorial valuations have not been considered yet.

###  1.2 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 [Barman and Krishnamurthy, 2020, Ghodsi et al., 2022].

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.

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 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.

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.

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 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.

Result 3 For job-scheduling valuations, a 2-approximate MMS allocation can be
found efficiently.

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.

##  2 Preliminaries

For any integer $k\geq 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})\leq 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.

  * •

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})\leq v_{i}(S_{1})+v_{i}(S_{2}).$

  * •

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})\leq
v_{i}(S_{1}\cup\\{e\\})-v_{i}(S_{1}).$

  * •

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\\}).$

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})\leq\mathsf{MMS}_{i}$ for
all $i$, then $\mathbf{X}$ is called an 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.

######  Definition 1 ($\alpha$-MMS)

An allocation $\mathbf{X}=(X_{1},\ldots,X_{n})$ is $\alpha$-approximate
maximin share ($\alpha$-MMS) fair if
$v_{i}(X_{i})\leq\alpha\cdot\mathsf{MMS}_{i}$ for any agent $i\in N$. The
allocation is MMS fair if $\alpha=1$.

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

###### Lemma 1

For any agent $i$ with subadditive valuation $v_{i}(\cdot)$, we have the
following bounds for $\mathsf{MMS}_{i}$,

$\mathsf{MMS}_{i}\geq\max\big{\\{}\max_{j\in M}v_{i}(\\{j\\}),\frac{1}{n}\cdot
v_{i}(M)\big{\\}}.$

##  3 Submodular valuations

By Lemma 1, 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.

###### Theorem 1

For any $n\geq 2$, there is an instance with submodular valuations for which
no allocation is better than $n$-MMS.

Proof For any fixed $n\geq 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)\leq 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$.

##  4 Bin packing model

Although Theorem 1 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}\geq 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}\geq\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.

###### Lemma 2

$\mathsf{MMS}_{i}\cdot c_{i}\geq\frac{s_{i}(M)}{n}$ for any $i\in N$

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

###### Theorem 2

For the bin-packing model, no algorithm performs better than 2-MMS.

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 Barman and
Krishnamurthy [2020], Huang and Lu [2021]. Although this lemma does not hold
for arbitrary subadditive valuations, it holds for the bin-packing model.

We call a bin-packing instance identical ordering (IDO) if $s_{i,1}\geq
s_{i,2}\geq\cdots\geq 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^{\prime}\in
M$ with $j<j^{\prime}$, $s_{i,\sigma_{i}(j)}\geq
s_{i,\sigma_{i}(j^{\prime})}$. Using these permutations, we can construct the
IDO instance by setting $s^{\prime}_{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.

###### Lemma 3

If there exists an allocation
$\mathcal{A}^{\prime}=(A_{1}^{\prime},...,A_{n}^{\prime})$ in the IDO instance
$I^{\prime}$, such that
$v_{i}^{\prime}(A_{i}^{\prime})\leq\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})\leq\alpha\cdot\mathsf{MMS}_{i}$ for all $i\in N$. Besides,
$\mathcal{A}$ can be constructed in polynomial time.

Next, we present the main algorithm (Algorithm 1) 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 1 so
that the approximation ratio improves to $(3+\delta)/2$ when MMS values get
large.

###### Theorem 3

Algorithm 1 returns a $2$-MMS allocation for bin-packing instances in
polynomial time.

Before the proof of Theorem 3, 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}\leq\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 1 to 1) and
bag filling (Steps 1 through 1). 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.

###### Lemma 4

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.

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.

1 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.

2 Output: An allocation $\mathcal{A}=(A_{1},A_{2},\cdots,A_{n})$ such that
$v_{i}(A_{i})\leq 2\cdot\mathsf{MMS}_{i}$ for every $i\in N$.

3 Initialize $R=M$.

4 while  _$|N| >1$_ do

5 Initialize $Q=N$, $B=\emptyset$,
$k=\max\\{i\in[1,\lceil\frac{m}{n}\rceil]\mid G_{i}\cap R\cap
H\neq\emptyset\\}$.

6 for  _$i=1$ to $k$_ do

7 Pick the largest item $g$ in $G_{i}\cap R$.

8 $B\leftarrow B\cup\\{g\\}$, $R\leftarrow R\backslash\\{g\\}$.

9 end for

10 $Q=\\{i\in N\mid B=\emptyset\ or\ \forall j\in
B:s_{i,j}\geq\frac{c_{i}}{2}\\}$.

11 while  _$s_{i}(B)\leq\frac{s_{i}(M)}{n}$ for some agent $i\in N$ and
$L_{i}\cap R\neq\emptyset$ _ do

12 Pick an item $g$ in $L_{i}\cap R$.

13 $B\leftarrow B\cup\\{g\\}$, $R\leftarrow R\backslash\\{g\\}$.

14 $Q=\\{i\\}$.

15

16 end while

17 Pick an agent $i$ in $Q$.

18 $A_{i}\leftarrow B$, $N\leftarrow N\backslash\\{i\\}$.

19

20 end while

Allocate the remaining items in $R$ to the last agent.

Algorithm 1 2-MMS allocation for IDO bin-packing instance.

###### Lemma 5

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.

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 2. 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 5. 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\\})\leq\frac{s_{i}(M)}{n}$ and
$s_{i}(\\{g\\})\leq\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)\leq\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.

Now, we are ready to prove Theorem 3.

Proof of Theorem 3 Clearly, Algorithm 1 runs in polynomial time. For all the
agents except the last one, Lemma 4 and Lemma 5 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^{\prime}$, then we have

$s_{i}(M^{\prime})=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 5, agent $i$ can use no more than $2\mathsf{MMS}_{i}$ bins
to pack all the items in $M^{\prime}$. Second, at least one bag allocated to
other agents is not large enough for agent $i$, i.e,
$s_{i}(A_{j})\leq\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 4, 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.

##  5 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}\geq 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}\geq\rho_{i,2}\geq\cdots\geq\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., 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.111 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 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
Barman et al. [2018] and Caragiannis et al. [2019], 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 Feige et al. [2021] no
algorithm can be better than $44/43$-approximation.

1 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.

2 Output: An allocation $\mathcal{A}=(A_{1},A_{2},...,A_{n})$ such that
$v_{i}(A_{i})\leq 2\cdot\mathsf{MMS}_{i}$ for every $i\in N$.

3 Initialize allocation $\mathcal{A}=(A_{1},...,A_{n})$ with $A_{i}=\emptyset$
for every $i\in N$.

4 while  _$M\neq\emptyset$_ do

5 for  _$i=1$ to $m$_ do

6 Pick $g\in\operatorname*{arg\,max}_{g^{\prime}\in M}s_{i,g^{\prime}}$.

7 $A_{i}\leftarrow A_{i}\cup\\{g\\}$, $M\leftarrow M\backslash\\{g\\}$.

8 end for

9

10 end while

Algorithm 2 2-MMS allocation for IDO job-scheduling instance

Next we focus on the upper bound and prove a result similar with Lemma 3 in
the bin packing model. That is, it suffices for us to design algorithms for
the IDO instances where $s_{i,1}\geq s_{i,2}\geq\cdots\geq 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 4 (presented in the
appendix). Since the proof is almost the same as that of Lemma 3, 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 2): 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}$.

###### Theorem 4

Algorithm 2 computes a 2-MMS allocation for every IDO job-scheduling instance
in polynomial time.

To prove Theorem 4, we present an algorithm (Algorithm 3) for every agent to
assign the jobs that Algorithm 2 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.

1 Input: A set of jobs $A=\\{1,2,...,t\\}$ with sizes $s_{1}\geq
s_{2}\geq\cdots\geq s_{t}$, and a set of machines $P=\\{1,2,...,k\\}$ with
speeds $\rho_{1}\geq\rho_{2}\geq\cdots\geq\rho_{k}$, and a threshold $\tau$.

2 Output: An allocation $T=(T_{1},T_{2},...,T_{k})$.

3 Initialize $T_{i}=\emptyset$, $c_{i}=\tau\cdot\rho_{i}$ for every $i\in P$,
$g=1$.

4 for  _$i=1$ to $k$_ do

5 while  _$s(T_{i})+s_{g}\leq 2c_{i}$ and $A\neq\emptyset$_ do

6 $T_{i}\leftarrow T_{i}\cup\\{g\\}$, $A\leftarrow A\backslash\\{g\\}$.

7 $g\leftarrow g+1$.

8 end while

9

10 end for

Algorithm 3 Job scheduling with threshold

###### Lemma 6

For every agent $i$, denote $A_{i}$ as the jobs that Algorithm 2 allocates to
her. If $\tau\geq\mathsf{MMS}_{i}$, Algorithm 3 assigns all the jobs in
$A_{i}$ among her machines $P_{i}$.

Proof of Lemma 6 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 3. 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}\geq\mathsf{MMS}_{i}\cdot\rho_{i,j}$. Besides, $c_{i,1}\geq
c_{i,2}\geq\cdots\geq c_{i,k_{i}}$. We denote $T=(T_{1},T_{2},...,T_{k_{i}})$
as the allocation returned by Algorithm 3 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^{\prime}=(T^{\prime}_{1},T^{\prime}_{2},...,T^{\prime}_{k_{i}})$ where
$T^{\prime}_{j}=T_{j}\backslash t_{j}^{*}\cup t_{j+1}^{*}$ for
$j\in[1,k_{i}]$. In agent $i$’s MMS-defining partition, every job $g\in M$
must be assigned to one machine $j$. This implies that
$s_{i,g}\leq\mathsf{MMS}_{i}\cdot\rho_{i,j}\leq c_{i,1}$ for every $g\in M$.
From Algorithm 3, we know that $s_{i}(T_{1}\cup t_{2}^{*})>2c_{i,1}$, thus we
have $s_{i}(T^{\prime}_{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}^{*}}\leq c_{i,j}$ for
every $j\in[1,l]$ where $l$ is less than $k_{i}$. Similar to the claim that
$s_{i}(T^{\prime}_{1})>c_{i,1}$, we have $s_{i}(T^{\prime}_{j})>c_{i,j}$ for
any $j\in[1,l]$. Summing up these $l$ inequalities, we have
$\sum_{j=1}^{l}s_{i}(T^{\prime}_{j})>\sum_{j=1}^{l}c_{i,j}$. Since Algorithm 2
allocates jobs to agents in a round-robin fashion, we know that for any job
$g$ in $\cup_{j=1}^{l}T_{j}^{\prime}$, 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)\geq\sum_{g\in\cup_{j=1}^{l}T_{j}^{\prime}}n\cdot
s_{i,g}=n\cdot\sum_{j=1}^{l}s_{i}(T^{\prime}_{j})>n\cdot\sum_{j=1}^{l}c_{i,j}\geq
n\cdot\sum_{j=1}^{l}\mathsf{MMS}_{i}\cdot\rho_{i,j}.$

By the pigeonhole principle, in agent $i$’s 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\geq 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}\leq\mathsf{MMS}_{i}\cdot\rho_{i,j}\leq
c_{i,l+1}$. Since any job in $S$ is not smaller than job $t_{l+1}^{*}$, we
have $s_{i,t_{l+1}^{*}}\leq s_{i,g}\leq c_{i,l+1}$.

Therefore, we have $s_{i,t_{j}^{*}}\leq c_{i,j}$ for every $j\in[1,k_{i}]$.
Similarly, we have $s_{i}(T^{\prime}_{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 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}$.

Proof of Theorem 4 Clearly, Algorithm 2 runs in polynomial time. For each
agent $i$, we set the threshold $\tau=\mathsf{MMS}_{i}$. Lemma 6 shows that
all the jobs Algorithm 2 allocates to agent $i$ can be assigned to her
machines. Besides, we know from Algorithm 3 that the completion time of each
of agent $i$’s machines doesn’t exceed $2\mathsf{MMS}_{i}$. Therefore,
$v_{i}(A_{i})\leq 2\mathsf{MMS}_{i}$ holds for every agent $i\in N$, which
completes the proof.

#### Remark

Note that although the proof of Theorem 4 requires the value of each
$\mathsf{MMS}_{i}$ which is NP-hard to compute, Algorithm 2 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 Barman and
Krishnamurthy [2020], Garg and Taki [2021]. 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 3, until no job remains unallocated at the end of Algorithm 3. Such
an algorithm runs in polynomial time since Algorithm 3 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.

##  6 Proportionality up to one or any item

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.

######  Definition 2 ($\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\\})\leq\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\\})\leq\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$.

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)\geq 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.

###### Theorem 5

For the bin-packing model and the job-scheduling model, no algorithm performs
better than $n$-PROP1 or $n$-PROPX.

##  7 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.

## References

  * Amanatidis et al. [2017] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi.  Approximation algorithms for computing maximin share allocations.  _ACM Trans. Algorithms_ , 13(4):52:1–52:28, 2017.
  * Amanatidis et al. [2020] G. Amanatidis, E. Markakis, and A. Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  _Theor. Comput. Sci._ , 841:94–109, 2020.
  * Amanatidis et al. [2022] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris.  Fair division of indivisible goods: A survey.  _CoRR_ , abs/2202.07551, 2022.
  * Aziz et al. [2017] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In _AAAI_ , pages 335–341. AAAI Press, 2017.
  * Aziz et al. [2020] H. Aziz, H. Moulin, and F. Sandomirskiy.  A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation.  _Oper. Res. Lett._ , 48(5):573–578, 2020.
  * Aziz et al. [2022] H. Aziz, B. Li, H. Moulin, and X. Wu.  Algorithmic fair allocation of indivisible items: A survey and new questions.  _CoRR_ , abs/2202.08713, 2022.
  * Barman and Krishnamurthy [2019] S. Barman and S. K. Krishnamurthy.  On the proximity of markets with integral equilibria.  In _AAAI_ , pages 1748–1755, 2019.
  * Barman and Krishnamurthy [2020] S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  _ACM Trans. Economics and Comput._ , 8(1):5:1–5:28, 2020.
  * Barman et al. [2018] S. Barman, A. Biswas, S. K. K. Murthy, and Y. Narahari.  Groupwise maximin fair allocation of indivisible goods.  In _AAAI_ , pages 917–924. AAAI Press, 2018.
  * Bhaskar et al. [2021] U. Bhaskar, A. R. Sricharan, and R. Vaish.  On approximate envy-freeness for indivisible chores and mixed resources.  In _APPROX-RANDOM_ , volume 207 of _LIPIcs_ , pages 1:1–1:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * Brânzei and Sandomirskiy [2019] S. Brânzei and F. Sandomirskiy.  Algorithms for competitive division of chores.  _CoRR_ , abs/1907.01766, 2019.
  * Budish [2011] E. Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ , 119(6):1061–1103, 2011.
  * Caragiannis et al. [2019] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  _ACM Trans. Economics and Comput._ , 7(3):12:1–12:32, 2019.
  * Chan et al. [2019] H. Chan, J. Chen, B. Li, and X. Wu.  Maximin-aware allocations of indivisible goods.  In _IJCAI_ , pages 137–143. ijcai.org, 2019.
  * Feige et al. [2021] U. Feige, A. Sapir, and L. Tauber.  A tight negative example for MMS fair allocations.  In _WINE_ , volume 13112 of _Lecture Notes in Computer Science_ , pages 355–372. Springer, 2021.
  * Garg and Taki [2021] J. Garg and S. Taki.  An improved approximation algorithm for maximin shares.  _Artif. Intell._ , 300:103547, 2021.
  * Ghodsi et al. [2021] M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Improvement.  _Math. Oper. Res._ , 46(3):1038–1053, 2021.
  * Ghodsi et al. [2022] M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Beyond additive valuations.  _Artif. Intell._ , 303:103633, 2022.
  * Huang and Lu [2021] X. Huang and P. Lu.  An algorithmic framework for approximating maximin share allocation of chores.  In _EC_ , pages 630–631. ACM, 2021.
  * Kurokawa et al. [2018] D. Kurokawa, A. D. Procaccia, and J. Wang.  Fair enough: Guaranteeing approximate maximin shares.  _J. ACM_ , 65(2):8:1–8:27, 2018.
  * Li et al. [2022] B. Li, Y. Li, and X. Wu.  Almost proportional allocations for indivisible chores.  _TheWebConf_ , 2022.
  * Lipton et al. [2004] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In _EC_ , pages 125–131. ACM, 2004.
  * Moulin [2018] H. Moulin.  Fair division in the age of internet.  _Annu. Rev. Econ._ , 2018.
  * Plaut and Roughgarden [2020] B. Plaut and T. Roughgarden.  Almost envy-freeness with general valuations.  _SIAM J. Discret. Math._ , 34(2):1039–1068, 2020.
  * Seddighin and Seddighin [2022] M. Seddighin and S. Seddighin.  Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem.  2022\.
  * Zhou and Wu [2021] S. Zhou and X. Wu.  Approximately EFX allocations for indivisible chores.  _CoRR_ , abs/2109.07313, 2021.

##  Appendix A More Related Works

We refer the readers to Amanatidis et al. [2022], Aziz et al. [2022] for
detailed surveys on fair division of indivisible items. Beyond
proportionality, in another parallel line of research, envy-freeness and its
relaxations, namely envy-free up to one item (EF1) and envy-free up one any
item (EFX), are very widely studied. It is shown in Lipton et al. [2004] and
Bhaskar et al. [2021] for goods and chores, respectively, an EF1 allocation
exists for the monotone combinatorial valuations. However, the existence of
EFX allocations is still unknown even with additive valuations. Therefore,
approximation algorithms are proposed in Amanatidis et al. [2020], Zhou and Wu
[2021] for additive valuations and in Plaut and Roughgarden [2020], Chan et
al. [2019] for subadditive valuations.

##  Appendix B Bin-packing model: a $(3+\delta)/2$ approximation

In this section, we make a slight improvement on Algorithm 1 and prove that
the new algorithm returns us $(3+\delta)/2\mathsf{MMS}$ allocations when MMS
values get large. At Step 1 in Algorithm 1, instead of arbitrarily picking an
item in $L_{i}\cap R$, we pick the smallest item in it. Then we have the
following theorem.

###### Theorem 6

The modified Algorithm 1 computes a $(3+\delta)/2$-MMS allocation for all IDO
bin-packing instances in polynomial time when MMS values get large.

Before proving Theorem 6, we introduce some notations and observations. If the
total size of a set of items doesn’t exceed $c_{i}$, we say these items are
acceptable for the agent $i$. If not, we still say they are passable for agent
$i$, as long as there exist small items for agent $i$ among them and removing
one small item makes the remaining items acceptable for the agent. Consider
$\mathsf{MMS}_{i}$ passable sets of items, first, the total size of these
items is greater than $\mathsf{MMS}_{i}\cdot c_{i}$, which is at least
$\frac{s_{i}(M)}{n}$ according to Lemma 2. Besides, agent $i$ can use no more
than $\lceil\frac{3}{2}\cdot\mathsf{MMS}_{i}\rceil$ bins to pack them. To
achieve this, agent $i$ first converts each passable set to an acceptable one
by taking out the special small item. This gives her $\mathsf{MMS}_{i}$
acceptable sets which can be packed using $\mathsf{MMS}_{i}$ bins. Then, agent
$i$ can use at most $\lceil\frac{\mathsf{MMS}_{i}}{2}\rceil$ to pack the
$\mathsf{MMS}_{i}$ small items that are taken out.

Now, we are ready to prove Theorem 6.

Proof of Theorem 6 To prove Theorem 6, we show that every agent $i$ can use no
more than $\lceil\frac{3}{2}\cdot\mathsf{MMS}_{i}\rceil$ bins to pack all the
items in $A_{i}$. For the agents who receive the initialized bags, we’ve shown
in the proof of Lemma 4, that they can use $\mathsf{MMS}$ bins to pack the
items. For each agent $i$ who receives a bag in the bag filling procedure, we
first show that there are at most $\mathsf{MMS}_{i}$ large items for her in
the bag. According to the structure of $G$s, we know that the initialized bag
contains at most $\mathsf{MMS}_{i}$ large items for agent $i$. Furthermore,
after modifying the Step 1 in Algorithm 1, the items added by the agents
before agent $i$ cannot be large for agent $i$. This is because when this
happens, there remains no small item for agent $i$, thus she won’t fill the
bag and the bag won’t be allocated to her. Next, we show how agent $i$
arranges the items in the bag into $\mathsf{MMS}_{i}$ passable sets, which can
be packed using no more than $\lceil\frac{3}{2}\cdot\mathsf{MMS}_{i}\rceil$
bins. The agent first puts the large items into different sets, which creates
at most $\mathsf{MMS}_{i}$ acceptable sets. Then, she makes these sets
passable one by one by filling small items into them. If there are still some
small items left, the agent will create a new set and make it passable by
filling it with small items. This process is repeated until no small item is
left. Recall that the size of the bag doesn’t exceed $\frac{s_{i}(M)}{n}$
before the last item is added. This implies that arranging all the items
except the last one in the above way creates less than $\mathsf{MMS}_{i}$
passable sets. Otherwise, the total size of these sets exceeds
$\frac{s_{i}(M)}{n}$. Therefore, after filling the last item, agent $i$ can
still get no more than $\mathsf{MMS}_{i}$ passable sets.

For the last agent $i$ who receives the remaining items, there are two cases.
In the first case, the total size of the remaining items is at most
$\frac{s_{i}(M)}{n}$. Besides, from the proof of Theorem 3, we know that at
most $\mathsf{MMS}_{i}$ among them are large for the agent. As we’ve shown
previously, these items can be arrange into less than $\mathsf{MMS}_{i}$
passable sets and be packed in no more than
$\lceil\frac{3}{2}\cdot\mathsf{MMS}_{i}\rceil$ bins. In the second case, all
the remaining items are large for agent $i$. Since there are at most
$\mathsf{MMS}_{i}$ such large items, the agent can use $\mathsf{MMS}_{i}$ bins
to pack them.

##  Appendix C Missing examples and proofs

In this section, we provide the examples and proofs omitted in the main body
of the paper.

#### An example of general valuation function

Note that there exist simpler examples, but we choose the following one
because it represents a particular combinatorial structure – minimum spanning
tree. Let $G=(V,E)$ be a graph shown in the left sub-figure of Figure 1, where
the vertices $V$ are the items that are to be allocated, i.e., $M=V$. There
are two agents $N=\\{1,2\\}$ who possess different weights on the edges as
shown in the middle and right sub-figures of Figure 1. The valuation functions
are measured by the minimum spanning tree in their received subgraphs.
Particularly, for any $S\subseteq V$, $v_{i}(S)$ equals the weight of the
minimum spanning tree on $G[S]$ – the induced subgraph of $S$ in $G$ – under
agent $i$’s weights. Thus, $\mathsf{MMS}_{i}=0$, for both $i=1,2$, where an
MMS-defining partition for agent $1$ is $\\{v_{1},v_{2}\\}$ and
$\\{v_{3},v_{4}\\}$ and that for agent $2$ is $\\{v_{1},v_{4}\\}$ and
$\\{v_{2},v_{3}\\}$. However, it can be verified that no matter how the
vertices are allocated to the agents, there is one agent whose value is at
least 1, which implies that no bounded approximation is possible for general
valuations.

Figure 1: An instance with unbounded approximation ratio

Proof of Lemma 1 The first claim is straightforward, since in any MMS-defining
partition of agent $i$, the item with largest value must appear in one of the
bundles, and by the monotonicity of the valuations, the value of this bundle
is at least $\max_{j\in M}v_{i}(\\{j\\})$.

To see the second claim, let $\mathbf{X}=(X_{1},\ldots,X_{n})$ be an MMS-
defining partition for agent $i$, then $v_{i}(X_{j})\leq\mathsf{MMS}_{i}$ for
all $j$. Summing up all these inequalities, we have

$v_{i}(M)\leq\sum_{j\in N}v_{i}(X_{j})\leq n\cdot\mathsf{MMS}_{i},$

where the first inequality is by the subadditivity of the valuations.

Proof of Theorem 2 We first recall the impossibility instance given by Feige
et al. [2021]. In this instance there are three agents and nine items as
arranged in a three by three matrix. The three agents’ valuations are shown in
the matrices $V_{1},V_{2}$ and $V_{3}$.

$\displaystyle V_{1}=\begin{pmatrix}6&15&22\\\ 26&10&7\\\
12&19&12\end{pmatrix}$ $\displaystyle V_{2}=\begin{pmatrix}6&15&23\\\
26&10&8\\\ 11&18&12\end{pmatrix}$ $\displaystyle
V_{3}=\begin{pmatrix}6&16&22\\\ 27&10&7\\\ 11&18&12\end{pmatrix}$

Feige et al. [2021] proved that for this instance the MMS value of every agent
is $43$, however, in any allocation, at least one of the three agents gets
value no smaller than 44.

We can adapt this instance to the bin-packing model and obtain a lower bound
of 2. In particular, we also have three agents and nine items. The numbers in
matrices $V_{1},V_{2}$ and $V_{3}$ are the sizes of the items to each agent
$1,2$ and $3$. Let the capacities of the bins of each agent be $c_{i}=43$ for
all $i$. Accordingly, we have $\mathsf{MMS}_{i}=1$. Since in any allocation,
there is at least one agent who gets items with total size no smaller than 44,
for this agent, she has to use 2 bins to pack the assigned items, which
finishes the proof.

Proof of Lemma 2 From the definition of maximin share, we know that each agent
$i$ can use $n\cdot\mathsf{MMS}_{i}$ bins to pack all the items. This implies
that the total capacity of $n\cdot\mathsf{MMS}_{i}$ bins is no smaller than
the total size of all the items. That is, $n\cdot\mathsf{MMS}_{i}\cdot
c_{i}\geq s_{i}(M)$, which completes the proof.

Proof of Lemma 3 We show that given $I$ and $\mathcal{A}^{\prime}$, Algorithm
4 finds $\mathcal{A}$ in polynomial time. Clearly, Algorithm 4 runs in
polynomial time. Now, we will show that Algorithm 4 finds the required
allocation $\mathcal{A}$. Considering the $g$-th iteration of the second for-
loop (Steps 4 to 4), suppose that item $k_{g}$ is allocated to agent $i$, we
have $k\in A_{i}^{\prime}$ and $k_{g}\in A_{i}$. Before $k_{g}$ is allocated,
exactly $g-1$ items have been allocated, since an item is removed from the set
$R$ after it is allocated. Therefore, $k_{g}$ is among the top $g$ smallest
items for agent $i$. Note that $g$ is the item with the exactly $g$-th
smallest size for agent $i$, hence we have $s_{i}^{\prime}(g)\geq
s_{i}(k_{g})$ for any $g\in A_{i}^{\prime}$ and $k_{g}\in A_{i}$. This implies
that it requires no more bins for agent $i$ to pack items in $A_{i}$ than
those in $A_{i}^{\prime}$, i.e., $v_{i}(A_{i})\leq
v_{i}^{\prime}(A_{i}^{\prime})$. Note that the maximin share depends on the
sizes of the items but not on the order, which means that the maximin share of
agent $i$ in $I^{\prime}$ is the same as her maximin share in $I$. Hence, the
condition that $v_{i}^{\prime}(A_{i}^{\prime})\leq\alpha\cdot\mathsf{MMS}_{i}$
gives us $v_{i}(A_{i})\leq\alpha\cdot\mathsf{MMS}_{i}$ for all $i\in N$.

1 Input: Instance $I=(N,M,\\{v_{i}\\}_{i\in N},\\{s_{i}\\}_{i\in N})$ with an
allocation $\mathcal{A}^{\prime}=(A_{1}^{\prime},...,A_{n}^{\prime})$ for the
IDO instance $I^{\prime}=(N,M,\\{v_{i}^{\prime}\\}_{i\in
N},\\{s_{i}^{\prime}\\}_{i\in M}$) such that
$v_{i}^{\prime}(A_{i}^{\prime})\geq\alpha\cdot\mathsf{MMS}_{i}$ for all $i\in
N$ .

2 Output: An allocation $\mathcal{A}=(A_{1},A_{2},...,A_{n}$) such that
$v_{i}(A_{i})\geq\alpha\cdot\mathsf{MMS}_{i}$ for all $i\in N$.

3 For all $i\in N$ and $g\in A_{i}^{\prime}$ set $p_{g}:=i$.

4 Initialize allocation $\mathcal{A}=(A_{1},A_{2},...,A_{n})$ with
$A_{i}=\emptyset$ for all $i\in N$, and initialize $R\leftarrow M$.

5 for  _$g=m$ to $1$_ do

6 Pick $k\in\operatorname*{arg\,min}_{g^{\prime}\in
R}\\{s_{p_{g},g^{\prime}}\\}$.

7 Update $A_{p_{g}}\leftarrow A_{p_{g}}\cup\\{k\\}$ and $R\leftarrow
R\backslash\\{k\\}$.

8 end for

Algorithm 4 $\alpha$-MMS Allocation for General Bin-Packing Instance

Proof of Theorem 5 For the bin-packing model, let’s consider an instance with
$n$ agents and $n+1$ items. The capacity of each agent’s bins is 1, i.e,
$c_{i}=1$ for any $i\in N$. Each item is very tiny so that every agent can
pack all the items in just one bin, e.g., $s_{i,j}=\frac{1}{n+1}$ for any
$i\in N$ and $j\in M$. Therefore, we have $v_{i}(M)=1$ and
$\mathsf{PROP}_{i}=\frac{1}{n}$ for each agent $i\in N$. 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}$, agent $i$ stills needs one bin
to pack the remaining items. Hence, we have
$v_{i}(X_{i}\backslash\\{g\\})=1=n\cdot\mathsf{PROP}_{i}$ for any $g\in
X_{i}$, which completes the proof.

For the job-scheduling model, we can consider an instance with $2n$ agents and
$2n+1$ jobs where each agent possesses $2n$ machines with the same speed of 1,
and the size of each job is 1 for every agent. It can be easily seen that for
every agent $i$, the maximum completion time of her machines is minimized when
assigning two jobs to one machine and one job to each of the remaining $2n-1$
machines. Therefore, we have $v_{i}(M)=2$ and
$\mathsf{PROP}_{i}=\frac{2}{2n}=\frac{1}{n}$ for any $i\in N$. Similarly, by
the pigeonhole principle, at least one agent $i$ receives two or more jobs in
any allocation of $M$. This implies that
$v_{i}(X_{i}\backslash\\{g\\})=1=n\cdot\mathsf{PROP}_{i}$, thus completing the
proof.