| paper | Average weights and power in weighted voting games |
| authors | Daria Boratyn, W. Kirsch, Wojciech Słomczyński, Dariusz Stolicki, K. Życzkowski |
| venue | MSS 2020 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given \(\tau\), \(k\), rational \(x\), and a society with \(\tau\) top-choice types whose mass vector \(\mu\) is drawn uniformly from \(\Delta_\tau\), compute \(D_{\tau,k}(x)=\Pr_{\mu\sim\operatorname{Unif}(\Delta_\tau)}[\mu_k^\downarrow\ge x]\) exactly or within additive error \(\varepsilon\).
Types are complete voter rankings grouped by top choice, \(\mu\in\Delta_\tau\) is their population-mass vector, and the objective is exact or approximate evaluation of the uniform-prior tail probability of \(\mu_k^\downarrow\); there is no intervention variable.
The strongest residual objection is that the mirror evaluates an outer prior over societies and interprets \(W\) as vote-share mass rather than preserving the paper's individual weighted-player power game; the plurality application makes this a bounded semantic distance, not a fatal one.
fatal: False
The mirror covers Theorem 3 and its plurality vote-share application; it leaves the spline result, Coleman-efficiency bloc model, Penrose–Banzhaf analysis, and other analytical results untreated.
The strongest honest case is a qualified yes, led by Theorem 3. The qualification matters: this paper contains no named theorem, lemma, proposition, or corollary establishing a complexity classification such as NP-hardness, membership in P, W[1]-hardness, or FPT. The only NP-hardness statement is attributed to Zick, Skopalik, and Elkind (2011), so it cannot serve as an anchor for this paper. What follows is therefore a positive case based on the paper’s exact computational mathematics, not a full ChoCo complexity anchor.
The natural regime is a large electorate with \(N\gg\tau\) voters but only \(\tau\) relevant types. For the plurality interpretation suggested by the authors, type \(t\) is a top-choice class, \(\mu_t\) is its population share, and \(\mu\in\Delta_\tau\) is the continuous society. A finite electorate is recovered by taking \(N_t/N\approx\mu_t\). The uniform distribution on \(\Delta_\tau\) is then a prior over possible societies, not the population itself; the population object is \(\mu\).
My lead problem is Continuous \(k\)-th-Share Evaluation. Given \(\tau\), \(k\), and a rational threshold \(x\), compute
\[ D_{\tau,k}(x) = \Pr_{\mu\sim\mathrm{Unif}(\Delta_\tau)} \left[\mu^\downarrow_k\ge x\right], \]
or, in an associated design version, choose the largest \(x\) such that \(D_{\tau,k}(x)\ge\rho\). An exact solution is a piecewise-polynomial density or CDF; an approximate solution returns the value within additive error \(\varepsilon\).
The anchor is Theorem 3, proved in this paper. It states that if \(W\sim\mathrm{Unif}(\Delta_n)\), then \(W^\downarrow_k\) is absolutely continuously distributed, supported on \([1/n,1]\) for \(k=1\) and on \([0,1/k]\) for \(k>1\), with density
\[ f_{n,k}(x) = n(n-1)\binom{n-1}{k-1} \sum_{j=k}^{\min(n,\lfloor 1/x\rfloor)} (-1)^{j-k} \binom{n-k}{j-k} (1-jx)^{n-2}. \]
Under the mirror, \(W\) becomes the type-mass vector \(\mu\). This is a genuine population continuization: the question is about the distribution of the largest or \(k\)-th largest population share in a high-multiplicity society. The authors themselves say that Theorem 3 can be used to compute the probability that a candidate with a specified vote share wins under plurality, so they should recognize this interpretation as their problem rather than as an unrelated simplification.
I would expect this mirror to be Class A. The formula has only \(O(\tau)\) summands on each of \(O(\tau)\) intervals, and the large population size \(N\) disappears except for rounding error when returning to a finite electorate. Further questions include analogous exact algorithms for non-uniform Dirichlet priors, several candidates sharing a preference type, and explicit finite-\(N\) approximation guarantees.
A second, weaker mirror uses Theorem 19, proved in this paper. The theorem states that if \(U(w,q)\) is the weighted voting game induced by \(w\) and quota \(q\), \(W\) is uniform on \(\Delta_n\), and \(p\) is any real-valued function on weighted voting games, then
\[ q\longmapsto \mathbb E\!\left[p\!\left(U(W,q)\right)\right] \]
is a spline of degree at most \(n-1\).
The corresponding continuous problem is Type-Mass Quota Design. Let \(T\) be \(\tau\) coordinated voting types, let \(\mu_t\) be the mass of type \(t\), and define
\[ G(\mu,q) = \left\{ S\subseteq T: \sum_{t\in S}\mu_t\ge q \right\}. \]
For example, let
\[ C(\mu,q) = 2^{-\tau} \left| \left\{ S\subseteq T: \sum_{t\in S}\mu_t\ge q \right\} \right| \]
be the type-level Coleman efficiency. Given a target \(\rho\), the decision problem is to find
\[ q^\star = \max\left\{ q\in(1/2,1]: \mathbb E_{\mu\sim\mathrm{Unif}(\Delta_\tau)} [C(\mu,q)]\ge\rho \right\}, \]
or to compute the entire function \(q\mapsto\mathbb E[C(\mu,q)]\). Theorem 19 predicts that this function is a spline of degree at most \(\tau-1\).
For fixed \(\tau\), this looks tractable through polytope-volume or spline methods. When \(\tau\) is part of the input, I would expect a possible Class C boundary: the arrangement of coalition hyperplanes can be exponentially large, and the paper supplies structure but not a polynomial-time evaluation algorithm. This is exactly the sort of computational question ChoCo could add.
The weakness is clear. The second mirror requires coordinated type-level participation. If every infinitesimal voter independently joins a coalition, participation concentrates and the Coleman index becomes degenerate for quotas above \(1/2\). Thus the quota-design mirror is convincing only for federations, firms, or constituencies whose members act through type-level representatives. The first mirror is stronger because it needs no such modification: it concerns population mass directly.
So my positive verdict is narrow but defensible. The paper does support a continuous-population mirror for its order-statistical and averaged-rule-design results, with Theorem 3 as the strongest anchor and Theorem 19 as a promising extension. It does not support a claim that the paper already contains, or directly anchors, a continuous computational-complexity landscape.
This paper fails the programme’s primary gate: it contains no paper-owned theorem about the complexity of a computational problem, nor an exact, approximation, or parameterized algorithm for bribery, control, campaigning, or robustness. The only NP-hardness result mentioned belongs to Zick, Skopalik, and Elkind. The paper’s own results are probabilistic and geometric statements about random weight assignments. Thus any continuous-population problem must be invented after the fact; neither proposed anchor is actually a continuization of a computational result of this paper.
Theorem 3 is the strongest-looking case, but it relies on a level mismatch. In the paper, \(W=(W_1,\ldots,W_n)\) assigns voting authority to \(n\) named players. It is not a population distribution, and the uniform measure on \(\Delta_n\) is a prior over institutional weight assignments, not a society whose members have been aggregated into types.
The proposed identification \(W=\mu\) can be made, but only by changing the game. If \(\mu_t\) is the mass of a preference type, then the theorem concerns the share of a candidate’s electorate, not the voting power of the paper’s players. The resulting question
\[ \Pr_{\mu\sim\operatorname{Unif}(\Delta_\tau)} \bigl[\mu_k^\downarrow\ge x\bigr] \]
is a legitimate order-statistics calculation, but its input is an outer prior over societies rather than a society on which one performs a computational intervention. Given \(\mu\), finding \(\mu_k^\downarrow\) is merely a statistic of the supplied society; the theorem supplies no manipulation, control, robustness, or optimization problem.
The better attempted repair is to replicate each player by many identical voters and interpret the player’s weight as the mass of its type. That produces an unavoidable fork. If copies act independently, the largest individual weight tends to zero and the paper’s order statistic and pivotality questions disappear. If all copies of a type act together, then the copies are not the players in the relevant game: the \(\tau\) types are. The model has simply become the original finite \(\tau\)-player weighted voting game with weight vector \(\mu\). The large population is descriptively present but computationally invisible. This is a relabelling of the weight simplex, not a high-multiplicity relaxation of the paper’s problem.
Theorem 19 has the same defect more clearly. The proposed
\[ G(\mu,q)= \left\{ S\subseteq T:\sum_{t\in S}\mu_t\ge q \right\} \]
is a game in which entire types coordinate. But the paper’s Coleman index samples subsets of individual players. If there are \(N_t\) copies of type \(t\), a random individual coalition contains a random number \(X_t\) of those copies, not either all or none of them. In the natural equal-weight model, its total mass is
\[ \sum_t \mu_t\frac{X_t}{N_t}, \]
which concentrates at \(1/2\) as multiplicities grow. For every fixed \(q>1/2\), the Coleman efficiency therefore collapses in the continuum limit. The type-level expression \(G(\mu,q)\) is not that limit; it imposes a new bloc-coordination rule.
One can certainly study coordinated constituencies. But then the constituencies are the actual players, and Theorem 19 is already exactly the corresponding random-weight statement with \(n=\tau\). The population inside each constituency contributes no agent-level combinatorics. Conversely, retaining individual coalitions destroys the proposed theorem’s semantics. The two choices preserve either the formula or the population, but not both.
The spline theorem also does not provide an algorithmic anchor: its \(p\) is an arbitrary function on weighted games, and the theorem says only that an outer expectation is piecewise polynomial in \(q\). “Type-Mass Quota Design” would be a new stochastic geometry problem requiring additional modelling choices, not a continuous mirror of a computational result in this paper.
The honest negative case is therefore not that these neighboring questions are meaningless. Order statistics of random population shares and quota design for coordinated blocs may each be worthwhile elsewhere. It is that neither survives as a continuous-population version of this paper’s problem: one replaces voting authority by population share, while the other replaces individual participation by bloc coordination. The paper offers no computational result whose population continuization ChoCo could chart.
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.