| paper | d4-conf-wine-2024-0002 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed mass-transfer model is coherent and the authors would likely recognize it. But Theorems 3 and 8 concern axioms and distortion; neither asserts that an object can be computed, bounds computation, or proves computational hardness, so bit (a) fails.
fails bit a — no named computational result to mirror
The proposed model covers the approval-voting questions behind Theorems 3 and 8. It does not study algorithms for computing minimax committees; the related implications in §§4.2–4.4 are also mechanism impossibilities.
This paper has no named result about running-time complexity: it proves no NP-hardness, polynomial-time, or parameterized-complexity classification. Its strongest computationally adjacent anchor is an approximation impossibility, which is still a credible mirror of the paper’s mechanism-design question.
The lead anchor is Theorem 8, proved in this paper. It says that for approval elections with \(m\ge 3\) alternatives, committee size \(1\le k\le m-2\), and \(n\ge 6\) voters, every strongly group-strategyproof multi-winner voting rule has an infinite approximation ratio for \(k\)-minimax approval voting. Here the loss of a committee \(C\) on profile \(P\) is \(\max_i d(C,P_i)\), and the benchmark is the \(k\)-committee minimizing that worst voter loss.
A direct continuous version is the Continuous Strong-GSP Minimax Approximation problem. Fix \(A\) and \(k\). A voter type is an approval set \(t\subseteq A\), with Hamming-distance preferences over \(k\)-committees. A society is a finite-support rational distribution \(\mu\) over approval types. A mechanism \(F\) maps each \(\mu\) to a committee \(F(\mu)\) of size \(k\). Its loss is
\[
D_\mu(C)=\max_{t:\mu_t>0}d(C,t),
\]
the worst loss among the types present, and the benchmark is \(\min_{|K|=k}D_\mu(K)\).
For strong group-strategyproofness, a coalition can transfer mass \(x_{t,t'}\ge 0\) from true type \(t\) to reported type \(t'\), with total outgoing mass at most \(\mu_t\). The resulting distribution determines the new committee; utilities are still evaluated using the coalition members’ true types. There must be no such transfer that weakly improves every participating positive mass and strictly improves some positive mass. The question is whether there is a deterministic \(F\) with that property and a finite uniform approximation factor \(\rho\). A solution would be such an \(F\) and \(\rho\); the expected answer is no.
The transfer from the paper’s result is exact. Any rational \(\mu\) can be represented by a finite electorate with a common denominator, and a finite coalition deviation becomes a mass transfer. Thus a continuous mechanism would induce a finite strongly GSP voting rule on every such electorate. Restricting to electorates with \(n\ge 6\), Theorem 8 rules out a finite approximation factor. Equivalently, the paper’s proof uses the fact that a mechanism with finite minimax approximation must be unanimous on unanimous profiles, while Theorem 3 rules out strong GSP and unanimity together.
That supporting anchor, Theorem 3, is also proved here: for approval elections with \(m\) alternatives and committee size \(1\le k\le m-2\), there is no multi-winner approval voting rule that is both strongly GSP and unanimous. Its continuous mirror asks whether a mechanism on rational mass distributions can satisfy mass-strong-GSP and return \(S\) on the unit-mass society \(\delta_S\) whenever \(|S|=k\). The expected answer is again no, by restricting the mechanism to empirical distributions. A continuous version of Theorem 3 is a natural existence question; Theorem 8 is the stronger anchor for an approximation question. Both are negative results transferred from finite profiles. In the programme’s vocabulary, that is closest to Class B, though it is a transfer of mechanism impossibility, not a computational-hardness reduction.
A plausible regime is a large digital community or municipality choosing \(k\) equal-cost projects, with many participants but relatively few distinct approval ballots: millions of participants, perhaps only hundreds or thousands of observed types. A type is the participant’s complete approval set for the projects; its mass is its fraction of the population. The committee remains integral, as in the paper. Authors working on strategic approval voting should recognize mass-based coalitions and worst-type loss as close analogues of their model.
The weakest point is that this mirror does not expose a new complexity landscape. Every rational society in the proposed domain is itself a finite electorate in anonymous, aggregated form. Moreover, the minimax objective depends on which types have positive mass, not on their mass values. So the continuous question is sensible, but the paper’s impossibility transfers by restriction rather than revealing a tractability gain or continuum-specific hardness. Further questions include whether a finite guarantee becomes possible if coalitions must have at least some minimum mass, and what changes for randomized mechanisms or the paper’s open parameter cases.
The strongest negative case is about fit with ChoCo’s question, not whether a continuous model can be written down. A large participatory-budgeting vote with many citizens sharing approval sets is a credible high-multiplicity regime. The best mirror would take a distribution \(\mu\) over approval sets, return an integral \(k\)-committee, require mass-strong GSP under transfers between reported types, and require \(F(\delta_S)=S\) for every \(k\)-set \(S\). That is a coherent model the paper’s authors could recognize.
But Theorem 3 is an axiomatic incompatibility: strong GSP and unanimity cannot coexist. Its best continuous mirror is still an existence question about a social choice function on the approval-profile simplex. The impossibility already follows on rational empirical distributions, where a mass deviation represents a finite coalition deviation. Extending the domain to irrational masses adds no computational question; the theorem imposes no continuity or other regularity condition on \(F\).
Theorem 8 is no stronger computational anchor. Its best mirror asks for a finite distortion guarantee for a mass-strong-GSP mechanism, with worst loss \(\max_{t:\mu_t>0}d(F(\mu),t)\). That is a legitimate mechanism-design question, but “approximation ratio” here measures the outcome’s distortion, not the running time or approximation quality of an algorithm. The paper’s impossibility holds regardless of computational resources, including for exponential-time mechanisms. And for rational \(\mu\), scaling the electorate preserves its support and minimax loss, so the finite result transfers directly. A separate question about the runtime of computing a minimax committee would be algorithmic, but it is not what Theorem 8 establishes.
So I would not claim these mirrors are incoherent, or use their direct inheritance from finite results as an objection in itself. The sharper case is that both anchors ask about axioms and distortion for mechanisms, not computational complexity. The paper supplies no computational theorem for ChoCo to continuize; studying these mirrors could be worthwhile in mechanism design more broadly, but it would not chart the computational landscape this programme set out to map.
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.