| paper | d4-conf-atal-2015-0171 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6 bounds manipulation incentives but makes no computational claim. The proposed mass-coalition optimization is a plausible extension, yet it cannot supply the missing computational character of a named result in the paper.
fails bit a — no named computational result to mirror
Theorem 6 is an incentive bound, while optimizing over coalitions of prescribed mass adds a new computational problem.
fatal: True
The proposed question extends the manipulation analysis surrounding Theorem 6; it does not mirror a computational result, and leaves the other theorems and empirical evaluations outside.
On the anchor rule as written, this paper has no qualifying named computational result: none of its numbered results says that a problem is in P, NP-hard, FPT, or otherwise classifies its computational complexity. Its empirical calculations do not supply such a theorem.
The closest useful anchor is Theorem 6, proved here. It says that for multidimensional constrained facility location under the \(L_2\) norm, closest candidate mechanisms are \(\varepsilon\)-group-strategy-proof, with
\[
\varepsilon=\max_{d_r,d_s\in D}\|d_r-d_s\|_2.
\]
That is a bound on manipulation incentives, not a complexity result, so it cannot strictly serve as the required anchor. Still, it gives the strongest basis for a positive mirror. The authors study coalitions’ misreports and gains directly, and their empirical section evaluates manipulation as the population grows; replacing counts with masses preserves the question they are asking.
I would call the candidate mirror Continuous Coalition Gain for CCM. An instance has a finite set \(T\subseteq\mathbb{Q}^m\) of possible ideal-point types, a finite feasible location set \(D\subseteq\mathbb{Q}^m\), a quantile mechanism \(p\), a rational population distribution \(\mu\) over \(T\), and a prescribed coalition mass \(\alpha\). A type \(t\) means agents with the same ideal point and the same \(L_2\) cost function; \(\mu_t\) is their fraction of the population. The mechanism applies the paper’s quantiles to the reported population and projects the resulting facility locations onto \(D\), using a fixed tie-breaking rule.
The question is to find the largest individual gain attainable by a viable coalition of mass \(\alpha\), or report that none exists. A solution consists of a subdistribution \(\nu\leq\mu\) of total mass \(\alpha\) identifying the coalition, and a report distribution \(\rho\) of total mass \(\alpha\). The resulting reports are \(\mu-\nu+\rho\). With \(x\) the outcome under \(\mu\) and \(x'\) the outcome under \(\mu-\nu+\rho\), viability requires \(c_t(x')\leq c_t(x)\) for each type with \(\nu_t>0\), with strict improvement for positive coalition mass of at least one type. The objective is
\[
\max_{t:\nu_t>0}\bigl(c_t(x)-c_t(x')\bigr),
\qquad
c_t(x)=\min_j\|x_j-t\|_2.
\]
The returned value is therefore a manipulation gain, not a property of an encoding. Theorem 6 supplies a natural check on this quantity: it cannot exceed the diameter of \(D\).
A plausible regime is a large electorate choosing among a fixed set of candidates, with many voters sharing each of a modest number of issue-position types. For example, millions of voters might fall into hundreds of stable preference types. This makes mass the natural size of a coalition, while preserving the paper’s ideal points, cost function, quantile mechanism, feasible candidates, and group-manipulation question. In the fixed-\(m,q\) regime, I would expect this mirror to be tractable: for finite \(T\), quantile outcomes come from finitely many coordinate values, and each candidate outcome can be checked using linear constraints on coalition and report masses. Enumerating those outcomes and solving the resulting feasibility problems is polynomial when dimension and facility count are fixed. With \(m\) and \(q\) variable, that enumeration grows quickly; the complexity there is open.
The mirror covers only Theorem 6’s constrained, multidimensional CCM result. Its weakest point is also substantial: the theorem is an incentive bound, not a computational claim, and its diameter bound is geometric and applies broadly to mechanisms whose outcomes lie in \(D\). Thus the proposed optimization question is closely aligned with the paper’s manipulation analysis, but the paper does not establish its algorithmic landscape. This is a credible lead for a continuization study, not a case that meets the required anchor rule without qualification.
The strongest objection is that this paper has no computational result to continuize. Its numbered theorems concern incentive properties: Theorem 1 gives unbounded manipulation gain, Theorems 2 and 3 bound it for particular profiles, Theorem 4 proves group strategy-proofness in one dimension, and Theorems 5 and 6 give incentive bounds. None classifies the complexity of a problem or presents an algorithm. The empirical analysis computes outcomes for sampled profiles, but it does not establish a computational result either.
Theorem 6 is therefore a weak anchor. Its bound, \(\varepsilon=\max_{d_r,d_s\in D}\|d_r-d_s\|_2\), depends on the feasible locations, not on the population, its size, or its type distribution. A mass-population version would preserve the same geometric bound. To get a computational question, one must add something like a prescribed coalition mass and ask for the best attack. That is a plausible follow-up, but the coalition-mass optimization is a new problem, not a continuous version of what Theorem 6 proves. The closer profile-specific bounds in Theorems 2 and 3 face the same gap: making their geometric bounds computable from a mass description would be a new computational task.
The proponent’s stronger formulation is sensible: a large election can have many voters drawn from a modest set of ideal-point types, and a coalition can naturally be described by a subdistribution of those types. I would not reject it on grounds of multiplicity or identity. But with finite support and finitely many feasible outcomes, one can fix the before-and-after outcomes and the benefiting type, express the quantile conditions as linear constraints on coalition and report masses, and check feasibility with an LP. For fixed dimension and facility count, enumerating the candidate outcomes gives a direct route to the answer. Variable dimension or facility count could still produce an interesting complexity problem, but that added search is not present in the paper’s result. The proposed “largest individual gain” also needs care: an arbitrarily small positive mass of a type can contribute that type’s full gain, so a supremum or a minimum mass requirement may be needed to make the optimization well-defined. That is repairable, but it further illustrates the extra modelling choices involved.
A continuous society for this facility-location setting is entirely plausible. The negative case is narrower: none of the paper’s named results supplies a computational anchor, and the best proposed mass-coalition problem earns its interest as a new study of manipulation, not as a mirror of Theorem 6. I would vote against a green, paper-anchored ChoCo entry. I cannot honestly rule out every worthwhile computational question one could build from these models; that is where the universal negative case is weakest.
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.