Fair Allocation of Indivisible Chores: Beyond Additive Costs
Authors: Bo Li
Fangxiao Wang
Yu Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: fair allocation of chores
beyond additive cost functions
bin packing
job scheduling

Abstract: We study the maximin share (MMS) fair allocation of $m$ indivisible tasks to $n$ agents who have costs for completing the assigned tasks.
It is known that exact MMS fairness cannot be guaranteed, and so far the best-known approximation for additive cost functions is $\frac{13}{11}$ by Huang and Segal-Halevi [EC, 2023]; however, beyond additivity, very little is known. 
In this work, we first prove that no algorithm can ensure better than $\min\{n,\frac{\log m}{\log \log m}\}$-approximation if the cost functions are submodular. 
This result also shows a sharp contrast with the allocation of goods where constant approximations exist as shown by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. 
We then prove that for subadditive costs, there always exists an allocation that is $\min\{n,\lceil\log m\rceil\}$-approximation, and thus the approximation ratio is asymptotically tight.
Besides multiplicative approximation, we also consider the ordinal relaxation, 1-out-of-$d$ MMS, which was recently proposed by Hosseini et al. [JAIR and AAMAS, 2022]. 
Our impossibility result implies that for any $d\ge 2$, a 1-out-of-$d$ MMS allocation may not exist.
Due to these hardness results for general subadditive costs, we turn to studying two specific subadditive costs, namely, bin packing and job scheduling. 
For both settings, we show that constant approximate allocations exist for both multiplicative and ordinal relaxations of MMS.

Fair Allocation of Indivisible Chores: Beyond Additive Costs
Bo Li
Fangxiao Wang'
Yu Zhou'
Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China
comp-bo. 1....1pppr eeplly..uuu....
fangxiao.. wang@connect.pol.. polyu mellu.hk. .k, csyzhou@comp. popp:opppppoy......mmm.mmmmmm.l. polyu.edu. edu. .hk
Abstract
We study the maximin share (MMS) fair allocation of m indivisible chores to n agents who have costs for completing the assigned chores. It is known that exact MMS fairness cannot be guaranteed, and so far the best-known approximation for additive cost functions II by Huang and Segal-Halevi [EC, 2023]; however, beyond additivity, very little is known. In this work, we first prove that no algorithm
can ensure better than min log log Jaappoxximation if the cost functions are submodular. This result also shows sharp contrast with the allocation of goods where constant approximations exist as shown by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. We then prove that for subadditive costs, there always exists an allocation that is min n, [log m aapppooximmtionn and thus the approximation ratio is asymptotically tight. Besides multiplicative approximation, we also consider the ordinal relaxation, 1 -ouut-of-d MMS, which recently proposed by Hosseini et al. [JAIR and AAMAS, 2022]. Our im- possibility result implies that for any d 2 2, l-out-of-d MMS allocation may exist. Due these hardness results for general subadditive costs, turn studying two specific subadditive costs, namely, bin packing and job scheduling. For both settings, we show that constant approximate allocations exist for both multiplicative and ordinal relaxations of MMS.
log m
Introduction
1.1 Background and related research
Although fair resource allocation has been widely studied in the past decade, the research is centered around additive functions [3] However, in many real-world scenarios. the functions more complicated. Particularly, the functions appear in machine learning and artificial intelligence (c.g, clustering (37]. Sketches [18]. Coresets (36), data distillation 41)) often submodular, and we refer the readers to recent survey that reviews some major problems within machine learning that have been touched by submodularity [12]. Therefore, in this work, study the fair allocation problem when the agents have beyond additive cost functions. The mainly studied solution concept is maximin share (MMS) fairness [14], which 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 allocated her. PROP is too demanding in the sense that such an allocation does not exist even when there is a single item and two agents. Due to this strong impossibility result, the maximin share (MMS) of an agent is proposed relax the average utility by the maximum utility the agent can guarantee herself if she is to partition the items into n bundles but receive the least favorite bundle.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

For the allocation of goods, although MMS significantly weakens the faimess requirement, it was first shown by Kurokawa al. [31 32 that there are instances where no allocation is MMS fair for all agents. Accordingly, designing (efficient) algorithms to compute approximately MMS fair allocations steps into the center of the field of algorithmic fair allocation. Kurokawa et al. 32 first proved that there exists a 5 --approximate MMS fair allocation for additive utilities, and then Amanatidis et al.
[]] designed a polynomial time algorithm with the same approximation guarantee. Later, Ghodsi et al. [23] improved the approximation ratio to 1. and Garg and Taki [22] further improved it to
+ o(1). On the negative side, Feige et al. (20) proved that no algorithm can ensure better than 30
40 approximation. Beyond additive utilities, Barman and Krishnamurthy [ initiated the study of approximately MMS fair allocation with submodular utilitiies, and proved that 0.21 21-approximate
MMS fair allocation can be computed by the round-robin algorithm. Ghodsi et al. (24) improved the approximation ratio to 3. and moreover, they gave constant and logarithmic approximation guarantees for XOS and subadditive utilities, respectively. The approximations for XOS and subadditive utilities are recently improved by Seddighin and Seddighin 44). There are also several works that delve into concrete combinatorial problems and seek to improve approximation ratios compared to more general functions. Li et al. (33 and Hummel and Hetland (30) introduced interval scheduling and independent set structures, respectively, into MMS fair allocation problems. In both cases, the induced utility functions correspond to special cases of XoS functions. Both of these two works enhanced the approximation ratios for their specific utility functions. Some other combinatorial problems that have been studied for goods include the knapsack problem [1 g
and matroid constraints [1].
For the parallel problem of chores, where agents need to spend costs on completing the assigned chores, less effort has been devoted. Aziz et al. [4] first proved that the round-robin algorithm ensures 2-approximation for additive costs. Barman and Krishnamurthy (6) Huang and Lu (28] and Huang
and Segal-Halevi (29) respectively improved the approximation ratio to 4 11 and 13
11 Recently,
3. 9
Feige et al. [20] proved that with additive costs, algorithm can be better than 44 -aprroxximte.
4n
However, except a recent work that studies binary supermodular costs [00], very little is known beyond additivity.
Besides multiplicative approximations, we also consider the ordinal approximation of MMS, namely, 1 1-out-of-d MMS fairness which is recently studied in [5] 26 27]. and proportionality up to any item (PROPX) which is an alternative way to relax proportionality [3 34]. For indivisible chores, Hosseini et al. [26] and Li et al. (34) respectively proved the existence of l-out-of- 4 and exact PROPX allocations. All the above works also assume additive costs. More works related to
3n MMS fair
this paper in the literature can be seen in Appendix A
1.2
Main results
In this work, we aim at understanding the extent to which MMS fairness can be satisfied when the cost functions are beyond additive. In sharp contrast the allocation of goods, first show that no algorithm can ensure better than min(n, log log m J-approximation when the cost functions
log
submodular!! Further, we show that for general subadditive cost functions, there always exists an allocation that is min(n, log m) aapprxxxittee MMS, and thus the approximation ratio is asymptot- ically tight. Next, we consider the ordinal relaxation, l-out-of-d MMS. It is trivial that louut-of-1 MMS is satisfied no matter how the items are allocated, and somewhat surprisingly, our impossibility result implies that for any d 2 2, there is an instance for which no allocation is ofout-of-d MMS.
Result For general subadditive cost functions, the asymptotically tight multiplicative approximation ratio of MMS is min(n. log m). Further, for any d 2 2, a al- l-out-of-d MMS allocation may not exist.
Result I combines Theorems 2 and Corollary I The strong impossibility in Result does not rule out the possibility of constant multiplicative or ordinal approximation of MMS fair allocations for specific subadditive costs. For this reason, we turn to studying two concrete settings with subadditive costs. The first setting encodes a bin packing problem. which has applications in many areas (e.g.. semiconductor chip design, loading vehicles with weight capacity limits, and filling containers (17].. In the first setting, the items have sizes which can be different to different agents. The agents have bins that can be used to pack the items allocated them with the goal of using as few bins as possible. The second setting encodes a job scheduling problem, which appears in many research
In this paper use log(-) to denote (.).
2

---

areas, including data science, big data, serf-performance computing, and cloud computing [25] In the second setting, the items are jobs that need to be processed by the agents. Each job may be of different lengths to different agents and each agent controls set of machines with possibly different speeds. Upon receiving a set of jobs, an agent's is cost is determined by the corresponding minimum completion time when processing the jobs using her own machines (i.e., makespan). As will be clear, job scheduling setting is more general than the additive cost setting. Besides, it uncovers new research directions for group-wise fairness.
Result 2 For the bin packing and job scheduling settings, a 1-out-of- ] MMS allocation and a 2-approximate MMS allocation always exist.
Result 2 combines Theorems 3 4 and Corollaries 2
3 Besides studying MMS faimess, in Appendix
we also prove hardness results for two other relaxations of proportionality, ie., PROPI and PROPX.
Preliminaries
In a fair allocation instance I= (N, fe: heN), there are n agents denoted by N = [n]] and m items denoted by M = (ei,...,,m Cm Each agent i E N has cost function over the items, u; 2 R U {0). Note that for simplicity, we abuse (-(-) to denote a cost function. The items are chores, and particularly, upon receiving a set of items S C M, (y()) represents the effort or cost agent i needs to spend on completing the chores in S. The cost functions are normalized and monotone, i.c., v: (0) = 0 and (x S 2y (S2) for any S S S2 S M. Note that no bounded approximation can be achieved for general cost functions, and we provide one such example in Appendix [B.]] Thus we restrict our attention to the following three classes. A cost function v; subadditive if for any S1.52 C M, (S, US22) S (;(S1) + 2/ (S2). . is submodular if for any S1 S S2 C MM and any e E M S2, (S2 U (et) (S2)) S (S (e)) 22 (S,). It is additive for any S M, u; (S) = Eees (i(fe)). It widely known that any additive function is also submodular, and any submodular function is also subadditive.
For any integer A: 2 1, let [k] (1....,k) k).
An allocation A- (AI....; An) is an n-partition of the items where A; contains the items allocated to agent i such that A, n, = 0 for any * j and UIEN A, = M. For any set S and integer d, let (S( be the set of all d-partitions of S. The maximin share (MMS) of agent is
min MMS (1) (X1...; (M),
max v; (X²)).
Note that may neglect n and I in MMS, (T) when there is ambiguity. Note that the computation of MMS is NP-hard even when the costs are additive, which can be verified by a reduction from the Partition problem. Given an n-partition of M, X (XI,..., Xx),, if (x())) < MMS; for any j E [n]. then X is called an MMS defining partition for agent i. Note that the original definition of MMS; for chores is defined with non-positive values, where the minimum value of the bundles is maximized. In this work, to simplify the notions, we choose to use non-negative numbers (representing costs), and thus the definition equivalently changed to be the maximum cost of the bundles being minimized. To be consistent with the literature, we still call it maximin share.
Definition (a-MMS) An allocation A = (Ai...., An) is a-approximate maximin share (a-MMS) fair u (A:) S for all E N. The allocation is MMS fair if 1.
Given the definition of MMS, for any agent with subadditive cost v;(-), we have the following bounds for MMS,,
MMS, 2 max {
max vi(fe)), (M)) eE
Following recent works 2. 26), we also consider the ordinal approximation of MMS, namely, 1-out-of-d MMS faimess. Intuitively, MMS fairness can be regarded 1-out-of-n MMS (i.e..
partitioning the items into n bundles but receiving the largest bundle). Since l-out-of-n MMS allocations may not exist, we can instead find maximum integer d < n such that l-out-of-d MMS allocation is guaranteed to exist. Given a d-partition of M, X (X1,..., Xa), if uz (X,)) < MMS, for any j E [d], then X is called a loout-of-d MMS defining partition for agent i. An allocation A is l-out-of-d d MMS fair if for every agent i E N, (A,) < MMS More generally, given any a 2 1, we have the bi-factor approximation, a-approximate 1-out-of-d MMS, if vA,))) I MMS; for
3

---

every i E N. By the definition, we have the following simple observation, whose proof is deferred to Appendix(B.2
Observation 1 For any instance with subadditive costs, given any integer 1 S d S l-out-of-d MMS allocation is [=_ -MMS fain.
General subadditive cost setting
By Inequality [ if the costs subadditive, allocating all items to single agent ensures approximation of n, which the most unfair algorithm. Surprisingly, such an unfair algorithm achieves the optimal approximation ratio of MMS even if the costs submodular.
Theorem For any n 2 2. there is an instance with submodular costs for which no allocation is log m -MMS.
better than n-MMS or log log
Proof. For any fixed 2 2, we construct an instance that contains agents and n items. By taking logarithm of m = n² twice, it is easy to obtain
log m
log m
72
log log log log
log log
Thus, in the following, it suffices to show that allocation can be better than n-MMS. Let each item correspond to point in an n-dimensional coordinate system, i.e.,
M = ( ..,
,,, Fn)
aı; [n] for all i [n]]-
For each agent N, we define n covering planes {Cu)teln) and for each / [n].
Ci (2,,, .......... vn)
x; and zj E [ni] for all j E [n]] {i)).
(2)
Note that (Cu)tejn) forms an exact cover of the points in M, i... U, Ca M and Ca Ct. for all * For any set of items S M, u/ (S) equals the minimum number of planes in (a)ttjn that cover S. Therefore, (S) [n] for all S. We first show e=(-) is submodular for every i. For any S S T S M and any E M \ T, if e is not in the same covering plane as any point in T, is not in the same covering plane any point in S, either. Thus, (T U {ct) (T) implies (2 {e}) - (S) 1, and accordingly,
UTTUU vT(T) S (S u,))).
Since [Cu)le(m) is exact cover of M, MMS; 1 for every where the MMS defining partition is simply {Ca [ej] Then to prove the theorem, it suffices to show that for any allocation of M, there at least one agent whose cost n. For sake of contradiction, we assume there is an allocation A (Ai.....44 An) where every agent has cost at most there exists a plane Ca, such that A, n Ca, = Consider the point = (/1..... 4n), it is clear that b Ca, and thus b & A; for all i. This means that b is not allocated to any agent, contradiction. Therefore, such an allocation A does not exist which completes the proof of the theorem.
1. This means that for every i N,
To facilitate the understanding of Theorem in Appendix C. we visualize an instance with 3 agents and 27 items where no allocation is better than 3-MMS. The hard instance Theorem Talso implies the following lower bound for l-out-of-d MMS, whose proof is in Appendix C.2
Corollary For any S S n, there is an instance with submodular cost functions for which no allocation l-out-of-d MMS.
Theorem For any instance with subadditive cost functions, there always exists a min(n, [log m MMS allocation.
Proof. We describe the algorithm that computes min(n, [log m m]] -MMS allocation in Algorithm I. First, if log m 2 n, we are safe to arbitrarily allocate the items to the agents, which ensures nn-aproximmtionn.
The tricky case is when log m < n, where we cannot allocate too many items to a single agent. For this we first look at agent I's MMS defining partition D "i....,,A, where v (D.) < MMS,

---

Algorithm I Computing a min(n, MMMMSS allocation for subadditive costs
Input: An instance (N, M, {1; New) with general subadditive costs.
Output: An allocation A = (A1,.... such that 2 (A,) S [logm] MMS; for all E N.
Initialize A; t for every i N.
2: if' log m 2 then
3: A1 .M.
4: else
5:
i 1 and Mo + M.
6: end if
7:
while Mi-1 # and S n
8:
Let (Dí 1..... D2,) be one of i's MMS defining partitions over M.
9:
Let R Dj PoMMe M, for E [n]. Re-index the bundles such that R2] 2 ... |
10:
A; + U m1 RtJ and Mj f M \ Az.
11:
i 1-1+1. 1.
12: end while
for all j [n] and assume that they are ordered by the number of items, i... [Di] > | In order to ensure that agent I's cost no more than [log m times her MMS, we ask her to take away [log m largest bundles (in terms of number of items) in D', i..., Ai = [[o[[ mi]) D). Since the cost function is subadditive,
21 (A1)
Σ
e1(D)) [log m| MMS
]E[
Moreover, since average each bundle in D contains items and A1 contains the bundles with largest number items, |Ai] 2
m. That is, at least log fraction of the items are taken away by agent 1. Let Mi M Ai be the set of remaining items, and we have
Îlog m]
m logm
log m
Mil S
m
We next ask agent to take away items in a similar way to agent 1. Let D -Df,.... D2) be one of agent 2's MMS defining partitions, and R (R ... R2 be the remaining items in these bundles, i.c., R?? D3 M1. Again, we assume [R 2 ... 2 R Letting A = U mi) R
and M2 M2 Ag. we have (A2) < [log m] MMS,. Moreover, since on average each bundle in R contains [Mal items and A₂ contains the bundles with largest number of items,
|Mi
log m
A 2 [og m]
|
which gives
log m
M1 (
log m
M2 <
n
We continue with the above procedure for agents = 3..... n with the formal description shown in Algorithm [T. It is straightforward that every agent who gets bundle A, has cost at most [log MMS,. Further, by induction, Equation 3holld for all agents é I n, i.c.,
M <1-
(1-log log m
|M-1] (1- log m
n
To show the validity of the Algorithm, it remains to show that the algorithm can allocate all items, ie., M, 66. This can be seen from the following inequalities,
|Mal S (1 log m
log
log mn
Jogg
log m
m
m
<
m < m
1.
n
y1
7
Since |Mpl < 1, Mn must be empty, which completes the proof of the theorem.
5

---

Note that Theorem 1 does not rule out the possibility of beating the approximation ratio for specific subadditive costs. In the next two sections, we turn to studying two specific settings, where we are able to beat the lower bounds in Theorem and Corollary by designing algorithms that can guarantee constant ordinal and multiplicative approximations of MMS. We will mostly consider the ordinal approximation of MMS. By Observation [] the ordinal approximation gives result of the multiplicative one, which can be improved by slightly modifying the designed algorithms.
4
Bin packing setting
4.1
Model
The first setting encodes a bin packing problem where the items have sizes and need to be packed into bins by the agents. The items may be of different sizes to different agents. Specifically, each item ej E M has size $i,j 2 0 to each agent E N. For set of items S, s((S) = Le, 81.. Each agent i E N has unlimited number of bins with the same capacity c.. Without loss of generality, we assume that e
Cn and C₁ maxe;EM $t for all i E N.
Upon receiving a set of items S M, agent i's cost (S is determined by the minimum number of bins (with capacity 6:) that can pack all items in S. Note that the calculation of vz(S) involves solving classic bin packing problem which is NP-hard. For any two sets S and S2, (s(Si U S2) S (Si) + 0; (S2) since the optimal packing of S U.2 is no worse than packing S1 and S2 separately and thus (-) is subadditive. Accordingly, MMS; is essentially the minimum number k; such that the items can be partitioned into bundles and the items in each bundle can be packed into no more than &y bins. The definition of MMS, gives MMS. 2
s.(M)) for all i E N.
d
We say an item Ej E M is large for an agent if the size of e, to i exceeds half of the capacity of i's bins, i.e., 81, > 5: otherwise, we say G, is small for i. Let H, denote the set of i's large
items in M, and L, denote the set of i's small items; that is, H, = {e; E M Si 2 } and
L, = (e, E M Si,j I }. Since two large items cannot be put together into the same bin, the number of each agent i's large items is at most MMS. d: that is, HH < MMS; d.
We apply a widely-used reduction 13 28 restrict our attention on identical ordering (IDO) instances where $;, 2 ... 2 Si.m for all i. Specifically, it means that any algorithm that ensures a-approximate I-out-of-d MMS allocations for IDO instances can be converted to compute a- approximate i-out-of-d MMS allocations for general instances. The reduction may not work for all subadditive costs, but we prove in Appendix that it does work for the bin packing and job scheduling settings. Therefore, for these two settings, we only consider IDO instances.
4.2 Algorithm
Next, we elaborate on the algorithm that proves Theorem
Theorem 3 A 1-out-off MMS allocation always exists for any bin packing instance.
Let d d - In a nutshell, our algorithm consists of two parts: in the first part, partition the items into bundles second part, for each of the d bundles and each of the agents selected for it, we present imaginary assignment of the items in the bundle to the bins of the agent. These imaginary assignments are used to guide the allocation of the items to the agents, such that each agent receives cost more than her l-out-of-d MMS.
bag-filling fashion and select one or two agents for each bundle. In the
4.2.1 Part 1: partitioning the items into d bundles
The algorithm in the first part is formally presented in Algorithm which runs in d rounds of bag initialization (Steps 5 to 8) and bag filling (Steps 12 to 18). For each round j E [d]. we define candidate agents- those who think the size of the bag B, is not large enough and have unallocated small items (Step Note that the set of candidate agents changes with the items in the bag and the
Note that although the value of (S) also depends on to simplify the notations, we let the subscript i absorb e and neglect extra parameter in vz(-).

---

unallocated items. In the bag initialization procedure, we put into the bag the item ej and the items every d items after e; (i.e., Ej+d; cj+2d....) as long as they have not been allocated and are large for at least one remaining agent. We select one such agent. After the bag initialization procedure, if there at most one candidate agent, the round ends and the candidate agent (if exists and has not been selected) is added as another selected agent. Otherwise, we enter the bag filling procedure.
In the bag filling procedure, as long as there exist least candidate agents, we let two of them be the selected agents and put the smallest unallocated item into the bag. If there is at most one candidate agent after the smallest item is put into the bag. the round ends and the only candidate agent (if exists and has not been selected) replaces one of the selected agents.
Algorithm 2 Partitioning the items into d bundles.
Input: An IDO bin packing instance (., M. (uiEEN, (sshieN)
Output: A d-partition of the items B (Bi...., Ba) and disjoint sets of selected agents G = (G....., ,,a).
1: Initialize L; &- {ez E : sij S 3 } for each i N, and R + M.
2: for to d do
3: Initialize Bj f 0, G5 t 0, t
4: N(B,) + {i E N: (B,) S (. and L2 n R 0). // Candidate agents
5: while & E R and there exists an agent i E N who thinks e, is large do
6: B, B, U fe,), R t R fe), t ++d.
7:
G, (i).
8:
end while
9:
if (IN(),)) = and N(B)) + G, then
10:
Pick E ((B)). ) G2 G-G (i).
11:
end if
while (B,B) 2 do
13:
Pick i, i2 E (B3), Gj + i2)
Pick the smallest item e E R, Bj + + B, R R (c).
15:
if [B,)
and (B,) & G, then Pick E (B,) and replace one arbitrary agent in Gy with agent i.
17: end if
end while
19:
N +- N Gj-
20:
end for
The way we establish the bag and select the agents makes the following two important properties satisfied for every round j E [d].
Property 1: for each selected agent E Gj, there are at most MMS, items in Bj that large for i. Besides, letting ej be the item lastly added to Bj. if ež is small for i, then (B (eg1) = e(())
Property 2: for each remaining agent i' (i.c., i' & Uveb] Gi), either sB, 2v (M) no unallocated item is small for at the end of round j. Besides, no item in fe,, Cjtd, that is large for i' remains unallocated at the end of round j.
Proof. For the first property, observe that large items added into the bag only in the bag initialization procedure, where one out of every d items is picked. Since there most d MMS, large items for every agent the bag contains at most MMS) of i's large items. There where ej is small for an agent i E Gj. First, i is the only candidate agent after ež is added, for which case, we have sBBB)) < sM(M) Second, is one of the two selected candidate agents before eğ is d
cases
added, for which case, we have BB {e5)) < sa(a)) In both cases, 8; (B {et)) S s((M) holds. The second property is quite direct by the algorithm, since there is no candidate agent outside G, at the end of round j (i.e., N(,) G, = 0), and all unallocated large items in {ey, Cjtd:...) are put into the bag in the bag initialization procedure.
d
7

---

Property ensures that the items in each bundle B, E B can be allocated to the selected agents in Gj, such that each agent E G3 can use more than MMS, bins to pack all the items allocated to her, which will be shown in the following part. Property 2 ensures the following claim.
Claim All the items can be allocated in Algorithm 2
Observe that when the last round begins, there are at least (- (d-1)) 1)-2 2 remaining agents. If all the unallocated items are large for some remaining agent, all of them are added into the bag during the bag initialization procedure of the last round and thus no item remains unallocated. Now consider the case where some unallocated item is small for any remaining agent. By Property 2, for any J (d - 1] and any remaining agent i', we have sy (B,))> Sx(M0) This gives that the total size of the unallocated items to i' is smaller than M,( Besides, after the bag initialization procedure of the last round, no large item remains and every remaining item is small for any remaining agent. Combining these two facts, we know that there are always at least 2 candidate agents and thus all small items can be allocated in the bag filling procedure, which completes the proof.
Proof.
d
4.2.2 Part 2: Allocating the items to the agents
Next, we allocate the items in each bundle B, E B to the selected agents in Gy. Let i be any agent in Gj and By Bj {e)) } where eţ is the item lastly added to By. We first imaginatively assign the items in B' to i's bins as illustrated by Figure 1 We first put i's large items in B'J into individual empty bins. Then we greedily put into the bins the remaining small items in B' in decreasing order of their sizes, as long as the total size of the assigned items does not exceed the bin's capacity. The first time when the total size exceeds the capacity, with large items are filled, we move to an empty bin). We call the item lastly added to each bin that makes the total size exceed the capacity an extra item. Denote by (B,) the of extra items and by (B) = B3 (B,) the other items in B'. Extra items (B))
move the next bin and so on (if all the bins
G
C2
Bundle:
Bundle:
Scheduling the large items
Scheduuiig the small items
Lange item
Small Iteen
Figure 1:
Imaginary assignment of B' to agent i's bins
If all items in By are large for some agent E Gj. we allocate all of them to i. Otherwise, we know that round j enters the bag filling procedure, thus there are two agents in Gj and the last item e is small for both of them. Letting i be the agent who has more large items in B, and is be the other agent, we allocate i the items in W,, (B)) and allocate ig the items in Jr, (B)) U {e5}.
Now are ready to prove Theorem
Proof of Theorem 3 Consider any round j [d]. all items in By are large for some agent E Gj. by Property 1, we know that there are at most MMS; items in By. Thus can pack all items B3 using no more than MMS. bins.
For the other case, recall that the agent i Gj who has more large items in B, receives the items in W., (B'). and the other agent i2 receives the items in Jr, (B²) U {ez}. We first discuss agent i1. By Property 1, we know that for each agent {ii, i2). there are at most MMS, large items in BY and sx (B²) < d These two facts imply that the imaginative assignment of BJ, to é,, no *,, (M) contradiction.
sz(M)
more than MMS;, bins are used. Since otherwise, s;, (B)) > MMS,, C,, 2 Therefore, i can pack all items in W., (B)) using no more than MMS, bins.
d
Next we discuss agent 12. Observe that in the imaginary assignment of BJ, to it for each extra item in Jr, (B'), there exists another item in the same bin with larger size. Therefore, we have
8

---

Algorithm 3 Computing 2-MMS allocations for the bin packing setting
Input: An IDO bin packing instance (N, M, (Vi {Si)ieN). Output: An allocation A = (A Aa) such that 0z (A( S 2 MMS; for all i N.
1: Initialize R <- M.
2: for j = to n do
3: Initialize B, 5- 0. t j. an arbitrary agent in N.
4: while & E R and there exists an agent i N who thinks e, is large do
5: Bj B, U fes), R + R fa), -t..
6: ++i. i.
7:
end while
while there exists an agent i E N that satisfies 8: si, S s((M) and Lg n R + +00 do
8:
9:
k -.i.
10: Pick the smallest item e E R, By < B3 U (c). R R (e).
11: end while
12: A& + By, N t N {k}.
end for
812 (J,, (BB)) St (B))
Combining with the fact that there are at most MMS large items in Bj for i2, we know that i2 can use no more than MMS, bins to pack all items in Jr, (B') and there exists one bin with at least half the capacity not occupied. Since otherwise, si, (Ji, (B))) > (M, a contradiction. Recall that the last item eğ is small for i2, it can be put into MMS; 2 2 2d
Eig (M)
2d
the bin that has enough unoccupied capacity. Therefore, i2 can also pack all items in Jr. (B)) U {ej}
using most MMS,, bins, which completes the proof.
For the multiplicative relaxation of MMS, by Theorem and Observation | guaranteed. Actually, we can slightly modify Algorithm to compute 2-MMS allocation.
MMSS allocation
Corollary 2-MMS allocation always exists for any bin packing instance.
Proof. To compute 2-MMS allocation, we replace the value of d with n in Algorithm 2 and select only one agent in each round who receives the bag in that round. The modified algorithm is formally presented Algorithm 3 Following the same reasonings in Parts and (i.e., Subsubsections
4.2.1 and 4.2.2p. it is not hard to see that all items can be allocated in Algorithm 3 and for any i EEN, N, there are at most MMS; large items in A,. Besides, if the last item et is small for we have s,A,, {{()) < (.(M), Again, in the imaginary assignment of A, \ {ee} to i, no more than MMS; bins are used and at least one of them does not have an extra item. Therefore, agent can
use MMS; bins to pack all items in W(AA; {e))) and another MMS; bins to pack all items in (A, (ee1) {e?), which completes the proof.
In Appendix D.2 we show that the above multiplicative ratio is actually tight in the sense that there exists an instance where allocation is better than 2-MMS. Besides, in Appendix D.3] show that the al algorithm that proves Corollary 2 actually computes an allocation where every agent can use at most 3 MMS, + bins to pack all the items allocated to her.
Job scheduling setting
The second setting encodes job scheduling problem where the items jobs that need to be processed by the agents. Each item Ej E M has a size s,,j 2 to each agent i N, and for a set of items 5 C M, s, (S) Eeyes Si.j- As the bin packing setting, we only consider IDO instances N exclusively controls
of k; machines P. = [k:] with possibly different speed Pt.: for each I E P. Without loss of generality, we assume Pt,1 2 Pt,k. Upon receiving set of items S M. agent i's cost vy(S) the minimum completion time of processing S using her own machines P. (i.c., the makespan of P.). Formally,
where 81,1
8t,m for all i. Each agent
Ee,eh 8i,
(x(S) (T Th, Jem, ( (S) [E[ka]
min
max
Pi.

---

Note that the computation of (S) is NP-hard if k; 2 2. For any two sets S1 and S2, (51 U U2) - (s(()) + (S2) since the makespan of scheduling Si U. is larger than the sum of the makespans of scheduling S1 and S2 separately, thus (4(+) is subadditive.
Regarding the value of MMS intuitively, it is obtained by partitioning the items into d K2 bundles, and allocating them to k; different types of machines (with possibly different speeds) where each type has d identical machines so that the makespan is minimized Note that when each agent controls a single machine, i.e., k; = 1 for all i, the problem degenerates the additive cost case, and thus the job scheduling setting strictly generalizes the additive setting.
For the job scheduling setting, we have the following two main results.
Theorem 4 A lfout-of-
[ MMS allocation always exists for any job scheduling instance.
Corollary 3 A 2-MMS allocation always exists for any job scheduling instance.
Note that simply partitioning the items into n bundles in round-robin fashion does not guarantee I-out-of- |]] MMS even for the simpler additive cost setting. Consider an instance where there are four identical agents and five items with costs 4, 1, I, 1, 1, respectively. For this instance, the value of I-out-of-[
[
[ MMS for each agent is 4 as the 1-out-of-2 MMS defining partition is {{4), (1, 1, 1, 1}}- However, the round-robin algorithm allocates two items with costs 4 and to agent, who receives a cost more than her lfout-of-d MMS. Our algorithm overcomes this problem by first partitioning the ] bundles and then carefully allocating the items in each bundle to two agents.
items into
Let d = -. For each agent i E N and each machine E P., let C1 = Pa.s MMS denote l's capacity. In nutshell, our algorithm consists of three parts: in the first part, we partition all items into d bundles in a round-robin fashion. In the second part, for each of the bundles and each agent, we present an imaginary assignment of the items in the bundle to the agent's 's machines. These imaginary assignments are used in the third part to guide the allocation of the items in each of the bundles to two agents, such that each agent can assign her allocated items to her machines in a way that the total workload on each machine does not exceed its capacity (in other words, each agent's 's cost is no more than her louut-of-d MMS). We defer the detailed algorithms and proofs to Appendix B
6 Conclusion
In this work, we study fair allocation of indivisible chores when the costs are beyond additive and the fairness is measured by MMS. There many open problems and further directions. First, there only existential results for min(n, [log m] J-MM allocations in the general subadditive cost setting and l-out-offL MMS allocations in the job scheduling setting. Polynomial-time algorithms that achieve the same results remain as open problems. Second, for the general subadditive cost setting and the bin packing setting, we provide the tight approximation ratios, but for the job scheduling setting, we only have a lower bound of 14 immediate direction to design better approximation algorithms or lower bound instances for the job scheduling setting. Third, in the appendix, we show that for the bin packing setting, there exists an allocation where every agent's cost is no more than times her MMS plus 1. We suspect that the multiplicative factor can be improved to 1. Fourth, for the job scheduling setting, we restrict us on the case of related machines in the current work, is interesting to consider the general model of unrelated machines. As we have mentioned, the notion of collective maximin share fairness in the job scheduling setting can be viewed as a group-wise faimesss notion, which could be of independent interest. Finally, we can investigate other combinatorial costs that can better characterize worldw problems.
43 which is inherited from the additive cost setting [20]. One
Acknowledgement
The authors are ordered alphabetically. This work is funded by NSFC under Grant No. 62102333, HKSAR RGC under Grant No. PolyU 25211321, and CCa-Huawei Populus Grove Fund.
'e provide another interpretation in Appendix E.1 which shows that the job scheduling setting uncovers new research directions for group-wise fairness.
10

---

References
[1] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, 13(4):52:1-52:228 2017.
[2] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci., 841:
2020.
[3] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsika, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: A survey. CoRR, fbs/2208.08782, 2022.
[4] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. Algorithms for max-min share fair allocation of indivisible chores. In AAAI, pages 335-341. AAAI Press, 2017.
[5] Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. Fair allocation through competitive cquilibrium from generic incomes. In FAT, page 180. ACM, 2019.
[6] Siddharth Barman and Sanath Kumar Krishnamurthy, Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 8(1):511-5:28, 2020.
[7] Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, and Yadati Narahari. Group- wise maximin fair allocation of indivisible goods. In AAAI, pages 917-924. AAAI Press, 2018.
[8] Siddharth Barman, Arindam Khan, Sudarshan Shyam, and K. V. N. Sreenivas. Finding fair AAAI Press, 2023.
allocations under budget constraints. In AAAI, pages
[9] Siddharth Barman, Arindam Khan, Sudarshan Shyam, and K. V. N. Sreenivas. Guaranteeing envy-freenese under generalized assignment constraints. In EC, pages 242 269. ACM, 2023.
[10] Siddharth Barman, Vishnu V. Narayan, and Paritosh Verma. Fair chore division under binary supermodular costs. CoRR, abs/2302. 11530, 2023.
[11] Umang Bhaskar, R. Sricharan, and Rohit Vaish. On approximate envy- for indivisible chores and mixed resources, In Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
volume 207 of LIPIcs, pages 1:1-1:23.
[12] Jeff A. Bilmes. Submodularity in machine learning and artificial intelligence. abs/2202.001.22, 2022.
CoRR,
[13] Sylvain Bouveret and Michel Lemaûtre. Characterizing conflicts in fair division of indivisible goods using scale of criteria. Auton. Agents Multi Agent Syst, 30(2):259-22)) 2900, 2016.
[14] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 1966))1011-1103, 201
[15] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput., 7(3): 2019.
[16] Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. Maximin-aware allocations of indivisible goods. In IJCAI, pages 137-143. ijcai.org, 2019.
[17] Edward G Coffman, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of combinatorial optimization, pages 455-531. 2013.
[18] Graham Cormode. Data sketching. Commun. ACM, 60(9):48-55 2017.
[19] Amitay Dror, Michal Feldman, and Erel Segal-Halevi. On fair division under heterogeneous matroid constraints. J. Artif. Intell, Res., 76:567-611, 2023.

---

[20] Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In WINE, volume 13112 of Lecture Notes in Computer Science, pages 355-372. Springer, 2021.
[21] Jiarui Gan, Bo Li, and Xiaowei Wu. Approximation algorithm for computing budget-feasible EFI allocations. In AAMAS, pages 170-178. ACM, 2023.
[22] Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. Artif. Intell., 300: 2021.
[23] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvement. Math. Oper. Res., 46(3): 1038-1053, 2021.
[24] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Beyond additive valuations. Artif. Intell., 303: 103633, 2022.
[25] Sönke Hartmann and Dirk Briskorn. An updated survey of variants and extensions of the essource-constraing project scheduling problem. European Journal of operational research, 197(1):1-14, 2022.
[26] Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. Ordinal maximin share approximation for chores. In AAMAS, pages 597-605. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2022.
[27] Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. Ordinal maximin share approximation for goods. J. Artif. Intell. Res., 74, 2022.
[28] Xin Huang and Pinyan Lu. An algorithmic framework for approximating maximin share allocation of chores. In EC, pages 630-631. ACM, 2021.
[29] Xin Huang and Erel Segal-Halevi A reduction from chores allocation to job scheduling. CoRR, abs/2302.04581. 2023.
[30] Halvard Hummel and Magnus Lie Hetland. Fair allocation of conflicting items. Auton. Agents Multi Agent Syst. 36(1):8, 2022.
[31] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? In AAAI, pages 523-529. AAAÍ Press, 2016.
[32] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approxi- mate maximin shares. J. ACM, 65(2):8:1-8:2) 2018.
[33] Bo Li, Minming Li, and Ruilong Zhang. Fair scheduling for time-dependent resources. In NeurlPS, pages 21744-21756, 2021.
[34] Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In WWW, pages 122-131. ACM, 2022.
[35] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In EC, pages 125-131. ACM, 2004.
[36] Gaëlle Loosli and Stéphane Canu. Comments on the "core vector machines: Fast SVM training on very large data sets". J. Mach. Learn. Res., 8:291-301, 2007.
[37] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed sub- modular maximization: Identifying representative elements in massive data. In NIPS, pages 2049-2057, 2013.
[38] Hervé Moulin. Fair division in the age of internet. Annu. Rev. Econ., 2018.
[39] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM Discret. Math., 1432):1039-1066 2020.
12

---

[40] Masoud Seddighin and Saeed Seddighin. Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem. AAAL, pages 5183-5190. AAAI Press, 2022.
[41] Edward Lloyd Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. In NIPS, pages 1257-1264, 2005.
[42] Shengwei Zhou and Xiaowei Wu. Approximately EFX allocations for indivisible chores. CoRR, abs/2109.07313. 2021.
13

---

Appendix
A
because it More related works
Besides proportionality, in another parallel line of research, envy-freeness and its relaxations, namely envy-free up to one item (EF1) and envy-free up to any item (EFX), are also widely studied. was shown (35) and [TT] for goods and chores, respectively, that an EFI allocation exists for the monotone combinatorial functions. However, the existence of EFX allocations is still unknown even with additive functions. Therefore, approximation algorithms were proposed in 42 for additive functions and in 39 [6] for subadditive functions. We refer the readers to 3 for detailed survey on fair allocation of indivisible items.
B Missing materials in preliminaries
B.1 Impossibility result for general cost functions
We provide an example to show that no bounded approximation ratio can be achieved for general cost functions. Note that there exist simpler examples, but choose the following
represents a particular combinatorial structure minimum spanning tree. Let G = (V, E)) be a graph shown in the left sub-figure of Figure where the vertices V are the items that are to be allocated, i.e, M V. There are two agents N (1,2) who have different weights on the edges as shown in the middle and right sub-figures of Figure The cost functions
measured by the minimum spanning tree in their received subgraphs. Particularly, for any S C V, 4; (S) equals the weight of under agent i's weights. Thus, MMS; O, for both i = 1, 2, where an MMS defining partition for agent is {v), 02) and {v3, 3 and that for agent 2 {vi, v4 and {v2, va). However,
the minimum spanning tree on G[S] the induced subgraph of S in G
be verified that matter how the vertices are allocated to the agents, there is one agent whose cost is at least 1, which implies that
no bounded approximation is possible for general costs.
V1
1/2
P1
122
2
12
1
V4
V3
14
V/
1
G = EV,
Agent I'ss weights
Agent 2's weights
Figure 2: An instance with unbounded approximation ratio
B.2 Proof of Observation
To prove the observation, suffices show MMS/ [ MMS, for any agent i E N. Let X = (X1...., Xx) be an MMS defining partition for agent which satisfies vx(X, < MMS, for every j E [n]. Consider d-partition X' (Xi... .x....... X,)) built by evenly distributing the bundles in X to the bundles in X'; that is, the number of bundles distributed to the bundles in X' differs by at most one. Clearly, X' satisfies vi vx()) S [2] MMS, for every j [d]. By the definition of o-out-of-d MMS, it follows that
MMS < max u S 1 MMS,,
jE(d]
thus completing the proof.
14

---

2
x
3
Agent
Agent 2
Agent
Figure 3: An instance with 3 agents and 27 items
C Missing materials in general subadditive cost setting
C.1 An example that helps understand Theorem
The example is illustrated in Figure where each agent has three covering planes. Take agent 1 for example, her three covering planes contain the items whose z coordinates are 1, 2, 3. respectively. If there exists an allocation that is better than 3-MMS, then each agent is allocated items from at most 2 of her covering planes. Without loss of generality, we assume that agent 1 (or agents 2 and respectively) is not allocated any item whose x (or y and z respectively) coordinate is 1. Then, the item (1, 1, is not allocated to any agent, contradiction.
C.2 Proof of Corollary
consider the same instance that is designed in Theorem [ In this instance, we have proved that no matter how the items are allocated among the agents, there is at least one agent, say i, whose cost is Moreover, by the design of the cost functions, for any integer d, it can be observed that MMS. = [ Note that a is always smaller than n for all 2 2, thus the allocation is not 1-out-of-d MMS to i.
D Missing materials in bin packing setting
D.1 The IDO reduction
For bin packing or job scheduling instance I, the IDO instance I' is constructed by setting the size of each item e, E MM to each agent i N in I' to the j-th largest size of the items to i in I. Then the IDO reduction is formally presented in the following lemma.
Lemma For the bin packing or job scheduling setting. if there exists an allocation A' (A....., A.,) in the IDO instance I' such that (a((()) S a MM) for all E N, then there exists an allocation A (AI...., And in the original instance I such that v,(A,) S a MMS; for all i E N.
Proof. We design Algorithm 4 that given I, I' and A', computes the desired allocation A. In the algorithm, we look at the items from em to e1. For each item, we let the agent who receives l' pick her smallest unallocated item in
To prove the lemma, first show that (A,)) (A,) for all e N. Consider the iteration where we look at the item eg. We suppose that in this iteration agent i picks item ey;; that is, ey E A, eg' A, and eg' is the smallest unallocated item for i. Since an item is removed from the R after it is allocated, exactly m g items have been allocated before eg' is allocated. Therefore, eg' among the top m g + smallest items for agent Recall that cy is the item with the exactly (m + 1) smallest size to i, hence Si.g' S S.'.g The same reasoning can be applied to other items in A/ and A,, and to other agents. It follows that for any i E N, any eg A and the corresponding eg' E A,, 8i.g' S 8/..-- For the bin packing or job scheduling setting, this implies uy (A,) S (A().. Since the maximin share depends the sizes of the items but not the order, the maximin share
15

---

of agent i in I' is the same as that in I. i.e., (T) = MT) (A() S a (M') gives vs (A.) - a MMS; (1), which completes the proof.
Hence, the condition that
Algorithm 4 IDO reduction for the bin packing and job scheduling settings Input: A general instance I, the IDO instance I' and an allocation A' = (A()-., A22) for the IDO instance such that (A)) I o MMS, for all i E N. Output: An allocation A (A1,..., A,,) such that (A,)) a (IMS for all i N.
1: For all i N and eg A/, set Ps +-.
2: Initialize A; + for all i E N, and R + M.
3: for g m do
4: Pick Eg' arg m (fp.
5: Ap, +- AA, U (eg), , &- R {
6: end for
D.2 Lower bound instance
We present an instance for the bin packing setting where no allocation can better than 2-MMS. We first recall the impossibility instance given by Feige et al. [20]. In this instance there are three agents and nine items as arranged in a three by three matrix. The three agents' costs are shown the matrices V1, 1/2 and Vg.
6
15
22
6
15
23
V
26
10
1/2
26
10
8
12
19
12
11
18
12
6
16
22
1/3
10
11
18
12
Feige et al. [20) 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 cost no smaller than 44.
We can adapt this instance to the bin packing setting and obtain lower bound of 2. In particular, we also have three agents and nine items. The numbers in matrices V1, 1/2 and V/3 are the sizes of the items to agents 1, 2 and 3, respectively. Let the capacities of the bins be c; 43 for all i E {1, 3}. Accordingly, we have MMS,
for all E {1, 2, 3). Since in any allocation, there at least one agent who gets items with total size smaller than 44, for this agent, she has to use two bins pack the assigned items, which means that no allocation can be better than 2-MMS.
D.3 Computing MMS + allocations
Recall that in the proof of Corollary 2 it has been shown that each agent E N can use MMS, bins to pack all items in W (AA,)) {ee }) and another MMS, bins to pack all items in JA {ef)) {ef}: Actually, since all items JA(A; [e")) {e]} are small for i and at least two small items can be Therefore, each agent i can use no more than MMS; + bins to pack all the items allocated to her.
put into one bin, only needs MMS;" bins to pack all items (A, \.
2
E
Missing materials in job scheduling setting
E.1
Another interpretation to the job scheduling setting
An alternative way to explain the job scheduling setting is to view each agent as a group of k; small agents and MMS? as the collective maximin share for these k; small agents. We believe this notion of collective maximin share is of independent interest as a group-wise fairness notion. We remark that this notion is different from the group-wise (and pair-wise) maximin share defined in 7 and [55, where the max-min max-min value defined for each single agent. In our definition, however, set of agents share the same value for the items allocated to them.
16

---

E.2
Algorithm
E.2.1 Part 1: partitioning the items into d bundles
We first partition the items into d bundles B (BI..... B2) in round-robin fashion. Specifically, we allocate the items in descending order of their sizes to the bundles by turns, from the first bundle to the last one. Each time, we allocate one item one bundle, and when every bundle receives an item, we start over from the first bundle and so on. For any set of items S, let S' be the /-th largest item in S, then algorithm formally presented Algorithm
Algorithm& 5 Partitioning the items into d bundles
Input: An IDO job scheduling instance (N, M, (uiJiENs (silie))
Output: A d-partition of M: B (Bi,..., Ba)-
1: Initialize B3 / for every [d]. and t-
2: while r I m do
3: for j= to do
4: i S m then
5: By +- B, (M[r).
6:
r+r+l.
7:
end if
8: end for
9:
end while
By the characteristic of the round-robin fashion, we have the following important observation.
Observation 2 For each bundle B5 E B and each item ex E B₁ \. (B (if exists),, the d items before ek (i.e., items eg-1, Ck-2; ....... Ck Ck-d-1 d-1) 1-) have least the sizes ek-
E.2.2 Part 2: imaginary assignment
Next, for each bundle B, E B computed in the first part and each agent E N, we imaginativelyy assign the items in B, \ BB[L] [1] i's machines follows. We greedily assign the items with larger sizes to i's machines with faster speeds (in other words, with larger capacities), as long as the total workload exceeds the capacity, we move to the next machine and so on. The algorithm is formally presented in Algorithm 6 and illustrated in Figure 4 For each E P., C/2, contains the items imaginatively assigned to machine that do not make the total workload exceed I's capacity, and f, is the last item assigned to that makes the total workload exceed the capacity. Note that C₁ may be empty and t4,1 may be null. For simplicity, let &,,0 B,[1]; that is, B, [1] is assigned an imaginary machine 0. The items in Ure[s.] C22, called internal items (as shown by the dark boxes in Figure 4) and } are called external items (as shown by the light boxes).
machine does not exceed the its capacity. The first time when the workload
(fr......, 1..
Algorithm 6 Imaginary assignment
Input: bundle B, B computed in the first part and an agent N. Output: Sets of internal items {C/, C/,,A and external items (ti,o....,
Initialize C
0. f4, t- null for every I [ks], and <- 1.
2: while r < | do
3: for l = to k; do
4:
4,1-1 <~ By(r), r +
5: while r < [Byl and (C C (B,()) s c..1 do
6:
C/21 - C
7: end while
8: end for
9:
end while
For each bundle B, E B and each agent i N, the imaginary assignment has the following important properties.
17

---

b,1
C1
14.2
C2
4,0
C
C,
C
C
Machine:
k;
Figure 4: The imaginary assignment of B3 to agent i
Property 1: all items in By \ {B,[1}} can be assigned to agent i's machines. Besides, the last machine k; does not have an external item; that is, tik. is null.
Property 2: for any 1 S 1 k4, the total size of the internal items C₁₁,, does not exceed the capacity of machine 1, i.e., s;(C S G1
Property 3: for any < I k; the external item f4111 (if not null) has size no larger than the capacity of machine 1, i.e., 8; (tt, S C...
Proof. The first property holds since otherwise, sBBB) \ (B,[I)] > EvERRal Cta. By Observation 2 it follows that
s (MMM) d- s; (BJ > d-
Σ
[E[R:]
However, since all items can be assigned to i's machines in i's 1-out-of-d MMS defining partition, we have (M) S d. ElE[ka] C.t. contradiction.
The second property directly follows the algorithm. For the third property, 8;(1,,0) S G,1 follows two facts that 12,0 is assigned to some machine in i's 1-out-of-d MMS defining partition and Ca the largest capacity the machines. We then consider ( E [k2 - 1] and show s, (t,,)) S C,1+1 (if ti is not null). The same reasoning can be applied to any other (' E [k 1]. Let S1 = Upeny (CL,p U ((i,p)). From the algorithm, we know that 8; (Si) Epe[j Cipp and 4. is the smallest item in St. By Observation 2, there exist another d 1 disjoint sets of items {S2..... Sa) such that (S²) 2 s((S for every & E [2, d] and 4, is also the smallest item in UNEld Sk. Hence, Exe(a (S() > d. E.Epen C.p- This implies that in i's l-out-of-d MMS defining partition, least one item in Uke[oj S4 assigned to machine p / + Combining with the fact that tú is the smallest item UkE[aj Sy. we have st(,t,) S Cr,+11
By these properties, for each machine E P.. we can assign either the internal items C₁ or the external item 4, to I, such that its completion time does not exceed MMS; This intuition guides the allocation of the items to the agents in the following part.
E.2.3 Part 3: allocating the items to the agents
Lastly, for any bundle B, E B, we arbitrarily choose two agents i,, i2 items in B, as formally described in Algorithm Recall that in the imaginary assignment of B; to each agent E {81, 82,, the items in B, are divided into internal items Ute(k.] C and external items (tr,o...., 3. Let E = {ei..... ((e)) contain all external items shared by i and iz. Note that ej = t,,00 = t, We allocate the items in B, to agents i and in in E rounds. In each round q E [[]], we first find the machines of i and ig which the shared external items eg and e assigned (denoted by 4,, 12, lg and l22 respectively. If q [E, simply let I k, and '22 kzg)). We then find the agent é E {11, iz) whose machine 4 + 1 has more internal items. We allocate it her internal items from machine 4 + 1 to machine K-- and allocate the other agent in 's external items from machine 4 to machine 1/2 1.
N and allocate them the
Since 2 2dd= = 2 1 S no more than agents are needed to allocate all items. Thus to prove Theorem 4 it remains to show that each agent can assign her allocated items to her machines such that the total workload on each of the machines does not exceed its capacity.
18

---

Algorithm/ 7 Allocating the items to the agents
Input: A d-partition of the items B (Bi...., Ba) returned by Algorithm
Output: allocation A = -A1,...;AA, An) such that oz (A())) MMS, for i E N. 1: Initialize A, + for every i E N.
2: for 1 to d do
3: Arbitrarily choose 2 agents i1, E N.N,NG + (61.2))
4: {C], (0.........0 C,,,,, 1. (ti,,0.......... Ai f- Algorithm 6 Bj. i1).
5: {C (2.1....... C ki b (tig,u,. Ui.., kag f- Algorithm 6 Bj. 12).
6: < (4i,00.-..,44 du,
light, )- Re-label E t Gg. // Shared
external items by d1 and i2
7:
for to E do
8:
Find 1 [0, kg and l/ E [0, kig] such that eng 11.11 122.22
9:
q < [B| then
10:
Find 1/ E ki, and 12 E [0, Kig] such that c 1i liails
11:
else
12:
In = ki and 1/2 kig-
13:
end if
14:
if IC 1h,++ 2 IC matt then
AG, U C Aig +- U lid.
else
Aig + - Ulzt C Ai t UL--1 ligd
18: end if
19: end for
20:
end for
Proof of Theorem Consider any bundle B, B and assume the two chosen agents are i1, i2 E N. We first look at the first round of the process of allocating the items in By i and iz. Without loss of generality, assume that the first machine of i contains more internal items than that of iz, i... C², 2 C² From the algorithm, the items i takes are U Ch By the second property of the imaginary assignment, these items can be assigned to the first machines of i such that the total workload on each machine does not exceed its capacity. Besides, the items i2 takes are U'i-5' by,t, which are ei and a subset of C% By the second and third properties of the imaginary assignment, these items can be assigned to the first i2 machines of i2 such that the total workload each machine does exceed its capacity. The same reasoning can be applied to all following rounds. By induction, it follows that both i and i2 can assign their allocated items to their machines such that the total workload each machine does not exceed its capacity. This means that both i and i receive costs no more than their l-out-of-d MMS, which completes the proof.
For the multiplicative relaxation of MMS, by Theorem 4 and Observation guaranteed. As the bin packing setting, after slight modification, Algorithm computes a 2-MMS allocation, which is better than 1-MS.
1-MMS allocation
Proof of Corollary 3] We show that by replacing the value of d with n, Algorithm 5 coomputes 2-MMS allocation. Particularly, in the new version of Algorithm we partition the items in M into bundles in round-robin fashion and allocate each of the bundles to agent in N. By the properties of the imaginary assignment, for each agent, the makespan of processing either the internal items the external items in her bundle using her machines does exceed MMS," This implies that for each agent, the cost of her bundle does not exceed 2 MMS,, which completes the proof.
F Proportionality up to one or any item
We now discuss two other relaxations for proportionality, i.e., proportional up to one item (PROPI) and proportional up to any item (PROPX), which also widely studied for additive costs.
19

---

Definition 2 (a-PROPI and a-PROPX) An allocation A (A A.) is a-approximate pro- portional up one item (a-PROPI) (.(AAee)) S a- 2x(M) for all agents E N and some item E Ag. It is a-approximate proportional up to any item (a-PROPX) if v. (A.M)))) I a r.(M) for all agents E N and any item e A, The allocation PROPI or PROPX if a =
is easy to see that a PROPX allocation is also PROPI. Although exact PROPX or PROPI allocations are guaranteed to exist for additive costs, when the costs are subadditive, no algorithm can be better than n-PROP1 or n-PROPX. Consider an instance with n agents and n + items. The cost function is (S( for all agents E N and any non-empty subset S S M. Clearly, the cost function subadditive since (5( + by (T) 2 (, TT) for any S. C M. By the pigeonhole principle, at least one agent i receives two more items in any allocation of M. After removing any item
E Ai, A, is still empty. That is, (Ai Me)) = n Ms(M] for any E Aj. This example can be easily extended to the bin packing and job scheduling settings, and thus we have the following theorem.
Theorem For the bin packing and job scheduling settings, no algorithm performs beller than n-PROPI or n-PROPX.
Proof. For the bin packing setting, consider an instance with n agents and n + 1 items. The capacity of each agent's bins is 1, i.e, G for all N. Each item is very tiny that every agent pack all items in just one bin, e.g., $i,j n+1 for any E and ej E M. Therefore, we have (y(M) = and PROP; " or more items in any allocation of M. After removing any item E A,, agent still needs one bin to PROP, for any E A;-
1 for each agent N. By the pigeonhole principle, at least one agent receives two
pack the remaining items. Hence, have (A(A(()) =
For the job scheduling setting, consider an instance with 2n agents and 2n + items where each agent possesses 2n machines with the same speed of and the size of each item is for every agent. can be easily seen that for every agent E N, the maximum completion time of her machines is minimized when assigning two items to one machine and one item to each of the remaining 2n 1 machines. Therefore, we have v (M) pigeonhole principle, at least one agent receives two more items in any allocation of M. This implies that (, (ee) = n PROP; for any e E Ac, thus completing the proof.
2 1 for any E N. Similarly, by the and PROP, = 2n
20


Reviews:
[{"review_id": "HEe1HAh8ZY", "reviewer": "Reviewer_MebF", "summary": "The paper studies the classical fair allocation of indivisible items setting with two twists: (1) Items correspond to *tasks* instead of *goods*, i.e., any agent would prefer receiving no item at all. (2) Valuations are not additive but may be subadditive. The paper also considers some special cases of subadditive valuations, namely, submodular, \"bin packing\", and \"scheduling\" costs. As an objective, the paper focusses on the classic notion of the maximin share (MMS). Since MMS allocations do not always exist, the paper considers both a multiplicative as well as an \"ordinal\" relaxation of the MMS notion. \n\nThe contribution of the paper is threefold (I am omitting the ordinal approximation results for simplicity): (1) For the subadditive case, the paper presents a lower bound of $\\min\\{n,log(m)/loglog(m)\\}$ as well as a mechanism providing an approximation of $\\min\\{n,\\log(m)\\}$. (2) For bin packing, the paper presents a multiplicative $2$-approximation and a tight lower bound of $2$ for any mechanism. (3) For job scheduling, the paper presents a mechanism providing a multiplicative $2$-approximation, however, without a matching lower bound.", "questions": "-  Intuitively, subadditive costs make the problem \"easier\" in the sense that allocation all tasks to one agent at least has the same approximation guarantee as in the additive case. This is certainly not the case for superadditive cost functions. Do you have any results in this direction? \n- I was missing a concrete (real-world) motivation for subadditive cost functions in the context of allocation tasks. Could you elaborate on that? ", "limitations": "The limitations of the paper are well addressed, in particular, within Section 6. Here, the paper transparently communicates all resulting open questions. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper makes significant progress within the classic setting of fair allocation of indivisible items. While this literature has been long focussed on the case of additive valuations/costs, in recent years there has been a growing body of literature studying more general valuations/costs, with the paper under review being one of these. Hence, I am optimistic that the paper will lead to follow-up work. \n- The paper develops new mechanisms that are tailored to the studied cost functions. These mechanisms and their analysis is certainly non-trivial and lead to a significant technical contribution. \n", "weaknesses": "- Since the result for the general, subadditive case is rather negative (i.e., there is no constant approximation for MMS), the main contribution of the paper is for the special cases of bin packing and scheduling. Having said this, this can hardly be seen as a critique for the paper, but rather as a sign of the challenging endeavor to study beyond additive costs. \n- I think that the writing of the paper could be improved, as I had to reread several parts of the paper. I added a list of suggestions within the minor comments. \n- Unfortunately, the newly developed mechanism is not very elegant, and one can't help but wonder whether there exists a simpler mechanism to achieve the same approximation guarantee. Also, the mechanisms do not come with a polynomial-time implementation, hence, leaving the question open whether the same guarantees can be achieved efficiently. \n\n**Minor Comments**\n- The paper uses the term \"tasks\", while a large fraction of the literature uses the term \"chores\". I would suggest to add a comment on that. \n- line 21: You mention \"functions\" without clarifying their role in the problem. (Of course this is clear for any person knowing fair allocation, but for others it may not.)\n- line 60: \"As far as we know, all the above works also assume additive costs\" - Sounds a bit weird in this context, since checking these papers should be doable. \n- line 71: \"the asymptotically tight multiplicative\" - I think it is weird to use this phrase in a theorem environment, especially since you are ignoring log-factors. I would suggest to just mention the upper and lower bounds. \n- line 99: \"Note that no bounded approximation\" - At this point, it is not clear what should be approximated. \n- Proof of theorem 1: I was very confused of the usage of the term \"covering planes\" since, as far as I understand, these objects are actually (partial) grids, i.e. finite set of points. \n- line 214: I think it would be helpful for the reader to learn about the meaning of the abbreviation \"IDO\". \n- line 228-236: I did not find the intuition for the algorithm very helpful before reading the algorithm (and even after that). I would suggest to refine this, having in mind that the reader has not read the algorithm at this point. \n- line 316: I think that $j \\in P_i$ is a bad choice for an index since here $j$ is a machine but before $j$ used to correspond to jobs/items. \n- Section 5: It would have been nice to hear some (very brief) summary of how Theorem 4 is achieved, i.e., how does the mechanism look like? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our paper’s contribution to the literature on fair allocation, as well as the technical depth and the potential to stipulate subsequent research. We also thank the reviewer for pointing out our paper’s weaknesses and offering many constructive and helpful suggestions for improving our paper.\n \nIn the following, we first answer your questions.\n \n**Question 1: on the superadditive cost functions.**\n \n**Response:** Yes, we have considered superadditive cost functions and found that no bounded approximation is possible. Let us consider a simple instance with two agents $N = \\\\{1, 2\\\\}$ and four items $M = \\\\{a, b, c, d\\\\}$. The cost functions are described below: \n- When $|S| \\le 1$, $v_i(S) = 0$ for both $i = 1$ and $2$\n- When $|S| = 2$,\n   - $v_1(\\\\{a, d\\\\}) = v_1(\\\\{b, c\\\\}) = 0$; $v_1(\\\\{a, b\\\\}) = v_1(\\\\{a, c\\\\}) = v_1(\\\\{b, d\\\\}) = v_1(\\\\{c, d\\\\}) = 1$.\n   - $v_2(\\\\{a, b\\\\}) = v_2(\\\\{c, d\\\\}) = 0$; $v_2(\\\\{a, c\\\\}) = v_2(\\\\{a, d\\\\}) = v_2(\\\\{b, c\\\\}) = v_2(\\\\{b, d\\\\}) = 1$.\n- When $|S| = 3$, $v_i(S) = 1$ for both $i = 1$ and $2$\n- When $|S| = 4$, $v_i(S) = 2$ for both $i = 1$ and $2$\n\nIt can be verified that the cost functions are superadditive. Besides, MMS$_i = 0$ for both $i = 1$ and $2$ since agent $1$ can partition the items into $\\\\{\\\\{a, d\\\\}, \\\\{b, c\\\\}\\\\}$ and agent $2$ can partition the items into $\\\\{\\\\{a, b\\\\}, \\\\{c, d\\\\}\\\\}$. However, no matter how the items are allocated to the agents, there is one agent whose cost is at least $1$.\n\nWe have included a similar example in Appendix B.1 of the manuscript.\n \n**Question 2: concrete motivation for subadditive cost functions in the context of allocating tasks**\n \n**Response:** Firstly, we can regard the job scheduling and bin packing models as two examples that motivate subadditive cost functions in the context of allocating tasks. One interpretation of the cost of a set of tasks is the time taken to complete them. Sometimes agents may be able to perform tasks in parallel, in which scenario the agents have job-scheduling cost functions. Sometimes agents have to finish tasks by a deadline and can hire processors to finish them. The cost of hiring processors equals the number of processors, in which scenario the agents have job-scheduling cost functions.\n \nSecondly, and more concretely, doing laundry and cleaning the house can be carried out simultaneously, and thus induce subadditive cost functions. Similarly, when it comes to teaching, adding more students to a class can actually result in a decrease in the marginal cost for the teacher, as the teacher only needs to prepare the teaching materials once, regardless of the number of students.\n \nNext, we respond to your comments.\n \n**Comment 1: on the inherent difficulty of the problems.**\n \n**Response:** We thank the reviewer for understanding the inherent difficulty of the problems.\n \n**Comment 2: the writing of the paper could be improved**\n \n**Response:** We thank the reviewer for pointing out this weakness and offering so many helpful suggestions for improving the writing quality. We will carefully polish our paper and address the reviewer’s concerns.\n \n**Comment 3: simpler mechanisms to achieve the same approximation guarantee**\n \n**Response:** We have tried several simpler algorithms but none of them performs well, especially for the ordinal approximation settings. For example, round-robin is a commonly-used algorithm in fair division that guarantees $2$-MMS (multiplicative approximation) for additive cost functions. However, it does not ensure $1$-out-of-$\\lfloor n/2 \\rfloor$ MMS in terms of ordinal approximations. To see this, we can consider an instance with four identical agents and five items of costs $4,1,1,1,1$. A $1$-out-of-$\\lfloor n/2 \\rfloor$ MMS defining partition is $\\\\{\\\\{4\\\\},\\\\{1,1,1,1\\\\}\\\\}$ and thus the $1$-out-of-$\\lfloor n/2 \\rfloor$ MMS equals $4$. The round-robin algorithm allocates two items with costs $4$ and $1$ to one agent, who receives a cost higher than her $1$-out-of-$2$ MMS.\n \nThis example also appears in Appendix E.2 of the manuscript."}, {"review_id": "gnp5cuDOeI", "reviewer": "Reviewer_RP1j", "summary": "The paper deals with problem of allocating indivisible chores to agents whose valuation functions for bundles of chores are subadditive or submodular, where an allocation that guarantees every agent their maximin share (MMS) may not exist. Here, an agent's maximin share is the agent's worst-case disutility from a partitioning of the items that minimizes the disutility of the worst (maximum disutility) partition. The paper provides new upper and lower bounds on the approximability of MMS allocations.\n\nI have reviewed a previous version of this paper submitted to IJCAI 23 where I was positive about the technical contributions of the paper. This revision addresses the concerns with writing and a minor technical issue raised there. The revisions have certainly helped with the readability.", "questions": "None", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem setting of subadditive and submodular (dis)utility functions is novel. \n\nThe new results for these classes of valuation functions provided is this paper are likely to be of interest to the comsoc / fair division research community.\n\nThe technical results are interesting, non-trivial and use interesting techniques that are new to me. I was able to verify the technical results.\n\nRelevant related work is well cited and discussed.", "weaknesses": "The relevance to NeurIPS for what seems a very AI/computational social choice focused paper is not clear although this is attempted in the introduction.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper again. We are pleased to hear that the reviewer acknowledges the technical contribution of our work and the improvements made in the revised manuscript. We will incorporate all reviewers’ suggestions to further enhance and refine the paper.\n \nWe understand the reviewer’s concern about the relevance of our paper to NeurIPS. We humbly offer the following justifications, hoping they will be helpful in addressing this concern. On one hand, we can see that AI/Computational Social Choice works have been increasingly welcomed at conferences such as NeurIPS and ICML in recent years. For example, a growing number of fair allocation papers have been presented at NeurIPS and ICML in recent years, e.g.,\n \n- “Fair Scheduling for Time-dependent Resources” at NeurIPS 2021\n- “Fair and Efficient Allocations Without Obvious Manipulations” at NeurIPS 2022\n-  “Multi-agent Online Scheduling: MMS Allocations for Indivisible Items” at ICML 2023\n \nOn the other hand, our paper focuses on submodular (and subadditive) functions, and these functions have significant relevance to various machine learning and optimization scenarios, as we attempted to motivate the relevance in the introduction. Thus, we think the investigation of fair division under submodular functions can contribute to NeurIPS.\n"}, {"review_id": "CdzNo2dC5Z", "reviewer": "Reviewer_AniE", "summary": "This paper studies the MMS fair allocation of combinatorial tasks (indivisible chores) problem where the cost function is submodular or subadditive. For submodular functions, they prove that no algorithm can ensure better than min{n, log m/log log m}-approximation. For more general subadditive cost functions, they prove that there always exists an allocation that is min{n , log m}-approximation MMS, which is (almost) asymptotically tight. What’s more, for ordinal relaxation, 1-out-of-d MMS, they prove that for any d≥2, there is an instance for which no allocation is 1-out-of-d MMS. Finally, the authors give two specific settings which are bin packing setting and job scheduling setting and prove that 1-out-of-[n/2] MMS allocations always exist for these two settings.", "questions": "No question.", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides solid and clean theoretical results on MMS chores allocations. It also contains some interesting techniques. For example, the author gives a quite interesting example for Theorem 1, and I also find the proof of Theorem 2 mathematically natural and complete.", "weaknesses": "I do not find any obvious weaknesses. Perhaps the relevance of this paper to machine learning is not very strong. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for the dedicated effort in reviewing our paper. We are especially appreciative of the reviewer's acknowledgment of the theoretical results and techniques presented in our paper. We also understand the reviewer’s concern about the relevance of our paper to machine learning. We humbly offer the following justifications, hoping they will be helpful in addressing this concern.\n \nOn one hand, we can see that fair division works have been increasingly welcomed at conferences such as NeurIPS and ICML in recent years. For example, a growing number of fair allocation papers have been presented at NeurIPS and ICML in recent years, e.g.,\n \n-  “Fair Scheduling for Time-dependent Resources” at NeurIPS 2021\n-  “Fair and Efficient Allocations Without Obvious Manipulations” at NeurIPS 2022\n-  “Multi-agent Online Scheduling: MMS Allocations for Indivisible Items” at ICML 2023\n \nOn the other hand, our paper focuses on submodular (and subadditive) functions, and these functions have significant relevance to various machine learning and optimization scenarios, as we attempted to motivate the relevance in the introduction. Thus, we think the investigation of fair division under submodular functions can contribute to NeurIPS.\n"}, {"review_id": "1kHYVs0c8g", "reviewer": "Reviewer_6vH3", "summary": "This paper studies the allocation of m indivisible chores among n agents with non-additive preferences. The authors show that, for the case of approximate MMS, the best approximation factor is super constant, and specifically they give a lower bound of min{n, log m/ log log m } for submodular costs, and an upper bound of min{n, log m} for subadditive costs. The lower bound also implies a negative result for 1-out-of-d MMS allocations in this setting.\nThe authors proceed to study special cases of subadditive costs, and specifically costs encoded by combinatorial problems, and namely bin-packing and job scheduling. So, for example, in the case of bin-packing, the cost for a subset of items is the minimum number of bins to pack them. For both cases, the authors give an algorithm for finding a 1-out-of-(n/2) MMS allocation.", "questions": "Have combinatorial values of this nature (and as a tool for bypassing negative results) been considered in the goods case?\n\n\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper studies an interesting, natural problem: chore allocation beyond additive costs.\n- The results are relatively complete, and the authors settle, up-to-constants, all their questions.\n", "weaknesses": "- The main algorithmic results (for bin-packing and scheduling) seem like twists to the standard approximation algorithms (e.g., Next Fit or Best Fit for bin-packing). Of course, this is expected, but these connections/insights are not explicit in the text, so it’s harder to see what’s new about this work.\n\n(Some typos:\nLine 134: “which is somehow the most unfair algorithm” -> drop “somehow”.\nLine 342: “or the job scheduling setting, we restrict us on the case”)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your appreciation of the problem we have studied and the results we have obtained. We also thank the reviewer for the constructive and helpful comments.\n \n**Question 1: combinatorial problems considered in the case of goods**\n \n**Response:** We appreciate this question and will incorporate the following discussion in the revised paper, as we consider it a compelling motivation for our research problems.\n \nWhen it comes to goods, there have been several papers that delve into concrete combinatorial problems and seek to improve approximation ratios compared to more general valuations. For instance, we draw attention to two papers [1,2] that introduce interval scheduling and independent set structures, respectively, into MMS fair allocation problems. In both cases, the induced valuation functions correspond to special cases of XoS (fractionally subadditive) functions. While a general XoS valuation guarantees an approximation ratio of 1/4.6, these two works [1,2] manage to enhance this approximation for their specific functions.\n \n[1] “Fair Scheduling for Time-dependent Resources” at NeurIPS 2021\n\n[2] “Fair Allocation of Conflicting Items” at AAMAS 2022\n\n[3] “Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem” at AAAI 2022\n \nSome other combinatorial problems that have been studied for goods include the knapsack problem and matroid constraints, e.g.,\n \n[4] “Approximation Algorithm for Computing Budget-Feasible EF1 Allocations” at AAMAS 2023\n\n[5] “Guaranteeing Envy-Freeness under Generalized Assignment Constraints” at EC 2023\n\n[6] “On fair division under heterogeneous matroid constraints” at JAIR 2023\n \n \n**Comment 1: connections with standard algorithms**\n \n**Response:** Yes, our algorithms reflect some ideas from standard algorithms (such as Next Fit), and we will make the connections and differences more explicit. Informally, in the second phase of our algorithms, we prove that we can assign each bundle obtained from the first phase to two agents without violating the MMS constraints. To prove this claim, we introduce an imaginary partition of the items, which is derived from the standard algorithms with certain modifications, such as allowing for one over-filled item. By leveraging the structural properties of this partition, we can prove our claim. In essence, the standard algorithms serve as a step within our algorithms."}]

Author rebuttal:

Meta-review: All reviewers felt that it is a solid fair division paper with solid theoretical results, though no reviewer seems to be extremely excited about them (and one reviewer commented that they are mostly based on existing techniques). Multiple reviewers raised the question about the relevance to NeurIPS as a minor issue. Given that AGT is a keyword this year, the paper will not be rejected just because of the topic; on the other hand, the decision will be made in comparison with other AGT submissions.

We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!
Decision: Accept (poster)