| paper | Proportionally Fair Makespan Approximation |
| authors | Michal Feldman, Jugal Garg, Vishnu V. Narayan, Tomasz Ponitka |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given rational machine-type masses \(\mu_i\) summing to one, rational job-class supplies \(\lambda_j\), and costs \(c_{ij}\) satisfying \(\sum_j \lambda_j c_{ij} = C\) for every type \(i\), choose a finite-support flow \(x\) over integral configurations \(b \in \mathbb{Z}_{\ge 0}^r\) with \(\sum_b x_{i,b} = \mu_i\) and \(\sum_{i,b} b_j x_{i,b} = \lambda_j\), together with payments \(p_{i,b}\), minimizing makespan \(\max\{\sum_j c_{ij} b_j : x_{i,b} > 0\}\), subject to proportionality for every used \((i,b)\): \(\sum_j c_{ij} b_j - p_{i,b} \le \sum_{u,b'} x_{u,b'}(\sum_j c_{ij} b'_j - p_{u,b'})\), and, for the normalized anchor, attaining the unconstrained optimum.
High-multiplicity unrelated-machine scheduling: machine types have mass \(\mu_i\) and complete cost vectors \(c_i\); job classes have supplies \(\lambda_j\); integral per-machine configurations flow through \(x_{i,b}\); makespan is optimized and type/configuration payments certify proportionality.
Theorem 3 does not itself provide a polynomial-time method for finding the exact proportional schedule; solving the succinct configuration-flow problem is new computational work rather than a transferred algorithm.
fatal: False
The mirror covers Theorems 1 and 3 for proportional makespan scheduling in general and normalized settings. It leaves the lower bound in Theorem 2, envy-freeness results, approximate envy-freeness, and the goods-allocation results unaddressed.
There is a credible continuous mirror, and I think the strongest version is an extension of the paper’s unrelated-machine scheduling model into a high-multiplicity fleet regime. It is not merely “fractional scheduling”: machines remain the population, jobs remain indivisible, and only the distribution of machine types becomes continuous.
The plausible scenario is a large cloud or edge fleet. There are many machines but only a small or moderate number of hardware types. Machines of the same type have the same complete processing-cost vector over a recurring catalogue of job classes. Job supplies scale with fleet size: if the fleet has mass one, \(\lambda_j\) denotes the number of jobs of class \(j\) per unit machine mass. Thus the number of machines and jobs both grow, while the number of distinct machine and job types remains much smaller.
Formally, let \(i\in[\tau]\) index machine types, with rational mass \(\mu_i\), \(\sum_i\mu_i=1\), and let \(j\in[r]\) index job classes. A machine of type \(i\) processes one job of class \(j\) at cost \(c_{ij}\). A configuration is an integral vector \(b\in\mathbb Z_{\ge0}^r\), meaning that one individual machine receives \(b_j\) whole jobs of class \(j\). Let \(x_{i,b}\) be the mass of type-\(i\) machines receiving configuration \(b\). Feasibility is
\[ \sum_b x_{i,b}=\mu_i\quad\text{for every }i, \qquad \sum_{i,b}b_jx_{i,b}=\lambda_j\quad\text{for every }j. \]
The load of such a machine is
\[ \ell_i(b)=\sum_j c_{ij}b_j, \]
and the makespan is \(L(x)=\max\{\ell_i(b):x_{i,b}>0\}\).
Payments are allowed exactly as in the paper. A payment \(p_{i,b}\) is attached to a machine of type \(i\) receiving configuration \(b\), with no sign restriction. Proportionality requires, for every used \((i,b)\),
\[ \ell_i(b)-p_{i,b} \le \sum_{u,b'}x_{u,b'}\bigl(\ell_i(b')-p_{u,b'}\bigr). \]
The right-hand side is machine type \(i\)’s average net cost for the whole allocation. This is precisely the finite-machine definition after normalizing the population mass to one.
This has an exact rational-clone interpretation. If \(\mu,\lambda\), and \(x\) are rational, choose \(M\) clearing all denominators. Create \(M\mu_i\) machine clones of type \(i\) and \(M\lambda_j\) individual jobs of class \(j\); assign \(Mx_{i,b}\) clones configuration \(b\). Every job is still assigned whole to one machine. Conversely, every such finite cloned schedule aggregates to \(x\). Loads, payments, proportionality, and makespan are preserved. This is the crucial reason the construction is a genuine high-multiplicity mirror rather than an unrelated fractional allocation problem.
My lead anchor is Theorem 3, proved in this paper: “There is a proportional mechanism for the job scheduling problem over normalized instances \(N\) that attains the optimal makespan.”
The corresponding continuous problem is:
Normalized Proportionally Fair Makespan\(_\infty\). The input is rational \(\mu\), rational job supplies \(\lambda\), and a rational cost matrix \(c\) satisfying
\[ \sum_j \lambda_jc_{ij}=C \quad\text{for every machine type }i. \]
Among all feasible configuration flows \(x\), let \(\mathrm{OPT}_\infty\) be the minimum makespan without a fairness requirement. The task is to output a feasible \(x\) and payments \(p\) such that \(x,p\) are proportional and \(L(x)=\mathrm{OPT}_\infty\). A solution is the configuration flow together with the payment for every used type/configuration pair, certifying both feasibility and proportionality.
This is a faithful continuation of the normalized theorem. After clearing denominators, the input becomes a finite normalized scheduling instance with many identical machine and job clones. Theorem 3 supplies a proportional optimal schedule and payments; aggregation gives a solution to the continuous problem. The reverse direction also holds, so the mirror is not making the jobs divisible.
I expect this problem to be Class A in the intended finite-catalogue regime. For a fixed makespan threshold \(L\), feasibility is a configuration LP whose columns are integral bundles \(b\) satisfying \(\ell_i(b)\le L\). Proportionality can be handled through the paper’s mean-efficiency characterization, which extends to
\[ \sum_{i,b}x_{i,b}\ell_i(b) \le \sum_i\mu_i\sum_j\lambda_jc_{ij}. \]
The relevant pricing problem is an integer optimization over a bundle. With a fixed number \(r\) of job classes, this is fixed-dimensional integer optimization and is a natural target for column generation or separation-based convex programming. Theorem 3’s proof suggests that among makespan-optimal allocations, a minimum-total-cost choice supplies the required proportionality certificate.
The computational boundary is also meaningful. If the number of job classes is unrestricted, pricing becomes knapsack-like and may remain hard. That would not refute the mirror: it would show that the continuous population removes clone multiplicity but not the combinatorics of integral job configurations. Questions generated by the lead problem include whether exact optimization is polynomial for fixed \(r\), whether it is FPT in \(r\), and whether normalization simplifies the pricing problem beyond the generic configuration-LP bound.
A second, broader anchor is Theorem 1, also proved in this paper: “There is a proportional mechanism for the job scheduling problem over general instances \(C\) that gives a \(3/2\)-approximation to the optimal makespan.”
The corresponding problem is:
General Proportional Makespan-\(3/2_\infty\). The input is rational \(\mu\), rational job supplies \(\lambda\), and an arbitrary nonnegative rational cost matrix \(c\). Let \(\mathrm{OPT}_\infty\) be the unconstrained minimum continuous makespan. The task is to output a feasible configuration flow \(x\) and payments \(p\) satisfying proportionality and
\[ L(x)\le \frac32\,\mathrm{OPT}_\infty. \]
Again, the solution is the integral-configuration flow plus its payment certificate.
Theorem 1 transfers through the same clone dictionary: apply it to a sufficiently large finite clone instance and aggregate the resulting allocation. The anti-diagonal mechanism is particularly compatible with this interpretation because it operates on bundles and machine assignments, and its proportionality proof is exactly a mean-efficiency argument.
The computational qualification matters. Theorem 1 itself is an existence theorem whose proof takes an optimal allocation as the initial allocation \(B\). The paper’s Remark 4.1 explains that the mechanism is polynomial given \(B\), and that combining it with the cited 2-approximation for unrelated-machine scheduling yields a polynomial-time 3-approximation, not a named polynomial-time \(3/2\)-approximation. I would therefore not claim that the paper already proves the continuous problem is in P. The natural expectation is Class A when the configuration pricing problem is tractable, with unresolved or inherited hardness when the job-type dimension is part of the input.
I would deliberately not anchor on Theorem 2. Its \(3/2\) lower-bound construction relies heavily on forcing each of \(m\) machines to receive exactly one job. Naively cloning machines and jobs allows several low-cost jobs to be packed onto one clone, so the induction in the proof no longer automatically survives. Preserving that lower bound would require adding a capacity condition not present in the paper. That is a real limitation, not something to hide.
My weakest point is therefore that the mirror needs joint scaling of machines and job supply, plus a configuration-flow representation. A referee could say that this is an extension rather than the literal fixed-\(n\), fixed-\(m\) problem in the paper. The answer is that the extension is exactly the high-multiplicity regime: machine types are complete cost profiles, job classes are genuinely identical, every feasible continuous point clears to a finite cloned instance, and indivisibility is retained at the individual level. The authors should recognize it as high-multiplicity unrelated-machine scheduling with proportional payments.
So the positive case is strong but scoped: the paper’s two central proportional-makespan results admit a precise, author-recognizable population mirror. The normalized result is the lead because it yields an exact proportional optimum; the general result gives a \(3/2\) continuous approximation target. The open computational work lies in the configuration pricing problem, not in inventing a new fairness notion.
The strongest negative case is that neither anchor is actually a computational result of the sort ChoCo is meant to continuize.
Theorem 3 is an existence theorem: it says that some proportional optimal allocation exists on normalized finite instances. It does not give a complexity bound for finding that allocation. The proponent’s exact continuous problem therefore adds the computational content. With rational data, its configuration-flow formulation is equivalent to a high-multiplicity scheduling instance after clearing denominators. That is a legitimate problem, but it is a new succinct scheduling problem, not a continuous version of a computational theorem proved in the paper. The fairness part is already settled existentially by Theorem 3; the remaining difficulty is computing an optimal high-multiplicity schedule.
Theorem 1 is a weaker anchor still. Its \(3/2\) mechanism is polynomial only when supplied with an initial allocation \(B\). To obtain the stated ratio, \(B\) must be optimal, which is NP-hard to compute. The paper’s actual unconditional algorithmic consequence is a polynomial-time \(3\)-approximation, not a \(3/2\)-approximation. Applying the mechanism to a large clone instance does not yield a polynomial continuous algorithm either: denominator clearing may produce exponentially many clones. Thus the proposed \(3/2\) continuous problem is again a new high-multiplicity optimization problem, not a continuation of an algorithmic result from the paper. The anti-diagonal mechanism also operates on individually indexed machines and bundles; it has no intrinsic type-level operation until one chooses a finite lifting or supplies a separate configuration formulation.
There is a further mismatch in emphasis. Once payments are unrestricted, proportionality is equivalent to mean efficiency. In the normalized regime, the paper’s argument says that an optimal allocation can be selected to satisfy this scalar aggregate inequality. Consequently, the continuous formulation does not expose a new population-level fairness computation; it asks for an optimal configuration schedule and then attaches the payment certificate. That may still be a useful high-multiplicity scheduling question, but its value comes from the new scheduling formulation, not from continuizing the paper’s fairness theorem.
This is not, however, a decisive rejection of the proposed mirror. The machine-fleet story is genuinely plausible. A machine type can be its complete processing-cost vector, job classes can be recurring identical jobs, rational configuration flows clear exactly to finite cloned schedules, and the objective does not depend on the identity of machines within a type. The configuration LP and its pricing problem are precisely the sort of computational boundary ChoCo wants to study. Calling this “merely fractional scheduling” would be a mistake.
So the honest negative verdict is limited: the paper itself is a weak computational anchor, and the proponent overstates what Theorems 1 and 3 transfer algorithmically. But I cannot honestly sustain the universal claim that no worthwhile continuous mirror exists. The normalized high-multiplicity machine-fleet formulation survives the programme’s admissibility test, and probably survives the substantive-interest test as well.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.