Answer: \(\mathrm{NP}\text{-complete}\), even with positive dyadic rational masses
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing the candidate stable set is NP- complete. The proof adapts a construction that was used by Brandt et al. (2010) to show that computing the Banks set is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), target \(c\in C\), and binary-rational distribution \(\mu\) over a finite support of complete voter rankings, with strict pairwise majorities, let \(R_\mu^M\) be the induced majority relation. Is there a narcissistic candidate preference profile, an agenda, and a candidate entry-equilibrium strategy profile such that voters use the paper's sophisticated VSE refinement of \(R_\mu^M\) and the resulting outcome is \(c\)?
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(c\in C\). A society is given by its support: the list of \(\tau\) distinct strict complete voter rankings with positive binary-rational masses \(\mu_1,\ldots,\mu_\tau\) 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\).
Define \(aR_\mu^M b\) when the mass ranking \(a\) above \(b\) exceeds \(1/2\); assume no pairwise majority ties. Candidates are separate from the voter society, and all preferences are common knowledge.
An agenda \(\sigma\) is a permutation of \(C\), restricted to the running set \(B\). Voting by successive elimination first contests the first two running candidates, then contests the survivor against the next candidate, continuing to a final survivor.
Sophisticated voting is defined by backward induction at every contest: each voter type votes for the branch whose eventual winning candidate it strictly prefers, and the branch supported by a majority of mass is selected. If both branches yield the same candidate, their choice is immaterial. Let \(w_\sigma(B)\) be this outcome; a singleton wins automatically, and \(w_\sigma(\varnothing)=\bot\).
Each candidate \(a\) has a strict complete preference order \(\succ_a\) on \(C\cup\{\bot\}\), with \(a\) ranked first (narcissism); write \(\succeq_a\) for its weak extension. Candidate strategies are pure run/withdraw choices. A nonempty running set \(B\) is an entry equilibrium precisely when \(w_\sigma(B)\succeq_a w_\sigma(B\triangle\{a\})\) for every \(a\in C\), using sophisticated voting also after each deviation and keeping the agenda fixed.
Is deciding whether there exist narcissistic candidate preferences, an agenda \(\sigma\), and an entry-equilibrium running set \(B\) with \(w_\sigma(B)=c\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For an explicitly listed finite electorate of odd size, this existential outcome-membership problem is \(\mathrm{NP}\)-complete. [Brill and Conitzer, Strategic Voting and Strategic Candidacy](https://www.cs.cmu.edu/~conitzer/candidacyAAAI15.pdf). No result settling the exact rational-mass formulation was identified in the searches.
The problem is \(\mathrm{NP}\)-complete, even when every mass is a positive dyadic rational. Thus it is \(\mathrm{NP}\)-hard; a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The proof preserves the majority tournament of an explicitly listed odd electorate. It does not expand a rational-mass society into individual voters.
Let \(T=R_\mu^M\). The absence of pairwise majority ties means that, for distinct \(x,y\in C\), exactly one of \(xTy\) and \(yTx\) holds. Define \(D_T(x,y)\) to be the majority winner between distinct \(x,y\), and put \(D_T(x,x)=x\).
At any contest, let the eventual winners of its two branches be \(x\) and \(y\). If they differ, sophisticated voting selects the branch yielding \(D_T(x,y)\), by the definition of sophisticated voting. If they coincide, the eventual winner is their common value. Consequently, backward induction uses only \(T\).
Here is an explicit polynomial-time computation. Write the restricted agenda as \((b_1,\ldots,b_k)\). For \(i\in\{2,\ldots,k\}\) and \(x\in\{b_1,\ldots,b_{i-1}\}\), let \(F_i(x)\) be the eventual outcome when \(x\) is the current survivor and the next contest is against \(b_i\). Set \(F_{k+1}(x)=x\) for every \(x\in B\). Then
\(F_i(x)=D_T\bigl(F_{i+1}(x),F_{i+1}(b_i)\bigr).\)
Indeed, the two branches leave respectively \(x\) and \(b_i\) as survivor, with precisely the same remaining agenda. Their continuation outcomes are the two arguments in this recurrence. Decreasing induction on \(i\) therefore proves the recurrence and gives \(w_\sigma(B)=F_2(b_1)\).
There are \(\sum_{i=2}^k(i-1)\) nonterminal states, so the computation uses \(O(k^2)\) tournament operations. Empty and singleton running sets are handled directly.
In particular, two societies with the same majority tournament have identical sophisticated outcomes for every agenda and running set, including every set reached by a candidacy deviation.
Fix an agenda \(\sigma\) and a nonempty running set \(B\) with \(w_\sigma(B)=c\).
Lemma. There exist narcissistic candidate preferences making \(B\) an entry equilibrium if and only if
\(w_\sigma(B\cup\{a\})\ne a\quad\text{for every }a\in C\setminus B.\)
Necessity. If an absent candidate \(a\) would win by entering, narcissism implies \(a\succ_a c\). Entering would therefore be a profitable deviation.
Sufficiency. Give \(c\) any strict complete preference order with \(c\) first. For each \(a\ne c\), put \(a\) first and \(c\) second, order the other candidates arbitrarily, and put \(\bot\) last.
Check every deviation:
These are all unilateral deviations, so \(B\) is an entry equilibrium. This proves the lemma.
The proof also shows that allowing \(\bot\) anywhere below a candidate’s own name does not change existential outcome membership: the witnessing preferences can always place \(\bot\) last.
A certificate consists only of an agenda \(\sigma\) and a nonempty subset \(B\). Its length is \(O(m\log(m+1))\). By the lemma, the verifier checks \(w_\sigma(B)=c\) and, for each absent candidate \(a\), checks \(w_\sigma(B\cup\{a\})\ne a\).
There are at most \(m+1\) outcome computations, each using \(O(m^2)\) tournament operations. Thus verification after majority preprocessing uses \(O(m^3)\) tournament operations.
For completeness, the majority tournament can be computed exactly in polynomial bit time. Under the usual binary numerator-and-denominator encoding, write \(\mu_j=p_j/q_j\), and set
\(Q=\prod_{j=1}^{\tau}q_j,\qquad t_j=p_j(Q/q_j).\)
Because the denominator encodings contribute to \(L\), these integers have \(O(L)\) bits. A pairwise comparison is determined by
\(aTb\quad\Longleftrightarrow\quad 2\sum_{j:\,a\text{ precedes }b}t_j>Q.\)
Using schoolbook integer arithmetic, forming the common-denominator representation takes \(O(\tau L^2)\) bit operations. Computing all pairwise sums takes \(O(\tau m^2L)\) bit operations.
Consequently, a conservative total verifier bound, including candidate-index operations, is
\(O\bigl((\tau m^2+m^3)L^2\bigr)\)
bit operations. This establishes membership in \(\mathrm{NP}\) in the requested support representation.
We use the following established result: for an explicitly listed odd electorate, deciding whether a designated candidate belongs to the candidate stable set is \(\mathrm{NP}\)-complete. Section 4 defines this set using existential candidate preferences, an existential agenda, and an entry equilibrium under sophisticated successive elimination—the quantifiers required here. Candidates and voters are separate, and candidate preferences are narcissistic. See [Brill and Conitzer, Theorem 3](https://www.cs.cmu.edu/~conitzer/candidacyAAAI15.pdf).
Consider an instance of that problem with odd electorate size \(n\). Group identical rankings into distinct rankings \(\rho_1,\ldots,\rho_\tau\), with positive multiplicities \(k_1,\ldots,k_\tau\). Thus \(\tau\le n\) and \(\sum_j k_j=n\).
If arbitrary binary-encoded rationals are permitted, assigning mass \(k_j/n\) already gives an exact reduction. To cover the stricter interpretation requiring dyadic rationals, proceed as follows.
Let \(D\) be the least power of two satisfying \(D\ge 4n^2\). Define
\(f_j=\left\lfloor Dk_j/n\right\rfloor,\qquad r=D-\sum_{j=1}^{\tau}f_j.\)
Since
\(r=\sum_{j=1}^{\tau}\bigl(Dk_j/n-f_j\bigr),\)
we have \(0\le r<\tau\), and \(r\) is an integer. Increase exactly \(r\) of the integers \(f_j\) by one; call the resulting integers \(h_j\). Output ranking \(\rho_j\) with mass
\(\mu_j=h_j/D.\)
These masses satisfy all representation requirements:
We now prove preservation of every pairwise majority.
For each \(j\), the rounding construction gives
\(\left|\mu_j-k_j/n\right|\le 1/D.\)
Hence, for any pair \(a,b\), its supporting mass changes by at most
\(\left|\sum_{j:\,a\text{ precedes }b}\mu_j-\sum_{j:\,a\text{ precedes }b}k_j/n\right|\le \tau/D\le n/D\le 1/(4n).\)
In the original odd electorate, if \(s\) voters prefer \(a\) to \(b\), then
\(\left|s/n-1/2\right|=|2s-n|/(2n)\ge 1/(2n),\)
because \(2s-n\) is a nonzero integer. The rounding error is strictly smaller than this distance from the majority threshold. Therefore every majority comparison retains its direction, and the output has no pairwise majority ties.
The reduction is polynomial. If \(S\) denotes the explicit source input length, grouping rankings and performing the integer computations can be done in \(O(S^2)\) bit operations. The output length satisfies
\(L=O\bigl(m\log(m+1)+\tau m\log(m+1)+\tau\log(n+1)\bigr),\)
which is polynomial in \(S\), because the source lists all \(n\) voters explicitly.
Keep the candidate set and designated candidate unchanged. Section 4 proves that the source electorate and output rational-mass society have exactly the same majority tournament. Section 1 then proves equality of their sophisticated outcomes for every agenda and running set, including all unilateral deviations.
For any fixed candidate preferences, agenda, and nonempty running set, the entry-equilibrium inequalities are therefore identical in the two instances. The empty outcome causes no discrepancy: a unilateral deviation reaches the empty set only when a sole running candidate withdraws, and narcissism makes that candidate prefer winning to \(\bot\).
Thus the source instance is a yes-instance if and only if the constructed rational-mass instance is a yes-instance. This is a polynomial many-one reduction establishing \(\mathrm{NP}\)-hardness, even for dyadic masses. Together with Section 3, it proves \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-completeness for the stated rational-mass formulation, including positive dyadic masses. I found no major or minor mathematical issues requiring repair.
The tournament definition is valid: strict complete voter rankings and the absence of pairwise majority ties imply exactly one directed majority comparison for each pair of distinct candidates.
The backward-induction argument correctly compares eventual branch outcomes, rather than merely the candidates currently contesting. When those outcomes differ, their supporting voter mass is precisely the mass defining their tournament comparison. When they coincide, either branch produces the same outcome.
The dynamic-programming recurrence is well-defined. At stage \(i\), both \(F_{i+1}(x)\) and \(F_{i+1}(b_i)\) belong to the stated domain of the next stage; at the terminal stage, the separately defined terminal values apply. The survivor and remaining agenda determine the continuation, so merging histories into these states is justified.
The state count \(\sum_{i=2}^{k}(i-1)=k(k-1)/2\) and the resulting \(O(k^2)\) tournament-operation bound are correct. Empty and singleton sets are explicitly handled.
Consequently, equality of majority tournaments preserves outcomes for every agenda and running set, including deviation sets. This conclusion is fully established.
The lemma correctly characterizes when a fixed agenda and running set can be supported by narcissistic preferences.
For necessity, an absent candidate differs from the current winner, because the winner belongs to the running set. If entering elects that absent candidate, narcissism makes the deviation strictly profitable.
For sufficiency, the proposed orders are strict, complete, and narcissistic. Each deviation check is valid:
Thus every candidate weakly prefers the current outcome to its deviation outcome. Equality of outcomes causes no difficulty because equilibrium uses weak preference.
The construction respects the existential quantifiers: one collection of candidate orders simultaneously supports all deviation inequalities. Placing \(\bot\) last is permitted by the task.
The certificate is sufficient. Candidate preferences need not be supplied because the proved lemma characterizes their existence. An agenda and a running-set encoding have the claimed \(O(m\log(m+1))\) length.
There are at most \(m+1\) outcome evaluations, giving \(O(m^3)\) tournament operations after preprocessing.
The exact-arithmetic preprocessing is also correct:
The stated schoolbook-arithmetic bounds are conservative and polynomial. The final verifier bound
\[
O\bigl((\tau m^2+m^3)L^2\bigr)
\]
covers the stated preprocessing and outcome computations, including routine candidate-index operations.
The external theorem matches the source problem used in the reduction. The paper assumes an odd finite electorate, disjoint candidate and voter sets, narcissistic candidate preferences, and common knowledge. Its Section 4 uses the same successive-elimination procedure and backward-induction interpretation. Its candidate stable set existentially quantifies candidate preferences, agenda, and entry equilibrium; Theorem 3 establishes membership hardness. These definitions and hypotheses are confirmed in the [cited paper](https://www.cs.cmu.edu/~conitzer/candidacyAAAI15.pdf).
The paper’s convention for the empty outcome requires each candidate to prefer itself to that outcome. The prover explicitly addresses this convention when transferring equilibria. There is no mismatch affecting the reduction.
Every critical numerical bound checks out.
The least power of two above the threshold satisfies \(4n^2\le D<8n^2\). The remainder \(r\) is an integer satisfying \(0\le r<\tau\), so the prescribed number of distinct rounding increments is available.
The resulting masses are positive, sum exactly to one, have distinct support rankings, and are dyadic with \(O(\log(n+1))\)-bit numerators and denominators.
For both incremented and unincremented entries, the rounding error is at most \(1/D\). Hence every pairwise supporting mass changes by at most
\[
\frac{\tau}{D}\le\frac{n}{D}\le\frac{1}{4n}.
\]
An odd electorate’s supporting proportion is at distance at least \(1/(2n)\) from the threshold. The error bound is strictly smaller, so no comparison reverses or becomes tied.
The construction also handles the boundary case of one voter: there is one support ranking and the resulting mass is exactly one.
The output-length bound is polynomial in the explicitly listed source input length. Grouping rankings and performing the stated arithmetic fit the conservative \(O(S^2)\) construction bound.
The reduction preserves the candidate set, designated candidate, and every majority comparison. Section 1 therefore preserves all equilibrium-relevant outcomes under the same agenda.
For nonempty deviation outcomes, candidate preference comparisons transfer unchanged. A deviation reaches the empty set only when the sole running candidate withdraws; that candidate prefers its own victory to \(\bot\) in both formulations. Thus the difference in how preferences involving \(\bot\) are presented creates no discrepancy.
Both directions of the yes-instance equivalence follow. The polynomial reduction establishes \(\mathrm{NP}\)-hardness even for dyadic masses, and the certificate verifier establishes membership in \(\mathrm{NP}\).
Required clarification or repair: none.
⟨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.