| paper | d4-conf-sigecom-2010-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
The typed mass-allocation problem is a plausible extension that the authors would recognize. But the sole anchor in the positive case, Theorem 4.2, is a structural bound on feasible allocations; the paper’s computational result, Theorem 3.1, is expressly left outside the proposed mirror.
fails bit none — no continuous question survives
The unresolved point is whether the proposed general mass-allocation model is also meant to mirror Theorem 3.1, despite the case saying it does not. A concrete continuous question asking whether an \(O(\log m)\) approximation extends to typed populations would settle whether a computational anchor survives.
The proposed question covers the continuous version of the Theorem 4.2 lower-bound family; it leaves Theorem 3.1’s algorithmic upper bound and Theorem 5.1’s divisible-task result alone.
My lead is Theorem 4.2, proved in this paper. For its constructed instance, there are \(n\) jobs and \(m=n+\ell\) machines, with \(2^\ell=\log n/(4\log\log n)\). The first \(n\) machines have the paper’s triangular cost profiles; each of the remaining \(\ell\) machines has a uniform job cost of \(2,4,\ldots,2^\ell\). The unconstrained optimum makespan is \(1\). Theorem 4.2 says that for every partition of the jobs into bundles, every locally efficient assignment of those bundles has makespan at least \(2^\ell\). By Theorem 2.1, cited from Hartline et al. [15], local efficiency is equivalent to envy-free implementability. So this is a lower bound for any envy-free allocation, not just a limit on polynomial-time algorithms. It is an approximation barrier rather than an NP-hardness theorem.
I would mirror it with Continuous Envy-Free High-Multiplicity Makespan. An instance has machine types \(K\), job types \(J\), rational machine masses \(\alpha_k\) summing to \(1\), per-capita job supplies \(\beta_j\), and a cost \(c_{kj}\in\mathbb{Q}_{>0}\cup\{+\infty\}\) for type \(k\) to process type \(j\). A machine of type \(k\) must receive an integral bundle \(S\in\mathbb{Z}_{\ge0}^{J}\). Let \(x_{k,S}\) be the mass of type-\(k\) machines receiving bundle \(S\), and \(p_{k,S}\) their payment. Require \(\sum_S x_{k,S}=\alpha_k\) and \(\sum_{k,S}x_{k,S}S_j=\beta_j\). For every used bundle \(S\) on type \(k\) and used bundle \(R\) on type \(l\), envy-freeness requires \(p_{k,S}-\sum_j c_{kj}S_j\ge p_{l,R}-\sum_j c_{kj}R_j\). The objective is to minimize the largest load \(\sum_j c_{kj}S_j\) among bundles with \(x_{k,S}>0\). A solution is a feasible mass allocation and payments attaining that minimum.
For the Theorem 4.2 family, set \(\alpha_k=1/m\) for each machine type and \(\beta_j=1/m\) for each job type. This is the limit of \(q\) identical machines of each type and \(q\) copies of each job type: the population has \(N=qm\) machines and \(\tau=m\) types, so \(N/\tau=q\) grows without bound. A plausible setting is a large data-center fleet with many copies of each server performance profile processing repeated workload classes. Each machine still receives whole jobs; only the allocation across a type’s mass is fractional. Scaling the job supply with the fleet is part of making this high-multiplicity scheduling problem well-defined.
The concrete question for a prover is: for these masses and cost matrices, determine the minimum envy-free makespan and its asymptotic ratio \(R_n\) to the unconstrained optimum, which is \(1\). I expect the approximation barrier to persist, plausibly with \(R_n=\Omega(\log m/\log\log m)\). The proof’s load and job-count estimates are linear in the assigned bundles, and its reassignment argument appears to extend to moving equal masses of bundles between types. That suggests a Class-B-style persistence of the barrier, though it is not a complexity-class result. Further questions are whether the continuous optimum has a matching upper bound and whether the finite-machine characterization of envy-freeness by local efficiency extends to this mass-allocation setting.
The authors should recognize this as their same envy-free unrelated-machine makespan problem: the agents, costs, payments, integral job bundles, and objective all remain. The mirror covers only the indivisible-task lower-bound result of Theorem 4.2; it does not claim to mirror the divisible-task theorem or the paper’s algorithmic upper bound.
The weakest point is that Theorem 4.2 concerns one bundle per finite machine, whereas a continuous type may split its mass across several integral bundles. Its lower bound therefore does not automatically transfer: the mass-allocation version of the local-efficiency/payment characterization still needs proof. The construction also uses \(m\) distinct cost profiles as \(m\) grows, even though each scenario has many copies of each profile. I still find the mirror worthwhile because it isolates exactly whether the paper’s barrier comes from finite population size or from the growing variety of machine and job types.
The strongest case against the proposed mirror is that Theorem 4.2 is a bound on what envy-freeness permits, not a computational lower bound: it applies whether or not the allocation is found efficiently. Its proof also depends on a finite assignment of bundles to named machines and a permutation comparison. In the proposed continuum, each machine type can spread its mass across many bundles. The theorem’s argument therefore does not transfer just by replacing machine counts with masses; the continuous envy-free characterization and any corresponding lower bound would need to be established anew.
There is also a limitation in the witness family. It uses \(\Theta(n)\) distinct machine cost profiles and \(n\) job types. Replicating each profile \(q\) times creates high multiplicity, but the construction’s diversity still grows with its size. That makes it a weak demonstration that the lower bound is driven by population multiplicity, rather than by the detailed cost structure. A fixed catalog of server profiles would make a more convincing fleet scenario, but the paper’s lower-bound construction does not provide one.
These points weaken the claimed bridge from Theorem 4.2; they do not defeat the better mirror. A high-multiplicity scheduling problem with machine types, repeated workload classes, and integral bundles is a coherent computational question. Its continuous formulation could ask whether mass splitting changes the envy-free makespan or yields an efficient configuration-LP algorithm. Either answer would be informative. The paper’s own approximation algorithm in Theorem 3.1 also gives the programme a computational anchor beyond Theorem 4.2.
So the honest negative case is weak. The stated lower bound is not already a continuous-population result, and the fleet scenario is plausible. I can question whether this is the programme’s sharpest complexity mirror, but I cannot make a convincing case that no worthwhile continuous mirror exists.
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.