| paper | d4-conf-sagt-2025-0018 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 3.4 is a named result, but it bounds the quality of truthful mechanisms rather than the complexity of computing an outcome or mechanism. The proposed mass-strategyproof ratio problem is precisely stated, yet it does not turn that theorem into a computational result of this paper.
fails bit a — no named computational result to mirror
The proposed model covers only Theorem 3.4's deterministic, non-optional approximation lower bound; it leaves the randomized bounds and general optional-preference results aside.
The strongest case is a narrow one: a continuous version of the paper’s non-optional deterministic problem in which the strategic units are large, homogeneous resident cohorts. There is no named P/NP or parameterized-complexity result in this paper. The anchor here is its lower bound on the approximation achievable by truthful mechanisms.
Consider two obnoxious facilities and a multiset \(A\) of rational candidate locations. A type is a cohort’s position \(x\) and its public preference; for this mirror, every cohort is affected by both facilities. The society is a finite-support distribution \(\mu\) over types, with rational masses summing to one. A plausible regime is a large city with millions of residents but relatively few neighborhoods whose residents share the same relevant position and preferences. The mass \(\mu_x\) is the fraction of residents in that cohort.
Lead problem: Mass-Truthful Non-Optional Two-Facility Location. An instance is \(A\) and \(\mu\). A deterministic mechanism \(M\) maps \(\mu\) to an ordered pair of locations in \(A\). Define per-resident utility as \(u_x(y)=|x-y_1|+|x-y_2|\) and welfare as \(\mathrm{SW}_\mu(y)=\sum_x\mu_xu_x(y)\). Require mass-strategyproofness: for any \(\varepsilon\leq\mu_x\), a subgroup of mass \(\varepsilon\) at \(x\) cannot gain by reporting \(z\), changing the input to \(\mu'=\mu-\varepsilon\delta_x+\varepsilon\delta_z\). The question is to determine the infimum worst-case ratio \(\rho^\star=\inf_M\sup_{A,\mu}\max_{y\in A^2}\mathrm{SW}_\mu(y)/\mathrm{SW}_\mu(M(\mu))\), and give a matching mechanism or impossibility proof. This is a problem about the underlying location choice and its incentives, not an encoding.
My anchor is Theorem 3.4, proved in this paper: when every agent is affected by both facilities, every deterministic strategyproof mechanism has approximation ratio at least \(\sqrt{3}\). The proof uses candidate multiset \(\{0,0,2,2\}\) and two large cohorts. Set \(\alpha=\sqrt{3}-1\); initially, mass \(\alpha\) is at \(0\) and mass \(1-\alpha\) at \(1+\varepsilon\). Choosing \((0,0)\) gives a ratio at least \((1+\alpha)/(1-\alpha)\); choosing \((0,2)\) gives at least \(1+\alpha=\sqrt{3}\). Thus a mechanism below the claimed bound must choose \((2,2)\). Moving the right cohort to \(2\) cannot change that outcome: otherwise that cohort could have reported \(2\) at the initial profile and improved its utility. Then moving the left cohort from \(0\) to \(1-\varepsilon\) also cannot change the outcome, by the reverse deviation. At the resulting profile, \((2,2)\) has welfare approaching \(2\alpha\), while \((0,0)\) approaches \(2(2-\alpha)\), giving ratio \((2-\alpha)/\alpha=\sqrt{3}\). Rational approximations to the masses recover the same limiting bound for the rational-input mirror.
The continuous question asks whether that lower-bound barrier is tight for mass-strategyproof mechanisms. I expect the obstruction itself to transfer: the proof is driven by cohort proportions and deviations of whole cohorts, which are valid mass deviations, rather than by fine integer details. That is a Class B-like persistence claim, though it is an approximation lower bound, not a computational-hardness result. I would not claim the full optimum is \(\sqrt{3}\): the paper’s finite-population upper bound does not establish that its mechanism remains truthful against mass deviations.
The weakest point is the incentive model. In a nonatomic population, an individual’s report does not change \(\mu\), so ordinary individual strategyproofness can become vacuous. Mass-strategyproofness repairs that by allowing a positive-mass subgroup to deviate, but it is stronger than the paper’s individual incentive condition. The neighborhood scenario makes that change legible—cohorts or their associations act as the reporting units—but the authors could reasonably say it is a group-truthfulness variant rather than their original game. If they accept that co-modification, the population, utility, candidate sites, and strategic objective all remain recognizable.
This mirror covers only Theorem 3.4’s non-optional deterministic lower-bound result. It does not cover the randomized bounds or the general optional-preference results. Natural next questions are whether a mass-strategyproof mechanism can attain \(\sqrt{3}\), what changes under randomized mass-strategyproofness, and whether the optional-preference variant admits a similar cohort model.
The strongest objection is that Theorem 3.4 is a distortion lower bound, not a complexity result. The paper proves how well truthful mechanisms can approximate welfare; it does not classify the complexity of a computational problem or give a hardness result for computing an outcome. The proposed \(\rho^\star\) keeps that focus: it asks for the best ratio among mass-strategyproof mechanisms. That may be a worthwhile mechanism-design question, but it does not fill ChoCo’s stated gap in the complexity of computational social choice. To make it a complexity question, one would have to add a new task—such as deciding whether a mechanism with a given ratio exists or computing such a mechanism—and that task is not what the theorem anchors.
The mass model also changes what truthfulness means. In a nonatomic society, a single resident has measure zero, so changing that resident’s report leaves \(\mu\) unchanged and individual strategyproofness becomes vacuous. The proposed repair lets any positive mass \(\varepsilon\) deviate. That rules out coordinated group gains, which is stronger than the paper’s guarantee against a unilateral report. Treating a neighborhood as one weighted strategic agent is another possible repair, but then the neighborhood controls its entire mass. Neither choice follows automatically from replacing the population count with proportions. To preserve the original individual incentive, one can keep finite populations with individual mass \(1/n\); that gives a family of finite mechanisms indexed by \(n\), rather than a single nonatomic mechanism.
There is a credible cohort setting here: many residents could share a relevant position and preferences, and welfare aggregates naturally over their mass. So the proposed model is not incoherent, and its mass-transfer formulation is more careful than a literal continuum limit. My case against it is narrower: it looks like a new question about group-truthful facility-location mechanisms, not a computational mirror of the result in this paper. If ChoCo were expanded to include distortion and group-strategyproof mechanism design, this anchor could survive. Under the programme’s stated scope, I don’t see a strong continuous mirror of it.
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.