Answer: Both \(\mathrm{WINNER1}\) and \(\mathrm{WINNER0}\) are \(\mathrm{NP}\)-hard, even with all candidates initially running and no initial blocks.
Theorem 2 — class: hardness
Given a finite candidate set \(C\), candidate preferences, a fixed tie-breaking order, voter ranking types \(T\) with positive rational masses \(\mu_t\) summing to \(1\), an initial state, and a designated candidate \(c^\star\), does there exist a finite sequence of single-candidate improving moves that reaches an equilibrium where \(c^\star\) wins? For WINNER1, when a candidate withdraws, every type blocks that candidate; each type votes for its highest-ranked running candidate not blocked, or its highest-ranked running candidate if all running candidates are blocked. For WINNER0, no candidates are blocked. Initial refusal histories can be represented by splitting types that share a ranking but have different histories.
Let \(C\) be a nonempty candidate set, with \(m=|C|\); every candidate has a strict linear order over \(C\), with no requirement to rank itself first. Fix a strict tie-breaking order over \(C\), restricted to the running candidates in every election.
A society is given by its support: a list of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Each type specifies a strict ranking of \(C\) and an initial blocked set \(B_t^0\subseteq C\); identical rankings with different histories are distinct types. Thus \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A state is \(S=(A,(B_t)_t)\), with \(\varnothing\ne A\subseteq C\). Each type votes with its entire mass for its highest-ranked candidate in \(A\setminus B_t\), or its highest-ranked candidate in \(A\) if \(A\setminus B_t=\varnothing\). The winner \(w(S)\) is selected by mass-weighted Plurality and the fixed tie-breaking order.
A move toggles one candidate's membership in \(A\), keeping \(A\) nonempty. In WINNER1, withdrawal of \(c\) replaces every \(B_t\) by \(B_t\cup\{c\}\); entry leaves all blocked sets unchanged, and blocks are never removed. In WINNER0, all blocked sets are always empty.
A move by \(c\) from \(S\) to \(S'\) is improving precisely when \(c\) strictly prefers \(w(S')\) to \(w(S)\), after the prescribed block update. An equilibrium has no improving move, including entry moves.
Given an initial state \(S_0\) and \(c^\star\in C\), each variant asks whether a finite improvement sequence, possibly of length zero, reaches an equilibrium won by \(c^\star\).
For each of WINNER1 and WINNER0 with this rational-mass society, is the reachability decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite electorates, WINNER1 is \(\mathrm{NP}\)-complete and WINNER0 is \(\mathrm{NP}\)-hard, even starting with all candidates running and no blocks ([Polukarov et al., 2015](https://www.ijcai.org/Proceedings/15/Papers/094.pdf)).
No result settling this exact rational-mass formulation was located in the literature search.
Both \(\mathrm{WINNER1}\) and \(\mathrm{WINNER0}\) are \(\mathrm{NP}\)-hard for the rational-mass formulation. Hardness holds even when initially all candidates run and every blocked set is empty.
The proof is a polynomial reduction from the finite-electorate hardness results supplied in the question. It preserves the entire improvement dynamics, including entry moves and the fallback voting rule.
We use the following given result: for a nonempty finite electorate represented explicitly by its voters, both variants are \(\mathrm{NP}\)-hard, even with all candidates initially running and no initial blocks. These are the hardness conclusions of Theorems 2 and 3 of [Polukarov et al. (2015)](https://www.ijcai.org/Proceedings/15/Papers/094.pdf).
Their model uses fixed tie-breaking priorities and, when a voter has blocked every running candidate, selects that voter’s highest-ranked running candidate while retaining the blocks. Thus the voting and block-update rules agree with those in the question. No assumption that candidates rank themselves first is needed.
Let a finite-electorate instance have \(\mathrm{n}\) voters, where \(\mathrm{n}>0\). Keep its candidates, candidate preferences, tie-breaking order, initial running set, and designated candidate.
Partition the voters according to their ranking and initial blocked set. For each nonempty class indexed by \(\mathrm{t}\), let \(\mathrm{k}_t\) be its cardinality. Create one type with that class’s ranking and initial blocked set, and assign mass \(\mu_t=k_t/n\).
These masses satisfy \(\mu_t>0\) and \(\sum_{t=1}^{\tau}\mu_t=1\). Each numerator and denominator requires at most \(O(\log(n+1))\) bits, and \(\tau\leq n\). Fractions may be reduced without increasing their encoding lengths.
The construction is polynomial in the explicit finite-electorate input length: partitioning explicitly listed records and computing their multiplicities takes polynomial time, and each resulting type record has polynomial length. In particular, compression introduces no enumeration of possible rankings.
Fix any finite sequence of candidate toggles that keeps the running set nonempty. Apply the sequence in both instances, without yet requiring the moves to improve the outcome.
We prove inductively that, after every prefix:
The first two statements hold initially by construction. A toggle changes the same candidate’s running status in both instances. In \(\mathrm{WINNER0}\), blocks remain empty. In \(\mathrm{WINNER1}\), entry preserves every block, and withdrawal of \(\mathrm{c}\) adds \(\mathrm{c}\) to every block. Hence the first two statements persist.
Consequently, all original voters in class \(\mathrm{t}\) choose the same candidate as type \(\mathrm{t}\). This also holds in the fallback case, because their rankings, running sets, and blocked sets agree.
For each running candidate \(\mathrm{x}\), write \(\mathrm{N}_x\) for its finite-electorate vote count and \(\mathrm{M}_x\) for its rational-mass score. Then \(\mathrm{M}_x=N_x/n\). Multiplication by the positive constant \(\mathrm{1}/n\) preserves all score comparisons and equalities. The common tie-breaking order therefore selects the same winner.
Now consider any legal next move by candidate \(\mathrm{c}\). Both its current and resulting winners agree across the instances. Since candidate preferences are unchanged, the move is improving in one instance exactly when it is improving in the other.
It follows that the same candidate sequences are improvement sequences in both instances. At corresponding reachable states, every legal withdrawal and entry has the same improvement status. Thus equilibrium status and the equilibrium winner agree, including for a sequence of length zero.
We have proved that the finite instance is a yes-instance if and only if its rational-mass image is a yes-instance. Together with the polynomial construction, this establishes both hardness claims.
If the tie-breaking order is fixed externally rather than supplied as input, relabel candidates in priority order and apply the same relabeling to all rankings and the designated candidate. This preserves the argument.
For completeness, the following bounds use precisely \(\mathrm{m},\tau,L\) from the question. They also give finite decision algorithms without claiming polynomial running time.
Write each input mass as \(\mu_t=p_t/q_t\), with positive integers encoded in binary. Set \(\mathrm{Q}=\prod_t q_t\) and \(\mathrm{a}_t=p_t(Q/q_t)\). The total bit length of the denominators is at most \(\mathrm{L}\), so \(\mathrm{Q}\) has \(O(L)\) bits. Moreover, \(\sum_t a_t=Q\). Plurality comparisons can therefore use exact integer scores with \(O(L)\) bits.
Using elementary integer arithmetic gives these conservative bounds:
For \(\mathrm{WINNER0}\), a state is determined by its nonempty running set, so there are at most \(\mathrm{2}^m\) states. Exploring the reachable improvement graph and accepting precisely when a reachable equilibrium has the designated winner takes \(O(2^m m^2(\tau+1)L^2)\) time.
For \(\mathrm{WINNER1}\), let \(\mathrm{H}\) be the set of candidates withdrawn at least once since the initial state. Every reachable blocked set satisfies \(\mathrm{B}_t=B_t^0\cup H\), by induction on the moves. Thus a reachable state can be represented by \(\mathrm{(A,H)}\), giving at most \(\mathrm{4}^m\) representations. The same exploration takes \(O(4^m m^2(\tau+1)L^2)\) time.
The requested classification is therefore settled: both problems are \(\mathrm{NP}\)-hard. The argument does not assert membership in \(\mathrm{NP}\) for the full rational-mass formulation.
⟨structured verdict parsed — rendered above⟩
The argument establishes both requested hardness claims. The reduction is polynomial, preserves every legal improvement sequence, and preserves equilibrium status, including entry moves and the fallback voting rule. I found no major or minor mathematical issues.
The prover states the source result sufficiently precisely: with voters represented explicitly, both variants are \(\mathrm{NP}\)-hard even when all candidates initially run and all initial blocks are empty.
The cited paper’s Theorems 2 and 3 give the stated hardness conclusions. Its model specifies fixed candidate priorities, places unblocked running candidates above blocked running candidates while retaining the original order within each group, and retains blocks during fallback voting. It also explicitly says its results do not rely on self-supporting candidate preferences. These features match the target formulation. [Polukarov et al. (2015)](https://www.ijcai.org/Proceedings/15/Papers/094.pdf)
Consequently, the theorem application does not omit a relevant hypothesis. The finite-electorate hardness premise is also expressly supplied by USER_TASK; the prover need not reproduce its underlying hardness reductions.
Partitioning voters by both ranking and initial blocked set is the correct equivalence relation. It does not incorrectly merge voters who share a ranking but have different histories.
Every retained class has \(k_t\geq 1\), and \(n>0\), so each mass \(\mu_t=k_t/n\) is positive. Since the classes partition the electorate, their masses sum to \(1\).
The encoding bounds are correct: \(k_t\leq n\), each fraction needs \(O(\log(n+1))\) bits for its numerator and denominator, and \(\tau\leq n\). Reducing fractions cannot increase these lengths.
Because the source electorate is explicitly listed, partitioning its records and counting multiplicities takes polynomial time in its input length. Copying candidate preferences and the remaining instance data also takes polynomial time. No enumeration of all possible rankings is required.
The restricted source instances map to instances with all candidates running and all blocks empty, so the claimed restricted hardness is preserved.
The induction applies to every finite legal toggle sequence, before imposing the improvement condition. This avoids assuming the very correspondence that the proof must establish.
Initially, corresponding running sets and blocked sets agree by construction. Each toggle preserves the running-set correspondence. Under \(\mathrm{WINNER1}\), withdrawal applies the same union operation to every original voter and every corresponding type, while entry leaves blocks unchanged. Under \(\mathrm{WINNER0}\), blocks remain empty.
Therefore, each voter in a class and its corresponding type always have the same ranking, running set, and blocked set. Their chosen candidates agree both when an unblocked running candidate exists and when fallback voting applies.
The score identity \(M_x=N_x/n\) is exact. A class contributes either all \(k_t\) original votes or its entire mass \(k_t/n\) to the same candidate.
Since \(n>0\), this scaling preserves strict score comparisons and ties. The unchanged tie-breaking order therefore selects the same winner.
Candidate preferences are copied unchanged. Thus, for every legal next toggle, the candidate compares the same current and resulting winners in both instances. Improvement status agrees in both directions.
This establishes correspondence of all finite improvement sequences. At corresponding states, checking every legal toggle also gives the same equilibrium status. The argument explicitly includes entry moves and sequences of length zero. Hence the claimed yes-instance equivalence follows.
The relabeling observation is valid. Applying one consistent relabeling to candidate identities, rankings, candidate preferences, initial data, and the designated candidate preserves the relevant priority comparisons and dynamics. No additional tie-breaking assumption is needed.
The common-denominator construction is correct. The product \(Q=\prod_t q_t\) has \(O(L)\) bits, each \(a_t=p_t(Q/q_t)\) is an integer, and normalization gives \(\sum_t a_t=Q\). Consequently, every candidate’s integer score has \(O(L)\) bits.
Elementary exact arithmetic suffices for the stated conservative bounds. Scanning the rankings and accumulating scores fits within \(O((\tau m+m)L^2)\) bit operations. Computing the current winner and checking at most \(m\) legal toggles fits within \(O(m^2(\tau+1)L^2)\). Block updates and candidate-preference comparisons fit within that bound as well.
Common-denominator preprocessing is polynomial and is absorbed by the stated overall bounds.
For \(\mathrm{WINNER0}\), the running set determines the state, giving at most \(2^m\) states.
For \(\mathrm{WINNER1}\), the identity \(B_t=B_t^0\cup H\) follows from the specified updates. Thus \((A,H)\) determines every reachable state, and \(4^m\) is a valid upper bound on the number of representations. Different representations can describe the same state without invalidating this upper bound or the exploration.
Exploring reachable representations with repeated representations marked as visited gives the stated exponential decision bounds. The nonempty-running-set restriction only reduces the number of legal states and transitions. When \(m=1\), the withdrawal is excluded and the same bounds remain valid.
These algorithms establish decidability, while the reduction establishes the requested \(\mathrm{NP}\)-hardness classification. The prover correctly avoids claiming membership in \(\mathrm{NP}\) for the full rational-mass formulation.
No additional clarification or repair 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.