| paper | What Do We Elect Committees For? A Voting Committee Model for Multi-Winner Rules |
| authors | P. Skowron |
| venue | IJCAI 2015 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(K\), a finite set of complete voter types \(T\), rational masses \(\mu_\theta\), and representation probabilities \(p_{\theta,c}\in[0,1]\), choose a \(K\)-element committee \(S\subseteq C\) maximizing \(U_\mu(S)=\frac{1}{K}\sum_{\theta\in T}\mu_\theta\sum_{c\in S}p_{\theta,c}\) under uniform random dictatorship.
A finite type population with mass vector \(\mu\), discrete candidates and integral committee \(S\), type-dependent representation probabilities \(p_{\theta,c}\), and objective \(U_\mu(S)\); equivalently, compute \(\bar p_c=\sum_{\theta\in T}\mu_\theta p_{\theta,c}\) and select the \(K\) largest values.
The strongest objection is that, after computing \(\bar p_c\), the mirror contains no population-level combinatorial structure beyond weighted row aggregation and sorting; this bounds its substantive reach but does not kill the well-posed mirror.
fatal: False
The mirror covers Proposition 3's random-dictatorship optimality and Proposition 5's fixed-committee evaluator. It leaves the other optimality theorems, full-rule results, simulations, and cited rather than proved hardness results outside its scope.
The strongest honest case is a modest Class-A mirror, anchored in the paper’s named positive computational results. The paper contains no numbered NP-hardness theorem of its own: its claims about Chamberlin–Courant hardness in the appendix are citations to other work, not results proved here. I would therefore not pretend that this paper supplies a hardness anchor.
My lead mirror is Continuous Random-Dictatorship Committee Optimization, corresponding to Proposition 3, proved in the paper. Proposition 3 states, in full, that in the probabilistic model—where voter \(i\) assigns candidate \(c\) a representation probability \(p_{i,c}\), with arbitrary such probabilities—the top-\(K\) rule is optimal when the elected committee uses uniform random dictatorship. The proof establishes that a committee \(S\)'s expected satisfaction for voter \(i\) is \(\frac{1}{K}\sum_{c\in S}p_{i,c}\), so maximizing total satisfaction is exactly maximizing the sum of the candidates' scores.
The continuous problem is as follows. There is a finite candidate set \(C\), a committee size \(K\), and a finite set \(T\) of complete voter types. A type \(\theta\in T\) specifies the relevant issue preferences and representation probabilities \(p_{\theta,c}\in[0,1]\) for every \(c\in C\). The society is a rational distribution \(\mu\) over \(T\), where \(\mu_\theta\) is the fraction of the population of type \(\theta\). The committee remains an integral \(K\)-element set \(S\subseteq C\), and it uses precisely the paper’s uniform random-dictatorship rule. The objective is to choose \(S\) maximizing
\[ U_\mu(S)=\sum_{\theta\in T}\mu_\theta\frac{1}{K}\sum_{c\in S}p_{\theta,c}. \]
Equivalently, define the population-average representation score \(\bar p_c=\sum_{\theta\in T}\mu_\theta p_{\theta,c}\). A solution is any \(K\)-candidate set containing the \(K\) largest values of \(\bar p_c\). Thus the problem is solvable in polynomial time in \(m\), \(\tau=|T|\), and the input bit length: compute the \(\bar p_c\)'s and sort them. I expect this mirror to be tractable.
This is a genuine population continuization. The mass \(\mu_\theta\) is the fraction of voters, not a probability replacing the committee’s random decision rule. Candidates, committees, and ballots remain discrete. If a finite election has \(n_\theta\) voters of type \(\theta\), then \(\mu_\theta=n_\theta/n\), and \(U_\mu(S)\) is exactly the original paper’s total expected satisfaction divided by \(n\). Conversely, every rational mass vector can be realized by a finite election after clearing denominators.
A plausible regime is a large electorate electing a parliamentary, faculty, union, or organizational committee. Millions of voters may fall into a relatively small number of stable preference-and-belief profiles: for example, party or occupational groups sharing the same assessments of how likely each candidate is to represent them on future issues. Here \(n\) is enormous while \(m\) and \(\tau\) are moderate. The paper’s authors should recognize this as their problem: the paper already treats \(p_{i,c}\) as the relevant representation data and evaluates committees by aggregate expected satisfaction.
The second mirror is Continuous Committee-Quality Evaluation, corresponding to Proposition 5 in Appendix A, proved in the paper. Proposition 5 states that, for a decision rule \(\mathrm{sw}\), a fixed committee \(S\), and a utility profile \(\langle u_i\rangle_{i\in N}\), the value \(v\) defined in Equation (the paper’s expected total ultimate satisfaction) can be computed in polynomial time. The proof uses dynamic programming: for each voter, \(A[j][\ell]\) records the probability that exactly \(\ell\) of the first \(j\) committee members vote according to that voter’s preferences; the recurrence is \(A[j][\ell]=u_{i,c_j}A[j-1][\ell-1]+(1-u_{i,c_j})A[j-1][\ell]\), followed by a linear combination with the decision-rule values \(\mathrm{sw}(\ell)\).
The continuous version takes \(C\), \(K\), a rational type distribution \(\mu\), rational type utilities \(u_{\theta,c}\), a rational table for \(\mathrm{sw}(0),\ldots,\mathrm{sw}(K)\), and a fixed committee \(S\). It asks for the exact aggregate satisfaction
\[ V_\mu(S)= \sum_{\theta\in T}\mu_\theta \sum_{\ell=0}^{K}\mathrm{sw}(\ell) \Pr\!\left[\sum_{c\in S}B_{\theta,c}=\ell\right], \]
where the \(B_{\theta,c}\) are independent Bernoulli variables with success probabilities \(u_{\theta,c}\). Its decision form may compare two shortlisted committees \(S\) and \(S'\), asking whether \(V_\mu(S)\ge V_\mu(S')\). The dynamic program is run once per type and the results are mass-weighted, giving polynomial time in \(\tau\), \(K\), and the encoding length. This is also Class A.
The two mirrors generate natural further questions: whether committee optimization remains tractable for other decision rules \(\mathrm{sw}\); how the complexity depends on \(\tau\), \(K\), and the structure of the utility vectors; whether a succinct density over a genuinely continuous score space permits exact or approximate evaluation; and whether the paper’s full-rule problem—choosing both \(S\) and \(\mathrm{sw}\)—has a useful high-multiplicity formulation.
The weakest point is important: these mirrors do not show discrete hardness disappearing. Proposition 3 is already easy for individually listed voters, and Proposition 5 merely compresses a sum over repeated types. A sceptical referee could therefore call this a valid but conservative high-multiplicity reformulation rather than a major new complexity phenomenon. Still, the mirror is faithful: it preserves the paper’s probabilistic committee model, makes the population—not the outcome space—the continuous object, gives precise polynomial-time problems, and has an exact finite-to-continuous dictionary.
The strongest negative case begins with the paper’s eligibility problem. It does not itself establish a complexity landscape for committee selection. Proposition 3 is an optimality characterization, not a complexity theorem; Proposition 5 is a dynamic-programming observation for evaluating a fixed committee. The appendix’s hardness claims about Chamberlin–Courant and median rules are explicitly imported from other papers. Thus a substantial continuous-computational programme would have to be added to this paper, rather than continuizing one of its own complexity results.
Proposition 3 is the better of the two proposed anchors, but its mirror is almost entirely bookkeeping. Under random dictatorship,
\[ U_\mu(S) = \sum_{\theta\in T}\mu_\theta\frac{1}{K} \sum_{c\in S}p_{\theta,c} = \frac{1}{K}\sum_{c\in S}\bar p_c, \qquad \bar p_c=\sum_{\theta\in T}\mu_\theta p_{\theta,c}. \]
The population distribution affects the problem only through \(m\) first moments. Once those moments have been computed, the committee problem is simply sorting candidates. Replacing a finite electorate by rational masses neither creates a mass-allocation decision nor exposes a population-level combinatorial structure. It compresses repeated rows of the original score matrix.
A stronger version does not rescue it. One could let a type contain the voters’ complete issue preferences, correlations, and beliefs about every candidate. But random dictatorship observes only one committee member, so the objective still depends only on the corresponding first-order averages. Alternatively, one could use a genuinely continuous type space, but then the new difficulty is representing or integrating the distribution over \(p\)-vectors; that is a different computational model, not a consequence of Proposition 3. With finite support it reduces again to weighted row compression.
The proposed mirror of Proposition 5 is weaker still. For a fixed committee,
\[ V_\mu(S)=\sum_{\theta\in T}\mu_\theta V_\theta(S), \]
and each \(V_\theta(S)\) is obtained by the paper’s dynamic programme. Comparing two committees therefore means running the same fixed-committee evaluator twice and taking a weighted sum. The population is not an object being optimized, perturbed, bribed, or controlled. It is merely an index compression for an already additive objective.
The natural rescue would be to optimize over \(S\), over the decision rule \(\mathrm{sw}\), or over a richer OWA-style objective. That could certainly become an interesting high-multiplicity problem, but it would no longer be Proposition 5. The paper supplies no complexity result for that problem: Theorem 4 gives an existence claim through enumeration, while the appendix mostly cites external results. The required algorithmic contribution would therefore be new research on multiwinner optimization, not a continuous mirror of this paper’s result.
This negative case has a real limitation. I cannot honestly claim that Proposition 3 has no sensible continuous interpretation. A large electorate containing repeated representation-belief profiles is plausible, and the rational finite-to-continuous dictionary is exact. If the programme counts a modest Class-A high-multiplicity winner-determination problem as worthwhile, that mirror survives. The strongest defensible conclusion is narrower: both proposed anchors collapse to linear aggregation or fixed-solution evaluation, and the paper itself contains no qualifying computational theorem whose population continuization would open the intended complexity landscape. That is a weak negative against the mirror’s research value, not a universal proof that no worthwhile scenario can be built.
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.