Representation with Incomplete Votes

There is a credible positive case, but it is narrow: the natural mirror is not “fractional committees.” It is the paper’s adaptive information-acquisition problem over a continuous population of approval types.

The strongest anchor is Theorem 4.1, proved in this paper. It gives a high-probability bound for Algorithm 2 in the noisy-query model. The underlying LS-PAV result is cited from Aziz et al. (2018), but the incomplete-vote query theorem itself is proved here. A second anchor is Theorem 3.4, also proved here, for exact adaptive queries. A useful boundary anchor is Theorem 3.3, the non-adaptive lower bound, again proved here. These are query-complexity results rather than P/NP classifications, but they are explicit algorithmic and lower-bound results about the computational resources needed to produce a fair committee.

The mirror I believe in has candidates \(C\), committee size \(k\), and approval types \(A\subseteq C\). A type is a complete approval pattern over the currently available comments: two users have the same type exactly when they approve and disapprove every comment identically. The society is a finite-support distribution \(\mu=(\mu_A)_{A\subseteq C}\), where \(\mu_A\) is the fraction of users of type \(A\). The selected committee remains an ordinary \(k\)-element subset \(W\subseteq C\); only the population is continuized.

For a queried set \(Q\subseteq C\), the exact population response is the marginal distribution

\[ \rho_Q(S)=\sum_{A:A\cap Q=S}\mu_A \qquad(S\subseteq Q). \]

Thus an exact query reveals the proportions of users exhibiting every approval pattern on \(Q\). A noisy query samples \(A\sim\mu\) and returns \(A\cap Q\). This is precisely the paper’s partial-information model, with the finite electorate replaced by its type distribution. The paper itself explicitly motivates sampling with replacement from an underlying population distribution in footnote 6, so this is not an alien reinterpretation.

The continuous version of \(\alpha\)-EJR is also exact. A committee \(W\) satisfies it when, for every \(\ell\in[k]\) and every \(S\subseteq C\) with \(|S|=\ell\),

\[ \mu\bigl(\{A:S\subseteq A,\ |A\cap W|<\ell\}\bigr) < \frac{\ell}{\alpha k}. \]

Equivalently, there is no coalition of mass at least \(\ell/(\alpha k)\) that unanimously approves \(\ell\) common candidates while every member receives fewer than \(\ell\) approved committee members. This is the finite definition with voter counts replaced by mass; for rational \(\mu_A=n_A/n\), it is exactly the corresponding finite condition after scaling. The same replacement turns PAV into

\[ \operatorname{PAV}_\mu(W) =\sum_A\mu_A H_{|A\cap W|}. \]

A plausible high-multiplicity regime is a large civic platform running repeated consultations over a common, fixed comment slate. Millions of participants may come from recurring municipalities, organizations, language communities, or issue constituencies whose complete approval patterns repeat. The number of users is then enormous compared with the number of distinct approval types. This need not describe every Polis discussion; it is a legitimate instance regime of the paper’s problem. The paper’s guarantees remain worst-case over the type distribution, so the model is not made trivial by assuming that only a few opinion clusters exist.

My lead problem is:

Continuous Noisy-Query \(\alpha\)-EJR Committee Selection. The public instance consists of \(C,k,t,\alpha,\delta\), with \(m\ge t>k\), and a hidden society distribution \(\mu\) over approval types. An adaptive policy chooses query sets \(Q_1,Q_2,\ldots\), each of size at most \(t\), based on previous sampled responses \(A_j\cap Q_j\), where \(A_j\) is drawn independently from \(\mu\). After at most \(q\) samples it outputs a committee \(W\) of size \(k\). The policy is successful if, for every \(\mu\), it outputs an \(\alpha\)-EJR committee with probability at least \(1-\delta\). The optimization question is to minimize the worst-case number \(q\) of sampled users.

Theorem 4.1 supplies a direct Class-A result for this problem: Algorithm 2 succeeds using at most

\[ 578H_k \left\lceil\frac{m-k}{t-k}\right\rceil \left(\frac{\alpha k^2}{(1-\alpha)k+1}\right)^3 \log\!\left(\frac{4mk^4}{\delta}\right) \]

samples. For fixed \(\delta\), this is \(O(mk^6\log k\log m)\) at \(\alpha=1\), and \(O(mk^3\log k\log m)\) for fixed \(\alpha<1\). It also guarantees the paper’s \(\alpha\)-OAS property if that stronger condition is included.

This is recognizably the authors’ problem: the platform still decides which comments to show to incoming participants, responses are still incomplete, and the objective is still to obtain a fair committee from limited information. Nothing has been replaced by fractional outcomes. The continuous population simply makes the sampled responses draws from \(\mu\), exactly as their own large-population interpretation suggests.

The main follow-up questions are whether the theorem’s dependence on \(k,t,\alpha,\delta\) is tight, whether adaptive policies have a provable optimality or adaptivity gap, and whether one can design distribution-sensitive policies whose sample cost depends on the support size or geometry of \(\mu\), rather than only on \(m\).

The second mirror is the exact-query version:

Continuous Exact-Marginal \(\alpha\)-EJR Committee Selection. The instance is \(C,k,t,\alpha\) and a hidden distribution \(\mu\). The policy adaptively chooses sets \(Q_j\) of size \(t\), receiving the complete marginal vector \(\rho_{Q_j}\). It must output an \(\alpha\)-EJR committee while minimizing the worst-case number of exact marginal queries.

Here Theorem 3.4 gives the positive result. Algorithm 1 uses at most

\[ \left\lceil\frac{m-k}{t-k}\right\rceil \frac{\alpha k^2}{(1-\alpha)k+1}H_k \]

exact queries, yielding \(O(mk^2\log k)\) queries for \(\alpha=1\) and \(O(mk\log k)\) for fixed \(\alpha<1\). The proof carries naturally to \(\mu\): every PAV score and swap gain is an expectation under \(\mu\), and the certificate based on the largest marginal PAV gain is distributional rather than individual-specific. This is again Class A. The computational issue is not solving PAV globally—known to be hard in the discrete literature—but finding a fair committee by a local, query-efficient procedure.

Finally, Theorem 3.3 gives a genuine boundary problem:

Continuous Nonadaptive JR Elicitation. Before receiving any information, choose a family of query sets of size at most \(t\). Receive all corresponding marginal distributions \(\rho_Q\), then output a committee of size \(k\). The policy must satisfy continuous JR with probability at least \(1-\varepsilon\) for every hidden \(\mu\). The objective is the minimum number of precommitted queries.

Theorem 3.3 proves that for some \(k=\Theta(\log(1/\varepsilon))\), fewer than \(\Omega(m^{11})\) queries cannot suffice, for any \(t\). This lower bound survives the population limit: it is caused by indistinguishable aggregate approval structures and nonadaptivity, not by the need to count individual voters. It is therefore a useful boundary result rather than a reason to reject the mirror. The adaptive and nonadaptive versions together produce a meaningful landscape: tractable adaptive continuization, but an unavoidable information-theoretic barrier without adaptation.

The scope is deliberately limited. This mirrors the paper’s exact- and noisy-query committee-selection theorems and its nonadaptive lower bound. It does not claim a mirror for the matrix-factorization experiments, the growing-comment discussion, or every representation notion in the paper.

The weakest point is that the mirror needs query access to \(\mu\). If “given a continuous society” is interpreted as handing the algorithm the entire vector \(\mu\) explicitly, then the query problem collapses: the platform already knows the population and need not elicit anything. That objection is serious. The defence is that incomplete information is the paper’s computational subject, so an oracle-accessible distribution is not an arbitrary weakening but the continuous form of the paper’s input model. If that oracle interpretation is disallowed, this paper becomes a much weaker ChoCo candidate. Under the natural interpretation of its own query model, however, it offers a clean and author-recognizable Class-A continuous mirror.