d4-conf-aaai-2016-0086

My lead is a continuous version of the paper’s binomial-\(k\) winner determination problem. A type is a complete ballot: a vector of yes/no judgments satisfying the common integrity constraint \(\Gamma\). The society is a distribution \(\mu\) over those feasible ballots, with rational masses summing to \(1\). For a feasible consensus ballot \(x\), define

\[ S_{k,\mu}(x)=\sum_{t\in\operatorname{Mod}(\Gamma)}\mu_t \binom{\operatorname{Agr}(t,x)}{k}, \]

where \(\operatorname{Agr}(t,x)\) is the number of issues on which \(t\) and \(x\) agree. The outcome remains one complete, rational ballot; its score is the average binomial agreement across the population.

Call the resulting problem Continuous Binomial-\(k\) Winner Determination. An instance gives \(\Gamma\), the \(\tau\) supported ballots and their binary rational masses, \(k\), and a partial ballot \(b:J\to\{0,1\}\). It asks whether some score-maximizing feasible ballot \(x\) agrees with \(b\) on \(J\). A YES solution can include such a maximizing ballot; otherwise the answer is NO.

This is a natural high-multiplicity setting for a large online consultation or crowdsourced review platform: many people judge the same finite set of interdependent issues, and many submit the same complete judgment pattern. In the paper’s hotel-review example, six binary judgments allow at most \(64\) types, even if the reviewer population is in the thousands. For the complexity result, the agenda can vary across instances, with participants still numerous relative to the distinct ballots observed. Since the paper’s rules use only ballots, grouping agents who submit the same ballot loses no information those rules use.

The strongest anchor is Proposition 3, proved in this paper, building on Grandi’s cited result for \(k=1\). It states that WINDET for binomial-\(k\) rules \(F_{\{k\}}\)—given an integrity constraint, a finite profile of rational ballots, and a partial ballot, decide whether a winning ballot extends that partial ballot—is \(\Theta_2^P\)-complete for \(k\in O(1)\). The paper’s proof extends the hardness to each fixed constant \(k\). This is a direct mirror of that underlying winner-selection problem, with the finite profile replaced by its mass distribution.

I expect this version to be hardness-transferring (Class B). Given any discrete profile, set \(\mu_t\) to the fraction of its ballots equal to \(t\). Then \(S_{k,\mu}\) is the paper’s discrete score divided by the number of agents, so the maximizing ballots and the partial-ballot answer are unchanged. Thus the paper’s \(\Theta_2^P\)-hardness transfers. The continuous input may be more succinct than an explicit profile, so this establishes the lower bound rather than automatically settling the exact complexity under binary rational masses.

A second, useful anchor is Proposition 2, also proved in the paper. It states that the same WINDET problem is polynomial-time solvable when \(m-k\in O(1)\). Its continuous counterpart is the same problem above, restricted to \(k=m-d\) for fixed \(d\). Every winner must lie within Hamming distance \(d\) of some supported ballot: each supported ballot itself has positive score, while a ballot farther than \(d\) from every support type scores zero. Enumerating those neighborhoods takes at most \(\tau\sum_{i=0}^{d}\binom{m}{i}\) candidates; their feasibility and exact rational scores can then be checked. I expect this restricted version to be tractable, in time polynomial in \(m,\tau\), the mass bit length, and the size of \(\Gamma\), for fixed \(d\).

Together these anchors show a meaningful landscape for the mirror: small fixed \(k\) remains hard, while \(k\) close to \(m\) is tractable. Further questions include the exact complexity under binary rational masses, what happens for intermediate \(k\), and whether the paper’s conjecture that the smallest index in a more general \(F_{K,w}\) most affects complexity persists for continuous populations.

The mirror covers these winner-determination results, not the paper’s axiomatic analysis, polarization measure, or hotel-review experiments as such. Its weakest point is that the paper studies explicit finite profiles, whereas rational masses can succinctly encode populations whose denominator is exponentially large in the input length. Clearing denominators may therefore produce an exponentially long profile; the discrete classification transfers as hardness, but not necessarily as a complete classification. That gap is also a substantive continuization question: how does winner determination change when the population is supplied as support and mass? The authors should recognize the model as their problem—the scoring objective, feasible outcomes, and query are preserved—while the compressed population representation supplies the new computational question.