| paper | Representative Committees of Peers |
| authors | R. Meir, Fedor Sandomirskiy, Moshe Tennenholtz |
| venue | JAIR 2021 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→split discrete result → its continuous mirror
Answer: \(R_1^\star=R_2^\star=2\). For \(n=2\lceil k/2\rceil-1\ge3\), \(R_k^\star=1+(1-2p_n)q_n(p_n)/p_n\), where \(q_n\) is the binomial majority tail and \(p_n\in(0,1/2)\) uniquely satisfies \(p_n(1-2p_n)q_n'(p_n)=q_n(p_n)\). Moreover, \(R_k^\star=1+C/\sqrt{k}+o(k^{-1/2})\), with \(C=\max_{a\ge0}2a\Phi(-a)=0.3399424\ldots\). Exact rational evaluation is polynomial in \(m,\tau,k,L\), with unavoidable worst-case output size \(\Omega(k)\). Additive estimates and two-type rational witnesses are computable in time polynomial in \(L,1/\varepsilon\), with witness size \(O(1+\log(1/\varepsilon))\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(m\), \(k\), a finite explicit type set \(T\subseteq\{0,1\}^{m}\), and rational masses \(\mu_x\) summing to \(1\), compute \(R_k(\mu)=\mathbb{E}[SC_\mu(Z)]/\min_{z\in\{0,1\}^{m}}SC_\mu(z)\), where \(k\) types are sampled independently from \(\mu\), \(Z\) is their coordinate-wise majority with uniform tie-breaking, and \(SC_\mu(z)=\sum_{x\in T}\mu_x d_H(x,z)\); in the robust version, determine \(R_k^\star=\sup_{m,T,\mu}R_k(\mu)\) and an \(\varepsilon\)-optimal rational witness.
A high-multiplicity committee-election model in which complete binary-issue preference types \(x\) carry population mass \(\mu_x\); the random committee is generated by \(k\) independent draws, the outcome is integral coordinate-wise majority, and the objective is expected Hamming social cost relative to the issue-wise optimum.
The opponent shows that \(R_k(\mu)\) depends only on issue marginals and that the paper already contains the key one-issue and binomial asymptotics; the proponent does not establish much additional computational content.
fatal: False
The mirror covers Theorem 2, Corollary 2, and the \(k\)-SORT approximation-ratio analysis, including the issue-reduction argument; it leaves Propositions 3–4, Corollary 4, and Theorem 5 untouched.
The strongest honest positive case is qualified: this paper has a natural population-continuization, but it has no named NP-hardness, polynomial-time, FPT, or similar complexity theorem. Its anchors are approximation and minimax results. Thus the mirror is substantively credible, but formally weaker than the ChoCo programme’s ideal inputs.
My lead anchor is Theorem 2, proved in this paper (with the full proof in Appendix A). It states that, for every population size \(n\), committee size \(k\le n\), and number of issues \(m\),
\[ AR_{n,m}(k\text{-SORT}) \le 1+\frac{6e^{-1/2}}{\sqrt{k}}, \]
while, whenever \(2(k+1)^2\le n\),
\[ AR_{n,m}(k\text{-SORT}) \ge 1+\frac{2\bigl(\Phi(-1)-1/\sqrt{k}\bigr)}{\sqrt{k}}, \]
where \(\Phi\) is the standard Gaussian cumulative distribution function. Thus the worst-case approximation ratio of uniformly sampling \(k\) voters and applying issue-wise majority is \(1+\Theta(1/\sqrt{k})\); this is made explicit in the paper’s Corollary 2.
The corresponding continuous problem is:
Continuous \(k\)-SORT Ratio\(_\infty\). An instance consists of an integer \(m\), a finite support \(T\subseteq\{0,1\}^{m}\), a rational distribution \(\mu\) over \(T\), and a committee size \(k\). A type \(x\in T\) is a complete binary-issue preference vector, and \(\mu_x\) is its population mass. Draw \(k\) representatives independently from \(\mu\), apply coordinate-wise majority among their vectors, and break committee ties uniformly. For \(z\in\{0,1\}^{m}\), define
\[ SC_\mu(z)=\sum_{x\in T}\mu_x d(x,z). \]
The task is to compute the expected approximation ratio
\[ R_k(\mu) = \frac{\mathbb E[SC_\mu(Z)]} {\min_{z\in\{0,1\}^{m}}SC_\mu(z)}, \]
and, in the robust version, determine
\[ R_{\infty}^{*}(k) = \sup_{m,T,\mu}R_k(\mu), \]
together with an optimal or \(\varepsilon\)-optimal witness distribution and an upper-bound certificate.
This is genuinely a population continuization. The outcomes remain integral binary issue decisions, and the committee remains an integral set of \(k\) representatives. Only the electorate becomes a mass distribution. For a rational \(\mu\), clearing denominators produces a finite electorate with repeated complete types; as the electorate grows, sampling without replacement converges to the independent draws in the continuous model.
The model is plausible in a large university, professional association, or civic organization whose many members fall into a small number of recurring complete policy profiles. In the sharpest regime, there are two types, corresponding to the two positions on one binary issue, with \(n\gg 2\) voters and \(k\ll n\). More generally, \(\tau=|T|\) is small relative to the population size. This is exactly the high-multiplicity regime rather than an assertion that every election is naturally continuous.
The continuous question is also computationally meaningful. Let
\[ p_j=\sum_{x\in T}\mu_xx_j \]
be the mass supporting alternative \(1\) on issue \(j\), and let \(q_k(p)\) be the probability that a \(k\)-sample majority selects \(1\). Then
\[ \mathbb E[SC_\mu(Z)] = \sum_{j=1}^{m} \left(p_j(1-q_k(p_j))+(1-p_j)q_k(p_j)\right), \]
whereas
\[ \min_z SC_\mu(z) = \sum_{j=1}^{m}\min\{p_j,1-p_j\}. \]
Thus evaluating a given continuous society is polynomial in the explicit support size, \(m\), \(k\), and the encoding length of \(\mu\). Because the ratio is a weighted average of one-issue ratios, the worst case reduces to a one-dimensional optimization over \(p\in[0,1/2]\); cloning one issue across coordinates realizes the bound. I would therefore expect this mirror to be Class A: fixed-instance evaluation is straightforward, and the robust problem admits efficient approximation through univariate polynomial optimization. Theorem 2 supplies the inherited bounds and predicts the same \(1+\Theta(1/\sqrt{k})\) landscape.
I would not use Theorem 5 as a second anchor. It proves that \(k\)-SORT is worst-case optimal among distance-based \(k\)-committee rules with issue-wise internal voting, but its construction uses \(n!\) issues to make \(n\) individually distinct voters equidistant. That is a poor high-multiplicity witness: the combinatorics live in the number of distinct agents and types, not in repeated population mass. Similarly, Propositions 3 and 4 give useful continuous follow-up questions about weighted delegation, but they are approximation bounds rather than complexity classifications.
The main weakness is therefore formal and substantive. Theorem 2 is not a complexity theorem, and the paper never asks whether an input problem is in \(P\), NP-hard, or fixed-parameter tractable. Moreover, the authors already analyze the large-\(n\) regime, so a critic can say that the continuous result merely takes a limit of their hypergeometric calculation. The positive reply is that the high-multiplicity formulation changes the computational object: it exposes \(\mu\), \(\tau\), rational encoding length, type compression, and the exact binomial limit as primary parameters. It also opens questions absent from the paper: exact computation of \(R_\infty^*(k)\), finite-population convergence rates, succinctly represented distributions, and whether minimax optimality of sortition survives under genuinely repeated types.
So my verdict would be: a credible, authors-recognisable continuous mirror of Theorem 2 exists, and it is likely tractable, but this is an amber positive case rather than a strong ChoCo case because the paper supplies no qualifying named computational-complexity anchor.
The anchor fails at the programme’s entry gate. Theorem 2 is a distortion bound for a fixed randomized rule, not a computational result: it gives no decision problem, optimization problem, complexity classification, or algorithm. The proposed mirror therefore creates a computational question after the fact rather than continuizing one posed by the paper.
More importantly, its continuous society contains no computational information beyond issue-wise marginals. Let \(p_j=\sum_x\mu_xx_j\), and let \(b_k(p)\) be the probability that majority among \(k\) independent draws selects \(1\). Then
\[ \mathbb{E}[SC_\mu(Z)] = \sum_{j=1}^{m} \left(p_j(1-b_k(p_j))+(1-p_j)b_k(p_j)\right), \]
while
\[ SC_\mu^\star=\sum_{j=1}^{m}\min\{p_j,1-p_j\}. \]
Thus two distributions with completely different type structure, correlations, and multiplicities are indistinguishable whenever they have the same vector \((p_1,\ldots,p_m)\). The proposed type space is therefore redundant: the “continuous society” collapses to \(m\) independent scalar frequencies. This is not a case where continuization exposes a mass-transfer LP, a pricing problem, or any other new computational object.
The robust version collapses further. Since the overall ratio is a weighted average of the one-issue ratios, one obtains
\[ R_k^\ast=\sup_{0\le p\le 1/2}\rho_k(p), \]
where \(\rho_k\) is the one-dimensional binomial-majority ratio. That is exactly the reduction already used in Lemma 1 and in the proof of Theorem 2. Replacing a finite frequency by a mass \(p\), and a hypergeometric sample by its binomial limit, adds notation but no new problem. The paper has already carried out the relevant high-population calculation.
The natural high-multiplicity interpretation is perfectly sensible: for one issue there can be two complete types with masses \(p\) and \(1-p\). But that concession cuts against the proposed mirror’s value. In the strongest such regime the entire instance is one rational number, and every richer type space is provably invisible to the objective. Exact evaluation from an explicit \(\mu\) consists only of computing the marginals and a binomial tail; the finite-population analogue is already handled by the paper’s hypergeometric calculation. Asking for finite-population convergence rates is useful probability, but not a new computational-social-choice problem.
The proposed repairs do not help. Allowing sampling without replacement returns to the paper’s finite model. Making \(k\) a non-negligible fraction of the population requires a new sampling and cost-scaling model, not a mirror of Theorem 2. Introducing distances, delegation, or committee optimization would make the joint type distribution matter, but would move to the weighted rules of Propositions 3 and 4 or to a different problem entirely. Theorem 5 is no better: its equidistant construction deliberately gives essentially every voter a distinct full preference vector; duplicating those voters creates zero-distance clone classes and destroys the argument’s premise.
So the strongest honest negative verdict is not that a high-multiplicity society cannot be imagined. It can. The problem is that, for every recognisable continuization of the paper’s main result, the population disappears into marginal frequencies and the paper’s own analysis already supplies the answer. This is a legitimate continuous asymptotic restatement, but not a worthwhile ChoCo computational mirror.
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.