| paper | d4-conf-atal-2016-0031 |
| 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: For \(T=3\), \(\rho_T(\delta)=1/(2\delta)\) when \(0<\delta\le1/4\), and \(\rho_T(\delta)=1/\delta-2\) when \(1/4<\delta\le1/3\). For \(T\ge4\), the successive formulas are \(3/(4\delta)-1\) on \(0<\delta\le1/6\), \(1/\delta-5/2\) on \(1/6<\delta<1/5\), \(1/(2\delta)\) on \(1/5\le\delta\le1/4\), and \(1/\delta-2\) on \(1/4<\delta\le1/3\). The supremum is not attained exactly when \(T\ge4\) and \(0<\delta\le1/6\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
For feasible \(\tau\ge 3\) and rational \(\delta>0\), let \(S\subseteq\mathbb{Q}\) have \(3\le |S|\le\tau\), and let \(\mu\) be a rational distribution on \(S\) with \(\mu_x\ge\delta\) for every \(x\in S\). Let \(q_\mu\) be the lower weighted median, \(a=\min S\), and \(b=\max S\); define the mass version of MedianFurthest to return \(\{q_\mu,a\}\) when \(q_\mu-a>b-q_\mu\), and \(\{q_\mu,b\}\) otherwise. Determine the exact value of \(\rho_\tau(\delta)=\sup_\mu \frac{\sum_{x\in S}\mu_x\min_{f\in\mathrm{MF}(\mu)}|x-f|}{\min_{p,q\in\mathbb{R}}\sum_{x\in S}\mu_x\min\{|x-p|,|x-q|\}}\), and give rational distributions attaining or approaching the supremum.
Types are resident locations \(x\in\mathbb{Q}\), each carrying mass \(\mu_x\); the decision is a pair of facility sites in \(\mathbb{R}\). Compare the mass weighted median plus farther extreme rule with the optimal pair using average distance to the nearer facility, over societies with at most \(\tau\) types and each positive mass at least \(\delta\).
This is a restricted worst-case analysis of a fixed rule, and related aleatory-demand work studies approximation and a two-facility extension ([arXiv abstract](https://arxiv.org/abs/2409.18817)); that may narrow the novelty, but it does not answer this \((\tau,\delta)\) frontier or invalidate the mass extension.
fatal: False
The mirror covers Theorem 6's social-cost approximation analysis for MedianFurthest. It leaves the paper's truthfulness and verification results, including Theorems 2, 3, and 7, and its lower bounds outside the mirror.
The strongest honest mirror I see is the paper’s approximation result for social-cost facility location, not its truthfulness results.
The anchor is Theorem 6, proved in this paper (the text gives a proof sketch). For \(K=2\), MedianFurthest places one facility at the median reported location and the other at whichever extreme, leftmost or rightmost, is farther from the median; ties go to the right. The theorem proves that its social cost is at most \(3n/4\) times the optimal social cost.
A plausible high-multiplicity setting is residents choosing among public facilities along a corridor. A resident’s type is their location \(x\), which completely determines their connection cost. Many residents share each of \(\tau\) locations, with \(\tau\ll n\). The continuous society is a rational probability distribution \(\mu\) over those locations. The decision is a pair of facility sites \(F\subseteq\mathbb R\), and the objective is average distance to the nearer site:
\(\mathrm{SC}_\mu(F)=\sum_x\mu_x\min_{f\in F}|x-f|\).
This is the same social-cost placement problem, with type frequencies represented as masses.
I would call the mirror Mass Median-Furthest Frontier. Given an integer \(\tau\ge3\) and a rational mass floor \(\delta>0\), consider all rational distributions \(\mu\) on at least three and at most \(\tau\) distinct rational locations, with every positive mass at least \(\delta\). Let \(q_\mu\) be the lower weighted median and let \(a,b\) be the extreme support points. The continuous MedianFurthest rule returns \(\{q_\mu,a\}\) if \(q_\mu-a>b-q_\mu\), and \(\{q_\mu,b\}\) otherwise. The prover’s task is to determine exactly
\[
\rho_\tau(\delta)=
\sup_\mu
\frac{\mathrm{SC}_\mu(\mathrm{MF}(\mu))}
{\min_{p,q\in\mathbb R}\mathrm{SC}_\mu(\{p,q\})},
\]
and give matching distributions that attain or approach the bound. The cases with at most two support points are omitted because both costs are zero.
This question preserves the optimization objective and the algorithm’s placement rule. It also has an exact high-multiplicity bridge: clearing the rational masses’ denominators produces a cloned finite electorate, the weighted median becomes the ordinary lower median, and both costs scale by the same factor. The approximation ratio is unchanged. So the continuous question is one the authors should recognize as an extension of their approximation result, even though it does not extend every claim in the paper.
The mass floor matters. Without it, this rule has no finite approximation guarantee over continuous societies, even with only three types. For masses \((1/2,\;1/2-\varepsilon,\;\varepsilon)\) at locations \((0,1,2)\), the lower weighted median is \(0\), so the rule chooses \(0\) and \(2\). Its cost is \(1/2-\varepsilon\), while sites \(0\) and \(1\) cost \(\varepsilon\). The ratio diverges as \(\varepsilon\to0\). Thus the paper’s \(3n/4\) bound does not yield a uniform bound as population granularity vanishes; the useful continuous question is how the frontier depends on \(\delta\) and \(\tau\). I expect that frontier to be tractable through the one-dimensional structure, weighted-median cases, and consecutive-cluster structure of optimal 2-facility placement. That expectation is not proved by the paper.
The scope is deliberately limited to Theorem 6’s social-cost approximation guarantee. I would not use Theorem 4 as an anchor here: its lower bound depends on a declaration-graph condition for individually strategic agents, which does not transfer faithfully to an atomless society.
The weakest point is that truthful mechanism design is the paper’s central concern. An individual in an atomless population has zero mass, so their unilateral report cannot change \(\mu\); preserving the paper’s truthfulness predicate would therefore make it vacuous. Replacing individual deviations with positive-mass cohort deviations would be a substantive new strategic model. This mirror covers the paper’s facility-placement approximation result, and its limits should be stated alongside that positive case.
I can make a value objection, but I cannot honestly rule out the mirror. Theorem 6 is the paper’s strongest anchor for it: residents at repeated locations form a sensible high-multiplicity population, and MedianFurthest has a direct mass version.
The difficulty is that the paper’s \(3n/4\) guarantee has no finite population-limit bound. For the three-location distribution
\[
\mu_\epsilon=\tfrac12\delta_0+(\tfrac12-\epsilon)\delta_1+\epsilon\delta_2,
\]
the lower weighted median is \(0\), so MedianFurthest chooses \(0\) and \(2\). Its cost is \(\tfrac12-\epsilon\), while facilities at \(0\) and \(1\) cost \(\epsilon\). The ratio therefore diverges as \(\epsilon\to0\). The proposed mass floor \(\delta\) prevents that, but adds a regime restriction: as \(\delta\) shrinks, the frontier diverges at least on the order of \(1/\delta\). With rational masses, clearing denominators makes that frontier exactly a question about finite electorates of arbitrary size in which every occupied location has at least a \(\delta\) fraction of voters. That correspondence supports the model’s high-multiplicity story, but makes the proposed result a restricted extremal analysis of a fixed rule, rather than a new computational bottleneck.
The paper’s distinctive contribution is about truthfulness under verification. In an atomless society, one person’s report changes no mass, so individual truthfulness becomes vacuous. A model where a positive-mass cohort can misreport could restore strategic content, but it changes the deviation model and would need its own justification. There is adjacent computational work on facility location with distributional demand, approximation ratios, and a two-facility extension, though it does not answer this particular frontier question. [Auricchio and Zhang, “Facility Location Problem with Aleatory Agents”](https://arxiv.org/abs/2409.18817).
So the strongest negative case is that this is a narrow approximation-analysis project, weakly connected to the paper’s central mechanism-design results and not obviously a substantial complexity question. That is not enough to defeat the anchor: the mass version is well-posed, and I do not see a sound basis for claiming that no scenario makes it worthwhile.
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.