| paper | Improved Approximation Ratio for Strategyproof Facility Location on a Cycle |
| authors | Krzysztof Rogowski, Marcin Dziubiński |
| venue | IJCAI 2025 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite location-type set \(X=\{x_1,\ldots,x_\tau\}\subseteq G\), a mass vector \(\mu\in\Delta(X)\), and a fixed anonymous, neutral, possibly randomized lifting convention \(\mathcal R\) to odd-\(N\) profiles, define \(M^{\mathcal R}_{1/2,\infty}(\mu)\) as the limit of the paper’s RD+PCD mixture on lifted profiles; determine whether the limit is single-valued, verify finite-lift strategyproofness, and compute or bound \(\sup_{\mu\in\Delta(X)} \operatorname{SC}_{\mu}(M^{\mathcal R}_{1/2,\infty}(\mu))/\operatorname{OPT}(\mu)\), in particular whether it is at most \(7/4\).
Types are ideal locations \(x_j\) on the cycle with masses \(\mu_j\); the lifted decision is an odd finite population and its lottery \(\ell\in\Delta(G)\), evaluated by the continuous utilitarian ratio \(\operatorname{SC}_{\mu}(\ell)/\operatorname{OPT}(\mu)\), with \(\mathcal R\) preserving the paper’s strategic semantics.
PCD has no canonical single-valued limit at tied masses such as μ = d δ_x + d δ_y, and the proposed finite-population lift does not itself choose or justify a symmetric convention.
fatal: False
The mirror covers Theorem 1 and the RD+PCD mechanism’s \(7/4\) utilitarian guarantee; it leaves the normalization and cycle-cutting lemmas, experimental evidence, Hypothesis 1, and unrelated literature results without separate mirrors.
The strongest positive case is narrow but real. This paper has no named NP-hardness, polynomial-time, FPT, or parameterized-complexity theorem. Its only serious anchor is Theorem 1, proved in this paper: for every odd number of agents on a cycle, there is a strategyproof mechanism with utilitarian approximation ratio at most \(7/4\). That is an approximation-theoretic computational result, not a complexity classification, but it gives a natural high-multiplicity mirror.
The mirror is a city or service system arranged on a circular route. A type is an ideal location \(x\in G=\mathbb{R}/\mathbb{Z}\); two residents have the same type when they have the same ideal location and therefore the same distance cost to every facility location. A society is a finite-support distribution
\[ \mu=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}, \]
where \(\mu_j\) is the fraction of residents whose ideal location is \(x_j\). The intended regime is \(N\) very large and \(\tau\ll N\): for example, millions of residents concentrated in a modest number of neighbourhoods, campuses, school catchment areas, or preferred meeting times around a circular service network.
A facility mechanism maps reported ideal locations to a lottery \(\ell\in\Delta(G)\). Its continuous utilitarian cost is
\[ \operatorname{SC}_{\mu}(\ell) = \int_G\int_G d(x,y)\,d\ell(y)\,d\mu(x), \]
and
\[ \operatorname{OPT}(\mu) = \min_{z\in G}\int_G d(x,z)\,d\mu(x). \]
The natural continuous analogue of Random Dictator is simply
\[ \operatorname{RD}_{\infty}(\mu)=\mu: \]
sample a resident according to population mass and locate the facility at that resident’s ideal point.
The other ingredient is the population limit of PCD. Here one must be careful. For an odd finite population, PCD uses the reports \(k\) positions before and after each agent, where \(k=(N-1)/2\). A continuous PCD rule should therefore be defined as a limit of the finite PCD rules on odd empirical populations converging to \(\mu\). A valid formulation must include a tie-breaking or refinement convention, or else quantify over all subsequential limits. This is not cosmetic: with atoms, different rounding sequences can affect the limiting PCD lottery.
The lead continuous problem is therefore:
Given a finite type alphabet \(X=\{x_1,\ldots,x_\tau\}\subseteq G\), determine the best mixture
\[ M_{\lambda,\infty} = \lambda\,\operatorname{RD}_{\infty} +(1-\lambda)\,\operatorname{PCD}_{\infty}, \qquad \lambda\in[0,1], \]
among mixtures whose PCD component has a specified finite-population-consistent lift. The objective is
\[ \inf_{\lambda\in[0,1]} \sup_{\mu\in\Delta(X)} \frac{\operatorname{SC}_{\mu}(M_{\lambda,\infty}(\mu))} {\operatorname{OPT}(\mu)}. \]
A solution consists of the value of \(\lambda\), an explicit lottery-valued rule for every \(\mu\), and a finite-population lift: for every odd \(N\), the lifted rule must be anonymous, neutral, peaks-only, and strategyproof on the corresponding finite profiles, and its lotteries must converge to the claimed \(M_{\lambda,\infty}(\mu)\) as empirical distributions converge to \(\mu\). This lift requirement prevents the continuum version from declaring strategyproofness merely because an individual has zero mass and therefore cannot change \(\mu\).
The paper’s mechanism is the candidate \(\lambda=\frac12\). Theorem 1 gives
\[ \operatorname{SC}_{\mu_N} \bigl(M_{\frac12,N}(b^{(N)})\bigr) \le \frac74\operatorname{OPT}(\mu_N) \]
for every odd finite population. Whenever the lifted mechanism converges and \(\operatorname{OPT}(\mu)>0\), passage to the limit gives the same \(7/4\) bound for the continuous society. Thus the theorem supplies a strong candidate certificate for the continuous problem, even though the paper itself does not state that limit theorem.
I would expect the fixed-mixture evaluation problem to be Class A. For a given finite-support \(\mu\), the RD cost is a finite sum, the optimal facility can be found by minimizing a piecewise-linear circular distance function, and the PCD component can be computed from sorted types and their masses once the refinement convention is fixed. The worst-case optimization over mass vectors is harder, but the paper’s own normalization, cycle-cutting, and boundary-profile arguments suggest a finite-dimensional extremal reduction rather than a fundamentally new source of hardness. The natural follow-up is whether the continuous worst-case ratio is at most \(7/4\), whether it is actually below \(\frac32\), and whether another \(\lambda\) or another strategyproof rule improves the bound. One can also ask for an algorithm parameterized by \(\tau\), together with an additive discretization guarantee for finite elections.
This mirror is plausible because it preserves the paper’s actual question: same cycle metric, same single-peaked location preferences, same randomized facility outcome, same strategyproofness requirement, and the same utilitarian approximation objective. Only the population representation changes from a named list of agents to masses of indistinguishable location types. It does not replace the problem by fractional facility locations or by a generic probability model.
The weakest point is the incentive and PCD limit semantics. Ordinary unilateral strategyproofness is vacuous for a nonatomic distribution, while PCD need not have a unique limit on atomic high-multiplicity societies. If a referee rejects finite-population consistency as the definition of the continuum mechanism, this mirror loses much of its force. The positive case therefore depends on treating the continuous object as a genuine high-multiplicity limit of the finite mechanisms, with the limiting convention made explicit. Subject to that condition, Theorem 1 supports a credible Class A continuization of this paper’s central result; it does not support a claim that the paper already contains continuous computational social choice.
The proponent has correctly identified the paper’s only plausible anchor: Theorem 1. I would not reject the paper merely because it lacks an NP-hardness or polynomial-time theorem; an explicit approximation mechanism can count as a computational anchor. The difficulty is that the proposed continuous object is not well-defined while preserving that theorem’s semantics.
The obstruction is PCD. For \(N=2k+1\), PCD assigns weight using reports \(k\) positions before and after an agent. That is an order-statistical operation, not a function of population masses alone. Consider
\[ \mu=\tfrac12\delta_x+\tfrac12\delta_y. \]
There are two sequences of odd empirical societies converging to \(\mu\): one with \(k+1\) agents at \(x\) and \(k\) at \(y\), and one with the counts reversed. For a two-point profile, PCD selects the majority report, so the first sequence converges to \(\delta_x\), while the second converges to \(\delta_y\). Thus the same continuous society has different PCD limits. The problem is not an arbitrary tie-breaking detail: \(\mu\) has no exact odd clone at all, and the two legitimate approximations differ by only \(O(1/N)\).
The proponent’s repairs do not restore a direct mirror. Quantifying over all subsequential limits makes PCD set-valued rather than lottery-valued. Splitting the boundary contribution, randomizing the rounding, or choosing a preferred side defines a new continuous mechanism with an extra convention absent from the paper. Extending the finite model to even populations creates the same issue in another form. Such variants may be researchable, but they are extensions of PCD, not consequences of Theorem 1.
The incentive condition has a second, independent problem. On a genuine distribution \(\mu\), one individual has zero mass, so changing their report leaves \(\mu\) unchanged. Every distributional rule is therefore strategyproof under the literal unilateral definition. The proposed finite-population lift avoids vacuity only by retaining \(N\), oddness, rounding, and the finite mechanism itself. The resulting object is a family of finite mechanisms indexed by \(N\), not a strategyproof mechanism whose input is \(\mu\). Replacing unilateral deviations by positive-mass or type-level deviations would be meaningful, but it changes the strategic problem: Theorem 1 proves no such coalition or mass strategyproofness.
The strongest rescue is to abandon PCD and ask for the asymptotically optimal strategyproof mechanism on a high-multiplicity cycle. That is a legitimate new question, but it is not anchored by this paper. The paper proves only that one finite mechanism has ratio at most \(\frac74\); it does not characterize optimal mechanisms, derive a continuous objective, or provide a computational problem over mass vectors. The proposed optimization over \(\lambda\) is manufactured by the mirror rather than supplied by the paper. The theorem itself would merely pass to whichever subsequential limits happen to exist.
The negative case is therefore not universal. Agents are anonymous, the objective is additive, and a city with many residents sharing neighbourhood-level ideal locations is a credible high-multiplicity regime. A carefully specified asymptotic or coalition-based extension could be worthwhile. What the evidence defeats is the stronger claim made by the proponent: Theorem 1 does not yield a canonical continuous Class-A mirror preserving both PCD and strategyproofness. I would record this as “no direct mirror; potentially worthwhile extension,” not as a defensible absolute verdict that no continuous mirror exists.
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.