The Price of Anarchy in Spatial Social Choice

The paper has no numbered result asserting complexity, an algorithm, or approximation-complexity guarantees, so bit (a) fails under the explicit rule. The proposed cohortwise \(\lambda\)-Median threshold problem is precise and potentially interesting, but it replaces unilateral individual reports with positive-mass bloc deviations. Therefore it is a re-modeling rather than a continuous analogue supplied by this paper.

The objection that survived

The strongest objection is that a type-cohort controlling a common report \(\rho_t\) is a coalition, whereas the paper gives each individual one unilateral report; atomless unilateral deviations have zero outcome effect.

What the mirror covers

The proposed mirror covers the \(\lambda\)-1-Median price-of-anarchy claims, especially Theorems 4.6 and 4.2; it leaves the refinement, 1-Mean, and \(\ell_2\)-norm results alone.

Open questions for a prover

The case FOR (proponent)

Strictly under ChoCo’s anchor rule, this paper has no qualifying computational result. Its named results—Propositions 3.1, 3.4, 3.6, and 3.8; Theorems 4.2, 4.3, 4.6, 5.1, 5.3, and 6.1; and Lemma 5.2—are analytic equilibrium and price-of-anarchy statements. None proves NP-hardness, membership in \( \mathrm{P} \), fixed-parameter tractability, an algorithm, or an approximation-complexity bound. Thus I cannot honestly present one of them as a ChoCo computational anchor.

The strongest positive mirror, if analytic anchors are admitted, would be a cohort-continuous version of the paper’s \( \lambda \)-1-Median result, anchored by Theorem 4.6, proved in this paper.

Call it Continuum \( \lambda \)-Median Minimal-Dishonesty Robustness. An instance consists of a rational hyperrectangle \(X=[a,b]\subseteq\mathbb{R}^k\), a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) a sincere ideal point \(\pi_t\in X\) and a preference norm \(p_t\). The type is complete: agents of type \(t\) have the same \(\pi_t\), \(p_t\), and strategic behaviour. A report profile is a point \(\rho_t\in X\) for each type; hence the submitted population is the weighted empirical distribution \(\nu_\rho=\sum_t\mu_t\delta_{\rho_t}\).

For each coordinate \(i\), let \(a_i(\nu_\rho)\) and \(b_i(\nu_\rho)\) be the lower and upper weighted medians of the submitted reports, and let the mechanism choose \(r^\lambda_i(\nu_\rho)=(1-\lambda_i)a_i(\nu_\rho)+\lambda_i b_i(\nu_\rho)\). The sincere social cost is \(C_\mu(x)=\sum_t\mu_t\|\pi_t-x\|_1\). A report profile is a cohortwise minimally dishonest Nash equilibrium if no positive-mass type-cohort can change its common report to obtain a strictly preferred outcome, and no more honest report can yield an equally good outcome.

The computational question is: given \(I=(X,T,\mu,\pi,p,\lambda)\) and a rational threshold \(q\), decide whether every minimally dishonest equilibrium satisfies
\[ \frac{C_\mu(r^\lambda(\nu_\rho))} {\min_{x\in X}C_\mu(x)} \le q. \]
The strongest special case asks whether the ratio is exactly \(1\).

This is a recognizable population version of the authors’ problem: it preserves the same mechanism, the same \(L_1\) objective, the same individual distance preferences, the same tie-breaking parameter, and the same minimal-dishonesty refinement. The regime is a large repeated electorate containing a small number of policy or demographic cohorts, with \(N\gg\tau\). Rational masses correspond to replicated finite voters, and weighted medians recover the finite mechanism on clone-symmetric profiles.

The expected answer on hyperrectangles is Class A: Theorem 4.6 strongly suggests that the continuous price of anarchy is \(1\), while weighted medians and the sincere \(L_1\)-optimum are computable from the type masses. Theorem 4.2, also proved here, supplies the boundary: with general convex domains and interior tie-breaking, the same two-cohort construction gives an unbounded ratio even when the number of types is constant.

The weakest point is fundamental. In a genuinely atomless population, an individual deviation has zero effect on the outcome, so ordinary Nash equilibrium becomes vacuous. The proposed mirror therefore makes positive-mass cohorts the strategic actors. That is a substantive extension, not a direct high-multiplicity limit of the paper’s individual-agent game. It is plausible for coordinated voting blocs, but a referee could reasonably say that the strategic object has changed.

So the honest verdict is: there is a strong, author-recognizable continuous population extension around Theorem 4.6, probably tractable on hyperrectangles, but this paper supplies no qualifying named computational anchor. Under the programme’s strict scope, it is useful motivation rather than an admissible positive case.

The case AGAINST (opponent, writing after the proponent)

The proponent’s first point is decisive under ChoCo’s anchor rule: this paper has no qualifying computational result. Its numbered propositions, lemmas, and theorems are equilibrium characterizations and price-of-anarchy bounds. A price-of-anarchy bound is not an approximation-complexity result, and none gives an algorithm, hardness classification, or parameterized complexity statement. The proposed threshold problem therefore adds a new computational problem rather than continuizing one established by the paper.

The strongest possible rescue is the proposed mirror of Theorem 4.6. But its “cohortwise” game is not the high-multiplicity version of the paper’s game. In the paper, every \(v\) is an individual strategic player who changes one submitted ideal point. Replicating a type \(N\) times produces \(N\) independent players, not one player controlling the common report \(\rho_t\). A cohort deviation changes a positive mass of reports simultaneously; that is a coordinated coalition or delegated representative, neither of which appears in the original model.

This distinction is fundamental because the paper’s phenomenon is driven by unilateral strategic effects. In an atomless population, one individual’s report has measure zero and cannot change a median, mean, or selected outcome. Ordinary Nash equilibrium then becomes vacuous: every report is a best response because no individual can affect anything. The minimal-dishonesty refinement does not repair this. A more honest report also leaves the outcome unchanged, so a dishonest report fails the paper’s strict refinement; the refinement collapses toward truth-telling rather than selecting the paper’s strategic equilibria.

The apparently better alternatives do not preserve the object. One can declare each type-cohort to be a strategic bloc, but then the answer depends on an externally chosen coalition granularity. One can permit positive-measure deviations, but that is a coalitional equilibrium concept. One can model a distribution of reports within each type, but individual deviations again have zero effect. All are potentially interesting population games, yet each replaces the paper’s individual manipulation problem with a new strategic model. The issue is not that the notation needs a natural mass reformulation; it is that the identity and scale of the deviating agent determine the equilibrium concept itself.

Theorem 4.2 does not provide an independent escape. Its unbounded construction relies on splitting named individuals into two groups and showing that each individual’s report is minimally dishonest. In a genuine continuum, an individual in either group cannot move the outcome. If the two groups are instead treated as positive-mass blocs, the construction survives only in the newly introduced coalition game. Thus Theorems 4.2 and 4.6 do not yield a continuous computational boundary; they are two analytic consequences of the same finite-player equilibrium model.

The negative case is not airtight as a modelling claim. Spatial ideal points and social costs can certainly admit sensible repeated-cohort interpretations, and a new study of coordinated policy blocs could be worthwhile. But that would be a new continuous strategic-population programme, not a computational mirror of this paper. Under ChoCo’s stated scope and anchor rule, the paper supplies no result for such a mirror, while the proposed best mirror changes precisely the strategic object whose price of anarchy the paper studies.

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.