Answer: Both constructive and destructive modes are \(\mathrm{NP}\)-hard, even when every allowed-ranking set is a singleton.
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateonline-plurality-CCPV and online-plurality-DCPV are both coNP-hard. PROOF. We prove this by a reduction from the complement of the NP-complete problem Hitting Set: Given a set B = {b1,...,bm}, a nonempty collection S = {S1,...,Sn} of subsets of B, and a positive integer k ≤m, does S have a hitting set of size at most k, i.e., does there exist a set B′ ⊆B such that ∥B′∥≤k and for all Si ∈S , Si∩B′ ̸= /0. We turn an instance (B,S ,k) of hitting set into the follow- ing instance of online partition of voters. The set of candidates is {c,w,b1,...,bm} ∪A, where A = {ai | 1 ≤i ≤4mnk + 1}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), chair order \(\sigma\), distinguished candidate \(d\), and \(q\) ordered cohorts with binary-rational masses \(\alpha_i>0\), \(\sum_i\alpha_i=1\), and allowed rankings \(\Omega_i\), each cohort's common ranking is revealed on arrival. Does there exist a policy that, after observing each current ranking, assigns mass \(x_i\in[0,\alpha_i]\) to the left side and the rest to the right, such that for every allowed future ranking sequence the ties-promote plurality partition runoff succeeds? In constructive mode, success means some runoff winner \(w\) satisfies \(w\succeq_\sigma d\); in destructive mode, it means no runoff winner \(w\) satisfies \(w\preceq_\sigma d\). All population mass votes in the runoff for its highest-ranked finalist.
Let \(C\) contain \(m\geq1\) candidates, let \(\sigma\) be a strict chair order, and let \(d\in C\). Write \(a\succeq_\sigma b\) when the chair ranks \(a\) at least as highly as \(b\).
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses. Here types include cohort identity; \(\tau\) counts listed positive-mass cohorts, not possible rankings. Total society mass is \(1\).
The input includes a possibly empty history of cohorts with known strict rankings and fixed binary-rational left/right mass allocations, followed by \(q\geq1\) ordered cohorts of masses \(\alpha_i>0\). History mass plus \(\sum_{i=1}^q\alpha_i\) equals \(1\).
For each remaining cohort, \(\Omega_i\) is a nonempty explicitly listed set of strict rankings of \(C\); \(\Omega_1\) is a singleton giving the already revealed current ranking. Each later ranking is chosen arbitrarily from its own \(\Omega_i\) and revealed upon arrival.
After observing ranking \(i\), a deterministic policy irrevocably chooses a real \(x_i\in[0,\alpha_i]\), assigning that mass left and the remainder right. Its choice may depend on the revealed history but not future rankings.
Run mass-weighted plurality on \(C\) separately on each side. Ties promote: the union of both winner sets forms the finalists. A zero-mass side promotes every candidate. All society mass, including the history, votes in the plurality runoff for its highest-ranked finalist; all tied runoff winners belong to \(W\).
Constructive success means \(W\cap\{c\in C:c\succeq_\sigma d\}\neq\varnothing\); destructive success means \(W\cap\{c\in C:d\succeq_\sigma c\}=\varnothing\). The decision problem asks whether a policy guarantees the specified success for every allowed ranking sequence.
For each mode, is this continuous online plurality partition problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), \(q\), and total input bit length \(L\).
Discrete online plurality partition with ties promoting is \(\mathrm{coNP}\)-hard in both modes and belongs to \(\mathrm{PSPACE}\); discrete offline partition is \(\mathrm{NP}\)-complete in both nonunique-winner modes. [Source](https://arxiv.org/html/1203.0411v2). No classification of this precise continuous model was located.
Both constructive and destructive continuous online plurality partition are \(\mathrm{NP}\)-hard. Hardness holds even when every \(\Omega_i\) is a singleton, so all rankings are known in advance. This singleton restriction is, in fact, \(\mathrm{NP}\)-complete.
The proof below allows every split to be an arbitrary real number and uses dyadic rational input masses.
We reduce from perfect three-dimensional matching: given disjoint sets \(X,Y,Z\), each of cardinality \(k\), and triples \(S_1,\ldots,S_t\), does some collection of \(k\) triples cover \(U=X\cup Y\cup Z\)? This problem is \(\mathrm{NP}\)-complete. We use nonempty instances with \(k,t\geq1\); excluding the trivial empty instances preserves hardness. [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We regard each \(S_j\) as a three-element subset of \(U\). Define
\[
\]
\(D=2k+2,\qquad B=3D+2t+4,\qquad P=B+2k+1,\qquad A=P-4-2t=3D+2k+1.\)
We initially describe unnormalized masses. Section 2 converts them to dyadic masses summing to one.
The candidates are \(p,b,s_1,\ldots,s_t\), together with auxiliary candidates introduced below. Any displayed ranking is completed to a strict ranking by appending all unmentioned candidates in a fixed order.
An auxiliary cohort of mass \(r\), where \(0<r\leq1\), receives its own fresh candidate \(z\), ranks \(z\) first, and has its entire mass fixed on the left. Every such candidate is used first by exactly one cohort.
Consequently, every auxiliary candidate has first-round left score at most \(1\) and right score \(0\).
Construct the following history:
There are \(q=t\) remaining cohorts. Cohort \(j\) has mass \(1\) and the single allowed ranking \(s_j>p>b>\cdots\).
Let \(y_j\in[0,1]\) denote its unnormalized mass assigned left.
The total mass constructed so far is
\[
\]
\(N=8+2t+A+(B-4)+3kD=P+B+3kD.\)
Let \(T\) be the smallest power of two with \(T\geq N\), and put \(K=(T-N)/2\).
Add auxiliary cohorts contributing total mass \(K\) to \(p\) in the runoff and another total mass \(K\) to \(b\). Specifically, for each of these two totals, use \(\lfloor K\rfloor\) unit auxiliary cohorts and, if necessary, one auxiliary cohort of mass \(K-\lfloor K\rfloor\). Their rankings begin respectively with \(z>p>b\) and \(z>b>p\).
The resulting total mass is \(T\). Divide every cohort mass and fixed allocation by \(T\). Because \(T\) is a power of two and \(K\) is an integer or half-integer, all resulting masses and allocations are dyadic rationals.
All subsequent score calculations use unnormalized units; actual scores are divided by \(T\). A legal actual split \(x_j\) corresponds exactly to \(y_j=Tx_j\in[0,1]\).
Since \(N=O(t+k^2)\) and \(T<2N\), the construction has
\[
\]
\(m=O(t+k^2),\qquad \tau=O(t+k^2),\qquad q=t.\)
Every cohort, including every auxiliary cohort, is explicitly listed. With full strict rankings, the output bit length and construction time are both
\[
\]
\(O\!\left((t+k^2)^2\log(t+k+2)\right).\)
Thus this is a polynomial-time reduction under the specified support representation.
Both \(p\) and \(b\) have score \(2\) on each side.
For every selectable candidate \(s_j\), its left and right scores are respectively
\[
\]
\(1+y_j\quad\text{and}\quad1-y_j.\)
Every auxiliary candidate has left score at most \(1\) and right score \(0\). Hence the maximum score on each side is exactly \(2\), for every legal real-valued allocation.
The right winner set is therefore exactly \(\{p,b\}\). The left winner set is
\[
\]
\(\{p,b\}\cup\{s_j:y_j=1\}.\)
Writing \(J=\{j:y_j=1\}\), the finalist set is exactly
\[
\]
\(F=\{p,b\}\cup\{s_j:j\in J\}.\)
Every subset \(J\) is achievable: choose \(y_j=1\) for \(j\in J\) and \(y_j=0\) otherwise. Conversely, a fractional choice with \(y_j<1\) does not promote \(s_j\). This identifies the finalists for every real allocation.
Both sides contain positive anchor mass, so the zero-mass convention is respected automatically.
Let \(u(J)\) be the number of elements of \(U\) uncovered by the triples indexed by \(J\).
Candidate \(p\) receives:
Thus
\[
\]
\(\operatorname{score}(p)=4+2(t-|J|)+A+K=P+K-2|J|.\)
Candidate \(b\) receives its anchor mass \(4\), its auxiliary support \(B-4+K\), and mass \(D\) for every uncovered element. Hence
\[
\]
\(\operatorname{score}(b)=B+K+D\,u(J).\)
Each selected candidate \(s_j\) receives its own mass \(2\) and possibly element-cohort mass. An element cohort can vote for \(s_j\) only if its element belongs to \(S_j\). Since \(|S_j|=3\),
\[
\]
\(\operatorname{score}(s_j)\leq2+3D<B\leq\operatorname{score}(b).\)
Therefore every runoff winner belongs to \(\{p,b\}\). Their score difference is
\[
\]
\(\operatorname{score}(p)-\operatorname{score}(b)=2k+1-2|J|-D\,u(J).\)
If \(u(J)\geq1\), then, using \(D=2k+2\),
\[
\]
\(\operatorname{score}(p)-\operatorname{score}(b)\leq2k+1-D=-1.\)
Thus \(b\) is the unique winner whenever some element is uncovered.
If \(u(J)=0\), the difference is positive exactly when \(|J|\leq k\). But covering \(3k\) elements with three-element sets requires \(|J|\geq k\). Consequently, \(p\) is the unique winner exactly when \(J\) consists of \(k\) triples covering \(U\).
Such a cover is exact: its triples have total cardinality \(3k\), equal to the cardinality of their union, so they are pairwise disjoint.
We have proved:
\[
\]
\(W=\{p\}\ \Longleftrightarrow\ J\text{ is a perfect three-dimensional matching}.\)
For every other allocation, \(W=\{b\}\).
Put \(p\) first in the chair order and choose \(d=p\). The acceptable set is exactly \(\{p\}\). Constructive success is therefore equivalent to existence of a perfect matching.
Put \(p\) first and \(b\) second in the chair order, and choose \(d=b\). The forbidden set is exactly \(C\setminus\{p\}\). Destructive success is therefore equivalent to \(W=\{p\}\), again equivalent to existence of a perfect matching.
All ranking sets are singletons. Any split vector can be implemented by a deterministic policy, and every policy induces a split vector on the unique ranking sequence. The reduction thus proves \(\mathrm{NP}\)-hardness for both specified online problems.
When every \(\Omega_i\) is a singleton, enumerate the two nonempty first-round winner sets \(H_\ell,H_r\). There are fewer than \(2^{2m}\) pairs.
For each pair, its finalist set and runoff scores are fixed by the input rankings. Check whether those runoff scores satisfy the requested success condition.
If they do, test whether the guessed first-round winner sets are realizable. Let \(s_{a,h}(x)\) be candidate \(a\)'s first-round score on side \(h\). These are rational affine functions of the split variables. Introduce thresholds \(M_h\) and require
\[
\]
\(s_{a,h}(x)=M_h\quad(a\in H_h),\qquad s_{a,h}(x)<M_h\quad(a\notin H_h),\)
together with \(0\leq x_i\leq\alpha_i\).
These constraints characterize the winner sets exactly. They also handle zero-mass sides: all scores are then zero, so only the full candidate set can satisfy the constraints.
Strict inequalities can be checked by replacing each with
\[
\]
\(s_{a,h}(x)\leq M_h-\varepsilon,\qquad0\leq\varepsilon\leq1,\)
and maximizing \(\varepsilon\). The original system is feasible exactly when the optimum is positive: finitely many satisfied strict inequalities have a positive minimum slack. All variables can be bounded, and all coefficients are rational, so rational linear programming applies in polynomial bit complexity. [Aspvall and Stone, *Khachiyan’s Linear Programming Algorithm*](https://www.sciencedirect.com/science/article/pii/0196677480900024).
This gives deterministic time
\[
\]
\(2^{O(m)}\operatorname{poly}(m,\tau,q,L).\)
Alternatively, guessing the two winner sets and performing this polynomial-time verification proves membership in \(\mathrm{NP}\). Together with the reduction, the singleton restriction is \(\mathrm{NP}\)-complete in both modes.
Put
\[
\]
\(R=\prod_{i=2}^{q}|\Omega_i|,\)
with the empty product equal to \(1\). This is the number of allowed complete ranking sequences.
Expand the tree of revealed ranking prefixes. It has at most \(qR\) decision nodes. Assign one split variable to each node, shared by all descendant leaves. This enforces the information restriction exactly: a decision depends only on already revealed rankings.
For a deterministic policy, previous allocations are themselves determined by the ranking prefix, so this tree representation loses no permitted dependence on revealed history. Conversely, any assignment of legal splits to its nodes defines a deterministic policy.
Enumerate two nonempty winner sets at every leaf. There are at most \(2^{2mR}\) such assignments. At each leaf, compute the runoff outcome and reject the assignment if success fails there. For surviving assignments, impose the winner-set constraints from above simultaneously at all leaves, using the shared node variables. One rational linear program tests feasibility.
The resulting deterministic running time is
\[
\]
\(2^{O(mR)}\operatorname{poly}(m,\tau,q,R,L).\)
Since the ranking sets are explicitly listed, \(|\Omega_i|\leq L\), giving the bound solely in the requested parameters
\[
\]
\(2^{O(mL^{q-1})}\operatorname{poly}(m,\tau,q,L^{q-1},L).\)
For \(q=1\), both modes admit a polynomial-time algorithm.
Let \(a\) be the current cohort's top candidate. Only its scores vary:
\[
\]
\(s_{a,\ell}(x)=\ell_a+x,\qquad s_{a,r}(x)=r_a+\alpha_1-x.\)
All other first-round scores are fixed. Winner sets can change only at the at most \(2(m-1)\) values where one of these expressions equals another candidate's score. Test every breakpoint in \([0,\alpha_1]\), both endpoints, and one rational midpoint of each intervening interval. The winner sets are constant on each such open interval, so these tests are exhaustive.
There are \(O(m)\) tests, each requiring \(O(m\tau)\) rational operations to compute the runoff. The bit running time is
\[
\]
\(O\!\left(m^2\tau\,\operatorname{poly}(L)\right).\)
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-hardness in both modes for the precise continuous model. The singleton-ranking restriction is also correctly shown to be \(\mathrm{NP}\)-complete. I found no major or minor mathematical issues.
The stated source problem is perfect three-dimensional matching: each triple contains one element from each of three disjoint sets of size \(k\), and a solution consists of \(k\) triples covering all \(3k\) elements. This is the standard \(\mathrm{NP}\)-complete problem recorded in [Karp’s paper, reproduced here](https://sites.math.washington.edu/~thomas/teaching/m514_web/50YearsIP.pdf).
Treating the triples as three-element subsets of the disjoint union preserves their identity and the matching condition. Restricting to \(k,t\geq1\) does not remove the hard instances.
The definitions are internally consistent:
\(A=P-4-2t=3D+2k+1\).
In particular, \(A\) and \(B-4\) are positive integers, so all stated numbers of auxiliary cohorts are legal. Every auxiliary cohort has a distinct top candidate, ensuring that its candidate receives first-round support from exactly that cohort.
The anchor allocations sum to their respective cohort masses. The remaining cohorts have positive masses, their allowed-ranking sets are nonempty singletons, and \(q=t\geq1\). Completing the displayed ranking prefixes by appending unmentioned candidates produces strict rankings without changing any score calculation used in the reduction.
The total-mass calculation is correct:
\(N=8+2t+A+(B-4)+3kD=P+B+3kD\).
Since \(N\) is an integer, \(K=(T-N)/2\) is a nonnegative integer or half-integer. The padding adds exactly \(2K=T-N\), bringing total mass to \(T\). Zero residual masses are omitted, so every listed cohort remains positive.
Dividing by the power of two \(T\) produces dyadic masses and allocations. It also preserves all first-round and runoff comparisons. The correspondence \(y_j=Tx_j\) covers every permitted real split.
The bounds \(N=O(t+k^2)\) and \(T<2N\) justify the stated candidate and cohort counts. Listing all cohorts separately respects the task’s definition of \(\tau\), including cohort identity. Full rankings and binary encodings fit within the claimed construction time and output length:
\(O((t+k^2)^2\log(t+k+2))\).
Both anchors receive score \(2\) on each side. Selectable candidate \(s_j\) receives \(1+y_j\) on the left and \(1-y_j\) on the right. Auxiliary candidates receive at most \(1\) on the left and \(0\) on the right.
Consequently, the maximum score on either side is exactly \(2\). The right winner set is exactly \(\{p,b\}\), and the left winner set adds precisely those \(s_j\) satisfying \(y_j=1\).
Thus the claimed finalist set is valid for every real allocation, including fractional allocations:
\(F=\{p,b\}\cup\{s_j:j\in J\}\), where \(J=\{j:y_j=1\}\).
Every subset \(J\) is attainable by the stated endpoint choices. Both sides have positive anchor mass, so the zero-mass promotion rule creates no additional finalists.
All contributions have been accounted for correctly:
These facts give exactly the displayed scores:
\(\operatorname{score}(p)=P+K-2|J|\) and
\(\operatorname{score}(b)=B+K+D\,u(J)\).
The bound on a selected candidate is also valid. Only the three elements in its triple can contribute element-cohort support, regardless of overlaps or the ordering of incident candidates. Hence its score is at most \(2+3D\).
Since \(B=3D+2t+4>2+3D\), every selected candidate has strictly smaller runoff score than \(b\). Therefore all runoff winners belong to \(\{p,b\}\).
The score difference is correctly calculated as
\(2k+1-2|J|-D\,u(J)\).
If \(u(J)\geq1\), it is at most \(-1\), as claimed. Thus \(b\) wins uniquely whenever any element is uncovered.
If \(u(J)=0\), covering \(3k\) elements with triples requires \(|J|\geq k\). At \(|J|=k\), the difference is \(1\); at every larger integer cardinality, it is negative. Therefore there is no omitted tie case.
A cover by exactly \(k\) triples is a perfect matching: the total cardinality of the triples equals the cardinality of their union, forcing pairwise disjointness. The conclusion that \(W=\{p\}\) exactly for perfect matchings, and \(W=\{b\}\) otherwise, follows.
In constructive mode, putting \(p\) first and choosing \(d=p\) makes the acceptable set exactly \(\{p\}\).
In destructive mode, putting \(p\) first and \(b\) second and choosing \(d=b\) makes the forbidden set exactly \(C\setminus\{p\}\).
These choices implement the task’s predicates exactly. Neither reduction silently substitutes a different winner convention.
With singleton allowed-ranking sets, there is exactly one ranking sequence. Any split vector can be implemented by a deterministic policy, and every policy induces such a vector. Thus the existential split condition is equivalent to the required policy condition on these instances. This proves hardness for both online problems.
Enumerating two nonempty winner sets is exhaustive. Their union fixes the runoff outcome because rankings and total cohort masses are known, and runoff participation does not depend on the earlier allocation.
The equality constraints for winners and strict inequalities for nonwinners characterize the first-round winner sets exactly. They also implement the zero-mass convention: when every side score is zero, a proper subset cannot satisfy the strict inequalities.
The shared-\(\varepsilon\) test is valid because there are finitely many strict inequalities. Feasibility with strict inequalities gives positive minimum slack; positive feasible \(\varepsilon\) gives all required strict comparisons. When there are no strict inequalities, \(\varepsilon\) is independent and may equal \(1\), provided the remaining constraints are feasible.
The resulting problem has rational data and polynomial encoding length. Polynomial bit-complexity linear programming is applicable; this standard guarantee is also described in [Dadush and coauthors’ research paper](https://link.springer.com/article/10.1007/s10107-023-01956-2). Arbitrary real splits therefore cause no certificate-verification gap.
The stated deterministic time
\(2^{O(m)}\operatorname{poly}(m,\tau,q,L)\)
and membership in \(\mathrm{NP}\) are justified. Combined with the reduction, this establishes the claimed singleton-restriction completeness.
There are \(R=\prod_{i=2}^{q}|\Omega_i|\) leaves and at most \(qR\) decision nodes. Sharing one split variable across all leaves descending from a revealed prefix enforces the information restriction.
The representation also permits dependence on previous allocations: under a deterministic policy, those allocations are determined by the same ranking prefix. Conversely, a legal assignment of node variables specifies a deterministic policy.
Enumerating winner-set pairs at every leaf and imposing their constraints simultaneously therefore checks precisely whether one policy succeeds on all allowed sequences. A common positive slack is valid because the expanded tree contains only finitely many strict inequalities.
The claimed bounds
\(2^{O(mR)}\operatorname{poly}(m,\tau,q,R,L)\)
and
\(2^{O(mL^{q-1})}\operatorname{poly}(m,\tau,q,L^{q-1},L)\)
follow. The output appropriately does not claim general membership in \(\mathrm{NP}\).
With \(q=1\), only the current cohort’s top candidate has varying first-round scores. All possible changes in winner sets occur at the listed equality points or endpoints. Between consecutive points, all relevant comparisons remain unchanged, so one midpoint suffices.
This remains valid for \(m=1\), coincident breakpoints, endpoint ties, and zero-mass sides. The number of tests and the stated bit-time bound
\(O(m^2\tau\,\operatorname{poly}(L))\)
are sound.
The write-up resolves the requested hardness classification and supplies valid running-time bounds. No repair or additional mathematical clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.