| paper | Facility Location with Double-Peaked Preferences |
| authors | Aris Filos-Ratsikas, Min-Ming Li, Jie Zhang, Qiang Zhang |
| venue | AAAI 2015 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given rational \(b,c>0\), a rational finite-support society \(\mu=\sum_{j=1}^{\tau}p_j\delta_{x_j}\) with \(x_j\in\mathbb R\), and a target ratio \(\rho\), decide whether a polynomial-time randomized rule \(F\) exists that maps every such society to facility points \(y\in\mathbb R\), uses costs \(d(y,x)=c+\min\{|y-(x-b)|,|y-(x+b)|\}\), is truthful-in-expectation under every integral lift \(N\mu\) and one-agent report \(x\to z\), and satisfies \(\sup_{\mu}\mathbb E[SC_{\mu}(F(\mu))]/SC_{\mu}^{*}\le\rho\); if so, output such a rule.
Types are the finite support locations \(T=\{x_1,\ldots,x_{\tau}\}\) with masses \(p_j\); the facility remains an indivisible point \(y\in\mathbb R\), while the mechanism outputs a distribution over facility points. The objective is to minimize worst-case expected social-cost approximation subject to truthfulness across all finite integral lifts.
For the same normalized \(\mu\), different denominator-clearing population sizes \(N\) induce different one-agent deviations, so truthfulness must explicitly be required for every such \(N\) rather than left implicit.
fatal: False
The mirror covers M1's truthfulness and social-cost approximation in Theorems 1–2, with a natural maximum-cost extension using Theorem 3; it leaves deterministic characterizations, group-strategyproofness impossibility, and non-symmetric extensions untouched.
The strongest honest case is a genuine population mirror, but it fails the programme’s strict anchor gate: this paper contains no named NP-hardness, P-membership, FPT, W[1]-hardness, or comparable complexity theorem. Its numbered results are mechanism-design, truthfulness, impossibility, and approximation theorems. So the following is a substantive positive case, not a fully compliant computational-complexity case.
The natural mirror keeps the paper’s line, facility, and cost functions unchanged, and continuizes only the population. A type is a location \(x\in\mathbb{R}\), with the paper’s common parameters \(b,c>0\). Its cost is
\[ d(y,x)=c+\min\{|y-(x-b)|,\ |y-(x+b)|\}. \]
A society is a finite-support rational distribution \(\mu=\sum_{j=1}^{\tau}p_j\delta_{x_j}\), where \(p_j\ge 0\), \(\sum_jp_j=1\), and \(x_1<\cdots<x_\tau\). Thus \(p_j\) is the fraction of residents at location type \(x_j\). The intended regime is a large corridor, town, or collection of residential blocks with millions of residents but only \(\tau\) repeated location types, with \(\tau\ll N\). The repeated type story is plausible if residents of the same block have the same effective location and the same school-noise/parking trade-off.
The facility remains a single indivisible point \(y\); only the population is continuous. The two welfare objectives become
\[ SC_\mu(y)=\sum_jp_jd(y,x_j) \]
and
\[ MC_\mu(y)=\max_{j:p_j>0}d(y,x_j). \]
For a randomized mechanism \(F\), take expectations over its facility-location distribution. This retains randomization because it is part of the paper’s mechanism model; it is not the continuization being proposed.
The paper’s main positive anchor is Theorem 2, proved in this paper. It states that Mechanism M1 has approximation ratio \(1+b/c\) for social cost. M1 chooses a median agent \(x_m\), breaking ties by the smallest index, and outputs \(x_m-b\) or \(x_m+b\), each with probability \(1/2\). Theorem 1, also proved here, establishes that M1 is truthful-in-expectation.
The corresponding continuous problem is:
“Continuous Double-Peaked Social-Cost Mechanism Design.” Given \(b,c\) and a rational finite-support society \(\mu\), find a single randomized rule \(F\) mapping every such society to a distribution over facility locations, subject to truthfulness under the high-multiplicity lift, and output \(F(\mu)\) with approximation ratio at most \(\rho\).
The high-multiplicity truthfulness condition is precise. If \(N\) clears the denominators of \(\mu\), replacing one agent of type \(x\) by a report \(z\) changes the society to
\[ \mu'=\mu+\frac{1}{N}(\delta_z-\delta_x). \]
Truthfulness requires that the expected cost of a genuine type-\(x\) agent under \(F(\mu)\) is no greater than under \(F(\mu')\), for every report \(z\). A solution is therefore a succinct rule \(F\), its output on \(\mu\), and a proof that these inequalities hold for every one-agent mass transfer.
The natural candidate is the weighted-median rule
\[ F(\mu)=\tfrac12\delta_{q_\mu-b}+\tfrac12\delta_{q_\mu+b}, \]
where \(q_\mu\) is the lower weighted median. The finite proof of Theorem 1 lifts directly by expanding rational masses into repeated agents. The proof of Theorem 2 also becomes an integral proof: the median guarantees that an optimum lies between \(q_\mu-b\) and \(q_\mu+b\), and the additive error bound becomes \(SC_\mu(F(\mu))\le SC_\mu^*+b\). Since \(SC_\mu^*\ge c\), the ratio is at most \(1+b/c\). The paper’s lower-bound family becomes a sequence of finite-support distributions with a vanishingly small median type, so the supremum remains \(1+b/c\).
I would expect this problem to be Class A in the limited sense that the exhibited rule is efficiently computable: sort the \(\tau\) types, find the weighted median, and evaluate two finite sums. First-best social cost is also a finite piecewise-linear one-dimensional optimization problem. The more interesting follow-up is whether \(1+b/c\) is optimal among all truthful-in-expectation continuous rules, and how the answer changes when \(b\), \(c\), or the peak distances become type-dependent.
A second natural mirror uses Theorem 4, proved here. It states that every truthful-in-expectation mechanism has approximation ratio at least \(3/2\) for maximum cost, with no anonymity or position-invariance assumption. The paper’s proof uses two agents separated by a gap \(\lambda\); in the continuous model this is simply the society
\[ \mu=\tfrac12\delta_{x_1}+\tfrac12\delta_{x_2}. \]
The corresponding problem replaces \(SC_\mu\) by \(MC_\mu\) and asks for the best truthful-in-expectation rule. Theorem 4 transfers exactly through the \(N=2\) high-multiplicity lift. Theorem 3 supplies the matching candidate upper bound for M1, namely \(\max\{1+b/c,2\}\). Thus the continuous question is not trivial: it asks whether the \(3/2\) lower bound can be approached or attained by a population rule, and whether weighted-median mechanisms are optimal.
The original authors should recognise both mirrors as their problem. The line, the two peaks, the common \(b,c\), the facility action, the strategic reports, and the welfare objectives are unchanged. Only the electorate is represented by type masses. This is not a collision with a paper that already studies continuous populations: the paper’s input is a finite named profile \((x_1,\ldots,x_n)\). A weighted-mass theorem would be a discrete-to-continuous identity derived from that model.
The weakest point is that the continuous extension is mathematically quite easy. The paper’s proofs depend on median counting and finite sums, so much of the argument survives by replacing counts with masses. Moreover, individual deviations become delicate for an atomless population; the rational high-multiplicity lift is needed to prevent truthfulness from becoming vacuous. And because the paper has no qualifying complexity anchor, this case cannot honestly claim a ChoCo-style result about hardness dissolving, LP tractability, or a new complexity class. It is best presented as a plausible, concrete high-multiplicity mechanism-design mirror whose main value is to ask whether these approximation and truthfulness phenomena survive—and become computationally clearer—when the society itself is given as a distribution.
The strongest negative point is decisive at the programme level: this paper has no qualifying computational anchor. Its numbered results concern truthfulness, approximation ratios, mechanism characterizations, and impossibility. None asserts polynomial-time solvability, NP-hardness, parameterized complexity, or an analogous complexity classification. Thus the proposed mirrors are mechanism-design continuizations, not continuizations of a computational result of the paper.
Theorem 2 is the best rescue. The weighted-median version over a finite-support distribution is mathematically coherent, and I would not attack it by saying that its bound remains \(1+b/c\); that would be an impermissible objection based on the answer. The more fundamental problem is that the paper’s strategic model does not descend canonically to a population distribution.
A distribution \(\mu\) does not specify the granularity of an individual deviation. For the same \(\mu\), one may have \(N=2\) agents or \(N=2K\) agents. The deviation
\[
\mu\longmapsto \mu+\frac{1}{N}(\delta_z-\delta_x)
\]
is different in the two realizations, so truthfulness is not a property of \(\mu\) alone. If one passes to an atomless population, an individual has zero mass and cannot change \(\mu\) at all; literal individual truthfulness then becomes vacuous. If one retains a finite \(N\), one has merely encoded a finite high-multiplicity election. If one instead imposes truthfulness against positive-mass coalitions or arbitrary mass transfers, that is a new continuum mechanism-design model, not the model studied in the paper.
Theorem 1 therefore lifts only after making an additional, noncanonical choice about population granularity. The weighted-median welfare statement itself is a valid normalization of the finite proof, but it does not create a ChoCo-style computational question. Computing the weighted median and evaluating the two weighted sums is just evaluation of the already-given mechanism. Asking for the best truthful rule over all such distributions would be a new mechanism-design project rather than a continuous computational mirror of Theorem 2.
Theorem 4 is weaker still as a population anchor. Its lower-bound construction is explicitly a two-agent argument: one agent changes her report by an amount tied to the gap \(\lambda\). The proponent’s exact transfer uses \(N=2\), but a two-agent realization is not a high-multiplicity regime; it is simply the original finite instance written as a probability distribution. For large \(N\), the same unilateral deviation has mass \(1/N\), and the paper’s proof does not establish that its \(3/2\) argument survives that limit. In an atomless model the deviation has mass zero. A positive-mass-deviation formulation might recover a meaningful lower bound, but it changes the incentive notion and would require a new proof.
Theorem 3’s upper bound has the same status: a weighted-support analogue is plausible, but it is an averaged finite mechanism theorem, not a new computational result. If arbitrary distributions rather than finite supports are allowed, the model additionally needs an input representation and a convention for maximum cost—ordinary maximum, essential supremum, or support supremum.
So the negative case is strong against admitting this paper into the stated continuization programme: neither proposed anchor is a named computational result, and the strategic population model is under-specified in exactly the place where the continuum matters. But the universal claim that no worthwhile mirror exists in any scenario is not honestly defensible. Repeated residential blocks are a plausible high-multiplicity story, and a weighted-median population mechanism could be a sensible separate mechanism-design paper. The correct verdict is therefore: no compliant ChoCo mirror, despite a coherent but low-impact high-multiplicity reformulation.
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.