| paper | d4-conf-sagt-2024-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(\tau,k,L\), with exact cost and optimal locations computable in \(O(\tau^2L^2+\min\{k,\tau\}\tau^2L+kL)\) bit operations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(k\) and a finite distribution \(\mu=\sum_{i=1}^{\tau}\mu_i\delta_{a_i}\) with ordered rational locations \(a_i\), positive rational masses \(\mu_i\), and \(\sum_i\mu_i=1\), compute facility locations \(y_1,\ldots,y_k\in\mathbb{R}\) minimizing \(\sum_{i=1}^{\tau}\mu_i\min_{j\in[k]}|a_i-y_j|\), together with the minimum cost.
A unit-mass society whose types are locations on the line, with each type carrying rational mass; the decision variables are the \(k\) facility locations, and the objective is mass-weighted nearest-facility distance. This mirrors the paper’s social-cost benchmark, not its strategic incentives.
The mirror covers the optimal social-cost facility placement characterized by Theorem 1. It leaves the paper’s truthfulness analysis and its finite-sample Bayesian approximation guarantees unmirrored.
The strongest honest mirror is narrow: the paper has no named theorem establishing a problem as NP-hard, in P, FPT, or similar. Its eligible anchor is Theorem 1, a formulation result proved in this paper. It says that for a finite profile \(x\), the optimal \(k\)-facility social cost equals the minimum \(W_1\) distance from the empirical measure \(\mu_x\) to a probability measure supported on at most \(k\) points; the support of any such minimizer gives optimal facility locations, and conversely. The paper uses this formulation in its later analysis.
Call the mirror Rational-Mass \(k\)-Facility Location on a Line. An instance is \(k\) and an ordered list of rational locations \(a_1<\cdots<a_\tau\), each with a positive binary-rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Find \(k\) facility locations \(y_1,\ldots,y_k\in\mathbb R\) minimizing
\[
\sum_{i=1}^{\tau}\mu_i\min_{j\in[k]}|a_i-y_j|.
\]
A solution is the facility locations and their minimum per-capita social cost. Each type is a location: agents at that location have identical access costs for every possible facility placement. Their mass is their fraction of the population. Rational masses can be realized by a finite electorate after scaling to a common denominator, so this is directly the high-multiplicity version of the paper’s underlying \(k\)-FLP.
A credible regime is planning public services for a large city represented by a modest number of demand locations or catchment points. Millions of residents may contribute mass to a few hundred or thousand types, while \(k\) remains comparatively small. The authors would readily recognize the objective as their facility-location problem: it preserves the line, the number of facilities, and each agent’s nearest-facility cost. It changes the population representation to aggregate mass.
I expect this mirror to be Class A. For the stated finite-support input, sort the locations, compute the cost of serving each contiguous interval from its weighted median, then use dynamic programming over intervals and facilities. This gives an exact algorithm polynomial in \(k,\tau,L\), for example \(O(k\tau^2)\) transitions with polynomial-bit arithmetic. That tractability comes from the one-dimensional structure; it is not a claim made by the paper.
The paper’s Theorem 3, also proved here, supports the population-limit bridge: for i.i.d. agents drawn from \(\mu\), the expected-cost ratio of a percentile mechanism converges to the ratio of the corresponding \(W_1\) projection costs. Theorem 5 proves that choosing percentiles \(F_\mu(y_j)\), where the \(y_j\) are optimal facility locations for the \(W_1\) projection, yields an asymptotically optimal percentile mechanism. These are useful support for the mirror, not separate complexity anchors. Theorem 3’s stated assumptions concern absolutely continuous distributions, whereas the complexity question above uses finite-support mass input.
This case covers the paper’s optimal \(k\)-facility benchmark and its mass-based formulation. It does not mirror the full finite-\(n\) Bayesian approximation analysis or settle how a continuum model should preserve meaningful strategic incentives. My weakest point is that the paper already reasons about distributions and proves an asymptotic connection to a continuous \(W_1\) problem. The mirror is therefore close to the paper’s existing mathematics, and its finite-support version is already tractable by familiar line \(k\)-median methods. Still, finite stochastic samples and a deterministic society given as masses are distinct formulations; Theorem 1 and the limiting result make the connection a result, not a reason to dismiss the mirror.
Natural follow-up questions are whether exact complexity bounds can be given for richer encodings of atomless distributions, how efficiently the optimal percentile vector can be computed from those encodings, and which facility constraints or cost functions preserve tractability.
The strongest case against starts with the proposed anchor: Theorem 1 is an identity between finite-profile facility cost and a Wasserstein projection, not a result about computational complexity. Theorem 3 gives an asymptotic cost ratio, and Theorems 5 and 6 characterize optimal percentiles. None establishes an algorithmic bound or hardness result. So the proposed rational-mass problem is a computational question one could ask about the paper’s benchmark, but it does not continuize a computational result the paper proved.
The more ambitious version—given a population distribution \(\mu\), find the best \(k\) facilities—is already the paper’s continuous optimization problem, \(\min_{\lambda\in P_k(\mathbb R)} W_1(\mu,\lambda)\). The paper studies its limit role, characterizes the optimum through percentile locations, and derives equations for those locations. It does not analyze running time, so this is not a strict novelty collision under the programme’s rules. But a complexity question needs an input representation: finite rational support gives weighted one-dimensional \(k\)-median, while an arbitrary atomless distribution has no finite description unless one specifies a restricted family or oracle model. The former is a sensible high-multiplicity problem; the latter is a new, representation-dependent question rather than a single mirror supplied by the paper.
There is also a gap between that benchmark and the paper’s strategic contribution. In a literal continuum, each individual has zero mass, so one person’s report cannot materially change the aggregate facility choice. A mass-based optimization mirror preserves social cost, but it does not preserve the strategic force of the percentile mechanisms. Keeping finite agents preserves those incentives, but then the society remains a finite sample—the setting the paper already analyzes.
That is the best negative case, but it is not airtight. A finite-support rational-mass \(k\)-facility problem is a coherent population model, and it preserves the paper’s social objective. The fact that its algorithm is familiar, or that its answer may be easy, is not a valid reason to reject it under the programme’s criteria. I can argue that the paper offers no named computational result to mirror and that its continuous optimization object is already characterized; I cannot honestly establish that no worthwhile mirror exists in any scenario.
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.