| paper | A Quantitative Analysis of Multi-Winner Rules |
| authors | M. Lackner, P. Skowron |
| venue | IJCAI 2019 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\kappa_{\operatorname{AV}}(k,p)=k^{-1}\min_{0\le h\le k}[h+(k-h)p^{-h}]\). For CC, the guarantee is \(1\) for \(k=1\) and \(p/(p+1)\) for \(k=2\). For \(k\ge3\), put \(a=p-(p-1)/k\) and \(Z=2(k-1)p-k+3\). The CC guarantee is \((1+\max_{3\le h\le k}(ah-1)p^{-h})^{-1}\) when \((2p-3)a\le p-1\), and \(pZ/[pZ+2(k-1)p+1]\) otherwise. Every value is attained by a rational society and a worst tied winner. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), \(p\ge1\), and a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types, choose \(W\in\binom{C}{k}\) maximizing \(G_{p,\mu}(W)=\sum_{A\subseteq C}\mu_A\sum_{j=1}^{|A\cap W|}p^{-j}\), where \(\operatorname{AV}_\mu(W)=\sum_A\mu_A|Acap W|\) and \(\operatorname{CC}_\mu(W)=\sum_A\mu_A\mathbf{1}[A\cap W\ne\varnothing]\); compute the resulting AV and CC ratios and characterize their worst cases over \(\mu\) and tied winners.
Approval types \(A\subseteq C\) carry mass \(\mu_A\) with \(\sum_A\mu_A=1\); the decision variable is an integral committee \(W\in\binom{C}{k}\), the objective is the weighted \(p\)-geometric score, and AV/CC are weighted performance statistics.
Theorem 3 depends only on normalized approval-type masses, so the continuous formulation may add no population-sensitive phenomenon beyond re-encoding the paper's sufficient statistics.
fatal: False
The mirror covers the worst-case AV/CC guarantees in Theorems 3 and 1 under a mass-vector input; it leaves the empirical analysis, other rules, and cited but unproved PAV intractability outside.
The strongest honest case is a high-multiplicity approval-population mirror. The paper has no numbered theorem asserting NP-hardness, membership in P, W[1]-hardness, or FPT. Its statement that PAV is computationally intractable is unnumbered and cites earlier work. I therefore use the two strongest numbered results actually proved in this paper: Theorem 3 as the lead anchor, and Theorem 1 as a secondary anchor.
Take a finite candidate set \(C\), committee size \(k\), and approval types \(T=2^C\). A type \(A\in T\) is a complete approval set. A continuous society is a distribution \(\mu=(\mu_A)_{A\subseteq C}\), where \(\mu_A\) is the fraction of citizens with approval set \(A\). This is natural for public-facility selection: millions of residents may have the same set of acceptable hospital sites, while the number \(\tau\) of represented approval types is much smaller than the population \(n\). The selected committee remains an integral \(k\)-subset \(W\); only the population is continuous.
Define
\[ \operatorname{AV}_\mu(W)=\sum_{A\subseteq C}\mu_A|A\cap W|, \]
\[ \operatorname{CC}_\mu(W)=\sum_{A\subseteq C}\mu_A \mathbf 1[A\cap W\neq\varnothing], \]
and, for \(p\ge 1\),
\[ G_{p,\mu}(W) = \sum_{A\subseteq C}\mu_A \sum_{j=1}^{|A\cap W|}\frac{1}{p^j}. \]
A continuous \(p\)-Geometric winner is any \(W\in\binom Ck\) maximizing \(G_{p,\mu}(W)\). The population is fractional, but every unit of population receives the ordinary integral committee outcome.
My lead question is therefore:
Continuous \(p\)-Geometric Winner-and-Guarantee. Given \(C,k,p\), and a rational type distribution \(\mu\), compute a \(p\)-Geometric winning committee and its two performance ratios,
\[ \rho_{\mathrm{AV}}(\mu,W) = \frac{\operatorname{AV}_\mu(W)} {\max_{U\in\binom Ck}\operatorname{AV}_\mu(U)} \]
and
\[ \rho_{\mathrm{CC}}(\mu,W) = \frac{\operatorname{CC}_\mu(W)} {\max_{U\in\binom Ck}\operatorname{CC}_\mu(U)}. \]
At the guarantee level, the corresponding worst-case problem minimizes these ratios over all \(\mu\) and all \(p\)-Geometric winning committees, matching the paper’s use of the minimum over tied winners.
This is exactly the problem underlying Theorem 3, proved in the paper. The theorem states that the AV-guarantee of the \(p\)-Geometric rule lies between
\[ \frac{W(k\log p)} {k\log p+W(k\log p)} \quad\text{and}\quad \frac{2W(k\log p)}{k\log p}+\frac1k, \]
where \(W\) is the Lambert \(W\)-function, while its CC-guarantee lies between
\[ \frac{p-1}{p} \quad\text{and}\quad \frac{p}{p+k/(k+2)}. \]
Thus the theorem’s continuous interpretation says: for a society described by masses of approval types, how well does the selected committee preserve individual excellence and population coverage? The parameter \(p\) still controls the same trade-off: \(p=1\) gives AV, while \(p\to\infty\) approaches CC. Nothing has been simplified away.
I expect the per-instance ratio calculation to be tractable once a committee is supplied, but exact winner determination for general \(p\) is likely Class B: hardness should transfer through the integral choice of candidates, rather than disappear with population continuization. The special case \(p=1\) is easy, since AV selects the \(k\) candidates with largest approval mass. Further questions include the exact values of the two guarantees, parameterized complexity in \(k\), \(m\), and the support size \(\tau\), and whether any hardness depends on population multiplicity rather than candidate interactions.
As a second anchor, define the continuous PAV score by
\[ \operatorname{PAV}_\mu(W) = \sum_{A\subseteq C}\mu_A H(|A\cap W|), \]
where \(H(r)=\sum_{j=1}^{r}1/j\). The corresponding question is:
Continuous PAV Winner-and-Guarantee. Given \(C,k,\mu\), compute a committee maximizing \(\operatorname{PAV}_\mu(W)\), together with its AV and CC ratios as above; globally, determine the worst-case ratios over all continuous societies and tied PAV winners.
This mirrors Theorem 1, proved in the paper. It states that PAV’s AV-guarantee is between
\[ \frac{1}{2+\sqrt{k}} \quad\text{and}\quad \frac{2}{\sqrt{k}}, \]
and its CC-guarantee is between
\[ \frac12 \quad\text{and}\quad \frac12+\frac{1}{4k-2}. \]
This is especially valuable because the paper explicitly describes PAV as computationally intractable, albeit citing that fact from earlier work. The continuous version should remain Class B: for any finite profile with counts \(n_A\), setting \(\mu_A=n_A/n\) gives
\[ \operatorname{PAV}_\mu(W) = \frac{1}{n}\operatorname{PAV}(W), \]
so the maximizing committees are identical. Replicating every type \(L\) times makes the population arbitrarily large relative to the number of types without changing the answer. The discrete hardness therefore survives as candidate-selection hardness, not as an artefact of naming individual voters.
The bridge is exact for all these rules. If a finite profile has \(n_A\) voters of type \(A\), then \(\mu_A=n_A/n\), and every paper score is just multiplied by \(n\):
\[ \operatorname{AV}(W)=n\operatorname{AV}_\mu(W),\qquad \operatorname{CC}(W)=n\operatorname{CC}_\mu(W), \]
with the analogous identities for PAV and \(p\)-Geometric scores. Conversely, every rational \(\mu\) expands to a finite profile using a common denominator. Hence the continuous formulation is not a weaker problem or a fractional committee relaxation; it is the high-multiplicity version of precisely the same committee-selection questions.
The weakest point is that this mirror may look almost like normalized notation. Because the paper’s guarantees are homogeneous in the number of voters, many of its numerical conclusions probably transfer unchanged, and the paper does not itself advertise a population-continuum formulation. So I would not claim that the mirror automatically produces a new theorem. The positive case is instead that the formulation is a genuine, referee-recognizable high-multiplicity computational problem: the input is a compact distribution over voter types, population granularity disappears, and the central integral committee problem remains intact. That makes the paper a good test case for determining whether its complexity comes from population multiplicity or from the combinatorics of selecting candidates.
The strongest negative case is that neither anchor is a computational result of this paper. Theorem 3 and Theorem 1 are approximation guarantees over approval profiles, not complexity classifications, algorithms, or optimization theorems. The paper’s only computational claim—PAV’s intractability—is cited from earlier work and is not proved here.
For Theorem 3, the proposed continuous formulation is perfectly well-defined, but it is already implicit in the paper. Let \(n_A\) be the number of voters with approval set \(A\), and let \(n=\sum_A n_A\). With \(\mu_A=n_A/n\), every committee \(W\) satisfies
\[ G_{p,\mu}(W)=\frac{1}{n}\operatorname{sc}_{p\text{-geom}}(A,W), \]
and likewise
\[ \operatorname{AV}_\mu(W)=\frac{1}{n}\operatorname{sc}_{\mathrm{AV}}(A,W), \qquad \operatorname{CC}_\mu(W)=\frac{1}{n}\operatorname{sc}_{\mathrm{CC}}(A,W). \]
Thus the winning committees, ties, and both ratios are exactly unchanged. Conversely, every rational \(\mu\) expands to a finite profile by clearing denominators. Theorem 3’s infimum over finite profiles is therefore already an infimum over rational points of the approval-type simplex. The proposed “continuous” theorem does not expose a population-dependent phenomenon; it changes the notation for the sufficient statistics on which the paper’s theorem already operates.
This is not an objection that the answer happens to remain the same. The more fundamental point is that the paper contains no computational population operation to continuize. Its only decision variable is the integral committee \(W\), while the population enters solely through aggregate coefficients. If one supplies \(\mu\) explicitly, one has a weighted approval profile. If one gives a succinct formula for \(\mu\), that is a new input-encoding problem, not a consequence of continuization.
The same defeats Theorem 1. Continuous PAV satisfies
\[ \operatorname{PAV}_\mu(W) = \frac{1}{n}\operatorname{sc}_{\mathrm{PAV}}(A,W), \]
so the proposed continuous PAV winner problem is again exactly weighted PAV winner determination. The cited hardness may well survive, but the paper itself does not establish that as a computational result, and the theorem being mirrored is only a bound on the AV- and CC-guarantees. Replicating voters merely multiplies every score by the same constant; no individual-level phenomenon is being relaxed.
The strongest attempted rescue would be to model residents by locations, with approval sets induced by which facilities they accept. But after pushing that location distribution forward through the map \(x\mapsto A(x)\), every quantity in the paper depends only on \(\mu_A\). The geometry is discarded. Refining types with location, identity, or utility therefore contributes nothing unless the rule or objective is changed. Making candidates or committees continuous would be an outcome-space continuization, outside the programme’s scope.
One could instead ask for the minimum mass that must be persuaded or transferred to change a \(p\)-Geometric or PAV winner. That may be a worthwhile new ChoCo problem, but it requires a new intervention model and cost metric—such as \(L_1\) mass movement, transport over approval types, or candidate-specific persuasion costs. It is not a continuous mirror of either theorem; it is a new control problem attached to the paper.
Accordingly, the negative case is strong as a judgment that this paper supplies no paper-specific computational mirror: both anchors are quantitative profile theorems whose population dependence has already been quotiented out. It is not strong enough to establish the universal claim literally. The approval-type continuum is a sensible high-multiplicity model, and continuous PAV or \(p\)-Geometric winner determination could legitimately be studied as Class B questions. If the programme accepts a new computational question built around an existing rule as a worthwhile mirror, then Theorem 3 survives and the negative case should concede defeat.
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.