| paper | d4-conf-aaai-2018-0933 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable, with exact computation in \(\mathrm{FP}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a candidate set \(C\) of size \(m\), committee size \(k\), a decomposable committee scoring rule with polynomial-time computable rational component scores, a partial committee \(W\subseteq C\) with \(|W|<k\), and a society supported on \(\tau\) complete rankings \(t\), each with positive rational mass \(\mu_t\) summing to \(1\), define \(Q_\mu(S)=\sum_t\mu_t f_{m,|S|}(\operatorname{pos}_t(S))\) and \(Q_\mu(\varnothing)=0\). Compute, exactly, for every \(c\in C\setminus W\), \(B_\mu(c;k,W)=\sum_{S\subseteq C:\,W\subseteq S,\,|S|=k-1}\bigl(Q_\mu(S\cup\{c\})-Q_\mu(S)\bigr)\), and return a candidate maximizing this value. Is this computable in time polynomial in \(m\), \(\tau\), and the input bit length \(L\)?
The society is a rational distribution over complete ranking types. Candidate scores for each committee are averaged by type mass, and the output is the exact vector of restricted Banzhaf values and a maximizing candidate for the paper’s next selection step.
The mirror covers Theorem 2’s computation of restricted Banzhaf values for decomposable committee scoring rules. It does not cover the complexity of finding winning committees, the other heuristics, or the experimental results.
My lead is Continuous Restricted Banzhaf Evaluation. It mirrors a precise computational component of the paper’s Banzhaf heuristic.
Take a candidate set \(C\) of size \(m\), a committee size \(k\), and a finite set \(T\) of voter types, where each type is a complete ranking of \(C\). The society is a distribution \(\mu\) with positive rational masses \(\mu_t\) summing to \(1\); its input lists the \(\tau\) supported rankings and their masses. For a committee \(S\), let
\[ Q_\mu(S)=\sum_{t\in T}\mu_t f_{m,|S|}(\operatorname{pos}_t(S)), \]
with \(Q_\mu(\varnothing)=0\). Given a partial committee \(W\), with \(|W|<k\), compute for every \(c\in C\setminus W\)
\[ B_\mu(c;k,W)= \sum_{\substack{S\subseteq C\\W\subseteq S,\ |S|=k-1}} \left(Q_\mu(S\cup\{c\})-Q_\mu(S)\right). \]
The output is the exact vector of these values, together with a candidate maximizing it—the next choice in the paper’s Banzhaf construction. Require the scoring rule to be decomposable,
\[ f_{m,j}(i_1,\ldots,i_j)=\sum_{r=1}^{j}\gamma^{(r)}_{m,j}(i_r), \]
with polynomial-time computable, rational-valued component scores of polynomial bit length.
The anchor is Theorem 2, proved in this paper: for every decomposable committee scoring rule whose single-winner scoring functions are polynomial-time computable, there is a polynomial-time algorithm to compute the restricted Banzhaf values of each candidate in a given election. The continuous question above asks for those same values when the electorate is supplied as masses over rankings. The paper’s vote-by-vote additivity makes the extension direct: compute each supported ranking’s contribution and weight it by \(\mu_t\). I expect this mirror to be tractable in time polynomial in \(m,\tau\), and the mass bit length \(L\), under the stated score representation.
A fitting regime is a large membership organization electing a council from a fixed slate: for example, hundreds of thousands of voters ranking several dozen candidates, with many voters sharing one of a few hundred recurring full ballot orders. The type is the complete ballot; mass is the fraction of members casting it. That gives \(n\gg\tau\), while preserving the paper’s candidates, committee scores, and Banzhaf candidate-selection step. The authors should recognize this as their problem: only the electorate’s representation changes, and the Banzhaf values and their role in the heuristic remain the same.
The paper also says in prose that fixed-constant-\(t\) \(t\)-Borda rules are NP-hard to compute, citing Skowron, Faliszewski, and Lang (2016). The supplied text gives no numbered result for that claim, so I do not treat it as a formal anchor here. My case rests on Theorem 2; it covers the Banzhaf computation, not the complexity of finding an optimal committee. In particular, it does not claim that continuization removes hardness from winner computation.
The weakest point is that this is a narrow, already-tractable subproblem: the theorem is about computing the Banzhaf values, not proving the heuristic finds a winning committee, and its continuous version largely exploits linear aggregation over types. The mirror is nevertheless faithful and precise. It also raises useful next questions: does exact winning-committee computation for fixed-\(t\) \(t\)-Borda remain hard on rational societies, and which nondecomposable committee scoring rules make continuous restricted-Banzhaf evaluation hard?
The strongest case against this anchor is that the continuous version adds no new structure to the Banzhaf calculation. For each supported ranking \(t\), compute its contribution \(b_t(c;k,W)\) to candidate \(c\)’s restricted Banzhaf value; then \(B_\mu(c;k,W)=\sum_t\mu_t b_t(c;k,W)\). The paper’s vote-by-vote additivity already supplies the calculation. A rational society is also a finite election’s multiplicity vector divided by a common denominator. So the proposed mirror is a weighted-input corollary, not a new optimization problem or a new interaction between population structure and the committee.
That makes it a modest use of ChoCo’s research time. Its output is an intermediate vector used by a heuristic, rather than a winning committee or an intervention in the society. And the proposed membership-organization scenario depends on many members sharing one of relatively few *complete* rankings, a stronger condition than sharing broad political preferences.
But these objections do not defeat the anchor under the programme’s stated criteria. Theorem 2 is a named computational result; complete rankings are valid types; and a large organization with recurring ballot templates is a plausible high-multiplicity regime. The weighted extension gives exact values in time polynomial in \(m,\tau,L\), and the selected candidate remains the next step in the paper’s Banzhaf construction. Neither the result’s apparent ease nor its role as a subroutine disqualifies it: an outside answer does not invalidate a well-posed mirror, and one emphatic mirror is enough.
So the negative case here is weak. I cannot honestly claim that there is no worthwhile continuous mirror: this 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.