Answer: All six decision problems are \(\mathrm{NP}\)-complete, invoking the published finite-list hardness theorems.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor lazy strategic candidacy games, the prob- lems LAZY∃NE and LAZY∃WNE are NP-complete, even if all candidates have self-supporting preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), candidate preference orders, a priority order, and a finite support of voter rankings with binary-rational masses summing to \(1\), decide whether there is an active set \(A\subseteq C\) that is a pure Nash equilibrium under plurality by mass, the paper’s tie-breaking rule, and its laziness preference; in the winner-constrained variant, also require a specified candidate to win. For the dynamics variants, decide whether a legal sequence of joins from the empty set or withdrawals from \(C\) terminates at a specified active set or with a specified winner.
Let \(C\) be a nonempty candidate set, \(m=|C|\), with a strict preference order \(\succ_c\) over \(C\) for each candidate and a strict priority order \(\lhd\). Candidate preferences need not rank themselves first.
A society is given by its support: \(\tau\) distinct strict voter rankings over \(C\), each with positive binary-rational mass, summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
For nonempty \(A\subseteq C\), voters vote sincerely under plurality by mass, restricted to \(A\); score ties favor the earliest candidate in \(\lhd\). Define \(w(\emptyset)\) as the earliest candidate in \(\lhd\).
Candidate \(c\) strictly prefers state \(B\) to state \(A\) exactly when \(w(B)\succ_c w(A)\), or when \(w(B)=w(A)\) and \(c\in A\setminus B\). Each candidate chooses participation or abstention; a pure Nash equilibrium permits no profitable unilateral toggle.
The equilibrium problems ask whether some equilibrium exists, or whether one exists with specified winner \(p\in C\).
Join dynamics start at \(\emptyset\) and permit only profitable single-candidate joins; withdrawal dynamics start at \(C\) and permit only profitable single-candidate withdrawals. Moves cannot be reversed, and termination means no permitted profitable move remains. Each dynamics variant asks whether some terminal sequence ends at specified \(A_*\subseteq C\), or with specified winner \(p\).
For each of these six decision problems over rational-mass societies, is it in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard?
For finite voter lists, equilibrium existence and specified-winner equilibrium existence are \(\mathrm{NP}\)-complete even when every candidate ranks herself first; the four terminal-dynamics problems are also stated to be \(\mathrm{NP}\)-complete in [Obraztsova et al. (2015)](https://www.ijcai.org/Proceedings/15/Papers/092.pdf).
The [later journal treatment](https://link.springer.com/article/10.1007/s11238-025-10113-4) retains equilibrium hardness and proves specified-winner withdrawal hardness, but omits the other three dynamics hardness claims. No result explicitly treating these rational-mass input problems was located.
All six problems are \(\mathrm{NP}\)-complete, using the published finite-voter-list hardness theorems cited in the question.
| Decision problem | Complexity |
|---|---|
| Equilibrium existence | \(\mathrm{NP}\)-complete |
| Equilibrium with specified winner | \(\mathrm{NP}\)-complete |
| Join dynamics: specified terminal set | \(\mathrm{NP}\)-complete |
| Join dynamics: specified terminal winner | \(\mathrm{NP}\)-complete |
| Withdrawal dynamics: specified terminal set | \(\mathrm{NP}\)-complete |
| Withdrawal dynamics: specified terminal winner | \(\mathrm{NP}\)-complete |
The external hardness inputs are Theorems 1 and 2 of [Obraztsova et al. (2015)](https://www.ijcai.org/Proceedings/15/Papers/092.pdf). The equilibrium results and specified-winner withdrawal result also appear, with proofs, as Theorems 3 and 7 of the [journal treatment](https://link.springer.com/article/10.1007/s11238-025-10113-4).
The three other dynamics classifications therefore invoke the 2015 theorem whose proof was omitted; this document does not independently reconstruct those reductions. Invoking that published theorem as a known result, the transfer and membership arguments below give a complete classification for the input representation in the question.
Write the supported rankings as \(\rho_1,\ldots,\rho_\tau\), with masses \(\mu_i=a_i/b_i\), where positive integer numerators and denominators are encoded in binary.
Define
\(\displaystyle D=\prod_{i=1}^{\tau}b_i,\qquad \alpha_i=a_i(D/b_i).\)
Then every \(\alpha_i\) is a positive integer and \(\sum_i\alpha_i=D\). The binary length of \(D\) is at most the sum of the denominator lengths, hence is \(O(L)\). Each \(\alpha_i\), and every score sum, also has \(O(L)\) bits.
For nonempty \(A\), scan each ranking to find its first member of \(A\), and give that candidate integer weight \(\alpha_i\). These integer scores are precisely the mass scores multiplied by \(D\), so score comparisons and ties are preserved exactly. Apply \(\lhd\) to tied maximum scores. For \(A=\emptyset\), return the earliest candidate in \(\lhd\).
Using ordinary integer arithmetic, a conservative bit-operation bound, including preprocessing, is
\(\displaystyle Q(m,\tau,L)=O\!\left((\tau+1)L^2+(\tau m+\tau+m)L\right).\)
Thus winner computation is polynomial in \(m,\tau,L\). No expansion into individual voters is required.
For \(c\notin A\), joining is profitable exactly when
\(\displaystyle w(A\cup\{c\})\succ_c w(A).\)
There is no equal-winner improvement from joining, because the secondary preference favors abstention.
For \(c\in A\), withdrawing is profitable exactly when
\(\displaystyle w(A\setminus\{c\})\succ_c w(A)\quad\text{or}\quad w(A\setminus\{c\})=w(A).\)
These predicates can be checked using exact winner computation and the supplied candidate preference orders.
A certificate is a subset \(A\subseteq C\), represented by \(m\) bits. Compute its winner and check every candidate’s unilateral toggle. Reject precisely when some toggle satisfies the appropriate profitable-move predicate above.
This verifies equilibrium existence in \(O(mQ(m,\tau,L))\) time. For specified-winner equilibrium existence, additionally check \(w(A)=p\), within the same bound.
A certificate is an ordered list of at most \(m\) distinct candidates.
For join dynamics, start at \(\emptyset\) and add the listed candidates in order. For withdrawal dynamics, start at \(C\) and remove them in order. Check that every move is permitted and profitable.
At the final state \(A\), check:
For joins, the terminality check concerns candidates outside \(A\). For withdrawals, it concerns candidates inside \(A\). It does not require the endpoint to be a Nash equilibrium.
There are at most \(m\) moves and at most \(m\) terminality checks. Each certificate therefore has polynomial length and is verifiable in \(O(mQ(m,\tau,L))\) time. All four dynamics problems belong to \(\mathrm{NP}\).
Let a finite-list instance have \(n\) voters. Group identical rankings. If the resulting distinct rankings have multiplicities \(k_1,\ldots,k_\tau\), assign mass
\(\displaystyle \mu_i=k_i/n.\)
These masses are positive and sum to \(1\). For every nonempty \(A\subseteq C\) and \(c\in A\),
\(\displaystyle \operatorname{score}_{\mathrm{mass}}(c,A)=\operatorname{score}_{\mathrm{list}}(c,A)/n.\)
Consequently, all score comparisons, score ties, and winners are identical in the two representations. Their empty-state winners are identical because the priority order is unchanged.
Candidate preferences and participation states are also unchanged. Therefore, for every unilateral toggle, profitability is identical. It follows that the mapping preserves:
The transformation is polynomial in the explicit finite-list input length \(N\): grouping can, for example, be implemented within \(O(N^2)\) bit operations. There are at most \(n\) supported rankings, and each mass needs \(O(\log(n+1))\) bits for its numerator and denominator. The output length is therefore polynomial in \(N\).
This is a polynomial-time many-one reduction from each finite-list problem to its rational-mass counterpart.
If “binary-rational” is intended to require denominators that are powers of two, the preceding normalization can be replaced by the following construction.
Choose the smallest power of two \(T\) satisfying \(T\geq n(n+1)\), and put
\(\displaystyle K=\lfloor T/n\rfloor,\qquad R=T-Kn.\)
Then \(0\leq R<n<K\). Give each original ranking with multiplicity \(k_i\) mass \(Kk_i/T\). If \(R>0\), add mass \(R/T\) to the ranking that lists candidates in priority order. Merge this ranking with an existing identical ranking if necessary.
The total mass is \(1\), every retained mass is positive and dyadic, and the support size is at most \(n+1\).
To prove winner preservation, fix nonempty \(A\) and let \(e\) be its earliest candidate in \(\lhd\). In integer units with denominator \(T\), every original score is multiplied by \(K\), and only \(e\) receives the additional \(R\) units.
Let \(a\) be the original winner, with original maximum score \(M\).
Thus the winner remains \(a\) for every subset. Since \(T<2n(n+1)\), the construction still has polynomial output length and running time.
The finite-list theorems concern the same lazy participation preferences, sincere restricted plurality voting, fixed priority tie-breaking, and earliest-priority empty-state winner. Their dynamics start from \(\emptyset\) or \(C\), respectively, allow only the indicated profitable moves, and prohibit reversals. These hypotheses match the present task.
The representation transformation leaves the candidate set, candidate preferences, priority order, specified winner, and specified terminal set unchanged. Section 3 proves that it also preserves the entire profitable-move relation.
Hence each finite-list hardness reduction can be composed with this transformation. All six rational-mass problems are \(\mathrm{NP}\)-hard. Together with Section 2, they are \(\mathrm{NP}\)-complete.
For the two equilibrium problems, the hardness also retains the restriction that every candidate ranks herself first: the transformation changes only the society’s representation.
All six problems have deterministic algorithms running in
\(\displaystyle O\!\left(2^m mQ(m,\tau,L)\right).\)
For equilibria, enumerate every subset and verify it. For dynamics, compute reachability in the directed subset graph whose edges are profitable permitted moves. Each edge changes cardinality by one, so processing subsets by increasing cardinality for joins, or decreasing cardinality for withdrawals, computes reachability. Check the requested condition and terminality at reachable endpoints.
The equilibrium problems additionally admit a support-size bound. In an equilibrium, every participating candidate must have positive score. Indeed, if candidate \(c\) has zero score, no supported ranking votes for \(c\); removing \(c\) leaves every voter’s chosen candidate, and hence the winner, unchanged. Laziness then makes withdrawal profitable.
Since each supported ranking contributes positive mass to exactly one participating candidate, an equilibrium has at most \(\tau\) participants. Enumerating only such subsets gives running time
\(\displaystyle O\!\left((m+1)^\tau mQ(m,\tau,L)\right).\)
This uses the actual support size \(\tau\), irrespective of the denominators or any expanded voter population.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed classification by invoking the cited finite-list theorems. All six rational-mass problems are \(\mathrm{NP}\)-complete under that stated reliance on the literature. I found no mathematical error or blocking gap in the transfer, membership arguments, or additional running-time bounds.
The proof does not independently establish the three dynamics hardness results omitted from the journal treatment. It explicitly imports them from the published conference theorem. That is a valid theorem invocation under the verification standard given here, which permits known results provided their statements and hypotheses match.
The common-denominator construction is correct:
\[ D=\prod_{i=1}^{\tau}b_i,\qquad \alpha_i=a_i(D/b_i). \]
Every division is exact. Positivity and normalization imply that the integer weights are positive and sum to \(D\). Thus every score is at most \(D\), and both weights and scores have \(O(L)\) bits.
Multiplying all mass scores by the same positive number preserves strict comparisons and equality. Scanning each supported ranking for its first participating candidate therefore computes the correct restricted plurality scores. Applying the supplied priority order resolves ties correctly. The empty-state convention is handled explicitly.
The claimed bound
\[ Q(m,\tau,L)=O\!\left((\tau+1)L^2+(\tau m+\tau+m)L\right) \]
is conservative and valid using ordinary integer arithmetic. It accommodates common-denominator preprocessing, exact divisions and multiplications, ranking scans, score accumulation, and winner selection. It does not rely on expanding masses into individual voters.
Finding: Correct.
For an absent candidate, the equal-winner secondary preference cannot favor joining. Hence joining is profitable precisely when the new winner is strictly preferred.
For a present candidate, withdrawal is profitable either when it produces a strictly preferred winner or when it leaves the winner unchanged. These are exactly the preferences specified in the task, including candidates who do not rank themselves first.
Finding: Correct; no self-supporting assumption is introduced.
A participation subset determines a complete strategy profile. Checking every candidate’s unilateral toggle is necessary and sufficient for pure Nash equilibrium because each candidate has exactly two actions.
The certificate has \(m\) bits. At most \(m+1\) winner computations are needed, together with preference comparisons. The stated \(O(mQ(m,\tau,L))\) bound accommodates these operations. The specified-winner condition requires only checking the already computed winner.
The procedure also covers the empty subset and the one-candidate case.
Finding: Both equilibrium problems belong to \(\mathrm{NP}\).
An ordered list of distinct candidates correctly describes a monotone sequence. Each candidate moves at most once, so every sequence has at most \(m\) moves.
Checking each move’s profitability establishes that the sequence is permitted. Checking the endpoint condition and every remaining permitted move establishes terminality. The output correctly distinguishes terminality from Nash equilibrium: reverse moves are excluded from the terminality test.
An empty list represents a zero-move sequence, so initially terminal states are covered as well. The certificate length and the claimed \(O(mQ(m,\tau,L))\) verification time are polynomial.
Finding: All four terminal-dynamics problems belong to \(\mathrm{NP}\).
For a nonempty finite voter list, assigning each distinct ranking mass \(k_i/n\) preserves every nonempty-state score up to the common positive factor \(1/n\). Consequently, it preserves all winners and priority ties.
Keeping the priority order also preserves the empty-state winner. Since candidate preferences are unchanged, winner preservation for every subset implies preservation of every profitable toggle. The claimed preservation of equilibria, monotone sequences, terminality, and endpoint conditions follows.
Grouping explicit rankings and encoding the multiplicities takes polynomial time and produces polynomial output length. The implicit requirement \(n\geq1\) is satisfied by the cited hardness constructions; the reduction need only apply to those instances. No empty-electorate case is needed for the hardness conclusion.
Finding: The many-one transfer is valid for binary-encoded general rational masses.
The alternative construction correctly handles the narrower interpretation of binary-rational masses.
For \(n\geq1\), the choice \(T\geq n(n+1)\) gives
\[ K=\lfloor T/n\rfloor\geq n+1,\qquad 0\leq R<n<K. \]
The assigned integer weights sum to \(Kn+R=T\). Every retained weight is positive, and dividing by the power of two \(T\) gives dyadic masses. Merging identical rankings maintains the distinct-support requirement.
The added priority-order ranking votes for the earliest participating candidate \(e\). If \(e\) is not the original winner, its original integer score is at least one below the maximum: equality would make \(e\) win by priority. Therefore,
\[ K(M-1)+R<KM. \]
The extra mass cannot change the winner. All other score comparisons and priority ties remain unchanged. The separate case \(e=a\) is also correct.
Finally, \(T<2n(n+1)\) ensures polynomial encoding length.
Finding: Winner preservation and polynomial size are established for dyadic masses too.
The cited conference paper’s Theorem 1 states hardness for both equilibrium problems, including self-supporting candidate preferences. Its model uses sincere restricted plurality, lazy participation preferences, fixed priority ties, and the earliest-priority empty-state winner. These hypotheses match the task. [Conference paper](https://www.ijcai.org/Proceedings/15/Papers/092.pdf)
Theorem 2 states \(\mathrm{NP}\)-completeness for all four dynamics questions. Its surrounding definitions specify profitable joins from the empty state and profitable withdrawals from the full state, with no reversals and termination when no permitted improvement remains. Thus “converge” concerns terminal endpoints, matching the task. [Conference paper](https://www.ijcai.org/Proceedings/15/Papers/092.pdf)
The journal treatment confirms the equilibrium results in Theorem 3 and specified-winner withdrawal hardness in Theorem 7, as claimed. [Journal treatment](https://link.springer.com/article/10.1007/s11238-025-10113-4)
The omission of the conference dynamics proof limits independent verification of that external result; it does not create a missing step in the representation transfer. The prover accurately discloses this reliance rather than claiming to have reconstructed the reductions.
Finding: The theorem applications are verified. Composing them with the transfer proves hardness for all six problems.
Enumerating all subsets and checking every permitted toggle gives the stated
\[ O\!\left(2^m mQ(m,\tau,L)\right) \]
bound. For dynamics, cardinality strictly changes along every edge, so processing subsets in the specified cardinality order correctly computes reachability.
The support-size observation is also correct. A participating candidate with zero score receives no supported ranking’s vote. Removing that candidate leaves every voter’s chosen candidate unchanged, hence leaves the winner unchanged and makes withdrawal profitable. Such a candidate cannot participate in equilibrium.
Thus an equilibrium has at most \(\tau\) participants. The number of subsets of size at most \(\tau\) is bounded by \((m+1)^\tau\), validating the final running-time bound, including the empty subset.
Finding: Both additional bounds are valid.
No repair is required. The classification is established through the explicitly cited finite-list hardness results; independent proofs of the three conference-only dynamics results are outside what this output establishes.
⟨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.