d4-conf-wine-2015-0011

My lead is a narrow, exact mirror of Theorem 1, proved in this paper. It states that determining a winner under One-Step-\(k\)-Approval is NP-hard when \(k\) is part of the input and may have an exponentially large value. The proof reduces 3SAT with \(M\) clauses and \(m\) variables to an election with \(M\) voters and \(m\) binary issues, using \(k=7\cdot 2^{m-3}\). Each clause voter’s top-\(k\) set consists exactly of the assignments satisfying that clause, with the other issues free. A candidate receives all \(M\) votes exactly when its assignment satisfies every clause.

Call the mirror Continuous One-Step-\(k\)-Approval Winner. An instance has \(m\) binary issues, a binary-encoded integer \(1\le k\le 2^m\), and a support \(T\) of \(\tau\) types. A type is a compact acyclic CP-net together with the issue-order information used to derive its preference order. Each type has rational mass \(\mu_t\ge 0\), with \(\sum_{t\in T}\mu_t=1\). For a candidate \(c\in\{0,1\}^m\), define
\[ S_\mu(c)=\sum_{t\in T}\mu_t\,\mathbf{1}[c\text{ is among type }t\text{’s top }k\text{ candidates}]. \]
The task is to return a candidate maximizing \(S_\mu(c)\), with ties treated as co-winners. The decision is the winning configuration; the objective is its total approval mass. Each unit of mass still casts the type’s full top-\(k\) approval set—the model does not fractionalize anyone’s ballot or the outcome space.

A plausible regime is a large product-configurator or e-commerce population: customers have conditional preferences over configurations, and many share the same complete preference type. The mass records each type’s population share. \(k\) may be large when customers accept many configurations because some product features matter little to them. The paper itself studies this rule and proves Theorem 1 for precisely the large-\(k\) case, so the authors should recognize the mirror. It continuizes the population only; the candidates remain discrete configurations.

I expect Class B: hardness transfers. The reduction carries over by giving each clause type mass \(1/M\): a candidate’s score becomes its fraction of satisfied clauses, and a maximizer scores \(1\) exactly when the formula is satisfiable. Cloning each clause type any number of times makes the electorate arbitrarily large while leaving the support at most \(M\). More generally, clearing the denominators of rational masses recovers a finite high-multiplicity profile with exactly the same winner comparisons and ties. The hard combinatorics live in the exponentially large assignment agenda, not in keeping voters indivisible.

This covers Theorem 1’s winner-determination result, not the paper’s later destructive-bribery classifications. Further questions include whether the hard case becomes tractable under a common issue order, or under additional restrictions on the CP-nets or support. The main weakness is that the anchor is a preliminary result, and its reduction needs exponentially large \(k\); broad approval of that size may be less natural in many applications. Still, the mirror keeps the paper’s exact voting rule and candidate space, and its hardness gives a clear boundary: making the society continuous does not remove computational difficulty that comes from the agenda.