Answer: NP-hard: exact enumeration in time polynomial in \(m,\tau,L,a\) would imply \(\mathrm{P}=\mathrm{NP}\). Nevertheless, enumeration is possible in time \(2^k\operatorname{poly}(m,\tau,L,a)\), with individually extendible voter types and exact rational-mass arithmetic.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose an n-vote profile P is compatible with A1 > . . . > Aq. Let dmax = maxi≤q |DAq|. Let tmax(n) be the longest time it takes to apply local rules on n in- puts. Then, the running time of Process 1 is O(apdmax(np+ tmax(n)p + dmax)), where a is the number of H-Schwartz winners.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(p\) binary attributes with a supplied ordered partition \(A_1 > \cdots > A_q\), and a distribution over \(\tau\) types with positive binary-rational masses summing to \(1\), where each type specifies conditional preferences through a CP-net compatible with that partition and having a linear extension, compute the H-Schwartz winner set. At each attribute and setting of the other attributes, use weighted local majority, returning both values on an exact tie; form the induced graph as in the paper and return its Schwartz set.
Let \(m=p\geq 1\) binary attributes have outcome space \(X=\{0,1\}^{m}\) and a supplied ordered partition \(A_1>\cdots>A_q\) into nonempty blocks.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type supplies a CP-net with an explicit, complete conditional preference table of strict preferences at each attribute, promised to have a linear extension. For \(x\in A_\ell\), its parents must lie in \((A_1\cup\cdots\cup A_\ell)\setminus\{x\}\); dependencies within a block may be cyclic.
For each attribute and assignment to all other attributes, apply weighted majority to the types' conditional preferences, selecting both values on an exact tie. On \(X\), draw an edge from each selected value's outcome to the outcome with the other value, holding all other attributes fixed.
The H-Schwartz winner set \(W\) is the union of the strongly connected components with no incoming edge from another component. Compute \(W\) as an explicit list; write \(a=|W|\) and \(k=\max_\ell|A_\ell|\).
Is exact enumeration of \(W\) possible in time polynomial in \(m,\tau,L,a\), or is this computation NP-hard?
If it is NP-hard, is enumeration nevertheless possible in time \(f(k)\operatorname{poly}(m,\tau,L,a)\) for some computable \(f\)?
For finite electorates of \(n\) voters, an algorithm enumerates the winners in \(O(am d(nm+t(n)m+d))\) time, where \(d=2^k\) and \(t(n\)\) is the maximum local-rule evaluation time. [Xia–Conitzer–Lang](https://www.cs.cmu.edu/~conitzer/cyclic_votingAAAI08.pdf)
Schwartz membership for a general CP-net is PSPACE-complete; this concerns an unrestricted aggregate network, without the promised representation by individually extendible voter types. [Goldsmith–Lang–Truszczyński–Wilson](https://www.lamsade.dauphine.fr/~lang/papers/gltw08.pdf)
Weighted hypercubewise aggregation has been studied with Copeland, maximin and Kemeny selection; no complexity result for the precise rational-mass Schwartz enumeration problem above was located. [Conitzer–Lang–Xia](https://www.ijcai.org/Proceedings/11/Papers/038.pdf)
The computation is NP-hard, in an output-sensitive sense: an algorithm running in time polynomial in \(m,\tau,L,a\) would imply \(\mathrm{P}=\mathrm{NP}\).
Nevertheless, exact enumeration is possible in time
\(2^k\operatorname{poly}(m,\tau,L,a)\).
Both statements respect the promise that every supplied voter CP-net has a linear extension.
Encode a strict conditional preference by its sign: \(+1\) means that \(1\) is preferred, and \(-1\) means that \(0\) is preferred.
Fix an attribute \(v\) and a sign function \(h\) of some other attributes, supplied by an explicit table. Construct two voter types as follows:
With equal masses, this pair contributes twice the sign \(h\) to the unnormalized majority margin at \(v\), and zero at every other attribute.
Each constructed CP-net is acyclic: every dependency edge ends at \(v\), and its parents have no parents. To verify the linear-extension promise explicitly, order the attributes with \(v\) last, and compare outcomes lexicographically using the applicable conditional preferences. Outcomes differing at just one attribute are ordered according to that attribute’s CPT. Thus this lexicographic order extends the CP-net.
Consequently, sums of such sign functions can be implemented independently at different attributes using individually extendible voter types.
All masses can be dyadic. If the construction initially uses \(2B\) equally weighted types, choose a power of two \(N\) satisfying
\(2B\leq N<4B\).
Add \((N-2B)/2\) neutral pairs, each consisting of two separable types with opposite preferences at every attribute, and give all \(N\) types mass \(1/N\). These additions cancel everywhere.
If identical types occur, merge them and add their masses. The resulting support still has polynomial size, positive dyadic masses, and total mass \(1\).
Let \(\psi\) be a Boolean formula in conjunctive normal form with at most three literals per clause. Introduce a fresh variable \(u\), and put
\(\Phi=\psi\land u\).
Write the variables of \(\Phi\) as \(x_1,\ldots,x_s\), and its clauses as \(C_1,\ldots,C_r\). Then \(\Phi\) is satisfiable exactly when \(\psi\) is satisfiable, while the all-zero assignment never satisfies \(\Phi\).
Use the \(2s+1\) attributes
\(z,x_1,\ldots,x_s,y_1,\ldots,y_s\),
all in one supplied block. Define the desired aggregate preferred values by
\[
\begin{aligned}
\operatorname{pref}(x_i)&=
\begin{cases}
0,&z=0,\\
y_i,&z=1,
\end{cases}\\
\operatorname{pref}(y_i)&=
\begin{cases}
0,&z=0,\\
x_i,&z=1,
\end{cases}\\
\operatorname{pref}(z)&=
\begin{cases}
1,&\Phi(x_1,\ldots,x_s)\text{ is true},\\
0,&\Phi(x_1,\ldots,x_s)\text{ is false}.
\end{cases}
\end{aligned}
\]
Here and below, these displayed formulas specify conditional preferred values; they are not being supplied as a succinct aggregate CPT.
For each \(x_i\) and \(y_i\), use the paired construction from Section 1 with its two-parent sign function. This uses \(2s\) pairs.
For \(z\), define \(h_j(x)=+1\) when \(C_j\) is satisfied, and \(h_j(x)=-1\) otherwise. Use one pair targeting \(z\) for each \(h_j\), together with \(r-1\) pairs targeting \(z\) with constant sign \(-1\).
If \(b(x)\) clauses are unsatisfied, their total signal is
\[
\sum_{j=1}^{r}h_j(x)-(r-1)
=r-2b(x)-(r-1)
=1-2b(x).
\]
This is positive exactly when every clause is satisfied, and is never zero.
Thus the prescribed aggregate preferences are realized without ties. Every nonconstant voter table has at most three parents and at most eight rows. There are
\(B=2s+2r-1\)
pairs before padding, and each voter has only one possibly nonconstant table. The complete support representation, including all unconditional tables and masses, therefore has polynomial bit length.
The one-block partition satisfies the parent restriction automatically. Every voter is acyclic and has a linear extension by Section 1.
Let \(G\) be the graph in the question. Reverse every edge to obtain \(H\). Since all aggregate preferences are strict, an edge of \(H\) changes one attribute from its nonpreferred value to its preferred value.
Source strongly connected components of \(G\) are exactly sink strongly connected components of \(H\).
Define
\[
b=(z=0,x=0^s,y=0^s).
\]
For every satisfying assignment \(\alpha\) of \(\Phi\), define
\[
c_\alpha=(z=1,x=\alpha,y=\alpha).
\]
Both \(b\) and every \(c_\alpha\) have no outgoing edge in \(H\): every coordinate already has its preferred value.
We now show that every outcome reaches one of these outcomes in \(H\).
A sink strongly connected component cannot have a path leaving it. Since every vertex reaches one of the displayed outcomes, every sink component contains one of them. That outcome has no outgoing edge, so its strongly connected component is its singleton.
Consequently, the winner set is exactly
\[
W=\{b\}\ \cup\
\{c_\alpha:\alpha\text{ satisfies }\Phi\},
\qquad
a=1+\#\{\alpha:\alpha\text{ satisfies }\Phi\}.
\]
In particular, unsatisfiable instances have exactly one winner, and satisfiable instances have at least two.
Merely observing that satisfiability corresponds to multiple winners would not suffice: satisfiable instances can have exponentially many winners. The bounded output on unsatisfiable instances supplies the required argument.
Suppose an exact enumeration algorithm has total running time at most
\(P(m,\tau,L,a)\)
for some fixed polynomial \(P\).
Given \(\psi\), construct the preceding instance \(I\). Its parameters \(m,\tau,L\) are polynomially bounded in the length of \(\psi\). Choose a fixed polynomial cutoff \(Q\) that dominates \(P(m,\tau,L,1)\) on all these constructed instances.
Run the enumerator for \(Q(|\psi|)\) steps.
This procedure is correct. An unsatisfiable formula produces \(a=1\), so the algorithm must terminate within the cutoff and return only \(b\). A satisfiable formula either terminates with at least two winners or exceeds the cutoff; both branches give the correct answer.
This would decide SAT in polynomial time. Hence output-polynomial enumeration is impossible unless \(\mathrm{P}=\mathrm{NP}\).
The reduction already uses acyclic voter types with at most three parents per attribute and dyadic masses. Hardness therefore does not rely on individually inconsistent voters or large rational denominators.
Write the supplied masses as \(\mu_t=\alpha_t/\beta_t\), and let
\(D=\prod_{t=1}^{\tau}\beta_t\).
Its bit length is at most the sum of the denominator bit lengths, hence at most \(L\).
Precompute the integer weights
\(w_t=\alpha_t(D/\beta_t)\).
Because the masses sum to \(1\), these weights sum to \(D\).
For any attribute and conditioning assignment, read each type’s applicable CPT entry and compare the two integer sums
\[
\sum_{t:\,1\text{ preferred}}w_t
\quad\text{and}\quad
\sum_{t:\,0\text{ preferred}}w_t.
\]
Their equality detects an exact tie. All integers have \(O(L)\) bits, and explicit-table lookup takes polynomial time. Thus one local aggregate-rule evaluation takes some
\(T=\operatorname{poly}(m,\tau,L)\)
bit operations, without expanding masses into voters.
The positive result follows the block method of [Xia–Conitzer–Lang](https://www.cs.cmu.edu/~conitzer/cyclic_votingAAAI08.pdf). We give the graph argument and output-size accounting explicitly.
Split the attributes into an earlier prefix \(P\) and the next block \(B\). Preferences at attributes of \(P\) are independent of \(B\).
Let \(G_P\) be the graph on prefix assignments. For any strongly connected component \(C\) of \(G_P\), define \(U_C\) on assignments to \(B\): include a block edge whenever that edge exists under some prefix assignment in \(C\).
Lemma. The strongly connected components of the joint graph lying over \(C\) are precisely
\(C\times D\),
where \(D\) ranges over the strongly connected components of \(U_C\). Such a product is a source component exactly when both \(C\) and \(D\) are source components in their respective graphs.
Proof.
Every prefix edge lifts with any fixed block assignment, since prefix preferences do not depend on the block. Hence, with the block assignment fixed, one can move between any two prefix assignments in \(C\).
Consider an edge of \(U_C\). It occurs under some prefix assignment \(c\in C\). Starting from any prefix assignment in \(C\), first move to \(c\) while holding the block fixed, and then traverse that block edge. Repeating this procedure lifts any path of \(U_C\).
Conversely, a joint path that stays over \(C\) projects, after deleting stationary steps, to a path in \(U_C\). A path beginning and ending over \(C\) cannot leave \(C\) in its prefix projection: leaving and returning would make the intervening prefix vertices strongly connected with \(C\).
Thus two joint outcomes over \(C\) are mutually reachable exactly when their block assignments are mutually reachable in \(U_C\). This proves the product characterization.
If \(C\) has an incoming prefix edge from outside \(C\), that edge lifts at every block assignment, producing an incoming edge to every product \(C\times D\). If \(D\) has an incoming edge in \(U_C\), its witnessing prefix assignment likewise produces an incoming edge to \(C\times D\).
Finally, if both components are sources, no incoming joint edge can change the prefix from outside \(C\), or change the block from outside \(D\). Hence the product is a source. \(\square\)
Start with the single empty prefix. For each successive block \(A_\ell\), retain the source strongly connected components of the graph on the processed prefix.
For every retained component \(C\):
The lemma proves inductively that these are exactly the source components on the enlarged prefix. After the last block, their union is \(W\). Exact ties are handled by inserting both directed edges.
Let \(b_\ell\) be the total number of retained prefix outcomes after block \(\ell\), with \(b_0=1\). Every finite nonempty \(U_C\) has a source component. Therefore every retained prefix outcome has an extension at the next stage, giving
\[
1=b_0\leq b_1\leq\cdots\leq b_q=a.
\]
At stage \(\ell\), building all union graphs requires at most
\[
b_{\ell-1}\,|A_\ell|\,2^{|A_\ell|}
\leq a k2^k
\]
local evaluations. Each union graph has at most \(2^k\) vertices and \(k2^k\) edges. There are at most \(a\) retained prefix components, so their strongly connected components can also be computed within
\(2^k\operatorname{poly}(m,a)\)
bit operations.
Every intermediate explicit list contains at most \(a\) outcomes, each of length at most \(m\). Since \(q\leq m\) and local evaluation takes polynomial bit time, the total running time is
\[
2^k\operatorname{poly}(m,\tau,L,a).
\]
Thus the requested parameterized enumeration algorithm exists, with \(f(k)=2^k\).
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly. The SAT reduction establishes the stated obstruction to output-polynomial enumeration, and the block algorithm establishes enumeration in time \(2^k\operatorname{poly}(m,\tau,L,a)\). I found no major or minor issues requiring repair.
The paired construction has the claimed margins. At the targeted attribute \(v\), both voters contribute the sign \(h\); at every other attribute, their opposite unconditional preferences cancel. Assigning equal masses to all constructed voters therefore implements the desired sums independently at each attribute.
Each voter satisfies the linear-extension promise. All dependency edges enter \(v\), while every other attribute has an unconditional preference. The proposed lexicographic ordering, with \(v\) last, is well-defined: when comparison reaches \(v\), all its parents have equal values in the compared outcomes. Every permitted single-coordinate preference comparison is respected, so the resulting total order extends the CP-net.
The dyadic padding is valid. In the reduction, \(B\geq 1\), so a power of two \(N\) exists with \(2B\leq N<4B\). Both \(N\) and \(2B\) are even, making the number of added neutral pairs integral. Opposite separable preferences cancel at every attribute. Merging identical types preserves aggregate margins, positive dyadic masses, and total mass \(1\), while keeping support size polynomial.
Adding the fresh unit clause \(u\) preserves satisfiability and ensures that the all-zero assignment does not satisfy \(\Phi\). It also ensures \(s\geq 1\) and \(r\geq 1\), so every part of the construction is defined.
Each rule for \(x_i\) or \(y_i\) depends on two distinct other attributes. Each clause signal targeting \(z\) depends on at most three distinct variables. Thus the complete tables have at most eight rows, as claimed.
The clause-signal calculation is correct:
\(\sum_{j=1}^{r}h_j(x)-(r-1)=1-2b(x)\).
This is positive precisely when \(b(x)=0\), and negative otherwise. It is never zero. The actual majority margin has an additional common positive factor from paired voters and normalization, which does not change its sign.
The pair count \(B=2s+2r-1\) is correct. Including unconditional tables at every other attribute, parent identifiers, padding, and masses still gives a polynomial-size explicit input. The one-block partition satisfies the parent restriction, and all supplied voters remain individually extendible.
The edge orientation is handled correctly. The task directs edges from selected values toward the other value; reversing them produces the improving-flip graph \(H\). Accordingly, source strongly connected components of \(G\) correspond exactly to sink strongly connected components of \(H\).
The displayed outcomes are terminal in \(H\). At \(b\), all coordinates prefer zero, including \(z\), because the all-zero assignment fails \(\Phi\). At each \(c_\alpha\), the matching \(x_i,y_i\) coordinates are preferred and satisfiability makes \(z=1\) preferred.
The three reachability cases are exhaustive and valid:
These arguments require the existence of the specified path. Other available outgoing edges do not invalidate them.
The deduction about sink components is sound. A path starting in a sink component cannot leave it, so every such component contains a displayed terminal outcome. Since that outcome has no outgoing edges, its strongly connected component is a singleton. Consequently,
\(W=\{b\}\cup\{c_\alpha:\alpha\models\Phi\}\)
and \(a=1+\#\{\alpha:\alpha\models\Phi\}\).
No additional nontrivial sink components remain possible.
The cutoff argument correctly addresses the potentially exponential output on satisfiable instances.
For any fixed enumerator with the hypothesized polynomial total-time bound, the constructed input parameters are polynomially bounded in the SAT input length. A fixed polynomial cutoff can therefore dominate its running time whenever \(a=1\).
On an unsatisfiable input, the enumerator must halt before that cutoff and return exactly one winner. On a satisfiable input, either it halts and returns at least two winners, or it exceeds the cutoff. Both branches identify satisfiability correctly.
Thus the hypothesized enumerator would yield a polynomial-time SAT decision procedure. The proof establishes precisely the output-sensitive hardness claimed in the opening paragraph; it does not need to establish NP-completeness of a separate decision problem.
The common-denominator construction is valid. The bit length of \(D=\prod_t\beta_t\) is bounded by the total denominator encoding length, hence by \(L\).
Each \(w_t=\alpha_t(D/\beta_t)\) is an integer, and the normalization promise gives \(\sum_t w_t=D\). Positive weights and their partial sums are therefore bounded by \(D\). The required arithmetic uses integers of \(O(L)\) bits.
Because the input tables are explicit and complete, finding the applicable entry takes polynomial time even without an optimized lookup structure. Comparing the two weighted sums detects ties exactly. The stated bound \(T=\operatorname{poly}(m,\tau,L)\) is justified and does not expand masses into individual voters.
The parent restriction guarantees the needed independence: preferences within the processed prefix do not depend on the next block.
The product-component lemma is correct. Prefix paths within \(C\) lift while holding the block assignment fixed. Every edge in \(U_C\) can be realized after moving to its witnessing prefix assignment. Conversely, joint paths staying over \(C\) project to paths in \(U_C\). A joint path beginning and ending over \(C\) cannot leave that prefix component and return, since doing so would put the intervening prefix vertices in the same strongly connected component.
These facts establish the asserted components \(C\times D\). The source criterion also holds: an incoming prefix edge lifts to every block assignment, and an incoming union-graph edge has a witnessing prefix assignment in \(C\). When both components are sources, neither kind of incoming joint edge is possible.
The iterative algorithm therefore retains exactly the source components at every stage. Inserting both directed edges on ties is consistent with both the task and the lemma.
The attribution to Xia–Conitzer–Lang is accurate: their Process 1 uses conditional graph unions over prefix components, and Theorems 4–5 establish correctness and an output-sensitive bound for finite electorates. The present write-up supplies its own graph proof and rational-weight evaluation argument, so the extension does not rely on substituting support size for electorate size in that theorem. [Xia–Conitzer–Lang](https://www.cs.cmu.edu/~conitzer/cyclic_votingAAAI08.pdf)
Every nonempty finite \(U_C\) has a source component. Thus every retained prefix outcome has at least one retained extension, establishing
\(1=b_0\leq b_1\leq\cdots\leq b_q=a\).
This justifies bounding intermediate lists by the final output size.
At each stage, the claimed evaluation bound
\(b_{\ell-1}|A_\ell|2^{|A_\ell|}\leq ak2^k\)
is correct. Each union graph has at most \(2^k\) vertices and \(k2^k\) directed edges, including ties. There are at most \(a\) retained prefix components.
Explicit product lists contain at most \(a\) outcomes per stage, each requiring at most \(m\) bits. With \(q\leq m\), the graph construction, strongly connected component computations, rational arithmetic, and list materialization all fit within
\(2^k\operatorname{poly}(m,\tau,L,a)\).
The conclusion with \(f(k)=2^k\) follows.
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.