| paper | d4-conf-atal-2010-0306 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), rational costs \(c_{tj}\), per-agent workload bounds, per-capita job-supply bounds, and rational \(\alpha,\epsilon>0\), let each type \(t\) distribute its mass among feasible integral bundles \(B\), with \(x_{tB}\ge 0\) and \(\sum_B x_{tB}=\mu_t\). Each bundle has cost \(c_t(B)=\sum_j c_{tj}B_j\), and the resulting cost distribution is \(\nu_x=\sum_{t,B}x_{tB}\delta_{c_t(B)}\). With \(\widehat\Phi(\nu_x)=\frac{\pi}{2}\int_0^1\sin\!\left(\frac{\pi}{2}(1-u)\right)Q^\downarrow_{\nu_x}(u)\,du\), distinguish the promised cases \(\operatorname{OPT}\le\alpha\) and \(\operatorname{OPT}\ge\alpha+\epsilon\), where \(\operatorname{OPT}=\min_x\widehat\Phi(\nu_x)\).
A mass assignment over type-bundle pairs \((t,B)\), preserving integral bundles for individuals and rational per-capita supply constraints, minimizing the normalized limiting OWA of the induced individual-cost distribution.
A fixed finite set of unusually burdened reviewers has vanishing influence in the limit, narrowing the paper’s per-agent fairness motivation to burdens held by positive-mass groups.
fatal: False
The mirror covers Proposition 4’s fair assignment threshold problem, using Theorem 2’s limiting fairness rule; it leaves the paper’s axiomatic properties and numerical experiments unmirrored.
The strongest case is the paper’s Proposition 4, proved in this paper: for any fixed positive \(\alpha\), deciding whether there is an assignment with \(W(x)\le\alpha\) is NP-complete. Here \(x\) is the vector of agents’ total costs, sorted from largest to smallest, and \(W(x)=\sum_{k=1}^{n}\sin\!\left(\frac{(n+1-k)\pi}{2n+1}\right)x_{(k)}\). The authors prove the result by reducing from Partition: two agents split the items, and item \(j\) contributes the same size \(s(a_j)\) to either agent’s cost. A perfect partition gives equal costs \((\beta,\beta)\); any unequal split gives \((\beta-\varepsilon,\beta+\varepsilon)\) and a strictly worse \(W\).
My lead mirror is Infinite-Order Lorenz Mass Assignment. Consider a large workforce or review service in which many agents share the same cost profile and workload limits, while jobs come in recurring classes whose supplies scale with the population. An agent type \(t\) has mass \(\mu_t\), costs \(c_{tj}\) for job classes \(j\), and per-agent workload bounds. The type description includes all the costs and limits used by the problem. With \(N\) agents, the regime of interest has \(N\) much larger than the number \(\tau\) of positive-mass types. Job supplies are specified per capita.
An individual still receives an integral bundle. Let \(\mathcal B_t\) be the feasible bundles for type \(t\), and let \(x_{tB}\ge0\) be the mass of type-\(t\) agents receiving bundle \(B\). Require \(\sum_{B\in\mathcal B_t}x_{tB}=\mu_t\), and require each job class’s aggregate assignments to meet its per-capita supply bounds. An individual receiving \(B\) has cost \(c_t(B)=\sum_j c_{tj}B_j\). These bundles induce a cost distribution \(\nu_x=\sum_{t,B}x_{tB}\delta_{c_t(B)}\).
The paper’s Theorem 2 supplies the fairness rule: its finite-\(n\) OWA weights converge, after dividing \(W\) by \(n\), to the decreasing weight profile \(\sin(\frac{\pi}{2}(1-u))\). Thus define
\[
\Phi(\nu_x)=\int_0^1\sin\!\left(\frac{\pi}{2}(1-u)\right)Q^\downarrow_{\nu_x}(u)\,du,
\]
where \(Q^\downarrow\) lists costs from the worst off end of the population. The decision problem is: given rational type masses, costs, workload and job-supply bounds, and a threshold \(\alpha\), does there exist a feasible mass assignment \(x\) with \(\Phi(\nu_x)\le\alpha\)? A solution is the mass assigned to each integral bundle. Real mass can be split among bundles; no individual receives a fractional bundle. This is the paper’s cost-additive assignment problem with a population distribution and the limiting form of its own fairness objective.
I expect this mirror to be Class B: hardness transfers, though that is a conjecture for the mirror, not a consequence already proved by Proposition 4. The paper’s hardness comes from choosing bundles of items, and the program’s heuristic points toward hardness when the combinatorics live in the item set rather than in the number of agents. A prover could investigate configuration pricing or a scaled reduction. This is a recognizable assignment problem for the authors: it keeps their integral individual bundles, additive costs, feasibility constraints, and fairness criterion, while replacing repeated named agents with type masses.
The scope is Proposition 4’s fair assignment decision problem, not the paper’s axiomatic results or all its numerical experiments. The main weakness is that the Partition reduction has only two named agents. Replicating agents and scaling job supplies could allow mass to split in ways that destroy that particular reduction, so a new hardness proof is needed. There is also a bit-model detail: the limiting sine integral is a computable real, and exact threshold equality may require care. An additive-\(\varepsilon\) version is a natural companion question. The mirror remains worth asking because the population regime is plausible and the resulting complexity question is precisely whether that regime preserves the assignment problem’s item-side hardness.
Proposition 4 is the right anchor, but its hardness proof is a poor guide to the proposed continuum problem. It reduces Partition using two agents: the items must be divided between those two recipients so their costs match. In a population model with a positive mass of exchangeable agents, bundle patterns can be assigned to arbitrary fractions of each type. Scaling the job supplies with the population therefore convexifies the choice the reduction relies on. The proponent is right that the reduction does not automatically transfer; I see no basis for predicting that this mirror is NP-hard.
The stronger objection is about what survives as the same problem. In the paper assignment setting, each reviewer’s cost vector records their fit for particular papers. Those detailed profiles are likely to distinguish reviewers, leaving little repeated mass. A credible high-multiplicity version needs recurring reviewer profiles *and* recurring classes of papers, with supplies scaled alongside the workforce. That is a plausible new assignment regime, but it is a substantial change to the instances behind Proposition 4. The paper establishes hardness for individualized finite assignments; it does not establish that this changed regime retains the same computational bottleneck.
The proposed limiting fairness score is mathematically coherent: normalizing \(W\) by population size gives a decreasing weight on cost quantiles. But it shifts the fairness question toward population proportions. A finite set of unusually burdened individuals has vanishing influence in the limit; only a group with positive mass remains visible. That may be appropriate for a large workforce, but it weakens the link to the paper’s motivation of treating every agent equally. The required continuous question would also need a computational input model for the limiting objective, since its weights involve sine values and its cost distributions depend on bundle choices.
These points make the case against weaker than the case for. The paper has an explicit NP-completeness theorem, and recurring worker and job classes are a recognizable assignment problem. If continuous mixing makes the problem tractable, that is exactly the kind of result the programme seeks; if it remains hard, that is informative too. I cannot honestly conclude that no worthwhile mirror exists. The defensible negative case is narrower: Proposition 4 supplies no hardness transfer, and the best population model changes the regime enough that its value depends on whether the authors consider that recurring-class assignment setting central to their problem.
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.