| paper | d4-conf-ecai-2014-0124 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 1 is a computational result, and the proposed cohort model gives a precise continuous-mass question with the same \(9/8\) witness. But an atomless resident cannot change the distribution by an individual report, while making each bloc a strategic player changes the paper’s unit of strategy. That makes the cohort threshold a plausible extension, not a continuous analogue of the anchored result.
fails bit b-changes — the continuum limit changes the question
The proposed cohort question targets Theorem 1 only; it leaves the deterministic approximation algorithm and the randomized optimality and truthfulness results outside its scope.
The strongest case is a cohort version of the deterministic approximation barrier, anchored on Theorem 1, proved in this paper. It states that no deterministic strategyproof mechanism for heterogeneous two-facility location on a line can guarantee approximation ratio \(\alpha<9/8\). This is an approximation lower bound, not an NP-hardness result. Its witness has five agents at locations \(1,\dots,5\), with facility sets \(\{F_1\},\{F_2\},\{F_1,F_2\},\{F_2\},\{F_1\}\). The proof shows that a mechanism with ratio below \(9/8\) must choose optimal allocations on the truthful profile and on certain one-agent misreports, which makes it manipulable.
Here is a continuous-population question that preserves that mechanism-design issue at the level of population blocs. Let \(G=(V,E)\) be a line and \(F=\{F_1,F_2\}\). A type is \((x,S)\), where \(x\in V\) is a bloc’s known location and \(S\subseteq F\) is the set of facilities its residents want. An instance is a rational distribution \(\mu\) over these types. Each supported type represents a large, internally homogeneous bloc; its mass is its share of the population. A bloc may report a different \(S\), moving its whole mass to \((x,S')\). A deterministic mechanism maps the reported distribution to two distinct facility locations \(y_1,y_2\in V\). Its social cost is
\[ \mathrm{SC}_{\mu}(y_1,y_2) =\sum_{(x,S)}\mu_{x,S}\sum_{F_j\in S}d(x,y_j). \]
A solution is a mechanism that is strategyproof against every bloc’s report change and has approximation ratio at most \(\alpha\) on every instance. Call this problem Continuous Cohort HFL Threshold: determine the infimum such \(\alpha\).
A plausible regime is a line of towns or service districts. Each district has many residents with the same location and facility interests, and a local authority reports for the district. The resident population can be much larger than the number \(\tau\) of distinct district types: the paper’s five-type witness becomes a distribution with mass \(1/5\) on each type, regardless of how many residents each bloc represents. In that witness, the cost is the paper’s cost scaled by \(1/5\), so the ratio and the bloc’s incentives are unchanged. Theorem 1’s \(9/8\) obstruction therefore transfers exactly to this cohort problem. I would expect that approximation barrier to persist; in the programme’s terms this is closest to a hardness-transfer story, though it is an approximation impossibility rather than a complexity classification. It also raises questions about whether \(9/8\) is tight for cohort-strategyproof mechanisms and whether randomization removes the barrier.
The mirror keeps the paper’s line, two heterogeneous facilities, declared facility interests, social connection cost, and strategic facility reports. It covers Theorem 1 only; the paper’s randomized optimality and truthfulness results are outside this mirror’s scope.
The weak point is the strategic unit. In this formulation a district reports for its whole mass; the paper instead requires truthfulness for each individual agent. If the authors or a referee require individual-level strategyproofness, this is a cohort extension, not a literal continuous limit of Theorem 1. That caveat matters, but the extension still asks a concrete mechanism-design question in a plausible high-multiplicity setting, and its lower-bound anchor survives exactly under the stated cohort model.
Theorem 1 is the only anchor, and its lower bound depends on a named agent’s unilateral report changing the instance. A faithful atomless mirror would take a distribution \(\mu\) over types \((x,S)\), with location \(x\) public and facility interests \(S\) privately reported. One resident’s report leaves \(\mu\) unchanged, so the outcome cannot respond to that report. Strategyproofness becomes automatic, and the paper’s \(9/8\) argument loses its force.
Keeping finite populations does not supply a unique limit. If \(N\) residents share a type, one resident’s report changes its mass by \(1/N\). The same normalized distribution can describe populations of five or five hundred, with different unilateral perturbations. The distribution alone therefore does not specify the individual incentive constraints. Retaining \(N\) preserves those constraints, but leaves a finite-population problem; taking an atomless limit removes individual pivotality.
The proposed cohort repair does preserve the witness: five strategic blocs of mass \(1/5\) reproduce the paper’s five-agent instance, with social cost scaled by \(1/5\). That is a valid result for a model where each bloc reports in concert and evaluates its per-capita cost. Its strategic unit is a whole cohort, though, so it studies cohort or coalition strategyproofness. Treating a town authority as that unit could be a plausible governance assumption, but it changes the paper’s incentive question. Letting residents report individually returns to the atomless problem.
A threshold question for weighted cohorts could be worthwhile on its own. I cannot honestly rule that out across every plausible scenario. The strongest negative case is narrower: the \(9/8\) anchor does not establish a continuous mirror of this paper’s individual-strategyproofness result; its exact transfer relies on changing who acts strategically. The case against the broader cohort project is weak.
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.