| paper | d4-conf-ecai-2016-0109 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed limit is a coherent high-multiplicity mechanism-design extension, and its small-support witness makes the regime plausible. But Theorem 6 is an approximation impossibility bound, and the ε-strategyproof sequence keeps inputs as finite-agent histograms; in a literal atomless society, individual strategyproofness becomes vacuous. No proposed anchor yields a continuous computational question that preserves the paper’s strategic problem.
fails bit b-changes — the continuum limit changes the question
The proposed question isolates the Min variant’s sum-cost objective and asymptotic strategyproof approximation ratio; it leaves the other variants and objectives outside its conclusion.
The strongest mirror is the paper’s Min variant, sum-cost objective, in a large town where residents live in a small number of housing cohorts. Many residents in a cohort share a location and the same optional preference: either bus stop serves them, so their walking cost is the distance to the closer stop. A few smaller cohorts may rely on one route. The number of residents can be large while the number of distinct location–preference types stays bounded.
Here is a precise high-multiplicity version. Put the street on \([0,1]\), and let a type be \(t=(x,p)\), where \(x\) is a public location and \(p\in\{\{F_1\},\{F_2\},\{F_1,F_2\}\}\) is the reported preference. A society is a finite-support measure
\[
\mu=\sum_{j=1}^{\tau}a_j\delta_{(x_j,p_j)},\qquad \sum_j a_j=1.
\]
For facility locations \(y=(y_1,y_2)\), define \(c_p(x;y)\) as the distance to the specified facility for a single preference, and the distance to the closer facility for optional preference. The population’s average cost is
\[
\mathrm{SC}_\mu(y)=\int c_p(x;y)\,d\mu(x,p),
\]
and \(\mathrm{OPT}(\mu)=\inf_y\mathrm{SC}_\mu(y)\). Average cost gives the same approximation ratios as total cost.
To retain the paper’s individual strategyproofness, let each individual have mass \(\epsilon=1/N\). A deterministic mechanism maps the reported mass measure to \((y_1,y_2)\). It is \(\epsilon\)-strategyproof if, for every individual of true type \((x,p)\), moving that individual’s mass from \(p\) to any other report \(q\) cannot lower their true cost:
\[
c_p(x;M(\mu))\le
c_p\!\left(x;M\!\left(\mu-\epsilon\delta_{(x,p)}
+\epsilon\delta_{(x,q)}\right)\right).
\]
The continuous problem is to determine
\[
\liminf_{N\to\infty}R_{1/N}(5),
\]
where \(R_\epsilon(5)\) is the infimum worst-case approximation ratio over deterministic \(\epsilon\)-strategyproof mechanisms on societies with at most five supported types. A solution is a lower bound and, if possible, a matching family of mechanisms. The five-type restriction captures the witness below while keeping the population-to-type ratio arbitrarily large.
My anchor is Theorem 6, proved in this paper. It states that for \(n+2\) agents in the Min optional-preference model with the sum-cost objective, for arbitrarily small positive \(\eta\), no deterministic strategyproof mechanism has approximation ratio below
\[
2-\frac{1}{n+1}-\frac{\eta}{n^2}.
\]
As \(n\) grows, this lower bound tends to \(2\). The theorem’s constructed societies have only a constant number of location–preference types: the large cohort is concentrated at one location, with a few distinguished agents at other locations. After normalizing total population mass, these are precisely bounded-support, high-multiplicity societies. This is an approximation lower-bound result, not a theorem classifying runtime as NP-hard or polynomial.
I expect the lower-bound side of this continuous question to transfer: the paper’s pivotal societies already have \(\tau\le 5\), and their one-agent deviations are exactly transfers of mass \(1/N\). The remaining question is whether a mass-based mechanism can asymptotically match the bound. The paper’s Theorem 5 gives a strategyproof \((n/2+1)\)-approximation for this same discrete objective, so it does not settle that upper-bound question as \(n\) grows. A weighted, mass-based mechanism with a constant limiting ratio would be a meaningful further result.
The authors should recognize the mirror: it keeps the line, two heterogeneous facilities, public locations, private preferences, the closer-facility cost, deterministic mechanisms, strategyproofness, and the sum-cost objective. It changes the population representation to fractions over a small number of types, which suits a town with many residents in repeated housing cohorts.
The soft spot is the incentive notion at the limit. In a strictly atomless society, one individual has zero mass and cannot change \(\mu\), so individual strategyproofness becomes vacuous. The definition above keeps an individual’s \(1/N\) influence and then asks for the large-\(N\) limit. That makes this a credible high-multiplicity continuous mirror; a referee who requires incentives for individuals in a literal atomless model may reject the strategic part. The lower-bound witnesses also place the pivotal agents in cohorts whose masses vanish as \(N\) grows, so the limiting distribution by itself may lose the feature driving Theorem 6.
Theorem 6 is the proponent’s strongest anchor, and its five-type witness is a sensible high-multiplicity regime. That supports the model’s plausibility, but it does not make this paper a strong ChoCo mirror: Theorem 6 is a lower bound on the approximation ratio of deterministic strategyproof mechanisms. The paper’s other numbered results likewise establish strategyproofness, approximation guarantees, or impossibility bounds. None studies the running time or complexity of a computational problem. A continuous version would therefore extend the paper’s mechanism-design results, but would not chart the computational landscape ChoCo is meant to investigate.
The incentive issue makes the proposed limit especially hard to treat as a continuous-population result. In an atomless model, one person’s report changes no mass, so individual strategyproofness is automatic. Giving each person mass \(\epsilon=1/N\) restores meaningful incentives, but then the inputs and deviations are finite \(N\)-person profiles encoded as histograms. The proposed \(\liminf_{N\to\infty} R_{1/N}(5)\) is a legitimate asymptotic distortion question; it is not an algorithmic question about a continuous society.
The witness also loses its nontrivial objective in the ordinary limiting distribution. After normalizing the line to bounded length, the \(n-2\) residents at the central location carry nearly all the mass, while the distinguished agents that drive the lower bound have masses \(1/(n+2)\). The measures converge to a point mass, where the optimal average cost is zero and the approximation ratio no longer captures the theorem. One can rescale to retain the vanishing contributions, but then the question is explicitly about rare-agent, finite-population asymptotics rather than the objective on the limiting society.
So the proponent has identified a coherent high-multiplicity extension, but the case for it as a ChoCo computational mirror is weak: preserving the theorem requires finite-agent incentives, and the remaining question concerns distortion rather than computational complexity. I would not claim that weighted strategyproof facility location is uninteresting; it may be worthwhile on its own terms. The honest negative case is that this paper offers little computational content for the continuization programme.
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.