| paper | d4-conf-aaai-2018-0193 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: \(R^*(\gamma)=\max\{3/2,\,2-\gamma\}\) for every \(\gamma\ge0\), with the infimum attained. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2.3
statement extracted from the paper’s text layer
Given a finite-support rational distribution \(\mu\) over ideal locations on \(\mathbb{R}\), let a randomized mechanism choose a facility location \(Y\). For each \(\gamma\), determine the minimum worst-case ratio \(\mathbb{E}[\max_{x\in\operatorname{supp}\mu}|x-Y|]/(\operatorname{diam}(\operatorname{supp}\mu)/2)\), subject to normalized standard deviation at most \(\gamma\) on every positive-diameter society and group strategyproofness against deviations by positive-mass submeasures.
Types are ideal locations \(x\in\mathbb{R}\), and each society is a finite-support distribution \(\mu\) with rational masses. A mechanism maps \(\mu\) to a randomized facility location; its objective is maximum distance over the support, while incentive constraints compare expected distances for mass coalitions that may change their reported locations.
The mirror concerns the one-facility maximum-cost tradeoff in Theorems 2.3 and 2.4. It leaves aside the one-facility social-cost case and the multiple-facility results, including Theorem 3.1.
The strongest positive candidate is the one-facility maximum-cost tradeoff. Imagine a large municipality where many residents share a relatively small set of ideal points. A type is an ideal location \(x\); \(\mu_x\) is the fraction of residents at that location. A randomized mechanism \(M\) maps the finite-support distribution \(\mu\) to a facility location \(Y\). Its maximum cost is \(C_\mu(Y)=\max_{x\in\operatorname{supp}\mu}|x-Y|\), with optimum \(D_\mu/2\), where \(D_\mu\) is the support’s diameter.
A precise continuous question would be: for a normalized standard-deviation budget \(\gamma\), find the smallest worst-case approximation ratio
\[
A(\gamma)=\inf_M\ \sup_{\mu:D_\mu>0}\frac{\mathbb E[C_\mu(Y)]}{D_\mu/2},
\]
subject to \(\operatorname{std}(C_\mu(Y))/(D_\mu/2)\le\gamma\) for every \(\mu\), and to mass-group strategyproofness. For that condition, allow any submeasure of residents to change their reported locations; no such coalition may make every member’s expected distance weakly smaller and a positive mass of members’ distances strictly smaller. A solution is a mechanism satisfying these conditions and attaining the frontier.
The relevant named result is Theorem 2.4, proved in this paper. It says that for every \(\alpha\in[0,1/2]\), no strategyproof one-facility mechanism with maximum-cost approximation ratio \(3/2+\alpha\) can have standard deviation below \((1/2-\alpha)\operatorname{opt}(x)\) on every location vector \(x\). Theorem 2.3, also proved here, gives the matching mechanism: for every such \(\alpha\), GENERALIZED-LRM\(_\alpha\) is group-strategyproof, has expected maximum cost \((3/2+\alpha)\operatorname{opt}(x)\), and standard deviation \((1/2-\alpha)\operatorname{opt}(x)\). Together, they motivate the candidate frontier \(A(\gamma)=2-\gamma\) for \(0\le\gamma\le1/2\). The expected direction is a closed-form frontier, if the finite-agent incentive constraints carry over to mass coalitions.
The regime is plausible: residents at shared ideal points can be a high-multiplicity population, with many agents and relatively few types. But the transfer is not established. The paper’s strategyproofness constraints concern individual agents and finite coalitions; the proposed continuum condition allows positive-mass deviations and drops zero-mass ones. Also, maximum cost depends on the support’s extremes, not the masses, and the paper’s lower-bound proof reduces to two-player inputs. The population continuum may therefore add little to this result.
There is a more fundamental limitation for this programme: Theorem 2.4 is not a computational-complexity result. It proves a mechanism-design lower bound, rather than classifying an algorithmic problem as tractable or hard. Theorem 2.3 gives a mechanism and its guarantee; Theorem 3.1 proves an impossibility for a smooth tradeoff. None asserts a runtime or a complexity classification. So the population-level frontier is the best continuous analogue I can defend, but this paper has no eligible named computational anchor under the stated rule.
The best case against starts with a scope problem: none of this paper’s named theorems classifies the complexity of a computational problem. Theorems 2.3 and 2.4 characterize a strategyproof mechanism’s approximation and variance; Theorem 3.1 rules out a certain kind of mechanism family. Those are mechanism-design results, not runtime, hardness, or algorithmic results of the kind ChoCo is meant to continuize. So the strongest proposed anchor is not eligible for this programme.
The one-facility mirror is still sensible as a mechanism-design question. A large population sharing ideal locations is plausible, and a distribution over those locations is a natural model. But for maximum cost, the objective depends only on the support’s two extremes, not on the masses. The proposed frontier \(A(\gamma)=2-\gamma\) therefore carries over the paper’s two-extreme calculation; it does not expose a population-scale optimization problem. And the transfer is not automatic: the paper’s group-strategyproofness proof can identify a particular finite player who does not gain, while a mass-coalition condition needs a positive measure of non-gainers. An atomless population may have no mass at its extreme locations. Proving the corresponding mass-incentive theorem could be worthwhile, but it would be a new strategic characterization, not a computational mirror of Theorem 2.4.
The strongest alternative is Theorem 3.1: put a distribution over locations, define social cost by integrating distance to the nearest facility, and ask whether a smooth approximation-variance tradeoff exists under mass-based incentives. Here the masses matter, so this is a more substantial continuous model. But it remains an existence question about strategyproof mechanisms, not a computational one. Also, the finite-agent theorem does not transfer just by replacing counts with masses: individual deviations have zero effect in an atomless society, while positive-mass deviations impose different incentive constraints. Establishing a meaningful analogue would require new work on that incentive model, without yielding the complexity landscape this programme seeks.
So the paper supports a plausible continuous-population *mechanism-design* agenda, especially around the two-facility social-cost impossibility. I cannot honestly claim that no worthwhile continuous question exists. The negative case is narrower: none of the anchors raised, including their strongest natural mass-based versions, gives this programme a computational mirror.
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.