Answer: The decision problem is \(\mathrm{NP}\)-complete, and finding any maximizer is \(\mathrm{NP}\)-hard, even with support size \(\tau=1\) and mass \(1\).
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to find a winner under MLEπ1,q. More precisely, it is NP-complete to decide whether there exists an alter- native ⃗d such that N1(⃗d, PCP ) ≥T.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(p\) binary issues, an explicitly represented finite support of CP-net types \(N\), binary-rational masses \(\mu_N>0\) summing to \(1\), and a rational cutoff \(b\), decide whether some \(d\in\{0,1\}^p\) satisfies \(F^{(1)}_\mu(d)\ge b\), where \(F^{(1)}_\mu(d)=\sum_N\mu_N N_1(d,N)\) and \(N_1(d,N)=|\{i: N\text{ prefers }d_i\text{ to }\bar d_i\text{ in context }d_{-i}\}|\). The optimization version asks for a maximizer of \(F^{(1)}_\mu\).
There are \(m=p\ge2\) binary issues, with outcomes \(d\in\{0,1\}^p\). Each CP-net type \(N\) is encoded by a directed graph without self-loops and complete, explicitly listed conditional preference tables giving a strict order on \(\{0,1\}\) for every assignment to each issue’s parents; cycles are allowed.
A society is given by its support: the list \(\mathcal S\) of the \(\tau\ge1\) types with positive mass, each with its mass \(\mu_N\) as a binary rational, with \(\sum_{N\in\mathcal S}\mu_N=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For an outcome \(d\), let \(d_{-i}\) omit coordinate \(i\), and let \(\bar d_i=1-d_i\). Define \(N_1(d,N)=|\{i\in\{1,\ldots,p\}:d_i\succ^N_{i,d_{-i}}\bar d_i\}|\), where the comparison uses the table row selected by the parents’ values in \(d\), and \(F^{(1)}_\mu(d)=\sum_{N\in\mathcal S}\mu_N N_1(d,N)\).
Given a binary-rational cutoff \(b\in\mathbb Q\), the decision problem asks whether some \(d\in\{0,1\}^p\) satisfies \(F^{(1)}_\mu(d)\ge b\); the optimization version returns any maximizer, with no tie-breaking requirement.
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of equally weighted CP-net voters, the corresponding score-threshold problem is NP-complete, and finding a maximizer is NP-hard. [Verified discrete result](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_06_FP_0294.pdf).
No result explicitly addressing this normalized binary-rational mass formulation was located.
The decision problem is \(\mathrm{NP}\)-complete, and returning any maximizer is \(\mathrm{NP}\)-hard. In fact, both hardness statements hold with support size \(\tau=1\), mass \(1\), and at most four parents per issue.
Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
An outcome \(d\in\{0,1\}^m\) is a certificate of length \(m\). For every supported type \(N\) and issue \(i\), read the explicitly listed table row matching the parent values in \(d\). This determines whether issue \(i\) contributes to \(N_1(d,N)\), and hence computes the integer \(s_N=N_1(d,N)\), where \(0\le s_N\le m\).
The score comparison can be performed exactly. Write each mass as \(\mu_N=a_N/q_N\), with positive denominator, and write the cutoff as \(b=u/v\), with \(v>0\). Define
\(Q=\prod_{N\in\mathcal S}q_N\), and \(A=\sum_{N\in\mathcal S}a_Ns_N(Q/q_N)\).
Then \(F^{(1)}_\mu(d)=A/Q\), so acceptance is equivalent to the integer comparison \(vA\ge uQ\).
The bit length of \(Q\) is at most the sum of the input denominator bit lengths, hence is \(O(L)\). Since the masses sum to \(1\), we have \(0\le A\le mQ\). Thus all integers used have \(O(L+\log m)=O(L)\) bits. Explicit table scans and schoolbook integer arithmetic give, for example, the conservative verification bound \(O(m\tau L^2)\) bit operations.
Consequently, the decision problem belongs to \(\mathrm{NP}\).
We reduce from satisfiability of a formula \(\varphi=C_1\land\cdots\land C_q\), with variables \(x_1,\ldots,x_n\), where each clause contains at most three literals. This version of \(3\)-SAT is \(\mathrm{NP}\)-complete. We may assume \(n\ge1\), adding an unused variable if necessary.
Create two binary issues \(X_j,Y_j\) for each variable \(x_j\), and two binary issues \(A_r,B_r\) for each clause \(C_r\). Thus
\(m=2n+2q\ge2\).
Construct one CP-net \(N\), with mass \(\mu_N=1\). Specify its locally preferred values as follows:
In every table row, the designated value is ranked strictly above its complement. We explicitly list every row.
There are no self-loops: all parents differ from their child. The two-way dependencies are permitted because cycles are allowed. Each \(A_r\) has at most four parents, so its table has at most \(16\) rows; every other issue has exactly two rows. The construction therefore has at most \(4n+18q\) table rows.
Set the cutoff to \(b=m\). With an adjacency-matrix graph encoding, the output length is \(O(m^2)\), and the numbered construction can be written in \(O(m^2)\) time. In particular, it is a polynomial-size, polynomial-time reduction.
Because the support contains only \(N\), its score is \(F^{(1)}_\mu(d)=N_1(d,N)\le m\). Therefore \(F^{(1)}_\mu(d)\ge m\) holds exactly when every issue takes its locally preferred value.
For a variable pair, both issues are locally preferred exactly when
\(X_j=Y_j\).
Either common value is allowed, so these pairs permit arbitrary truth assignments.
For a clause pair, the local condition for \(B_r\) is \(B_r=A_r\).
If the clause is true, the condition for \(A_r\) is \(A_r=B_r\). Both conditions can hold, for example with \(A_r=B_r=0\).
If the clause is false, the condition for \(A_r\) is \(A_r=1-B_r\). Together with \(B_r=A_r\), this would require \(A_r=1-A_r\), which no binary value satisfies.
Suppose \(\varphi\) is satisfiable. Set each \(X_j\) to its satisfying truth value, set \(Y_j=X_j\), and set every \(A_r=B_r=0\). Each variable pair is locally consistent. Every clause is true, so each clause pair is also locally consistent. All \(m\) issues contribute, giving score \(m\).
Conversely, suppose an outcome has score at least \(m\). All issues must then be locally preferred. For every clause pair, simultaneous local consistency is impossible when its clause is false. Hence every clause is true under the assignment \(x_j=X_j\), and \(\varphi\) is satisfiable.
We have proved the exact equivalence
\(\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad\exists d:\ F^{(1)}_\mu(d)\ge b\).
This proves \(\mathrm{NP}\)-hardness, even for \(\tau=1\). Together with membership, it proves \(\mathrm{NP}\)-completeness.
Normalization also directly transfers the supplied discrete result, stated as Theorem \(8\) in [Xia, Conitzer, and Lang’s paper](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_06_FP_0294.pdf).
For an explicitly listed profile \(N^{(1)},\ldots,N^{(n)}\), group repeated types. If type \(N\) occurs \(c_N\) times, assign it mass \(\mu_N=c_N/n\), and replace the discrete cutoff \(T\) by \(b=T/n\). For every outcome,
\(F^{(1)}_\mu(d)=\frac1n\sum_{j=1}^nN_1(d,N^{(j)})\).
Thus every threshold comparison is preserved. The masses sum to \(1\), the support size satisfies \(\tau\le n\), and each mass uses \(O(\log n)\) bits. Since the source profile lists all voters explicitly, this transformation has polynomial encoding size.
Finally, an algorithm returning any maximizer would solve the decision problem: compute its returned outcome’s exact score and compare it with \(b\). This argument requires no tie-breaking rule. Therefore the optimization problem is \(\mathrm{NP}\)-hard.
For completeness, exhaustive enumeration solves either version in \(O(2^m m\tau L^2)\) bit operations using the verifier above. The hardness result rules out a polynomial bound in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the task. The decision problem is \(\mathrm{NP}\)-complete, and finding any maximizer is \(\mathrm{NP}\)-hard, including the claimed restriction to one supported type with at most four parents per issue. No substantive or expositional gaps require repair.
The proposed certificate is an outcome \(d\in\{0,1\}^m\), of length \(m\). Its length is polynomial in the input length because the input explicitly describes all \(m\) issues.
For each supported type and issue, the parents’ values in \(d\) select a unique row of the complete conditional preference table. The strict binary order in that row determines the contribution unambiguously. Hence each computed integer \(s_N=N_1(d,N)\) satisfies \(0\le s_N\le m\).
The exact arithmetic is correct:
\[ Q=\prod_{N\in\mathcal S}q_N,\qquad A=\sum_{N\in\mathcal S}a_Ns_N(Q/q_N). \]
Every quotient \(Q/q_N\) is an integer, and \(Q>0\). Thus \(F^{(1)}_\mu(d)=A/Q\), and multiplication by the positive denominators gives precisely the acceptance condition \(vA\ge uQ\). This remains valid for negative cutoffs.
The bit-length argument also holds. The product denominator has \(O(L)\) bits. Positivity and normalization of the masses imply \(0\le A\le mQ\). The additional multiplication by the cutoff numerator or denominator preserves an \(O(L+\log m)\) bit bound. Explicit input encoding gives \(\log m=O(L)\).
The stated conservative verification bound \(O(m\tau L^2)\) accommodates table scans and schoolbook arithmetic. Membership in \(\mathrm{NP}\) is established.
The source problem—satisfiability of conjunctive formulas whose clauses have at most three literals—is a standard \(\mathrm{NP}\)-complete version of \(3\)-SAT. Adding an unused variable preserves satisfiability and ensures \(n\ge1\).
The construction satisfies every target restriction:
Repeated variables within a clause cause no ambiguity: the parent set contains the distinct corresponding issues, whose values suffice to evaluate all literal occurrences.
The row count is correct. Variable pairs contribute \(4n\) rows. Each clause contributes two rows for \(B_r\) and at most sixteen for \(A_r\), yielding at most \(4n+18q\) rows. The maximum number of parents is four.
With the stated adjacency-matrix encoding, the output length and construction time are \(O(m^2)\). The cutoff \(b=m\) requires only \(O(\log m)\) bits. The reduction is polynomial.
With a single type of mass \(1\), the score is an integer bounded above by \(m\). Therefore meeting the cutoff \(m\) is equivalent to every issue being locally preferred. No averaging or cancellation can invalidate this equivalence.
For each variable pair, the two conditions are \(X_j=Y_j\) and \(Y_j=X_j\). Their conjunction is exactly \(X_j=Y_j\), with either binary common value permitted.
For a clause pair:
These calculations are correct and cover every parent assignment.
The forward direction specifies a complete outcome: the satisfying assignment supplies the \(X_j\), the \(Y_j\) copy them, and every clause pair takes value zero. Each local preference is satisfied, so the score is \(m\).
The reverse direction correctly uses the upper bound \(m\). An outcome meeting the cutoff must satisfy every local preference. The verified clause-pair calculation then excludes every false clause under the assignment \(x_j=X_j\).
Consequently, the stated equivalence between source satisfiability and target threshold feasibility holds. This establishes the claimed restricted \(\mathrm{NP}\)-hardness independently of the discrete-result citation.
The boundary case \(q=0\) also causes no defect: the formula is satisfied, and the variable pairs admit an outcome attaining the cutoff.
The cited [Theorem 8](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_06_FP_0294.pdf) states hardness of winner computation and \(\mathrm{NP}\)-completeness of the score-threshold problem for explicit CP-net profiles. Its degree-one consistency score matches the task’s local-preference count.
Grouping repeated types and assigning masses \(c_N/n\) gives exactly the displayed normalized score identity. Dividing the cutoff by the positive voter count preserves every threshold comparison. The masses have \(O(\log n)\)-bit encodings and sum to \(1\).
Grouping explicitly represented types can be performed in polynomial time. Semantic merging of differently encoded but equivalent types is unnecessary. This supplementary transfer is valid.
An algorithm returning any maximizer would decide threshold feasibility by evaluating the returned outcome and comparing its score with \(b\). Every maximizer has the same score, so no tie-breaking assumption is needed. The optimization hardness also inherits the reduction’s support-size and parent-count restrictions.
The exhaustive-enumeration bound \(O(2^m m\tau L^2)\) follows from applying the established verifier to all outcomes; retaining a best outcome does not change that bound.
No blocking issues or additional clarifications were found.
⟨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.