| paper | Ties in Multiwinner Approval Voting |
| authors | Łukasz Janeczko, Piotr Faliszewski |
| venue | IJCAI 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.5
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), listed approval types \(A\subseteq C\), and rational masses \(\mu_A\ge 0\) with \(\sum_A\mu_A=1\), construct \(W_0=\varnothing\); at each \(i\in\{1,\ldots,k\}\), branch over every \(c\in C\setminus W_{i-1}\) maximizing \(M_\mu(c\mid W_{i-1})=\sum_A\mu_A\bigl(H_{|A\cap(W_{i-1}\cup\{c\})|}-H_{|A\cap W_{i-1}|}\bigr)\), where \(H_j=\sum_{r=1}^{j}1/r\), and let \(\mathcal{G}_\infty(\mu,k)\) be the resulting committees; decide whether \(|\mathcal{G}_\infty(\mu,k)|=1\).
Types are approval sets \(A\subseteq C\), population is rational mass \(\mu_A\), the committee remains an integral \(k\)-subset, and the branching variables are tie-resolution choices; the objective is uniqueness under GreedyPAV marginal maximization.
The mirror is computationally equivalent to binary-encoded voter multiplicities and may therefore add little beyond a representation lemma or population-sensitive structure, although the proponent acknowledges its lightness.
fatal: False
The mirror covers Theorem 3.5 for GreedyPAV and Proposition 3.1 for batch non-AV 1-concave Thiele rules; it leaves the counting results, Phragmén and MEqS-specific dynamics, and experiments outside the mirror.
There is a credible continuous mirror, and the strongest one is the paper’s sequential unique-committee problem for GreedyPAV.
Take \(C\) to be the candidates and let an approval type be a set \(A\subseteq C\). A society is a finite-support rational distribution \(\mu=(\mu_A)\) over approval types, with \(\sum_A\mu_A=1\). The intended regime is a large electorate in which many voters share one of a relatively small catalogue of approval ballots: for example, recurring party, issue-bloc, or participatory-budgeting cohorts. Thus \(N\gg\tau\), where \(N\) is the number of voters and \(\tau\) the number of distinct approval types. Voters are not individually targeted; the committee remains an indivisible \(k\)-subset of candidates.
My lead anchor is Theorem 3.5, proved in this paper. It states that UNIQUE-COMMITTEE is FPT parameterized by \(k\) for greedy variants of 1-concave Thiele rules, including GreedyPAV.
The precise mirror is:
\[ \textsc{GreedyPAV-Unique}_{\infty}. \]
An instance consists of \(C\), \(k\), the listed approval types \(A\), and rational masses \(\mu_A\). Define
\[ \Phi_\mu(S)=\sum_A \mu_A H_{|A\cap S|}, \qquad H_j=\sum_{r=1}^{j}\frac1r. \]
Starting with \(W_0=\varnothing\), at step \(i\) every candidate \(c\notin W_{i-1}\) has marginal value
\[ \Phi_\mu(W_{i-1}\cup\{c\})-\Phi_\mu(W_{i-1}). \]
The rule branches over all candidates attaining the maximum, exactly as in the paper’s parallel-universes tie-breaking model. The output is the family \(\mathcal G_\infty(\mu,k)\) of committees obtainable after \(k\) steps. The problem asks whether
\[ |\mathcal G_\infty(\mu,k)|=1. \]
This is recognisably the authors’ problem: every discrete voter sum has simply become a mass-weighted sum, while candidates and committees remain discrete. If \(\mu_A=n_A/N\), multiplying every score by \(N\) recovers precisely the finite election with \(n_A\) voters of type \(A\). Conversely, any rational mass vector can be represented by arbitrarily many cloned voters. The continuous population is therefore not a fractional committee or a lottery over committees; it is a high-multiplicity approval electorate.
I expect \(\textsc{GreedyPAV-Unique}_{\infty}\) to be in Class A, FPT in \(k\), with running time \(f(k)\operatorname{poly}(m,\tau,L)\), where \(L\) is the input bitlength. The proof of Theorem 3.5 carries over: all marginal comparisons are exact rational sums over the \(\tau\) types, and the paper’s bounded-\(k\) search over possible tie resolutions is unchanged. This is the strongest mirror because the continuous reformulation is exact, the regime is natural, and the named algorithmic result survives without weakening the authors’ question.
A second, independent anchor is Proposition 3.1, also proved in this paper. It states that for every fixed 1-concave Thiele rule other than AV, UNIQUE-COMMITTEE is coNP-hard.
The corresponding problem is
\[ w\textsc{-Unique}_{\infty}. \]
It has the same input \((C,k,\mu)\), but winning committees are all maximizers of
\[ \Phi^w_\mu(S)=\sum_A\mu_A w(|A\cap S|), \qquad |S|=k. \]
The question is whether this maximizer is unique. For PAV, \(w(j)=H_j\); for CCAV, \(w(j)=[j\ge1]\).
The hardness reduction survives normalization exactly. Given the graph instance used in Proposition 3.1, create an approval type \(\{v_i,v_j\}\) of mass \(1/N\) for every edge and a singleton type \(\{v_i\}\) of mass \((\delta-d(v_i))/N\), where \(N\) is the total number of constructed voters. Every independent \(k\)-set has normalized score \(\delta k/N\), while every non-independent \(k\)-set has strictly smaller score, exactly as in the paper after division by \(N\). Hence the continuous instance has a unique winning committee precisely when the graph instance has no second independent set.
This is Class B: the hardness lives in the candidate graph and the committee choice, not in the number of named voters. It is therefore entirely compatible with high multiplicity. Each approval cohort can be replicated \(q\) times, making \(N\) arbitrarily larger than \(\tau\), without changing \(\mu\) or the winning committees.
The scope is deliberately narrow. These mirrors cover Theorem 3.5 for GreedyPAV and Proposition 3.1 for batch PAV or any other fixed non-AV 1-concave Thiele rule. I am not claiming here that the Phragmén and MEqS budget dynamics automatically continuize; those require a separate definition of per-unit budgets and exact mass-level tie events. Nor am I using the experimental tie frequencies as a complexity anchor.
The weakest point is that this is a relatively “light” continuization: the continuous population enters as weighted approval masses, while the committee remains integral and there is no mass-transfer decision. An opponent can say that the FPT result is merely a weighted version of the discrete theorem. I think that criticism limits the novelty of the mirror, but does not invalidate it. ChoCo’s object is the population, not necessarily a continuous action variable, and high-multiplicity weighted electorates are precisely the intended bridge. The natural follow-up questions are whether uniqueness is robust under small perturbations of \(\mu\), whether fixed \(\tau\) yields stronger algorithms, and whether the paper’s counting results admit analogous \(\#\)-complexity classifications for continuous approval societies.
The strongest negative case is that both proposed anchors collapse to weighted approval elections, rather than producing a genuinely new continuous computational object.
For Theorem 3.5, let \(D\) clear the denominators of the masses and set \(n_A=D\mu_A\). Then, for every committee \(S\),
\[ \Phi_\mu(S)=\sum_A\mu_A H_{|A\cap S|} =\frac{1}{D}\sum_A n_AH_{|A\cap S|}. \]
Every marginal comparison, every internal tie, and every recursively reachable committee is therefore identical to the finite election obtained by cloning each approval type \(n_A\) times. Conversely, every finite election reduces to its type-mass vector. The proposed \(\textsc{GreedyPAV-Unique}_{\infty}\) is thus not a limiting problem or a continuous optimization problem; it is exactly the same discrete problem with voter multiplicities encoded in binary.
Theorem 3.5’s proof confirms this. It never exploits a population-level structure. It repeatedly compares finitely many candidate marginals and branches over candidate tie resolutions. Replacing voter sums by rational weighted sums changes only the arithmetic representation. The FPT algorithm survives, but precisely because the population has contributed no new computational content. There is no mass transfer, separation problem, convex feasible region, or population-sensitive certificate to study.
The same objection defeats the proposed mirror of Proposition 3.1. Its reduction already uses approval cohorts as complete types: an edge cohort approving \(\{v_i,v_j\}\), and singleton cohorts approving \(\{v_i\}\). After normalization, the independent-set gap is unchanged. Replicating every cohort by an arbitrary common factor makes \(N\gg\tau\), but does not alter a single winning committee or score comparison. The hardness is therefore a candidate-selection problem represented by weighted coefficients, not a phenomenon involving a continuous society.
Changing the type space cannot repair this while preserving the paper’s problem. GreedyPAV and batch PAV depend only on the approval set \(A\), so any locations, demographics, prices, or latent traits can be pushed forward to the same mass \(\mu_A\). If those attributes affect the rule, they define a different voting rule. If voters have fractional approvals, or committees become fractional, the model is no longer the paper’s approval-based multiwinner problem. If one asks for the volume of tie-inducing masses, perturbation robustness, or random-mass probabilities, those may be worthwhile new questions, but they are not mirrors of Theorem 3.5 or Proposition 3.1.
This leaves a genuine weakness in the negative case. The paper does have named computational results, approval ballots admit a natural repeated-cohort interpretation, and rational-clone fidelity is exact. Under ChoCo’s stated remit, that is enough to make the mirrors legitimate Class B/A formulations even if they are mathematically light. The case against can establish that the proposed continuization is mostly a representation lemma and probably not a high-value target for the programme; it cannot honestly establish the universal claim that no worthwhile mirror exists. Both anchors survive the stronger scrutiny.
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.