Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Authors: Bo Li
Fangxiao Wang
Xing Shiji
Venue: ICML 2025 poster (2025)
Keywords: Fair division
Maximin share
Job scheduling
Primary area: theory->game_theory
TL;DR: The paper studies the fair scheduling of jobs among groups of (unrelated) machines and focus on the maximin share (MMS) fairness at the group level.

Abstract: We study the fair scheduling of jobs among groups of (unrelated) machines and focus on the maximin share (MMS) fairness at the group level. 
    The problem was first introduced by Li et al. [NeurIPS 2023], where each group consists of a number of identical machines (or identical up to different speeds), and the cost of a group is determined by the minimum makespan on completing all jobs assigned to it.
    It is left as an open problem when the machines within each group are unrelated.
    In this paper, we first resolve this problem and design a polynomial-time algorithm that computes a 2-approximate MMS allocation via linear programming techniques.
    We complement this result with a hard instance, showing that no algorithm can be better than $(2-\frac{1}{n})$-approximate MMS, where $n$ is the number of machines.
    Thus the approximation ratio 2 is asymptotically tight.
    When the groups consist of identical machines, we improve the approximation ratio to $\frac{4}{3}$.

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Bo Li Fangxiao Wang"
Shiji Xing
Abstract
In this paper, we foeus on a job scheduling problem among groups of machines, which was first introduced in (Li et al., 2023). There are two layers of objects, where number of indivisible jobs need to be first allocated to groups (viewed as super-agents). Each group controls a number of machines (which can be viewed as atomic agents). Upon receiving set of jobs, the group should further assign these jobs to its machines with the objective of completing all assigned jobs early as possible. Equivalently, we define cost function for each group that equals the minimum makespan of completing all jobs assigned to it. This setting is natural in practice; for instance, a group's 's workday can only conclude when all members have completed their assigned duties (e.g., facilitating the departure of a shuttle bus).
We study the fair scheduling of jobs among groups of (unrelated) machines and focus on the maximin share (MMS) fairness at the group level. The prob- lem first introduced by Li et al. [NeurIPS 2023], where each group consists of a number of identical machines (or identical up to different speeds), and the cost of group is determined by the minimum makespan on completing all jobs assigned to it. It left as an open problem when the machines within each group are unrelated. In this paper, we first resolve this problem and de- sign a polynomial-time algorithm that computes 2-approximate MMS allocation via linear pro- gramming techniques. We complement this result with a hard instance, showing that no algorithm can be better than (2 1 appproxximtee MMS, where the number of machines. Thus the ap- proximation ratio is asymptotically tight. When the groups consist of identical machines, we im- prove the approximation ratio to 3.
The fairness in this model is measured by the maximin share (MMS), introduced by Budish (2011). The MMS value of each group is the minimum cost it can ensure if the group partitions all jobs into n bundles and always receives the bundle with maximum cost. Li et al. (2023) proved that if the machines in each group are identical (i.e., they take the same time to complete a task), 2-approximate MMS allocation exists and can be found in polynomial time, Although Li et al. (2023) extended their results to related machines (i.e., the machines may have different speeds) within groups, the general setting of unrelated machines remains an open problem. In this work, we aim to resolve this open problem and also improve the approximation ratio for identical machines.
1. Introduction
Faimess has long been a fundamental concern in social and economic environments. In the recent decade, it has drawn increasingly more attention from artificial intelligence, ma- chine learning, and computer science due to the algorithmic and computation issues. One particularly noteworthy setting within the fairness discourse is resource allocation, which is not only theoretically intriguing but also holds practical importance. For an in-depth understanding of fair resource allocation, we recommend handbooks (Wooldridge, 2009; Brandt et al., 2016) and surveys (Moulin, 2019; Amanatidis et al., 2023) for a comprehensive overview.
The above problem aligns two separate lines of research in the literature, namely MMS fair allocation of chores and job scheduling problem. The majority of research in MMS fair allocation assumes additive valuations, which is a special case of the setting in the current paper when each group consists of a single machine (Huang & Lu, 2021; Huang & Segal-Haleve 2023). As proved in (Li et al., 2023), if agents have general subadditive valuations, MMS fairness does not admit better than n approximation. Our work presents a noteworthy class of valuations between additive and subadditive for which we can design (efficient) constant approximation algorithms.
'Equal contribution 'Department of Computing, The Hong Kong Polytechnic University. Hong Kong, China. Corre- Fangxiao
spondence to: Bo Li hiwpp--ooll@pply..edue Wang <fangxiao wang conncct. Shiji Xing <shi- ji.xing @ connect, pol.uu.kk............
On the other hand, the cost functions in our problem involve solving the optimization problem of scheduling among un- related machines well-known NP-hard problem. The
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
best-known approximation is 2 1 mm being the number of jobs, as proved in (Shchepin & Vakhania, 2005), and Lenstra et al. (1990) showed that the problem does not admit better than 3 polynomial-time approximation if P * NP. The tight approximation ratio remains unknown; see Open Problem 4 in (Schuurman & Woeginger, 1999). It is worth noting that finding approximate MMS fair allocations itself does not rely on the assumption of P vs NP, where the impossi- bility is universal and obtained from hard instances. Our work generalizes this model to scheduling among groups of unrelated machines.
Result 2 For any 2, there is an instance with a groups such that no allocation is better than (2 - GMMM..
Finally, we improve the approximation ratio to in the homogeneous setting, which improves the approximation of 2 proved by Li et al. (2023).'
Result 3 A 3-GMMS fair allocation exists in the homoge- neous setting.
Generalizing the hard instance in (Kurokawa et al., 2018). we can show that for any number of agents, exact GMMS allocations may not exist, which is true even when each group contains a single agent. In fact, in this case, the problem degenerates the case of chore allocation with additive cost functions and thus does not admit better than 44 approximation when n = 3 (Feige et al., 2021).
Our results are summarized in the following section.
1.1. Our Results
We consider the fair allocation problem among n asymmet- ric groups, where each group consists of gi (unrelated) private machines who are referred to as agents. Each ma- chine has an additive cost function (i.e., processing time) over the jobs. The maximin share (MMS) (Budish, 2011) of each group is defined the smallest cost it can guar- antee if it divides the jobs into bundles but receives the bundle with the largest cost. The cost of bundle of jobs for a group is the minimum makespan of completing these jobs, i... the minimum of the longest processing time by scheduling the jobs in this bundle to the machines within the group. To indicate the further distribution of the jobs among machines/agents within each group, we explicitly call this share group MMS, abbreviated as GMMS. An allocation is a-approximate GMMS fair (a-GMMS) to a group if its cost is no greater than a times its GMMS cost. Our objective is to understand to what extent we can allocate the jobs to groups so that GMMS fairness is (approximately) satisfied.
1.2. Related Works
The MMS fair division has been widely studied in the past years, with a particular focus on additive functions. For allo- cating goods, Kurokawa et al. (2018) first observed instances which do not admit MMS allocations, and proved the ex- istence of 3-MMS allocations. Amanatidis et al. (2017) designed a polynomial time algorithm with same approxi- mation ratio, which was later improved to 3 by Ghodsi et al. (2018). Garg & Taki (2021) & Garg (2024) further improved the approximation ratio to slightly larger than 3 algorithm has an approximation ratio better than 39 Re- garding chores allocation, it is known that no algorithm can guarantee an approximation ratio better than 41 (Feige et al., 2021), and constant approximation algorithms given in (Aziz et al., 2017; Huang & Lu, 2021; Huang & Segal-Halevi, 2023).
et al. 22023a).Akraml
4. Feige et al. (2021) proved that no
40-
43
We distinguish between two cases: if the machines within each group are unrelated, we call it the heterogeneous set- ting; if they are identical, we call it the homogeneous setting.
In many real-world cases, the functions are more compli- cated. For instance, the functions appear in machine learn- ing and artificial intelligence are often submodular (Bilmes, 2022). For goods, to approximate the MMS allocation, Barman & Krishnamurthy (2020); Ghodsi et al. (2022): Uzi- ahu & Feige (2023) and (Akrami et al., 2023b; Seddighin & Seddighin, 2024) respectively gave constant approxima- tion algorithms for submodular and XOS valuations. Gh- odsi et al. (2022); Seddighin & Seddighin (2024); Feige & Huang (2025) proved the existence of logarithmic ap- proximations. For chores allocation, Li et al. (2023) proved lower bound of min Tog log m } for submodular cost functions with binary margins. They also proved the exis- tence of min n, log m) -aprroximate MMS allocations, and improved the approximations to constants in two special
Our results can be summarized as follows.
Result 1 A 2-GMMS fair allocation can be computed in polynomial time in the heterogeneous setting.
Our algorithm to compute 2-GMMS allocations relies on LP rounding. We begin by constructing a fractional GMMS allocation in which a machine is assigned a positive fraction of a job only if the job's cost does not exceed the GMMS of the machine's 's group. Our method generalizes the LP techniques developed in (Lenstra et al., 1990) to accommo- date multiple groups. Then, we give a rounding procedure that converts the fractional allocation into an integral one, where each machine will have at most one fractional item in their bundle rounded up to integral, resulting in a 2-GMMS allocation. To complement this result, we show that no algorithm can be better than (2- -MMMS.
log m
'Li et al. (2023) extended their result to the setting of related machines, where machines within group have different speeds, i.c., the processing times are identical up to different scales.
2

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
models, where the cost functions involve solving the bin packing and job scheduling problems. Recently, Wang & Li (2024) considered the vertex cover model and also proved the existence of constant approximate MMS fair allocations. In another line, Barman et al. (2023) proved the existence of an exact MMS fair and Pareto optimal allocation under binary supermodular cost functions.
GMMS; =
min
max MMS(S n, ct,K).
(S Sinmn Je I5k$9
(1)
If a partition (Si...., St.) of M reaches the value of GMMS, i.e.,
max MMS(S n, Ct,k) = GMMS,, SSN
2. Preliminaries
it is called GMMS- partition to group G₁- Definition 2.1 (a-GMMS). Given a 2 1, an allocation A is called a-approximate GMMS fair (a-GMMS), if
For any integer k 2 1, let [k] = (I.....A k).. In group fair allocation instance, there are n groups and m indivisible chores, denoted by G = [GI...., } and M = fei,..., )m) Each group G, contains di machines which are referred to as agents, i.e., G, = {ai.1...... ,i.g: and g: G. 2 It is assumed that the groups do not over- lap, i.., G. nG = @ for all i * j. Denote by g Eien Pi the total number of agents. Each individual agent oi,j has cost function Ci.j 2 + Rza. where (S) represents her cost (or finishing time) on completing the chores in S ... For simplicity, denote (e) = ct ((e)). In this paper, the cost functions are assumed to be additive, i.e., (S) Eees C. Let C, - (c.1....,,..
Cig (Ai.)) S a GMMS, for all j E [g]] and i E [n]]
We have the following simple bound for GMMS,. Lemma 2.2. GMMS; 2 n-g: ΣeEM minigksa (e.
Alternatively, we can introduce a cost function for each group to measure the collaborative cost of the agents in the group, as in (Li et al., 2023). This is partly motivated by the job scheduling problem, where the makespan decides the overall cost of the group so that the agents in the group share the same "actual" cost. Formally, the cost function of group G, is denoted by C. : 2 + R20 where for all S C.M.
and c= (c1,-- ... Cn). We distinguish two cases. When agents in group have the same cost function, i.c., Ci.((e) ce, for all G. E G. E M and as.j. 04,1 E G,, we call it ho- mogeneous setting, and otherwise, a heterogeneous setting.
min max (i,((S)) Ci(S) = (S......,, (.)().)))) 15:50
Then we have the following lemma, which presents an equiv- alent definition of GMMS.
An allocation is denoted by A- = (AI....,A,, where A; = (Ai. g. is the allocation to group G2 and Ar. is the allocation to agent a.j. When there is no confu- sion, we also denote A; = A U...U Ai. It required that all items are allocated and every item is allocated exactly once, i.c, UsE(m) UJE(0.) Ar, M and A,, n A4g 12 0 for (11,4) + (12, Finally, we use I = M, to denote group chore allocation instance.
Lemma 2.3.
min max C,(S)). GMMS; (S USt.mSS S.) ET(M.)) 18/5m
(2)
subadditive, i.e.. C(S, U S2) I C(Si) C(S2) for any S and S2. In fact, the model in (Li et al., 2023) used Lemma 2.3 to study the MMS allocation of subadditive cost functions. By their results, we have an ( (n, log m)) approximation. If agents in each group have identical cost functions, the ap- proximation ratio improves to 2, but it's unknown a better approximation exists for the general heterogeneous case.
Note that the group cost functions
The agents in the same group collaborate with each other and have reached an agreement to complete their assigned items together so as to minimize the maximum cost. There- fore, they share the same fairness benchmark value which depends on the largest individual cost. To formally define the group maximin share, we first recall the original defini- tion of maximin share (MMS). For any integer A > and set S C M, denote by 11(S, k) the set of all k-partitions of S. When allocating items S among k agents, the MMS of an agent with cost function c is defined as
Our paper examines two case types: Section 3 covers cases with heterogeneous agents, where agents in a group have varied cost functions, while Section 4 addresses cases with homogeneous agents where agents within a group share identical cost functions.
MMS(S, ki
min max c(S)).
3. Heterogeneous Agents
(5 15....... (E)(()))) 15JSK
In this section, we present our main result. We first prove that no algorithm can perform better than (2- --MMS by constructing a hard instance and then design a polynomial- time algorithm that always computes a 2-GMMS allocation for all instances.
The group maximin share (GMMS) of group G; is the op- timal worst-case individual share by partitioning the items into 9, bundles where each agent a; shares responsibility of her bundle with the other n groups. That is
3

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
3.1. Lower Bound
Cr,(p,)) for all et E Q.
Theorem 3.1. There algorithm that can perform better
Claim 1. GMMS; = 1 for i I..... 1.
than (2 -.GMMS where is the number of groups.
Proof. It is easy to see that GMMS; > 1 since the small- est single-item cost of every agent is 1. Consider parti- tion (BI,... Bv) with B; = {er} U fer,p. E Tp. E [n - 1] and E [n]]- It can be verified that Ca(B:) = 1 by allocating ex to di,1 and (t.(p.k to (g,(p.)) and thus Cr,1 (er) (eI.))))))L
Proof. We construct the following instance with groups {Gi...., G, ), 2 11nn(nn11) 1) agents and n + n² (n items. The items are divided into two types:
Q {er E [m]]:
T fet.p. I E [m]. E [n - 1], and [n]],
Group G, contains n agents (an,1.-..,,a For each agent 0n S S n,
where the items in T are ordered by their indices, shown in Figure 1. Note that [Q] = and [T' = n² 1). We consider the following two different partitions of T, Upee(n Upe(n-11).Efa [)) Tp. and Use(n] TR. where
(nx)(ex) = 1 for each en E Q,
(n,( for each ei Q with I + k,
Tp. = (e1.p E T 1
(el,pe) = for each elp.k E Tk.
and
cn..(et,p,)) oo for each et, E Tk with k' + k.
Tg = felpp ET 1 and 1 S n 1--n-1 1).
The above partitions of T are illustrated in Figure 1. The green items correspond to one Tp. (in fact, it is 1.1 and the orange items correspond to one Ti (in fact, it T4).
Bg
T:
B,
8.
M.-
13
Bg
13
P
72
B..). (B....,,.)) projected on the l-axis. That is, each item (p. k) in Figure represents a row of items (p, k, with I = 1...., n.
Figure 2. Partition (Bi...,,
where the illustration is Figure
1
Claim GMMS, = 1.
Figure 1. The structure of items in T, where Tn-1,1 marked in green and T4 is marked orange.
Proof. By Lemma 2.2,
We next define the cost functions of the agents.
GMMS,
Σ min (e,
n- 1, group G, contains (n fa--1 1)n++ + agents denoted by a;, and (p.(p.A) with p [n and & E [n].
For i = I,..., n
n²
CEM
Isk
(n,k(en) +
Σ
For agent a;,1+
n
ISkSn
1E(m).pe(n-1]
- (e) = for all e E Q
Consider partition (Bi...., Br) with
-c,1(etp.k) = oo for all &1,p& E T.
Bg = U h < q. q.15
For each agent (p.(p.k) where p In and k E [n],
U fet.g glsss
((..))) for all el,p. Tpkk - -.. = oo for all et,p' & E Tyry with p/ # por k' *k.
where {er,0.8 | 1 k 1, & n] 0 and {er, 1 k > n, 1 S n) = 0, as shown Figure 2. That is, bundle

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Bg obtains items on each column & * q and nothing on column k q- To group Gn 's cost is for Bg we allocate eq to dn.g. an,g S cost is I; allocate { 1,2 1 1 S n to On for k < and (et.q. S 1 S n to an.k for k > g. so that every agent On, for # q has n items, each of which has cost
Definition 3.3. For fractional allocation x, we construct an auxiliary (multi-)graph G(x) -V, F.), where the vertices V = G1 U... U.G represent the agents. If a Ji + 0 and A * we construct an edge between as and asada and label the edge by l. A cycle in the graph is called share cycle if at least two edges in the cycle have different labels.
Lemma 3.4. There exists fractional allocation such that
Next we prove that for any allocation A = (AI...., An), at least one of the groups has makespan of at least 2 We start with two simple cases.
For every agent aig. Ci. Cx.(Xan) S GMMS..
For any di.5 + O, cg I GMMS,
Case 1. If A n QI 2 2 for any group G., Sinn- 1, then (A,) 2 2. This because only agent a;, has cost on items in Q while all other agents have cost infinity.
There no share-cycle in the auxiliary graph.
Further, such an allocation can be found in polynomial time.
Case 2. If nT, 2 2 for any group G₁ 1 < i S n-11 1, 1 S P S - and < k < n, then (A,) 2 2. This is because only agent (p.(p.)) has cost on items in Tp while all other agents have cost infinity.
Proof. We utilize the linear programming technique intro- duced in (Lenstra al., 1990) prove this lemma.
Fix a parameter & 0, which can be viewed guess of the value of GMMS, Let
Case 3. If An Ql 2 1 and IA, n TTTpl < for all 1 S n 1 and S p n and 1 S < n, we claim that (A,) 2
Suppose cg- E An QQ and thus eg- must be allocated to agent an,k", We next consider the allocation of Tu. Since A n T S for all 1 S i S n 1 and < p S n 1, we have [A, n TTe S n 1, and thus
Mt, = E st}
be the of items for which agent di, has cost no greater than li, and
Pa,(()) = {as. E G. c.)(e) S 4)
22
A Tk (n 1)2.
be the set of agents in G, who have cost on item e, no greater than t,. Consider the following linear program (P,
That is
Σ Gis(ei) BiAA St., Vj e e [n] MEMMi( E v-jia=1, =1 Ve M
An n T 2 nnn - 11 - (n 1)2
Since (e..(e))p))))) )= = o for all k * k., all items in An T&. are allocated to agent On, Therefore
jEP, (t),,
V 2 O, Vj (9,), [n].er Mi,(t.).
CA 2 Cn, (ex-) + Cn. (An TT=)
where i, j, k, represent group Gú, agent aij in Gt, the k-th bundle in the n-partition of group Gi, and item e'. Thus, variable vi.j. means the fraction of item allocated to agent a, in the k-thh bundle in the n- n--aarition of group G.. The first constraint means that the cost of every copy of every agent not greater than t,, and the second constraint means all items are allocated.
1+ - 1) _. n
n
Combining Cases 1, 2 and 3 completes the proof.
3.2. Upper Bound: A 2-GMMS Algorithm
Let E be the minimum value t; such that LP(t.) has feasible solution. Then we have the following claims. Claim 3. t can be computed in polynomial time.
Theorem 3.2. A 2-GMMS allocation can be computed in polynomial time for any instance.
Before showing our algorithm, we first introduce additional definitions. We use x (X1,...,, xx) to denote frac- tional allocation, where x; = (xi, Xj.a)) and x.j = j=!_... .... 2 such that each 0 S 2 < denotes the frac- tion of item e E M that agent 0z obtains. Thus, feasible allocation satisfies Eiejn, 4i. = 1 for all 1 < L < m. For simplicity, let c., (x.,)) = Eiem (e) od.y
Proof. Similar to (Lenstra et al., 1990), we can binary search E. An upper bound of 4 is the maximum cost among agents in G, by allocating each item to the agent with minimum cost on it, and a lower bound is gen times this maximum cost. For each t,, checking whether LP((t) ad- mits a feasible solution can be done in polynomial time.
5

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Claim 4. 17 < GMMS,-
away. Therefore, her total cost does not increase. Hence, by exchanging items in the above way, no agent's cost is increased.
Proof. This lemma is straightforward as LP((GMMS,) has a feasible (integral) solution.
It remains to decide the value of y so that at least one edge in this cycle is canceled and no agent passes more items than she possesses. Consider agent di If et and ét-1 are the same item, then her allocation X does not change in the process, since she essentially passes fractional item from her left neighbor to her right. Therefore, the edges between di and di 11-111 cannot be canceled and she will not give more item than she possesses no matter how large ry is. Thus we can safely exclude her from the calculation of y. Consequently, we only need to focus on agents who share different items with their neighbors. Assume ais is such an agent. If 1, then she will pass a fraction of e1 with amount y 1. Otherwise, she will receive cost an
We next construct a fractional allocation x = (x1...., Xn))
satisfying all conditions of Lemma 3.4. Denote by (uften)) a feasible solution of LP((G). Let
Σ vi.k..
n kE(n)
By the first constraint of LP,(
(xi(X < - n . 17 S GMMS,
Moreover, æi > if and only if v > 0 for some ls E [n]. By the definition of (1,( (())) S 1 I GMMS, Thus, satisfies the first two conditions of Lemma 3.4. If there is no share cycle in the auxiliary graph G(x), the lemma holds. Otherwise, we gradually modify x to satisfy the third condition without hurting the first two.
I.c 8, and needs to pass a fraction of et with TheR 11 ya. Theeg...... B: amount y
We need to select y such that 7 Ihir di S d/e. Furthermore, since we want to remove one edge from the cycle, we also hope that this inequality holds tight for some agent. We then can determine the value y by the following:
Iie The ai
Let C 0ii.i - 0ig.jo -....- - di Oir. be a share cy- ele in the auxiliary graph G(x)). Denote di + Oi2dd + + Gi..j. - ai as the right direction and the back- ward direction as the left. Let item e denote the item that agent (i and her right neighbor 0:41 share in the share cycle, where 1 ++1 1 = 1 if / = k. For agent di denote by aq = (et) the cost of her right shared item of the cycle and Bi = Ci (et-1) as the cost of the left shared item, where 1 1-
Br -he 0s
7 = min lES
IT 3,
where S is the set of agents in the shared cycle who share different items with their neighbors. As a special case,
if 1.
ag.t
62
a
64
a
Note that either of the following expressions must be less than or equal to 1: H. a, He 8. Ih. 3. or Theg a. since their product exactly 1. If Il.eng a;
B2
3.
y
Je (clanokk) ?
[w]e]
ll I1.e & < 1, we choose left as the desired direction and right otherwise. Without loss of generality, assume that the direction is right.
Figure 3. Exchanging items among the cycle in the right direction.
By reallocating the items in the cycle with the computed y, it is ensured that at least one edge in this cycle is cancelled and the reallocation is valid. Therefore, after the reallocation, there is one less edge in the graph G(x)). Consequently, in polynomial time, we can repeat this process until all share cycles are eliminated. In the process, the total cost of agents are non-increasing, so Ci I GMMS,
Let y > O be a sufficiently small number. As Figure 3 shows, we let agent 0i give a fraction of item 61 with cost y to dig.jz. The amount of the passed item e is 7 a." For agent 012.d2 the cost of the received fraction is 7 22. We want 0z2.j2 to pass fraction to her right neighbor that her total cost does not change. Therefore she will fraction of item 62 to dis.ja- Repeat this process for the remaining agents in the cycle. For agent anch with / E [2..... k). she will receive a fraction of e;-1 with cost y TTe &
an
pass 7 .1.03
Furthermore, no agent receives a new item in the exchanging items process. For item Ep and agent ai with Zi.j 0, (c,)(pp) < GMMS, still holds.
and will pass a fraction e with Thep-19 0,
11 to her right neighbor. Eventually, T1ig d;
Now we are ready to prove Theorem 3.2.
amount 7
agent Ji receives a fraction of the item és with cost
Proof of Theorem 3.2. We first obtain a fractional alloca- tion x satisfying all conditions of Lemma
[herk) 8:
7 The og
which is no greater than 7, the cost she gives
6

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
If there is no share cycle in G(x), then there exists an agent whose bundle contains only one fractional item. Assume not, then each agent who possesses fractional items must have at least two or more of them. Therefore, such agents will have at lease two adjacent edges with different labels in the auxiliary graph. Furthermore, since each non-isolated vertex in the auxiliary graph has degree of at least 2, a share cycle must exist, making a contradiction.
GMMS; 2 (M) = n and thus y: GMMS; 2 1.
We next introduce some notions to be used in the algorithm.
Recall that ce(e) I GMMS, vi E [m]]. e E M. An item e E M is called large for group G, if cy(e) > GGMMS, medium if
3 GGMMS, and small if c;(e) < 3 GMMS, For a set of chores S. let HS()). Di) and (S) respectively denote the set of large, medium and small items in S for group Gs, i.e.,
3 GMMS, S cj(e) -
Let Ja.j be such agent having received only one fractional item Ep. Let Aij = (ea = 1) U {ep). Note that for agent aij (A.,) S (te = 13) + ((e(()))) x (x.(( GMMS; 2GMMS, Then, delete the agent ai and all the edges labeled with ep in ((x).
(((E)) > GMMS.} }
H2(s)
EN E
2 GMMS }
D((S)= EN E
3 GMMS: S <c(ew)= -
Since the updated auxiliary graph G(x) is a subgraph of the
L,(S) {
GGMM..
previous one, there is still no share cycle. So we keep the above process until there is no agent in G(x) and we get a 2-GMMS allocation A ji
EK ES
c((e))
< 3
Let (g....., be an arbitrary GMMS-defining parti- tion for group Gs, and (SI,....., Sn,x) be an arbitrary n- partition of Se such that maxje[m] (S < GMMS; for S k S gt. Thus, each bundle Sk.j for k E [mx] and j E [g]] can contain at most one large item or at most two medium items, due to the definitions of GMMS. Hence, the total number of large and medium items in M satisfies
4. Homogeneous Agents
In this section, we switch our focus to the homogeneous setting where the agents within each group G3 have iden- tical cost functions. That is, for any two agents 0z.j. "t,y' (e.i(e) = (e) for all items e E M. For simplicity, we use c-). denote the cost function of all agents in group G.- Li et al. (2023) proved that the homogeneous setting admits 2-GMMS allocation. In the following, we improve this approximation ratio to 3-
[H:(M) + [D(MM 2
S n.-oo Di-
Next, we introduce our algorithm. The algorithm runs in two phases. In the first phase, we allocate items, via Algorithm I, to each group Gi, denoted by B = (Bi...., Bn). In the second phase, we allocate B, to agents in each group GG denoted by B, = (B.,,,..., B...))
4.1. Upper Bound: A #84 4-GMMS Algorithm
Theorem 4.1. There exists 1/2 GMMM allocation for all homogeneous instances.
Definition 4.2 (Ordered Instance). A homogeneous in- stance I (G, M).)) is called ordered if the agents in all groups have the same ordinal preference over all items, i... (e,)) 2 c.(22) 2 ... 2 c;(e,.. for all i E [n].
We start with Algorithm 1, which runs in n rounds. Each round j consists of two parts: bag initialization and bag fill- ing. In bag initialization. items are put in a bag S according to their indices, and one will be selected in every n items. Specifically, the selection adopts the following strategy:
It is widely known that when each group contains exactly one agent, the ordered instance is the most challenging case for approximating GMMS fairness (Barman & Krishna- murthy, 2020; Huang& & Lu, 2021; Li et al., 2022). This property also holds for the case where each group contains multiple identical agents (Li et al., 2023).
If there are currently x items bag S and x is even, the chore with index n x + j will be considered next;
If there are currently x items in bag S and is odd, the chore with index + n + 1 1-j j will be considered;
Lemma 4.3, (Li et al., 2023) For any 2 1, if an c-GMMS allocation exists for all ordered instances with homogeneous agents, then an a-GMMS allocation exists for all instances with homogeneous agents.
Assume item e, is being considered. If there is group that regards e, as large or medium, note this group, add e, to S, and begin considering the next item;
Otherwise, exit the bag initialization step.
By Lemma 4.3, it suffices to restrict our focus on ordered instances. In addition, we assume without loss of generality that the valuations of agents are normalized so that (MM) = n for all E [n]. By the definition of GMMS,, n 2.g0 gi by some group, contain two sequences: Items with indices
Consequently, the items in S, considered medium or large
7

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Algorithm 1 Assign Items to Groups
When (B,) = [ and l o O, let item e denote the last large item added in B, during the algorithm. Ac- cording to the algorithm's ''s selective strategy, after selecting item the next medium item (if any) is chosen after at least 2 - k) items. After the 2(n - k) items, the number of the medium items does not exceed (9. - r () x 2n. Since in bag initialization, if the algorithm selects item eg- before the algorithm selects ej+2n. only one another item is selected. In each subsequent group of 2n medium items, the algorithm selects 2 items to be included in B,. Hence,
n
Input: Ordered homogeneous instance I - (G, Output: Allocation B = (BI....,,B, Bn).
1: Initialize R- 4-+44 .M.
2: for from 1 to do
3: %Bag Initialization:
4: Initialize S + -0, +-
5: Let k be the index of one group such that G5 E G.
6: while RG, E s.t. e E (R) U (R) do
7: St SU (er), R + RV \ {e:), k i.
8:
if [t/n] is odd then
[B.( + [B.] H.(M))
Hi(M) n
9:
1 (((/// + 2) n n j.
<
+
= gi
10:
else
2
π
11:
t (L1/n] + +1) end if
which completes the proof.
12:
13:
end while
Claim 6. All the items can be allocated by Algorithm 1.
14:
Beaag Filling::
15:
while 3G; E G s.t. (s) < 1 and (R) # 0 do
Proof. Consider the last remained group is G; in the last round of the algorithm. In the bag initialization part, there is only one item unallocated in every n items among group G,'s 's large and medium items. Therefore, all the large and medium items can be added into B, during the bag initializa- tion part. If there are some items that are small for G., for the bundle S removed in every round before the last round, (5()) 2 (i(M) Therefore, for the remaining items S' in the last round, ca (S*) S (MM (n 1) ()(M))) s((M). All the small items for group G; are added into B, Hence, all the items can be allocated.
16:
++i. i.
17:
e the item with the largest index in R.
18:
S su [e). R + R {e).
19:
end while
20: Bx x S, g + g {.r)
21:
end for
a
j. 2, + j.4n+ + j. form one, and with indices 2n + 1 j, 4n +1 - j, 6n +1 j.... form the other.
n
In the bag filling step, the algorithm attempts to put more items in the bag S and assign the bag to some group It will check if there exists some group G; for which the cost of S is at most and there are small items unallocated. If such a group exists, the algorithm will note this group and add the smallest item (for all groups since the instance is ordered) to bag S. This step will be repeated until there is no group that satisfies the conditions. The algorithm will then allocate bag S to the last noted group, which will leave the algorithm. Eventually, after n iterations, one bag will be allocated to each group, and the algorithm terminates.
Clain 7. Given the set of items B, computed by Algorithm 1, we can divide B; into a ge-partition (A,, ...g:) such that cA(A),)) GMMS, for any agent 0j E G..
Proof. Firstly, initialize the set of bundles A., = 0 for all j E [oo]. We allocate one large item or two medium items to one empty bundle until all the items in HB,))) U (B,).) are allocated. All large and medium items can be allocated this way by Claim 5.
Claim 5. For group G., (B.) + [B:l < 9i-
After allocating the large and medium items, each agent in the group will have a cost at most 3 $GMMS,, which is directly derived from the definition of large and medium items. If L,(B)) = 0 then the proof is complete. Otherwise, consider e", the last item added to bag S(which becomes B,) 1 < GMMS, gi from Line 15 of the algorithm. For item e E L; (B:) (e"). find some agent ai with c(Ar)) < GMMS, and assign e to that agent:Ar, + Ai, U fe). Repeat this step un- til L,(B,) \ {e") is exhausted. Note that we can always find an agent to receive e. Otherwise, at some point each agent in G; has cost more than GMMS,, which means c, (e")) 2 EjE(o (AAs)) 2 9: GMMS,, asserting contradiction. Analogously, after allocating I,, (B.) \ (e*),
Proof. Recall that large and medium items are added to B,
in the bag initialization step. Denote k: = (M)) mod n. Since Algorithm allocates item among every large
and medium items into B,, [B,) = [.(MM or
by Algorithm 1. We have ca \ fe"))
[M)] 1, and [D((B,) [DI[M]] or (M)
n
a
n
When HB.)) = [H((M)] or ls = O,
HB,B) + [D:(
(M) n
DD(M)
2
[M+(M)++10]
+ + gr-
7
8

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
there exists some agent 0i." such that ez (A..5-)) S GMMS,- We then assign the only remaining item e" to this agent, thus A < Aij. U {{*) ). Note that each agent who would re- ceive small item this way has cost at most GMMS; before taking the item, so we can conclude that for each agent Oz.j
For any of chores S such that |S] the bundle is at least
m + 1, the cost of
(S 2 ( + 1)o - 02(5)
n
in (A,)) < 4 GMMS,
Iv
m + 1)e(MM - ((M) = m (M(M) > MMS;
n
π
Based on the discussion above, Theorem 4.1 is proved.
Hence, if there is an MMS allocation, it must be balanced, i.c., every agent must obtain exactly z chores. Since there is no MMS allocation in the goods instance I, there must be one agent a; who gets bundle A; such that v; (A.) < MMS; for any allocation A. Thus, in the chores instance. for any allocation A, there also exists an agent a, such that
We remark that the above algorithm is not polynomial since we need to first compute GMMS values. However, by applying the techniques in (Barman & Krishnamurthy, 2020), our algorithm can run in polynomial time, and the approximation ratio will increase to 3 + for an arbitrarily small constant c.
(A,,)
m Ui (M(M (2(A,)
4.2. Non-existence of GMMS Allocations
m (MM - -MMS = MMS;,
We finally show that an exact GMMS allocation may not exist for any number of groups, even when every group contains single agent, which degenerates to the traditional setting of MMS fair allocation of chores with additive cost functions. It is proved in (Aziz et al., 2017; Feige et al., 2021) that when n = 3, an MMS allocation is not guaran- teed. For > 3, it remains unknown, On the other hand, Procaccia & Wang (2014) designed a series of instances for the allocation of goods, showing that an MMS allocation is not guaranteed for any n 2 3. We next show how to convert these instances to chores. Note that, in this section, we restrict our focus to the case where each group contains a single agent. We use I = (M,N. v) to denote a goods instance, where N = {ai,...,da ) is the set of agents and (Ui...., 2n) is their valuation profile. For goods instance agents want to get higher utilities, and their MMS is defined by the maximum, over all n n-partitions of M, of the minimum value of bundle in the n-partition. We refer the readers to (Feige et al., 2021) for a formal definition.
implying that I' does not admit an MMS allocation.
5. Conclusion
In this work, we study the fair allocation problem of indi- visible chores among groups of agents, where fairness is measured by group maximin share (GMMS). For the hetero- geneous setting, we design a polynomial-time algorithm that returns 2-GMMS allocation, and prove that the approxi- mation ratio cannot be improved to better than 2 - A. For the homogeneous setting, we improve the approximation 3.
ratio to 4 but the best possible approximation in this case remains unknown.
Our paper uncovers many open problems and further direc- tions. As mentioned, the best possible approximation ratio in the homogeneous setting is still unknown. In fact, for the homogeneous setting, we still do not know if it makes a difference between the case of multiple agents within each group and when every group contains a single agent. Secondly, for the heterogeneous setting, our approximation ratio is tight only when the number of groups goes large. It is an open question whether can design better algorithms for a small number of groups. Thirdly, in this paper, we only consider identical and unrelated machines. It is interesting to extend our setting to related machines. We still do not know the setting of related machines is strictly harder than that of identical machines.
Theorem 4.4. For any n. 2 3, there is an instance that does not admit an exact MMS allocation.
Proof. Let = (M,N, v) be any goods instance such that (I) for every agent a; E .,, MMS, L (.M), and in one of her MMS-defining partitions, every bundle has the same number of goods, and (2) there is no MMS allocation. Note that the instances provided in (Procaccia & Wang, 2014) satisfy these requirements. We construct a chores instance I' (N,M! .). where M' M, A'' N, and (g) = (M) - v, (g) for any g E M'. Denote by MMS. the MMS of agent E N in I'. Hence
A Acknowledgments
This work is funded by the Hong Kong SAR Research Grants Council (No. PolyU 15224823) and the Guang- dong Basic and Applied Basic Research Foundation (No. 2024A1515011524).
MMS (MM m (M(M) - MMS, = m (M).
9

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Impact Statement
Feige, U., Sapir, A., and Tauber, L. A tight negative example for MMS fair allocations. In WINE, volume 13112 of Lec- ture Notes in Computer Science, pp. 355-372. Springer, 2021.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Garg, and Taki, S. An improved approximation algorithm for maximin shares. Artif. Intell., 300:103547,, 2021.
References
Ghodsi, M., Hajiaghayi, M. T., Seddighin, M., Seddighin, S., and Yami, H. Fair allocation of indivisible goods: Improvements and generalizations. In EC, pp. 539-556. ACM, 2018.
Akrami, H. and Garg, J. Breaking the 3/4 barrier for ap- proximate maximin share. In SODA, pp. 74-91. SIAM, 2024.
Akrami, H., Garg, J., Sharma, E.,, and Taki, S. Simplification and improvement MMS approximation. In IJCAI, pp- 2485-2493, ijeai.org, 2023a.
Ghodsi, M., Hajiaghayi, M. T., Seddighin, M., Seddighin, S., and Yami, H. Fair allocation of indivisible goods: Beyond additive valuations. Artif. Intell., 303:10363: 2022.
Akrami, H., Mehlhorn, K., Seddighin, M., and Shahkarami, G. Randomized and deterministic maximin-share ap- proximations for fractionally subadditive valuations. In NeurlPS, 2023b.
Huang, X. and Lu, P. An algorithmic framework for approx- imating maximin share allocation of chores. In EC, pp. 630-631. ACM, 2021.
Amanatidis, G., Markakis, E., Nikzad, A., and Saberi, A. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, (3(4):5211-52:25 2017.
Huang, X. and Segal- E. A reduction from chores allocation to job scheduling. In EC,, pp. 908. ACM, 2023.
Kurokawa, D., Procaccia, A. D., and Wang, Fair enough: Guaranteeing approximate maximin shares. J. ACM, 65 (2):8:1-8:27, 2018.
Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratiikss, A., Li, B., Moulin, H., Voudouris, A. A., and Wu, X. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., 322: 2023.
Lenstra, K., Shmoys, D. B., and Tardos, É. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990.
Aziz, H., Rauchecker, G., Schryen, G., and Walsh, AI- gorithms for max-min share fair allocation indivisible chores. In AAAI, pp. 335-341, AAAI Press, 2017.
Li, B., Li, Y., and Wu, X. Almost (weighted) proportional allocations for indivisible chores. In WWW, pp. 122-131. ACM, 2022.
Barman, S. and Krishnamurthy, S. K. Approximation algo- rithms for maximin fair division. ACM Trans. Economics and Comput., 1-):25) 2020.
Li, B., Wang, F,, and Zhou, Y. Fair allocation of indivisible chores: Beyond additive costs. In NeurlPS, 2023.
Moulin, H. Fair division in the internet age. Annual Review of Economics, 11(1):407-441, 2019.
Barman, S., Narayan, V., and Verma, P. Fair chore division under binary supermodular costs. In AAMAS, pp. 2863- 2865, 2023.
Procaccia, A. D. and Wang. Fair enough: guaranteeing approximate maximin shares. In EC, pp. 675-692. ACM, 2014.
Bilmes, J. A. Submodularity in machine learning and artifi- cial intelligence. CoRR, abs/2202.001 0012002... 2022.
Schuurman, and Woeginger, G. Polynomial time ap- proximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2(5):203- 1999.
Brandt, F., Conitzer, V., Endriss, U., Lang, J., and Procaccia, A. D. (eds.). Handbook of Computational Social Choice. Cambridge University Press, 2016.
Budish, E. The combinatorial assignment problem: Ap- proximate competitive equilibrium from equal incomes. Journal of Political Economy, 1696))1011-1103, 2011.
Seddighin, M. and Seddighin, S. Improved maximin guar- antees for subadditive and fractionally subadditive fair allocation problem. Artif. Intell., 327: 10404, 2024.
Feige, U. and Huang, Concentration and maximin fair allocations for subadditive valuations. CoRR, abs/2502.13541. 2025.
Shchepin, E. V. and Vakhania, N. An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Leut 33(2):127-133, 2005.
10

---

Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Uziahu, G. B. and Feige, U. On fair allocation of indivisible goods to submodular agents. CoRR, abs/2303.12444, 2023.
Wang, and Li, B. Fair surveillance assignment problem. In WWW, pp. 178-186. ACM, 2024.
Wooldridge, M. J. An Introduction to MultiAgent Systems, Second Edition. Wiley, 2009.


Reviews:
[{"review_id": "kpeGP6Uj8W", "reviewer": "Reviewer_x4k3", "summary": "This paper considers a fair resource allocation problem called Group Maximin Share (GMMS). There are two layers of allocation: at the first layer, there are $m$ items to be allocated to $n$ groups. Then, once items are allocated to each group $G_i$, they are further allocated to the $g_i$ agents in $G_i$. Each agent has a cost for each item, and the agent's cost on the allocation they receive is the makespan of the items; the cost of the group is the maximum makespan among the agents. The maximin share $\\textsf{GMMS}_i$ of the group $G_i$ is computed as follows (Lemma 2.3) in the paper: consider all possible partitions of $m$ items into $n$ parts. Consider the part $S$ that, when allocated to group $i$, has the worst cost. Here, cost is referring to the second layer, where it is the minimum maximum makespan among all possible allocations of $S$ to the $g_i$ agents in $G_i$. So the problem can be written as two successive min max problems. \n\nThe fairness goal is to find an allocation (at both layers) such that the cost of any group (computed as the maximum of the agents' makespans) is at most $\\alpha \\cdot \\textsf{GMMS}_i$. The authors show that for the heterogeneous case (agent's costs within a group are potentially different), there is an algorithm yielding $\\alpha = 2$, and that this is asymptotically tight ($2-1/n$). They also show that for homogeneous costs, there is an algorithm yielding $\\alpha = 4/3$.\n\n## update after rebuttal:\nAs my concerns were mainly about clarity of writing, I maintain my evaluation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's supportive review and constructive suggestions. We will carefully address the typos and polish the presentation.\n\n*Comment*: On the terminologies in related work and the model.\n\n*Response*: We thank the reviewer for pointing out this issue.\nWe will thoroughly examine the paper and improve the writing.\nSpecifically, we will focus on providing clear definitions for the terms used and expanding on the discussed models (e.g., related machines).\n\n\n*Comment*: On the definition of approximation ratios.\n\n*Response*: We thank the reviewer for raising this issue, and we agree that the approximation ratio is classically used in optimization problems to measure the multiplicative factor between efficient and optimal solutions. \nHowever, in the literature of MMS fair allocation of indivisible items, it becomes the convention to use the term \"approximation ratio\" to describe the best possible achievable factor of MMS. \nWe thought it might be better to be consistent with the literature when preparing the submission, but we also understand the potential ambiguity.\nPerhaps \"approximation factor\" and \"competitive ratio\" make more sense.\nWe are open to adjusting this terminology based on the reviewer's advice.\n\n\n*Comment*: On pg.5, the kth copy of $G_i$.\n\n*Response*: $k$ refers to the $k$-th bundle in the $n$-partition of group $G_i$. We will rephrase this sentence to make it clear.\n\n*Comment*: Sometimes ratios are listed as the reciprocal.\n\n*Response*: We will check the ratios carefully and make them consistent and accurate.\n\n*Comment*: On Theorem 4.4.\n\n*Response*: Thanks for the suggestion. We will mention \"exact allocation\" in the description of the theorem.\n\n*Comment*: On the definition of related machines.\n\n*Response*: Thanks for the suggestion. We will include the definition of related machines the first time we mention it in the paper.\nWe will also review other places to ensure the clarity of terminologies and models.", "claims_and_evidence": "Full proofs are provided.", "methods_and_evaluation_criteria": "No experiments are provided; this is a pure theory paper.", "theoretical_claims": "I did not check proofs in any detailed manner.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The most closely related literature is the work of Li et. al. (2023), where the problem was introduced. They showed a $O(\\min\\{n, \\log m\\})$-GMMS for the heterogeneous case and a 2-GMMS for the homogeneous case. The present work improves the first factor to 2 and the second factor to 4/3.", "essential_references_not_discussed": "The most relevant paper, Li et. al. (2023) is discussed, along with a number of references on MMS more broadly. I did not notice any important omissions for understanding the paper.", "other_strengths_and_weaknesses": "This paper contributes a worthy contribution of nearly matching upper and lower bounds for the heterogeneous case. The idea behind the proof of the 2-GMMS is nice: the authors compute a fractional solution to the LP, and then construct an auxiliary graph where edges are labelled with the fractional allocations. Then the solution is rounded to an integral one by sending allocations through the graph. While the 4/3-GMMS result for the homogeneous case is not proven to be tight, it is a notable improvement over previous work. \n\nThe main weakness of the paper is that the writing is unclear, particularly in the first half and with respect to both related work and the model at hand. Several problems are discussed without defining the relevant terminology, which makes it difficult to contextualize the present results. There is also an abuse of language, as approximation ratio is used to describe the fairness factor $\\alpha$, but this is not how approximation ratio is used in classic approximation algorithms (while the term is also used in the regular sense to discuss some related works, as I understand).", "other_comments_or_suggestions": "- pg.5: referring to $k$th copy of $G_i$ is confusing language \n- Sometimes ratios are listed as the reciprocal of what they should be. \n- In Theorem 4.4, it would be clearer to say something like an exact allocation. \n- It would be good to define what related machines means in this context", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1keiuxgL8Z", "reviewer": "Reviewer_MsHm", "summary": "The paper discusses the problem of group maximin share job allocation, where groups need to be assigned sets of jobs which are distributed to machines within each group to ensure the minimum largest makespan within that group. In the heterogenous setting, where machines within a group can have different cost functions, the authors show a lower bound of 2-1/n approximation ratio using a difficult example, and an upper bound of 2-MMS  approximation ratio by constructing a polynomial time algorithm for constructing an allocation. Further, in the homogenous case, they reduce the previous upper bound of 2-MMS to 4/3MMS (when the Group MMS allocations are known) and 4/3MMS +$\\epsilon$ relaxation in polynomial time.\n\nPost-rebuttal comment:\nThe author's rebuttal addresses some of my concerns, and as long as they fix the typos and minor errors, I am in favor of accepting this paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of the results and the insightful comments. We will carefully review the paper to refine the presentation, including the introduction and the technical proofs.  Below, we address your specific comments.\n\n*Comment*: On the term of Maximin Share.\n\n*Response*: The reviewer is correct that MMS should actually refer to the \"minimax share\". \nHowever, to be consistent with the allocation of goods (i.e., maximizing the worst-off agent's utility), the use of \"maximin share\" forms a convention in the literature of allocating chores (i.e., minimizing the maximum makespan). This is partially because the very first several works on this topic used \"non-positive utilities\" instead of \"non-negative costs\" to describe the valuation functions. Recent works on chores found it is more convenient to use non-negative costs, and maximin share is used for consistency. We will carefully explain the notations in the revised version and would be happy to make changes based on the reviewer's advice. \n\n*Comment*: On the range of the approximation ratio.\n\n*Response*:  We thank the reviewer for pointing out this issue. It is a typo in the title of Section 4.1, where the approximation ratio should be 4/3. To define the approximation ratios, we adopt the following rule.\n\n- For the problem of goods (corresponding to maximization objectives), the approximation ratio $\\alpha$ is defined to be smaller than 1, and $\\alpha$-approximation means the algorithm can guarantee at least $\\alpha$ fraction of the optimal utility;\n\n- For the problem of chores (corresponding to minimization objectives), the approximation ratio $\\alpha$ is defined to be greater than 1, and $\\alpha$-approximation means the algorithm can guarantee no more than $\\alpha$ times the optimal cost.\n\nWe will carefully review the paper and ensure consistency in approximation ratios.\n\n*Comment*: On the presentation of the introduction.\n\n*Response*: We thank the reviewer for the suggestion of sticking with the job scheduling problem.\nWe will reorganize the introduction and avoid talking about different kinds of things.", "claims_and_evidence": "The paper presents detailed proofs of the three claims.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proofs for the three theoretical claims, and was convinced of their correctness. I was not able to completely follow the final proof for Theorem 4.1 (4/3 GMMS allocation upper bound), but I can see how it holds.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper pushes the frontier of group job allocation, presenting new algorithms and improved upper and lower bounds for the problem setting of improving maximin share fairness. The designed counterexample proves a good lower bound for heterogenous utilities, which has not been seen before.", "essential_references_not_discussed": "The paper has good related work", "other_strengths_and_weaknesses": "One general comment I have about the paper is the slight confusion the term Maximin Share induces. In typical fair division literature, MMS refers to maximizing the worst-off agent's utility, but in this case, the problem is minimizing the maximum makespan, bringing it closer to a minimax setting. \n\nThere is also some inconsistency within the paper with how approximation ratios are presented. In most of the paper, approximation ratios larger than 1 are used, but in the related work, some of the values mentioned are below 1 (suggesting they are better than optimal?). This seems like a mistake, and I would encourage the authors to review the text and make this consistent.\n\nThis is also present in section 4.1. The title mentions a 3/4 GMMS algorithm, while the theorem states 4/3 GMMS. \n\n\nAnother note for the introduction: in the Introduction section, it seems like the message isn't clearly conveyed. It talks about indivisble jobs vs data points, machines, features and atomic agents. It is talking about too many different kinds of things, which sends a confusing message. Since the paper deals with the job scheduling problem, sticking with one single narrative would be better for readers trying to understand the contributions of the paper.", "other_comments_or_suggestions": "NA", "questions_for_authors": "No questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QCrgoCdBR0", "reviewer": "Reviewer_u6td", "summary": "This paper addresses the maximin share (MMS) fairness problem in the context of job scheduling among groups of machines. . The study paper builds upon the work of Li et al. (NeurIPS 2023), which considered MMS fairness for groups of identical or related machines but left open the case where machines within a group are unrelated. The authors provide a polynomial-time algorithm that computes a 2-approximate MMS allocation in the case of heterogeneous machines using linear programming techniques. The paper proves that no algorithm can achieve better than a (2 - 1/n)-approximate MMS allocation. When machines within each group are identical, the paper improves the approximation ratio from 2 to 4/3.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and the constructive comments. In the following, we answer your questions. We will carefully address these questions in the revised paper.\n\n*Question*: On line 118, all $k$-partitions of $S$.\n\n*Answer*: Yes, it is a typo, which should be all $k$-partitions of $S$. We will fix this in the revised version.\n\n*Question*: On line 127, $n-1$ groups and $n$ in $MMS(S_k,n,c_{i,k})$.\n\n*Answer*: The two statements are indeed correct but might be a little unclear. To define $GMMS_i$ for group $G_i$, we first partition all items into $g_i$ bundles, where the $k$-th bundle $S_k$ is further allocated to $n$ (imaginary) agents, and each of them has the same valuation as $a_{i,k}$'s (like the classic definition of MMS with no groups).  We will carefully refine the statements and clarify this definition in the revised version. If it helps, we will include a figure to illustrate the partition and these notations.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not check thoroughly all the proofs but I checked the high level ideas and they seem correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Very related", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n-The paper is well-written and closes an open question that was left from a previous work. \n\n-The results are clean, with clear proofs and tight bounds. \n\n-Also, nice linear programming techniques are used that make the proofs quite novel. \n\n-The problem is well-motivated  and well-defined.", "other_comments_or_suggestions": "No", "questions_for_authors": "Right column, line 118: Do you mean all k-partitions of S?\n\nRight column, line 127: Is this correct: \"of her bundle with the other n−1 groups.\"?\nAlso, in the equation below MMS(Sk,n,ci,k) is n correct?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IPIFlvZzHm", "reviewer": "Reviewer_sFkZ", "summary": "The paper studies a variant of the fair scheduling problem. There are groups of machines and tasks which need to be scheduled on these machines. The paper focuses on the fairness objective of (group) maximin share (GMMS) and shows that a 2 approximation to GMMS can be computed in polynomial time. The paper additionally improves upon a result in the literature by showing that a 4/3 approximation to GMMS exists when the agents in each group are homogenous. The paper as a whole is purely algorithmic and theoretical.\n\n## update after rebuttal\n\nThank you for the rebuttal! I hope you take the improvement suggestions seriously!", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of the paper and the detailed and constructive comments. We will carefully revise the paper following these suggestions.\n\n\n*Comment*: On the theoretical proofs.\n\n*Response*: We thank the reviewer for the suggestion of restructuring the proofs.\nWe will focus more on explaining and visualizing the proof ideas in the main body (including adding examples and figures), possibly putting some proofs in the appendix.\n\n\n*Comment:* On the motivations and examples.\n\n*Response*: We thank the reviewer for the suggestion of including more motivation in the introduction and one example after the definition. We will follow this suggestion to revise the paper. In particular, we will expand the motivating example in the introduction to motivate our setting (e.g., a group’s workday can conclude when all members complete their assigned duties) and add one concrete example after the definition of GMMS. We will also include a figure to illustrate the partition and the notations in GMMS.\n\n\n*Comment*: On the other comments.\n\n*Response*:\n\n- We will rephrase the sentence \"There are two layers of objects, ..., with the objective of completing these jobs as early as possible\" and the corresponding paragraph. Basically, we want to explain how the items are first allocated to groups and how the group will further distribute the items among its members. We will avoid using ambiguous words like \"can be viewed as\".\n\n- We will use \\citet for inline citations.\n\n- We will add guidance at the start of each (sub)section.\n\n- Regarding the abbreviations of large, medium, and small groups, we used H and L to represent high and low costs. We understand the ambiguity and will revise this part accordingly. \n\n- We will also address the other grammar issues and carefully revise the writing in the revised version.", "claims_and_evidence": "The paper is purely theoretical and all claims are backed up by (for the most part understandable) proofs. All claims and evidence seems to be present and non-problematic.", "methods_and_evaluation_criteria": "N/A due to being a purely theoretical paper.", "theoretical_claims": "I checked the proofs, however, I could not follow the proof of Theorem 3.2 fully. For the most part the proofs are understandable, however, I believe that the authors could have put more work into making them easier to digest. In particular, I would have been a fan of (even more) visualization in the proofs. For instance, the delegation of the illustration in Theorem 3.1 does not really help the proof (and I would have preferred it to be reversed). I think in general, the paper would have been nicer, if the authors maybe removed one of the proofs and instead focused more on extending/explaining the other two.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is part of the well established literature on (indivisible) fair division. Specifically, it builds upon the work of Li et al. (Neurips 2023) in studying MMS for a group scheduling problem, answers one of their open questions and improves upon their obtained bound. On a more meta-level it contributes to the understanding of MMS for non-additive fair division instances and contributes a non-trivial non-additive model in which constant factor MMS approximations can be achieved. The results and studied fairness notions are very \"standard\" for the fair division literature and are a generalization of commonly studied objectives in the multi-machine scheduling setting.", "essential_references_not_discussed": "I cannot think of any.", "other_strengths_and_weaknesses": "In general, I like this paper. The question studied is mostly natural (one might question the relevance to the ML literature, however, ICML has opened up to more non ML papers in recent years, and has included a game theory track this year, so I believe this is okay). I however (as argued above) believe that the authors could have improved the clarity of their writing throughout the work. In particular, as this is not a paper on ML, I think to be properly appreciated by non-ML readers, I think the paper should have included more motivation for their setting and additionally guidance to the reader. I am not really a fan of not including any examples at all, just a single example after the model definition greatly improves the readability and clarity in my experience.", "other_comments_or_suggestions": "\"There are two\nlayers of objects, where a number of indivisible jobs (can be\nviewed as data points) need to be first allocated to n groups\n(viewed as clusters or super-agents). Each group controls a\nnumber of machines (can be viewed as features or atomic\nagents). Upon receiving a set of jobs, the group should\nfurther assign these jobs to its machines with the objective\nof completing these jobs as early as possible.\" I find this whole sentence construction to be quite confusing (in particular the \"can be viewed as\" parts)\n\n\"MMS fair allocation of chores and job scheduling problem\" -> \"MMS fair allocation of chores and the job scheduling problem\"\n\nI prefer the use of \\citet for inline citations. \n\n\"does not admit better than n approximation\" -> \"does not admit a better than n approximation\"\n\n\"Each group i contains\" -> This should probably be each group G_i\n\nI am not the biggest fan of just starting new sections with a theorem. A bit of guidance to the reader is always nicer.\n\nI find it confusing that you call the groups large, medium, and small, but abbreviate them as H, D, L with L not being large", "questions_for_authors": "I have no questions at the moment", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission addresses a two-layer fair allocation (scheduling) problem referred to as Group Maximin Share (GMMS). In the first layer, a set of indivisible items (jobs) is distributed among multiple groups. Within each group, there is a second layer of allocation to the machines (or “agents”) in that group. Each agent’s cost is determined by the makespan of the items it receives, and the group’s cost is defined as the maximum makespan among its agents. The paper seeks fair allocations that achieve a bounded approximation with respect to each group’s GMMS value.

The paper gives a 2-approximation in the hetrogeneous case and a 4/3 approximation in the homogeneous case.

The reviews pointed out strong points in the paper. (1) It solves a noteworthy open question from prior work (Li et al., NeurIPS 2023). Establishes new results with rigorous theoretical proofs and nearly tight bounds. Employs a linear programming approach and rounding ideas that are both interesting and non-trivial. Offers a meaningful theoretical contribution to the fair division (MMS/GMMS) literature.

Reviewers pointed out that the presentation could be 

Despite the minor concerns around presentation, all reviewers agree that the paper’s contributions are significant and that it resolves meaningful open questions with strong theoretical results.
Decision: Accept (poster)