| paper | d4-conf-wine-2012-0009 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 5 and Theorem 3 bound the quality of the best envy-free allocation, so their obstruction holds even for an omniscient solver. They do not give an algorithmic approximation result or a computational hardness result under the stated criteria, and Theorem 1 is a characterization. The typed fleet optimization is plausible, but its computational question is inferred rather than anchored by a named computational result in this paper.
fails bit a — no named computational result to mirror
The proposed typed optimization reflects the paper's envy-free scheduling objective, but no result here establishes its computational complexity or a continuous-population bound; the remaining results are not computational anchors.
The strongest honest anchor is Corollary 5, proved in this paper. For its constructed cost matrix, with \(n\) jobs and \(m=n+\ell\) machines, where \(n=\tilde n/\log\tilde n+1\) and \(2^\ell=\log\tilde n\), every envy-free assignment has makespan \(\Omega(\log m)\), regardless of how the jobs are partitioned into bundles. The unconstrained optimum is \(1\), so this is a logarithmic lower bound on the envy-free makespan approximation. The proof uses Theorem 3, also proved here: every locally efficient assignment in that construction has makespan at least \(2^\ell=\log\tilde n\). The equivalence between envy-free implementability and local efficiency comes from Theorem 1, cited from Hartline et al. This is an approximation lower bound, not a named NP-hardness result.
I would mirror it as Typed Envy-Free Makespan\(_\infty\). An instance has a finite set \(T\) of machine types, a finite set \(J\) of task categories, rational type masses \(\mu_t\ge 0\) summing to \(1\), rational task supplies \(q_j\) per unit of machine population, and a processing cost \(c_{tj}\) for each type-task pair. Each machine gets an integral bundle \(k\in\mathbb Z_{\ge0}^{J}\); tasks remain indivisible, though a mass of machines can receive the same bundle. Let \(x_{t,k}\) be the mass of type-\(t\) machines receiving bundle \(k\). Feasibility requires
\[
\sum_k x_{t,k}=\mu_t
\quad\text{and}\quad
\sum_{t,k} k_jx_{t,k}=q_j\quad(j\in J).
\]
The load of that bundle on type \(t\) is \(c_t\cdot k\).
The problem is to find a feasible assignment and payments minimizing its makespan, subject to envy-freeness. More precisely, for every used pair \((t,k)\), there must be a payment \(p_{t,k}\) such that, for every other used pair \((u,k')\),
\[
p_{t,k}-c_t\cdot k\ \ge\ p_{u,k'}-c_t\cdot k'.
\]
The objective is to minimize \(\sup\{c_t\cdot k:x_{t,k}>0\}\). A decision version takes a threshold \(B\) and asks whether such an assignment and payments exist with makespan at most \(B\). This keeps the paper’s underlying question—envy-free assignment of indivisible task bundles to machines while controlling maximum load—rather than asking about a particular encoding.
A plausible regime is a large fleet of interchangeable machines in a fulfillment network or data center. Machines share complete processing-cost profiles, while standardized task orders recur at a rate proportional to fleet size. If there are \(N\) machines and \(\tau\) profiles, one can have \(N\gg\tau\), with task supplies scaling with \(N\). The authors should recognize the mirror: the agents are still machines, their types are their cost vectors, their bundles are still integral, and envy is still evaluated using payments and processing costs. My expectation is a transfer-style approximation obstruction when the number of types grows: the paper’s cost-profile and bundle structure seems capable of producing a logarithmic gap even when each profile is represented by many machines. That is a conjecture about the mirror, not a consequence of Corollary 5.
The useful next questions are whether a replicated construction gives \(EFOPT_\infty/OPT_\infty=\Omega(\log\tau)\), and whether a constant number of types admits a constant-factor guarantee or an efficient algorithm. The paper does not settle either.
The weak point is substantial: in the paper’s construction, the number of machine profiles is essentially the number of machines, \(\tau=m\). It gives no clone-invariant argument. In the continuous assignment, mass of one type can be spread across different bundles, which may remove the discrete obstruction. Establishing that the lower bound survives this mixing is the key proof the mirror still needs.
The proponent’s best anchor, Corollary 5, is a lower bound on the quality of any envy-free allocation, not a computational lower bound. Theorem 3 proves that every locally efficient assignment in the constructed instance has makespan at least \(2^\ell\); Corollary 5 translates this to an \(\Omega(\log m)\) gap for envy-free assignments. Theorem 1 supplies the link between envy-free implementability and local efficiency. None of these results says how hard it is to find an allocation, gives a running-time bound, or proves that an algorithm cannot achieve a better approximation. The gap persists even with unlimited computation because the better envy-free allocation does not exist.
The stronger typed mirror is coherent. A large fleet with recurring task categories and repeated machine cost profiles is a plausible high-multiplicity regime, and a mass distribution over integral bundles preserves the indivisible-task feature. One could ask for the minimum makespan among envy-free assignments, or ask whether such an assignment exists below a threshold. I would not dismiss that model as impossible, vacuous, or out of scope.
But that model poses a new computational optimization problem. The paper does not classify the complexity of finding its best envy-free allocation, either discretely or continuously. Its approximation ratio concerns the best allocation the fairness constraint permits, not the performance of an algorithm computing that allocation. So a continuous analogue of Corollary 5 would be a question about the price of envy-freeness in a population model. To turn it into the programme’s computational question, one must add an algorithmic problem that the paper’s named results do not establish.
The source result also gives no high-multiplicity parameterization: \(m\) counts machines in a particular cost matrix, while the continuous formulation needs to distinguish population size from the support size of machine types. That does not rule out a useful typed problem, but it underscores that the proposed computational target needs its own motivation and formal results; Corollary 5 does not supply them.
So the negative case is narrow. It defeats Corollary 5, Theorem 3, and the cited characterization as *computational anchors*: they are structural allocation results, not complexity results. It does not show there is no sensible continuous mirror. If the programme accepts a natural optimization problem inferred from a paper’s allocation objective, the typed fleet model survives and may be worth studying. My case against it depends on requiring the paper itself to anchor the computational question, rather than treating its broader allocation problem as sufficient.
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.