| paper | d4-conf-aaai-2015-0174 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 4.1 and Theorem 5.1 are computational lower bounds, but their force comes from unilateral reports by finite agents. In a nonatomic society, an individual report has zero effect; the proposed fix lets a positive-mass cohort deviate jointly, changing individual strategyproofness into coalition strategyproofness. The cohort model is precise and a cloud-office scenario is conceivable, but whether the authors would recognize that changed strategic unit as their problem remains unsettled.
fails bit b-changes — the continuum limit changes the question
The nonvacuous continuous incentive condition lets an entire positive-mass cohort report jointly, which is coalition strategyproofness rather than the paper's individual strategyproofness; the paper's cloud-office scenario does not establish that cohorts act as one principal.
fatal: True
The unresolved decision is whether a positive-mass cohort of identical offices can be treated as a strategic principal, making cohort-strategyproofness a recognized version of this paper's problem. Evidence that such offices submit demands jointly, or an explicit commitment to cohort deviations, would settle whether either lower-bound anchor survives.
The proposed mirror covers the approximation lower bounds in Theorem 4.1 and Theorem 5.1, conditional on cohort deviations. It leaves the deterministic and randomized upper bounds, their tightness results, and the strategyproofness and approximation analyses of the named algorithms unaddressed.
The strongest positive mirror I can defend is a mass-cohort version of truthful min-max facility location. Picture a cloud company with many offices at a modest number of network sites. Offices at the same site that need the same data are one complete type \(t=(v,S)\), where \(v\) is their graph vertex and \(S\subseteq\{F_1,F_2\}\) is their data request. The society is a rational distribution \(\mu\) over these types; \(\mu_t\) is the fraction of offices of type \(t\). With a fixed network and only four possible requests per site, the number of agents can greatly exceed the support size \(\tau\).
An allocation is a pair of distinct vertices \(x=(x_1,x_2)\), the locations of the two facilities. A type \(t=(v,S)\) has cost
\[
c_t(x)=\sum_{F_j\in S}d_G(v,x_j),
\]
and the objective is to minimize the maximum cost among types with positive mass:
\[
MC_\mu(x)=\max_{\mu_t>0}c_t(x).
\]
This preserves the paper’s path, two facilities, facility-set preferences, no-money setting, and worst-off objective. The mass is meaningful as population share, while the maximum objective protects even a small positive cohort.
Truthfulness needs an explicit co-modification. In a nonatomic population, an individual has zero mass and ordinarily cannot change the outcome, making individual strategyproofness vacuous. The substantive mirror I propose treats a cohort of identical offices as a reporting unit: for \(t=(v,S)\), any mass \(\lambda\in(0,\mu_t]\) may report another request \(S'\), changing the distribution to \(\mu'=\mu-\lambda\delta_t+\lambda\delta_{(v,S')}\). A mechanism is cohort-strategyproof if that cohort’s cost, evaluated at its true request \(S\), cannot fall after the report. This gives precise questions, though it is stronger than the paper’s individual-agent notion.
My lead anchor is Theorem 4.1, proved in this paper: there is no deterministic strategyproof algorithm for the paper’s facility-location problem with approximation factor \(\alpha<3/2\). The corresponding continuous question is whether there is a deterministic cohort-strategyproof mechanism for every rational \(\mu\) whose output always satisfies \(MC_\mu(x)\le\alpha\,OPT(\mu)\). The lower bound carries over: the theorem’s three-agent profiles are distributions with mass \(1/3\) on each of three types, and its individual deviations are permitted full-cohort deviations in this model. Thus no such mechanism can achieve \(\alpha<3/2\). I expect this obstruction to transfer from the finite problem; the next question is the best achievable ratio and whether an efficient mechanism attains it.
A second, separate anchor is Theorem 5.1, also proved here: no randomized strategyproof algorithm has approximation factor \(\alpha<4/3\). Its continuous counterpart asks for a randomized cohort-strategyproof mechanism, with expected individual cost obeying the incentive condition and expected maximum cost satisfying \(\mathbb E[MC_\mu(X)]\le\alpha\,OPT(\mu)\). The four-agent instances in the proof embed as distributions with mass \(1/4\) per type, so its \(4/3\) barrier transfers as well. Further questions include the optimal randomized ratio and whether randomization still improves on the deterministic bound under cohort incentives.
These are approximation lower bounds, not NP-hardness or polynomial-time classification results. The paper does not provide a named complexity-class hardness result to mirror. The scope here is only its two-facility, path, min-max, truthful-approximation results.
The weakest point is the strategic unit. The lower bounds transfer exactly only because the mirror permits a positive mass block to misreport; ordinary unilateral truthfulness for a continuum would not preserve the paper’s incentive constraints. A centralized office cohort could make that reporting model plausible, but the authors might regard it as a different mechanism-design problem. Also, because the objective is a maximum, the numerical values of positive masses do not affect the objective—only the support does. So this is a defensible continuous-population mirror, but a modest one: it preserves the population object and the approximation barriers, without showing that fractional masses unlock new optimization technology.
I would not dismiss the two anchors as noncomputational: Theorems 4.1 and 5.1 are named approximation bounds for truthful algorithms. The difficulty is that their strategic force comes from treating an office as an agent, while a continuous population makes each individual office negligible.
For Theorem 4.1, an individual office’s report does not change the distribution \(\mu\), so a mechanism that sees only \(\mu\) satisfies individual strategyproofness vacuously. The lower-bound example’s three types, each with mass \(1/3\), avoids that problem only by letting an entire type cohort report together. If each type instead contains many offices, a unilateral deviation moves only a small fraction of its mass; the theorem’s deviation no longer transfers. The same issue applies to Theorem 5.1: its four-agent example transfers as four mass blocks only if each block can coordinate its report.
The strongest repair is coherent: model many offices at each network site as a type \((v,S)\), and define a cohort-strategyproof mechanism that resists a positive mass of identical offices jointly changing their facility request. But that changes the strategic unit from an individual office to a coalition. A cloud company with centrally managed departments might make such coalitions plausible; the paper itself gives no reason to assume those departments act as one principal. Allowing arbitrary mass blocks to report also makes the model’s answer depend on which coalitions are admitted, a choice the paper’s individual-agent truthfulness does not settle.
There is a further mismatch with the population objective. For an allocation \(x\), the natural benchmark is
\[
MC_\mu(x)=\max_{t:\mu_t>0} c_t(x).
\]
It depends on the support of \(\mu\), not the masses: a tiny positive cohort counts as much as one comprising half the population, and its disappearance changes the benchmark abruptly. In the paper’s setting, duplicating offices at a site creates no congestion or other cost that would make their mass affect the allocation objective. The continuous weights can matter to a mechanism’s choices, but they do not make this optimization problem a continuous one.
This is not an “already done” objection: the paper studies finite agents, and it does not supply a continuous-population computational treatment. Nor do I think the continuous question has a known answer just because the original bounds exist. The negative case is narrower: the bounds transfer to a high-multiplicity society only under an added cohort-deviation model, and then they motivate a coalitional mechanism-design question whose strategic unit and mass-sensitive objective are not supplied by the paper.
That case is not airtight. Many identical offices at the same sites are a plausible population regime, and the resulting cohort problem could be worth studying. But I would not count either anchor as a strong continuous mirror without evidence that the authors would recognize cohort control as part of 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.