How Many Representatives Do We Need? The Optimal Size of a Congress Voting on Binary Issues

The strongest honest positive case is narrow: the paper contains no named computational-complexity result. Theorem 1, Theorem 2, Theorem 3, and Theorem 4 are asymptotic probability statements, not claims of membership in P, NP-hardness, FPT, or approximation complexity. Thus the paper is not itself a ChoCo complexity anchor in the strict sense. Still, it contains a very natural population-size optimization that has a credible high-multiplicity mirror.

The mirror I would use is this. A type is a competence level \(p_j\in[0,1]\), including everything the model uses: the probability of a correct vote and the assumption of conditional independence. The society is a finite-support distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\), where \(\mu_j\) is the fraction of society with competence \(p_j\). The regime is \(N\gg\tau\): for example, a large ensemble of classifiers or a large pool of experts divided into a small number of calibrated reliability tiers. The action is a mass fraction \(\kappa\) of representatives. Following the paper, the chosen mass must be the upper competence tail: all types above a threshold, and possibly part of one boundary type.

For a population scale \(N\), let \(x_j(\kappa)\) be the selected mass of type \(p_j\), with \(\sum_jx_j(\kappa)=\kappa\). Assuming \(Nx_j(\kappa)\) is integral, define independent random variables
\[ Y_j\sim\operatorname{Bin}(Nx_j(\kappa),p_j). \]
The reliability of the congress is
\[ Q_{N,\mu}(\kappa) = \Pr\!\left[ \sum_{j=1}^{\tau}Y_j>\frac{N\kappa}{2} \right]. \]
The problem is to output an admissible \(\kappa^\star\in\arg\max_\kappa Q_{N,\mu}(\kappa)\). Direct democracy is \(\kappa=1\). This is a genuine population continuization: individual identities disappear, mass is the decision variable, and the objective remains exactly the paper’s probability of a correct majority.

The parameter \(N\) is important. A literal nonatomic continuum of independent votes has zero sampling noise by the law of large numbers, so majority correctness collapses to a deterministic condition. \(N\) is therefore the finite-population fluctuation scale, analogous to the system-size parameter in statistical mechanics. The continuum object is \(\mu\); \(N\) controls the reliability resolution at which its aggregate vote is observed.

My lead anchor is Theorem 1, proved in this paper. It states that when the ordered competences are \(p_{(i)}=(N+1-i)/(N+1)\),
\[ (3-2\sqrt 2)N-O(1)\le K^\star\le \frac{N}{2}+O(1). \]
The corresponding problem is Uniform-Competence Continuous Congress Optimization: given the uniform competence distribution, or a rational finite-tier approximation to it, compute the optimal selected mass \(\kappa^\star\). The solution is a congress mass together with its reliability, not a list of named representatives.

This is recognisably the authors’ problem. The action is still “how many of the best experts should we retain?”, the objective is still majority accuracy, and the conclusion concerns the fraction of the population selected. The finite-tier regime is also plausible: many classifiers can share the same architecture, training procedure, calibration score, or audited reliability tier. I would expect the finite-type version to be tractable, at least approximately, by generating-function or dynamic-programming methods for the Poisson-binomial probability. The theorem’s exact constants need not survive fixed-tier discretization, so the honest prediction is only that the optimal mass remains bounded away from zero under suitable distributions. This is a Class A candidate, not a transferred hardness result.

A second credible anchor is Theorem 2, proved here; its proof uses Lemma 3, the cited Dvoretzky–Kiefer–Wolfowitz inequality. It considers a competence distribution \(D\) supported on \([L,H]\), with Lipschitz inverse CDF, and proves with high probability that
\[ c_HN-O(1)\le K^\star\le c_LN+O(1), \]
where
\[ c_H=1-F\!\left(\frac{1}{1+\sqrt{(1-H)/H}}+M\varepsilon\right) \]
and
\[ c_L=1-F\!\left(\frac{1}{1+\sqrt{(1-L)/L}}-M\varepsilon\right). \]

The matching continuous problem is Distributional Congress Certification. Its input is a rationally represented competence distribution \(F\), support bounds \(L,H\), a Lipschitz parameter \(M\), a population scale \(N\), and a confidence parameter \(\delta\). It must output a mass interval \([a,b]\) certified to contain the optimal congress fraction with probability at least \(1-\delta\), or compute a \(\delta\)-approximation to the optimal fraction itself. Theorem 2 supplies the form of the certificate.

This mirror is arguably more natural than the uniform one: the society is explicitly given by a distribution over competence types, and the result is about how the distribution’s upper tail determines the correct representative mass. With explicit finite support, I again expect a tractable or approximation-tractable problem. With succinct continuous CDFs, the representation and numerical-oracle model become part of the complexity question.

A third, weaker but still worthwhile anchor is Theorem 4, proved in Appendix A. It studies \(k=N^r\), for \(0<r<1\), and gives conditions under which a polynomial-sized congress is more or less accurate than direct democracy.

Its mirror is Polynomial-Mass Congress Dominance. Given a sequence of competence distributions \(\mu_N\), an exponent \(r\), and the finite-population scale \(N\), decide whether
\[ Q_{N,\mu_N}(N^{r-1})>Q_{N,\mu_N}(1). \]
A solution is a yes/no answer together with the two reliabilities, or an asymptotic certificate that the inequality holds for all sufficiently large \(N\). This preserves the paper’s central comparison while making the vanishing congress size a mass quantity: the congress has fraction \(N^{r-1}\) of society rather than merely \(N^r\) named members.

For each of these mirrors I would expect tractability in the explicit finite-type model, at least for additive approximation. No hardness transfers, because the paper supplies no hardness anchor. The interesting open questions are whether one can compute optimal mass with \(N\) given succinctly, whether one can optimize reliability minus a per-representative cost, how to learn \(\mu\) from samples, and whether correlated votes or weighted majority rules create genuine Class C behaviour.

The weakest point is serious: Theorem 1’s benchmark has essentially one distinct competence value per voter, so its literal instance family is not high-multiplicity. Moreover, preserving the paper’s probabilistic objective requires the extra scale \(N\); without it, a literal continuum destroys the voting noise. Finally, the resulting finite-type reliability calculation may be algorithmically straightforward, making this more a clean population formulation than an immediate contribution to the complexity landscape.

The positive case survives only in the more modest form: the paper offers a faithful, nontrivial mass-level decision problem whose natural finite-type regime is large and plausible, and whose main question is exactly the paper’s question about optimal congress size. It is a promising starting point for a ChoCo extension, but not a qualifying computational anchor by itself.