| paper | Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity |
| authors | Jiehua Chen, Martin Durand, Christian Hatschka |
| venue | IJCAI 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a finite set of organization types \(\Theta\), rational masses \(\mu_\theta\), machine counts \(m_\theta\), job multiplicities \(q_{\theta,p}\), and target \(T\), let \(\ell^{\max}_\theta\) be each type's optimal private-machine makespan. Does there exist a measurable nonpreemptive schedule on pooled atomless machine mass \(M=\sum_\theta \mu_\theta m_\theta\) that schedules the complete job bundle of almost every type-\(\theta\) organization by \(\ell^{\max}_\theta\) and has essential-supremum completion time at most \(T\)?
An atomless population of organization types \(\theta\), each carrying \(m_\theta\) machines and \(q_{\theta,p}\) nonpreemptive jobs of length \(p\), with pooled machine mass, measurable job intervals, type-specific individual-rationality deadlines, and an essential-supremum makespan objective.
Atomlessness removes the discrete machine-balancing and organization-packing structure that drives Theorem 2, reducing the mirror to cumulative fluid-capacity feasibility with type-specific deadlines.
fatal: False
The mirror directly covers Theorem 2 and gives a weaker population analogue of Theorem 3; it leaves the remaining propositions, corollaries, and parameterized results without separate continuous formulations.
My strongest mirror is a high-multiplicity version of the paper’s makespan problem. The natural agents are not individual jobs but organization units: many cloud tenants, university departments, or edge-computing sites repeatedly running one of a small number of workflow templates.
Let \(\Theta\) be a finite set of organization types. Type \(\theta\) consists of \(m_\theta\) identical private machines and \(q_{\theta,p}\) jobs of each processing time \(p\in\{1,\ldots,P\}\). The type is complete: organizations with the same \(\theta\) have identical machines and job multisets. The input gives a rational mass distribution \(\mu\) over \(\Theta\), with \(\sum_{\theta}\mu_\theta=1\). Thus \(\mu_\theta\) is the fraction of organizations of type \(\theta\), not a fraction of a job.
For every type, compute its local benchmarks \(\ell^\mathrm{max}_\theta\) and \(\ell^\Sigma_\theta\): respectively, the optimal makespan and optimal sum of completion times when its jobs use only its \(m_\theta\) private machines.
The continuum consists only of the population. Time remains the ordinary nonpreemptive scheduling axis. Formally, take an atomless population \(U_\theta\) of organizations of type \(\theta\), of measure \(\mu_\theta\), and a pooled machine population of total mass \(M=\sum_\theta\mu_\theta m_\theta\). A schedule assigns every job of almost every organization to one pooled machine and one nonpreemptive interval. The aggregate occupation of the machine population may not exceed capacity at any time. Individual rationality is imposed almost everywhere: every type-\(\theta\) organization must finish all its jobs by \(\ell^\mathrm{max}_\theta\), or must have the sum of its completion times at most \(\ell^\Sigma_\theta\), depending on the objective. No individual organization is allowed to be worse off merely because averages look acceptable.
My lead problem is \(\mathrm{Cmax\text{-}MOS}^{\mathrm{org}}_\infty\). Given \(I_\infty=(\Theta,\mu,(m_\theta,q_{\theta,p}))\) and a target \(T\), ask whether there is such a schedule satisfying individual rationality and with essential-supremum completion time at most \(T\). Equivalently, minimize the essential supremum of completion times.
This is a direct population mirror of the paper’s central scheduling question. It preserves shared machines, nonpreemption, organization-specific job bundles, the local-optimum baseline, and the requirement that every organization benefit. The only relaxation is that there may be a continuum of indistinguishable organization copies. A finite election with \(N\) organizations is recovered by taking masses \(n_\theta/N\); conversely, rational mass schedules can be approximated by cloning each type many times and rounding machine masses.
The anchor is Theorem 2, printed as “\(C_{\max}\)-MOS is FPT with respect to \(p_{\max}+k\) and therefore \(p_{\max}+m\).” This is an authors’ result, marked \((\star)\), with the full proof deferred to their full version; it is not merely cited, although its construction builds on Mnich and Wiese’s earlier single-organization algorithm.
The theorem’s structure is exactly what makes the mirror promising. Its proof groups jobs by processing time and by the organization’s local makespan phase, then uses balanced machine types and an ILP. In the population model, the number of phases is bounded by the number \(\tau=|\Theta|\) of organization types rather than by the total number of organizations. Integer variables counting machines become nonnegative mass variables.
For a fixed \(T\), one can describe the mirror by a configuration LP. A one-machine configuration \(K\) is a nonpreemptive sequence of type-labelled jobs whose type-\(\theta\) jobs finish by \(\min(T,\ell^\mathrm{max}_\theta)\). If \(a_{K,\theta,p}\) is the number of \(p\)-jobs of type \(\theta\) in \(K\), use a variable \(x_K\) for the mass of machines with configuration \(K\), with constraints \(\sum_Kx_K=M\) and \(\sum_Kx_Ka_{K,\theta,p}=\mu_\theta q_{\theta,p}\). Atomlessness lets the resulting job mass be disaggregated into complete organizations of the corresponding type, all meeting the same local deadline.
My expectation is Class A: an FPT algorithm parameterized by \(P+\tau\), and polynomial-time solvability for fixed \(P+\tau\), under the paper’s unary encoding. The pricing problem is a bounded one-machine scheduling problem with type deadlines. The resulting algorithm would be the continuous counterpart of Theorem 2, with high multiplicity replacing the paper’s parameter \(k\). Further questions are whether the dependence on \(\tau\) can be made polynomial, whether binary processing times cause pricing hardness, and how much additive error is needed when rounding the continuum schedule back to \(N\) discrete organizations.
A second, weaker but still credible mirror is \(\mathrm{C}\Sigma\text{-}\mathrm{MOS}^{\mathrm{org}}_\infty\). It has the same instance and schedule definition, but individual rationality requires, for almost every type-\(\theta\) organization, \(\sum_j C_{\theta,j}\le\ell^\Sigma_\theta\), while the objective is the normalized aggregate \(\mathrm{C}_\Sigma=\sum_\theta\int_{U_\theta}\sum_jC_{\theta,j}(u)\,du\). The decision question asks whether this value is at most a given rational \(B\).
This anchors on Theorem 3, also an authors’ result marked \((\star)\), with proof deferred to the full version: “\(C_\Sigma\)-MOS-DEC is NP-complete. It remains NP-hard even if \(n_{\max}=3\) and \(m_{\max}=2\).” The paper’s proof is a reduction from 3-PARTITION.
Here the continuous prediction is less secure, but my best case is that the intended repeated-template regime is Class A. The 3-PARTITION construction assigns individual integer jobs to exact triplet organizations. With an atomless population, one can use different whole feasible organization schedules for different masses of identical organizations. The jobs of each individual organization remain nonpreemptive and its own \(\Sigma\)-IR constraint remains intact; only the population is mixed. Thus the exact discrete partition may become a configuration/flow LP over complete organization patterns. With \(n_{\max}=3\), \(m_{\max}=2\), and unary processing times, the relevant pattern and pricing problems look amenable to dynamic programming or column generation.
This second mirror would therefore cover the paper’s NP-hard result while testing whether its hardness is genuinely population-integrality hardness. If the type support grows to include one exceptional type per 3-PARTITION item, hardness may return; that is a regime change, not a failure of the mirror. One could also ask whether a finite exceptional population preserves hardness against a large homogeneous background.
The main weakness is the \(\Sigma\)-objective. A naive aggregate constraint such as \(\sum_\theta\mu_\theta\mathbb E[C_\Sigma]\le\sum_\theta\mu_\theta\ell^\Sigma_\theta\) would be invalid: it could make half of a type better off and half worse off. The proposed problem explicitly requires individual rationality almost everywhere, so a genuine disaggregation theorem is needed. That issue is mild for Cmax, where each type has one common deadline, but substantial for CΣ, where several completion times must be coupled within each organization. Accordingly, the Cmax mirror based on Theorem 2 is my strongest case; the CΣ mirror is a worthwhile extension, but I would not present its tractability as established.
This case deliberately covers only the paper’s two central optimization problems, especially Theorem 2. It does not claim that every parameterized result in Table 1 has a continuous counterpart, nor does it continuize time, outcomes, or fairness axioms. The population itself is the continuous object, and the scenario—many repeated workflow organizations sharing machines—is a plausible high-multiplicity regime in which the authors’ original problem remains recognizably the same.
The strongest case against the proposal is that it changes the scarce resource, not merely the population. In the paper, machines and jobs are indivisible, and individual rationality applies to each organization’s complete schedule. The proposed variables \(x_K\), however, record only aggregate machine configurations and aggregate job counts. They do not by themselves produce a measurable assignment of complete job bundles to organizations.
For \(C_{\max}\), this defect can be repaired—but the repair exposes a degeneration. Every type-\(\theta\) organization has one common deadline \(d_\theta=\mathrm{OPT}\text{-}C^\theta_{\max}\). Once machines and organizations are atomless, the detailed organization structure disappears. Writing \(w_\theta=\sum_p p q_{\theta,p}\), \(M=\sum_\theta \mu_\theta m_\theta\), and \(d'_\theta=\min\{d_\theta,T\}\), feasibility reduces, apart from the elementary condition that every positive-mass job fit its deadline, to cumulative workload inequalities
\[ \sum_{\theta:d'_\theta\le d}\mu_\theta w_\theta \le Md \]
for each relevant deadline \(d\). Atomlessness supplies the required disaggregation into complete organizations. Thus the phases, finite machine types, and integer balancing that drive Theorem 2 have vanished. The resulting problem is fluid deadline scheduling, not a continuous version retaining the paper’s multi-organizational packing structure.
One can avoid that collapse only by retaining whole machine identities and indivisible organization copies. But then the configuration variables must remain integral, or integral at scale \(1/N\); the supposed atomless LP is no longer exact. The proposal therefore equivocates between a genuine high-multiplicity limit, in which the discrete packing disappears, and a discrete scheduling problem with many copies, in which the key integrality remains.
The \(C_\Sigma\) anchor is weaker. The proposed configuration LP is not valid for individual rationality: \(\sum_j C_{\theta,j}\le \ell^\Sigma_\theta\) must hold for almost every complete organization, not merely in expectation over its jobs. A valid formulation needs columns representing complete organization schedules and constraints coupling the jobs in each column. The proponent’s own warning identifies a substantive obstruction, not a minor technicality.
Theorem 3’s 3-PARTITION reduction also loses its essential object under an atomless population. An “integer job” of type \(p\) becomes divisible mass, so the exact triplet requirement is replaced by a fractional packing condition. Enriching the type with job identities does not fix this: positive mass of any type remains divisible. To preserve indivisible items, one must add atomic exceptional organizations, at which point the original discrete 3-PARTITION instance is simply embedded unchanged and the continuous population is irrelevant.
This is a real objection to the two mirrors as stated: the \(C_{\max}\) formulation collapses to fluid capacity scheduling, while the \(C_\Sigma\) formulation is not yet correctly specified and loses the reduction that motivates it. But the universal negative case is ultimately weak. The repeated-template scenario is a legitimate high-multiplicity regime, and the \(C_{\max}\) model can be made mathematically exact by a measurable disaggregation argument. Under the programme’s rules, that surviving Class A mirror is enough. The honest verdict is therefore not “no worthwhile mirror”: Theorem 2 has a credible continuous counterpart, while the proposed \(C_\Sigma\) counterpart requires substantially more work.
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.