| paper | Committee Scoring Rules: Axiomatic Classification and Hierarchy |
| authors | Piotr Faliszewski, P. Skowron, A. Slinko, Nimrod Talmon |
| venue | IJCAI 2016 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 15
statement extracted from the paper’s text layer
Given \(m\) candidates, committee size \(k\), a finite set \(T\) of complete ranking types, rational masses \(\mu\in\Delta^{|T|}\), and decomposable scores \(f_{m,k}(i_1,\ldots,i_k)=\sum_{j=1}^{k}\gamma^{(j)}_{m,k}(i_j)\) satisfying the paper's adjacent-layer condition, compute a committee \(S\subseteq C\) with \(|S|=k\) such that \(F_\mu(S)\ge (1-1/e)\max_{|S'|=k}F_\mu(S')\), where \(F_\mu(S)=\sum_{r\in T}\mu_r f_{m,k}(\operatorname{pos}_r(S))\).
A society is a rational distribution \(\mu\) over complete ranking types. The decision variable is an integral committee \(S\) of size \(k\), and the objective is the per-capita decomposable score \(F_\mu(S)=\sum_{r\in T}\mu_r\sum_{j=1}^{k}\gamma^{(j)}_{m,k}(i_j(r,S))\).
The paper does not formally establish the weighted-input extension or its bit-complexity in the encoding of \(\mu\), so a prover must verify that Theorem 15's guarantee and runtime survive aggregation by type.
fatal: False
The mirror covers Theorem 15's approximation result for decomposable rules. It leaves the axiomatic hierarchy, monotonicity characterizations, nondecomposability results, exact winner determination, and hardness claims cited from other papers largely untouched.
The strongest honest case is a single algorithmic mirror, anchored in Theorem 15. The paper contains no numbered NP-hardness theorem of its own: Section 5 reports hardness results from other papers only in prose. I therefore would not misuse those citations as anchors.
The lead mirror is Continuous Decomposable Committee Selection, \(\mathrm{CDCS}_{\infty}\). Let \(C\) be \(m\) candidates or products, let \(k\) be the required committee size, and let \(T\) be the relevant finite set of complete ranking types, with \(|T|=\tau\). A continuous society is a rational distribution \(\mu\) over \(T\). For a type \(r\) and committee \(S\), write
\[ \operatorname{pos}_{r}(S)=(i_1,\ldots,i_k), \qquad i_1<\cdots<i_k, \]
for the positions occupied by the members of \(S\) in that type’s ranking. The rule is decomposable if
\[ f_{m,k}(i_1,\ldots,i_k) = \sum_{j=1}^{k}\gamma^{(j)}_{m,k}(i_j). \]
The continuous problem is:
\[ \text{find }S\subseteq C,\quad |S|=k, \]
maximizing the per-capita score
\[ F_{\mu}(S) = \sum_{r\in T}\mu_r \sum_{j=1}^{k}\gamma^{(j)}_{m,k}(i_j). \]
Equivalently, in the approximation version, output \(S\) satisfying
\[ F_{\mu}(S) \ge \left(1-\frac1e\right) \max_{\substack{S'\subseteq C\\|S'|=k}}F_{\mu}(S'). \]
The solution remains an integral committee \(S\); the population is continuous, not the committee. Thus this is not outcome-space fractionalization or a lottery over committees.
The anchor is Theorem 15, proved in this paper. It states that if \(R_f\) is a decomposable committee scoring rule of the above form, every single-winner scoring function \(\gamma^{(j)}_{m,k}\) is polynomial-time computable, and the scoring layers satisfy the paper’s adjacent-layer monotonicity condition—written with natural one-based indexing as
\[ \gamma^{(1)}_{m,k}(p) \ge \gamma^{(2)}_{m,k}(p) \ge\cdots\ge \gamma^{(k)}_{m,k}(p) \quad\text{for every }p\in[m], \]
then there is a polynomial-time algorithm which, given an election \(E=(C,V)\) and \(k\), outputs a committee \(W\) such that
\[ \operatorname{score}_{E}(W) \ge \left(1-\frac1e\right) \max_{\substack{S\subseteq C\\|S|=k}} \operatorname{score}_{E}(S). \]
The paper prints the adjacent condition with slightly inconsistent indexing; the displayed form above is its evident intended meaning.
A natural high-multiplicity regime comes directly from the paper’s Example 1. Imagine a large retailer choosing \(k\) shirts from \(m\) possible shirts to display. Customers belong to a small number of stable preference segments—say, demographic or institutional cohorts—and all customers in a segment have the same ranking of the shirts. The type mass \(\mu_r\) is the fraction of customers in segment \(r\). There may be millions of customers but only hundreds of ranking types, so \(\tau\ll n\).
For the paper’s concrete two-position example, a customer’s score is
\[ \alpha_{\lceil .20m\rceil}(i_1) + \alpha_{\lceil .05m\rceil}(i_2), \]
representing one “good enough” purchase or two “very good” purchases. The continuous question is therefore: which \(k\) shirts should be displayed to maximize expected purchases per customer? This is not an invented story detached from the paper; the paper itself presents the shirt-store interpretation of decomposable committee scoring rules. The same formulation can of course be read electorally, with citizens as ranking types and \(S\) as the elected committee.
The high-multiplicity bridge is exact. If a finite election has \(n_r\) voters of type \(r\), then
\[ \mu_r=\frac{n_r}{n} \]
and
\[ F_{\mu}(S)=\frac{\operatorname{score}_{E}(S)}{n}. \]
Thus the winning committees are identical. The continuous version simply makes the population proportions primary and permits arbitrary rational masses rather than requiring a named voter for every unit of mass. The theorem’s weighted version should carry over because the objective is a linear weighted sum over types; the algorithm would aggregate identical voters rather than process them individually.
I would classify this anchored approximation problem as Class A. Its tractability comes from the structural decomposability condition and the polynomial-time approximation argument, not from replacing the committee by a fractional object. The continuous formulation exposes the genuinely distributional question—optimal committee selection for a population distribution—and gives runtime naturally measured in \(m\), \(\tau\), and the encoding length of the masses. It does not claim that exact winner determination becomes polynomial: Theorem 15 establishes only the \((1-1/e)\)-approximation guarantee, and exact optimization remains a separate question.
The main follow-up questions are whether exact \(\mathrm{CDCS}_{\infty}\) is hard for particular decomposable or OWA-based rules, whether fixed \(\tau\) or fixed \(k\) yields stronger algorithms, and whether the approximation ratio improves for threshold rules such as the shirt-display example. One can also ask for a formal rounding theorem relating arbitrary continuous masses to finite elections, and for a characterization of when type aggregation changes exact complexity rather than merely compressing the input.
My weakest point is that this is an algorithmic anchor, not a hardness anchor, and Theorem 15 already gives an approximation algorithm for ordinary finite elections. The paper therefore does not demonstrate that continuization dissolves a discrete hardness result. Its positive case is narrower: the authors explicitly study decomposable committee optimization, explicitly give a repeated-customer application, and their theorem naturally survives when the electorate is represented by type masses. That is a genuine continuous-population mirror, even though this particular result does not show a new complexity separation.
The strongest case against this mirror is that it adds no genuinely continuous computational structure. But it is not strong enough to defeat the anchor under ChoCo’s rules.
For any rational distribution \(\mu\), choose a common denominator \(N\) and create \(N\mu_r\) copies of each ranking type \(r\). Then, for every committee \(S\),
\[ \operatorname{score}_E(S) = N\sum_r \mu_r f_r(S) = N F_\mu(S). \]
Thus the winning committees and every multiplicative approximation guarantee are identical. Conversely, every finite election can be compressed into its vector of type multiplicities. The proposed continuous problem is therefore exactly weighted committee selection, with the weights written as proportions rather than voter counts.
This is not merely a complaint that “continuization does not help”; that would be inadmissible. The more fundamental point is that Theorem 15 never uses individual identity, population transfers, a limiting argument, or any operation over a continuum. It uses only an additive objective over ranking types. The finite theorem already contains the entire mathematical mechanism. A weighted version may be worth stating and proving formally, especially when the denominator of \(\mu\) is exponentially larger than its encoding, but that is a high-multiplicity reformulation of the same optimization problem, not a new continuous phenomenon.
The better versions do not escape this collapse. If customers have continuously varying utilities but the rule observes only rankings, the distribution pushes forward to the finite distribution over rankings. If demographic labels or other attributes affect scores, then they become part of the type, yielding the same finite weighted formulation. If one makes the committee fractional or introduces lotteries, one has moved to outcome-space continuity, which is outside the programme’s target. If one adds bribery, control, or robustness over the population, those could be worthwhile ChoCo problems, but they are new problems not anchored in this paper’s theorem.
Still, this does not establish that no worthwhile mirror exists. The retailer example is a convincing high-multiplicity regime, Theorem 15 is a named computational result, and the weighted extension is mathematically natural. Existing high-multiplicity work cannot be used against it, and there is no prior continuous treatment that creates a genuine collision. My negative case can therefore lower the priority of this mirror as a shallow re-encoding, but it cannot honestly defeat it. The proponent’s anchor survives.
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.