| paper | d4-conf-sagt-2023-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.1
For fixed \(\tau_0\ge2\), given a finite candidate set \(C\subset\mathbb{R}\) with \(|C|\ge2\), and empirical position masses \(\mu_x=k_x/n\) supported on at most \(\tau_0\) positions, determine the infimum limiting worst-case per-capita social-cost approximation ratio over anonymous deterministic mechanism families \(M_n\). Each \(M_n\) must choose distinct sites \((a,b)\in C^2\) and be strategyproof against every single-resident report change, which transfers mass \(1/n\); the ratio is evaluated on profiles with support at most \(\tau_0\) as \(n\to\infty\).
A high-multiplicity mechanism-design limit: each position \(x\) is a type with mass \(\mu_x\); the mechanism chooses distinct candidate sites \((a,b)\), the per-capita objective is \(\mathrm{SC}_{\mu}(a,b)=\sum_x\mu_x(|x-a|+|x-b|)\), and a unilateral report moves mass \(1/n\) between position types.
The strategic constraints remain finite-resolution: for a genuinely atomless population, an individual move has zero mass, so the theorem transfers only if the sequence limit counts as the programme’s high-multiplicity analogue.
fatal: False
The mirror covers the doubleton social-cost results in Section 3.1 and their asymptotic approximation frontier, using the bounds from Theorems 3.1 and 3.2. It leaves singleton and general preferences, max cost, and the same-site variant aside.
The strongest case is narrow: the doubleton, social-cost results in Section 3.1. The paper gives no NP-hardness or parameterized-complexity theorem. Its useful anchors are approximation results about truthful mechanisms, which are computationally relevant but not standard complexity classifications.
Take a city choosing two distinct sites from a finite candidate set \(C\) for two complementary facilities that every resident approves. A resident’s type is their position \(x\) and approval of both facilities; a type’s mass is its share \(\mu_x\) of the population. Imagine \(n\) residents but only \(\tau\) reported-position types, with \(n\gg\tau\). The mechanism chooses \((a,b)\in C^2\), \(a\ne b\), and the per-capita social cost is
\[ \mathrm{SC}_{\mu}(a,b)=\sum_x\mu_x\bigl(|x-a|+|x-b|\bigr). \]
To keep individual truthfulness meaningful as the population grows, retain a reporting quantum of \(1/n\): one resident changing their report moves mass \(1/n\) from their true position to their reported one. Mechanisms depend only on the resulting mass profile, so the society itself is represented by a distribution, while unilateral deviations remain defined.
The lead question is the Asymptotic Doubleton Strategyproof Approximation Frontier. For each \(n\), let \(M_n\) be an anonymous deterministic mechanism that maps candidate locations and an empirical mass profile to a distinct facility pair. Require strategyproofness for every single-resident report change, on the full domain of \(n\)-resident profiles. For fixed support bound \(\tau_0\ge2\), define
\[ \rho_\infty(\tau_0)= \inf_{(M_n)} \limsup_{n\to\infty} \sup_{\substack{I_n=(C,\mu)\\|\operatorname{supp}(\mu)|\le\tau_0}} \frac{\mathrm{SC}_{\mu}(M_n(I_n))} {\min_{a\ne b\in C}\mathrm{SC}_{\mu}(a,b)}. \]
A solution is a strategyproof mechanism family with a matching guarantee and lower bound determining \(\rho_\infty(\tau_0)\). This is a population-mass limit of their doubleton siting problem: locations and candidate sites still matter, the objective is still total travel cost, and the unilateral action is still a private position report.
Lead anchor: Theorem 3.2, proved in this paper. It says that for doubleton instances, every strategyproof mechanism has approximation ratio at least \(1+\sqrt{2}-\delta\), for every \(\delta>0\). The proof uses four candidate locations and two large groups of agents, then moves agents one at a time to force the mechanism to retain an unfavorable outcome. Those instances have only a few position types even as \(n\) grows, so the lower bound survives in the high-multiplicity regime: \(\rho_\infty(\tau_0)\ge1+\sqrt{2}\) for \(\tau_0\ge2\). This is a transferred approximation barrier, not an NP-hardness result.
Algorithmic companion: Theorem 3.1, also proved here. It says that the paper’s deterministic Median mechanism for doubleton instances—place the facilities at the two candidate locations closest to a median agent—has approximation ratio at most \(3\), and that this bound is tight for that mechanism. The corresponding mass-profile rule selects a median position and the two nearest candidate locations. It is strategyproof at each finite reporting quantum and gives \(\rho_\infty(\tau_0)\le3\). With support masses as input, the median and nearest candidates can be found in polynomial time. This supplies a concrete tractable mirror problem: construct and analyze a strategyproof facility-placement rule on mass profiles. Theorem 3.1 is tight for Median itself; it does not prove that \(3\) is the best ratio over all mechanisms.
Together the anchors give a precise frontier question, with \(1+\sqrt{2}\le\rho_\infty(\tau_0)\le3\). The expected picture is that the lower obstruction persists from the finite model, while a simple median rule remains tractable. Further questions are whether the gap can be closed, whether the answer changes when support grows with \(n\), and what happens with singleton or mixed approvals and with max cost. This mirror covers only doubleton social cost in Section 3.1; it does not stretch to the paper’s other results.
The weakness is the reporting quantum. If the society is made genuinely nonatomic and a deviation changes zero mass, individual strategyproofness becomes vacuous. Retaining \(1/n\) makes the mirror an asymptotic family of empirical distributions, rather than a single nonatomic mechanism-design model. Also, anonymity is natural for a society described only by its distribution but narrows the mechanism class. The authors could reasonably accept this as a high-multiplicity limit of their problem, yet object that the strategic model is still finite at each resolution.
The paper’s anchors are approximation guarantees for truthful mechanisms, not complexity results. The output is just a pair of candidate locations, and the results ask how well particular strategyproof rules approximate the best pair. That leaves little of the computational landscape this programme is meant to chart: for fixed sites and a mass profile, the Median rule is computed by a weighted median and distance comparisons. The harder question in the proponent’s mirror—finding the best ratio over all truthful mechanisms—is a mechanism-design frontier, not a complexity classification.
The deeper obstacle is that truthfulness here is about an individual’s ability to change the outcome. In an atomless society represented by \(\mu\), one person changing their reported position leaves \(\mu\) unchanged. Any mechanism \(F(\mu)\) therefore satisfies individual strategyproofness vacuously. For social cost, the mechanism can simply choose the pair minimizing \(\mathrm{SC}_{\mu}\), giving ratio \(1\). So Theorem 3.1’s ratio for Median is not a binding frontier in that model, and Theorem 3.2’s lower bound has no force there: its proof relies on successive one-person moves that alter the outcome.
The proponent’s reporting quantum is the strongest repair. It preserves those individual moves, but it makes the object a sequence of finite mechanisms \(M_n\), not a strategyproof mechanism on a continuous society. The lower bound may well persist along that sequence; that would be a meaningful high-multiplicity result. But the quantity \(\rho_\infty\) asks for the limiting approximation ratio of finite truthful mechanisms, not a new continuous computational problem. Replacing individual moves with positive-mass moves would give incentives real force in a continuum, but would study group strategyproofness, a different strategic question.
That said, the negative case is not airtight. The programme explicitly values high-multiplicity bridges, and the paper’s lower-bound construction uses only a few position types, so the proponent has a coherent asymptotic question with a nontrivial gap between \(1+\sqrt{2}\) and \(3\). If that kind of limit of finite strategic models counts as a worthwhile mirror, these anchors survive. I can argue that it falls outside the programme’s stated computational focus, but I cannot honestly claim 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.