| paper | d4-conf-wine-2021-0041 |
| 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→other discrete result → its continuous mirror
Answer: Every deterministic anonymous strategyproof mechanism has an unbounded approximation ratio on the specified \(\gamma\)-stable societies; no finite computable bound \(\rho(N,k)\) exists. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(k\ge3\), \(\eta>0\), and a rational finite-support location distribution \(\mu\) with \(N\mu_x\in\mathbb Z_{\ge0}\) and \(\sum_x\mu_x=1\), whose expanded \(N\)-resident profile is \((\sqrt{2}-\eta)\)-stable, does a deterministic anonymous strategyproof facility mechanism achieve an approximation ratio bounded in \(N,k\), when a resident's report moves mass \(\frac1N\) from \(x\) to \(y\)?
Represent each location \(x\in\mathbb Q\) as a type with mass \(\mu_x=n_x/N\). Choose \(k\) facility locations, minimize per-capita cost \(\sum_x\mu_x\min_j|x-c_j|\), and require strategyproofness for a resident's \(1/N\)-mass report changes among declarations in the stable domain.
The selected mirror covers Theorem 3's low-stability deterministic impossibility; Theorem 4 offers a separate \(5\)-stable randomized \(2\)-approximation mirror, while Theorems 1 and 2 are outside the selected question.
The strongest honest case is a finite-support, high-multiplicity mirror, not a literal atomless one. This paper has no named theorem establishing membership in P, NP-hardness, FPT, or another standard complexity classification, and it gives no running-time bound for its mechanisms. Its useful anchors are results about strategyproof mechanisms and their approximation guarantees. I would treat those as computationally relevant mechanism-design results, while keeping that distinction explicit.
Take residents of a city choosing among a relatively small set of ideal public-service locations. A type is a location \(x\in\mathbb Q\): residents of that type have identical distance preferences and connection costs. Let \(N\) be the number of residents and let \(\mu_x=n_x/N\), with \(\sum_x n_x=N\). The regime is \(N\gg\tau\), where \(\tau=|\operatorname{supp}(\mu)|\). The authority chooses \(k\) facilities on the line, and the per-capita objective is
\[
\operatorname{SC}_{\mu}(\mathbf c)=\sum_x\mu_x\min_j|x-c_j|.
\]
A single resident’s misreport moves mass \(1/N\) from their true location \(x\) to a reported location \(y\):
\[
\mu'=\mu-\frac1N\delta_x+\frac1N\delta_y.
\]
This keeps unilateral incentives meaningful. It is also an exact compressed representation of the corresponding finite profile: the paper’s stability condition can be applied to the expanded list of \(N\) locations, including its zero gaps between co-located residents. Thus the society is represented by type masses while the outcome remains a choice of facilities.
My lead is 5-Stable Type-Mass Random Facility Location, mirroring Theorem 4 (proved here). The theorem states that Random is strategyproof and achieves approximation ratio \(2\) on \(5\)-stable instances of \(k\)-Facility Location on the line. The mass version asks: given \(k,N,\mu\), with rational location support and integer counts \(N\mu_x\), design a randomized anonymous mechanism whose output is a distribution over \(k\) facility locations; require truthful reporting for each resident among reports admitted by the paper’s cluster-separation verification, and require expected social cost at most \(2\operatorname{OPT}_{\mu}\) on every \(5\)-stable input. A solution is the mechanism and proofs of those two guarantees.
The direct mirror draws the optimal contiguous clusters of the expanded population, then selects one resident uniformly from each cluster and places a facility at that resident’s location. In the mass representation, it selects location \(x\) with probability proportional to the mass assigned to \(x\) in that cluster. It applies the paper’s \(1.6\)-separation check before allocating facilities. The output and utility are still exactly those of the paper’s mechanism; only repeated, identical residents have been aggregated. This is a credible candidate for Class A: weighted \(k\)-median on a line has a dynamic program over support intervals, and the sampling probabilities have rational descriptions. The further computational question is to give a bit-complexity bound in \(k,\tau,L,\log N\) for the compressed implementation, including ties and cases where a location’s mass meets a cluster boundary. Theorem 4 itself does not provide that bound.
A useful second anchor is Theorem 3 (proved here). It states that for every \(k\ge3\) and \(\delta>0\), any deterministic anonymous strategyproof mechanism for \((\sqrt2-\delta)\)-stable instances with \(n\ge k+1\) has unbounded approximation ratio. Its type-mass question is whether a deterministic anonymous mechanism family on rational location distributions, with one-resident deviations of size \(1/N\), can obtain the corresponding bounded approximation guarantee on the low-stability domain. Over the full family of finite profiles, the representation is exact: anonymity lets us aggregate identical locations, and expanding the masses recovers the original strategic instance. So this is a genuine transferred mechanism-impossibility boundary. It is not NP-hardness or a standard Class B complexity result. Also, Theorem 3 does not parameterize its lower bound by support size; whether the obstruction persists when \(N\gg\tau\) is a separate question, not a consequence I would claim from the theorem.
The authors should recognize the lead mirror: it keeps their objective, facility decision, optimal clustering, stability premise, and individual distance incentives. The distribution is over agent types; facility locations remain outcomes. Existing perturbation-stability and high-multiplicity work supports the modeling move, but does not itself settle these strategic guarantees.
The weak point is also central: in a strictly nonatomic population, one person’s report changes no mass, so individual strategyproofness becomes vacuous. The \(1/N\)-mass deviation preserves the paper’s unilateral incentive notion, but makes this a high-multiplicity extension with finite individual influence, not a literal atomless limit. That qualification does not erase the mirror; it defines the version that actually preserves the paper’s question.
The strongest mirror is a high-multiplicity city model: \(N\) residents share \(\tau\) ideal locations, the authority places \(k\) facilities, and one resident’s report moves mass \(1/N\). That is a sensible regime for facility location. The problem is that it preserves the paper’s strategic question only by preserving its finite, individual agents almost exactly.
For Theorem 4, expand each location’s mass into its \(N\) residents. The resulting profile has the same optimal clustering, stability condition, and individual incentives; total social cost is just \(N\) times per-capita cost. The weighted version of Random samples a location in each cluster in proportion to its mass. Its \(2\)-approximation and strategyproofness then follow from the paper’s theorem on the expanded profile. Computing the clusters on \(\tau\) support locations is a routine weighted dynamic program; the remaining task is to state its bit complexity and handle ties. That could be useful implementation work, but it leaves little new computational question for the programme.
Theorem 1 offers an even cleaner positive mirror: compute the optimal weighted clustering and place facilities at its weighted medians. Its strategyproofness claim transfers by the same expansion. The paper’s positive results concern which mechanisms satisfy incentive and approximation guarantees; they do not classify the complexity of a computational problem. A support-size running-time analysis might accompany the translation, but the paper’s claims themselves supply no new complexity landscape.
Theorem 3 transfers just as directly when the type masses are counts over \(N\): its impossibility applies to finite profiles with those counts. Restricting attention to \(N\gg\tau\) could raise a support-sensitive question the theorem does not settle. That would be a question about a restricted finite game, though. Each resident still changes mass by \(1/N\). As \(N\) grows, that change vanishes; allowing a positive mass to misreport instead asks about coalition manipulation, which changes the incentive notion.
An atomless version therefore loses the paper’s individual strategyproofness condition: one resident has measure zero and cannot change the outcome. The finite-mass version retains the condition and inherits the paper’s results by expansion. A proposed continuum mirror sits between those choices only by changing what counts as a deviation.
So the negative case is about research value, not model coherence. High multiplicity is a plausible description of facility-location populations, and the mass representation is legitimate. The weak point in arguing against the mirror is that the programme explicitly values that bridge. The case rests on the narrower claim that, for this paper, the bridge translates existing mechanism results into weighted notation and routine computation; it does not open a distinct continuous computational 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.