d4-conf-aldt-2017-0007

My lead is Pessimistic Mass Campaigning. Its anchor is Theorem 10, proved in this paper: given an integer \(h\), a set of pessimistic voters with preference functions and individual utility thresholds, deciding whether there is a theory \(T\) for which at least \(h\) voters have utility at least their respective thresholds is NP-complete. The paper proves this by reduction from CNF-SAT. [The paper’s arXiv version](https://arxiv.org/abs/1706.06243) prints this as Theorem 10.

Here is the continuous version. The issues are \(X=\{x_1,\ldots,x_d\}\). A type \(\theta\) consists of a preference vector \(p_\theta:X\to[-1,1]\) and a turnout threshold \(k_\theta\); agents of that type evaluate platforms identically. The input gives a finite support of \(\tau\) types, with rational masses \(\mu_\theta\ge 0\) summing to \(1\), and a rational quota \(q\). For a world \(\omega:X\to\{-1,1\}\), let
\[ u_\theta(\omega)=\sum_{x_i\in X}p_\theta(x_i)\omega(x_i). \]
The question is whether there is a satisfiable campaign theory \(T\) such that
\[ \sum_{\theta:\ \min_{\omega\models T}u_\theta(\omega)\ge k_\theta}\mu_\theta\ \ge q. \]
A solution can be given as \(T\), or equivalently as one complete assignment \(\omega\). That equivalence preserves the paper’s problem: if a type meets its pessimistic threshold under \(T\), every world modeled by \(T\) meets it, so any one such world preserves all the qualifying mass. Conversely, a complete theory describing \(\omega\) gives each type exactly \(u_\theta(\omega)\). Thus the mirror keeps the authors’ candidate-platform decision and pessimistic voter model intact.

The regime is a large electorate represented by cohorts sharing the same issue preferences and minimum utility needed to turn out—for example, a campaign’s modeled voter segments. The number of people can be large while the number of distinct preference-and-threshold types is much smaller. Mass means the fraction of the electorate in each cohort, and the quota asks what fraction the candidate can motivate. This makes the population itself continuous; the issues, worlds, and platform remain discrete.

I expect this problem to be NP-complete by hardness transfer. The paper’s reduction gives each CNF clause a pessimistic type: for a clause with \(r\) literals, set \(p_\theta(x_j)=1/r\) for a positive occurrence, \(-1/r\) for a negative occurrence, and \(0\) otherwise; set \(k_\theta=-(r-1)/r\). Give each clause type mass \(1/M\), where \(M\) is the number of clauses, and set \(q=1\). A world reaches every type’s threshold exactly when its assignment satisfies every clause. Duplicate clause types can be merged by adding their masses. Membership in NP follows by guessing \(\omega\) and summing the qualifying rational masses. The hardness is driven by the issue assignment and clauses, so it survives the move to population mass; this is a Class B case.

The main follow-up questions are whether useful algorithms emerge when parameterized by \(d\) or \(\tau\), and whether maximizing the qualifying mass admits approximation guarantees under restrictions on preference vectors or thresholds. The weakest point is that Theorem 10 does not establish hardness when \(\tau\) is fixed: its reduction can use a growing number of types. So it supports a credible continuous-population mirror and shows that discrete hardness can persist, while leaving open whether a large electorate with a small fixed set of cohorts has a more favorable complexity profile.