Answer: \(\mathrm{NP}\)-complete for every fixed \(d\geq1\), even with exactly three types of masses \(3/8,3/8,1/4\). For \(d=0\), a weak local winner always exists and can be constructed in time polynomial in \(m,\tau,L\).
Theorem 4 — class: hardness
Input a set \(\mathcal{T}\u005c) of \(\tau\u005c) complete binary-valued CP-net types with total local preference tables and indegree at most a fixed constant, each assigned positive binary-rational mass \(\mu_t\u005c) summing to \(1\u005c). For neighboring assignments \(x,y\in\{0,1\}^n\u005c), let \(p_\mu(y,x)=\sum_{t\in\mathcal{T}:y\succ_t x}\mu_t\u005c). Decide whether there is an assignment \(x\in\{0,1\}^n\u005c) such that \(p_\mu(y,x)\le 1/2\u005c) for every one-variable neighbor \(y\u005c), and return a witness if one exists.
The domain has \(m\geq 1\) Boolean variables and outcomes \(x\in\{0,1\}^m\). A type \(t\) is a CP-net with a possibly cyclic dependency graph, no self-loops, and indegree at most a fixed constant \(d\); each parent assignment has an explicitly listed strict order on the two values. Types need not share a dependency graph.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
For outcomes \(x,y\) differing only in variable \(i\), write \(y\succ_t x\) precisely when the local table for \(i\), evaluated at their common parent assignment, prefers \(y_i\) to \(x_i\). Define \(p_\mu(y,x)=\sum_{t:y\succ_t x}\mu_t\).
A weak local winner is an outcome \(x\) satisfying \(p_\mu(y,x)\leq\tfrac12\) for every one-variable neighbor \(y\). Exact half-mass ties are allowed.
Is deciding whether a weak local winner exists in \(\mathrm{P}\), or is it NP-hard? In the polynomial-time case, can a witness also be returned in time polynomial in \(m,\tau,L\), with \(d\) fixed?
For finite unweighted societies with constant-bounded indegree, checking a proposed weak local winner is polynomial-time, and finding weak local winners is stated to be NP-complete by [Li, Vo and Kowalczyk (2011)](https://www.ifaamas.org/Proceedings/aamas2011/papers/B5_R64.pdf).
No verified complexity result for this exact rational-mass formulation was identified.
For every fixed \(d\geq 1\), deciding whether a weak local winner exists is \(\mathrm{NP}\)-complete. Hardness holds with exactly three types, each of indegree at most one, and fixed masses \(3/8,3/8,1/4\).
For \(d=0\), a weak local winner always exists and can be returned in time polynomial in \(m,\tau,L\).
The unweighted complexity claim appears in Theorem 4 of [Li, Vo and Kowalczyk (2011)](https://www.ifaamas.org/Proceedings/aamas2011/papers/B5_R64.pdf). Below is a direct proof for the specified rational-mass representation.
For type \(t\) and variable \(i\), let \(f_{t,i}(x)\in\{0,1\}\) be the locally preferred value, evaluated at the parent assignment supplied by \(x\). Because self-loops are forbidden, flipping \(x_i\) leaves this parent assignment unchanged.
Define the mass supporting the current value by
\(W_i(x)=\sum_{t:\,f_{t,i}(x)=x_i}\mu_t.\)
Every local order is strict and binary. Consequently, the mass preferring the neighbor obtained by flipping variable \(i\) is exactly \(1-W_i(x)\). Thus
\(x\text{ is a weak local winner}\quad\Longleftrightarrow\quad W_i(x)\geq \tfrac12\text{ for every }i.\)
These comparisons can be performed exactly in polynomial time. Write each input rational as \(\mu_t=a_t/b_t\), with positive integers encoded in binary. Set
\(D=\prod_t b_t,\qquad A_t=a_t(D/b_t).\)
The bit length of \(D\) is at most one plus the sum of the denominator bit lengths, hence is \(O(L)\). Normalization gives \(\sum_t A_t=D\). For each variable, verification amounts to checking the integer inequality
\(2\sum_{t:\,f_{t,i}(x)=x_i}A_t\geq D.\)
There are \(m\tau\) table evaluations, each using at most \(d\) parent values, and polynomially many arithmetic operations on integers of polynomial bit length. An outcome is therefore a polynomial-size, polynomial-time verifiable certificate. The decision problem belongs to \(\mathrm{NP}\).
Fix three types with masses
\((\mu_1,\mu_2,\mu_3)=(3/8,3/8,1/4).\)
Every individual mass is at most \(3/8<1/2\), while every pair has mass at least \(5/8>1/2\). Therefore their weighted majority agrees exactly with the ordinary majority of their three preferred bits, and ties never occur.
For a variable \(V\), choose its preferred bits in the three types according to the following table. Here \(U,W\) denote other variables.
| Desired equation | Type \(1\) prefers | Type \(2\) prefers | Type \(3\) prefers |
|---|---|---|---|
| \(V=U\) | \(U\) | \(U\) | \(U\) |
| \(V=\neg U\) | \(1-U\) | \(1-U\) | \(1-U\) |
| \(V=U\land W\) | \(U\) | \(W\) | \(0\) |
| \(V=U\lor W\) | \(U\) | \(W\) | \(1\) |
Each entry defines a valid strict local preference table:
Thus every variable has at most one parent in each type.
The majority identities follow explicitly: for the conjunction row, the mass preferring \(1\) is \(3(U+W)/8\), which exceeds \(1/2\) exactly when both inputs are \(1\). For the disjunction row, that mass is \((3(U+W)+2)/8\), which exceeds \(1/2\) exactly when at least one input is \(1\). The copy and negation rows are unanimous.
Because ties never occur, Section 1 implies that a weak local winner must assign every variable its majority-preferred bit. Conversely, an outcome doing so at every variable is a weak local winner. Hence the construction realizes precisely the displayed Boolean equations.
We reduce from \(\mathrm{3SAT}\), restricted to formulas having at least one variable and one clause. This restriction preserves \(\mathrm{NP}\)-hardness: adding a clause \(Z\lor\neg Z\lor Z\), with fresh variable \(Z\), ensures both conditions without changing satisfiability.
Let the input formula be \(F(Z_1,\ldots,Z_n)\).
For each \(Z_j\), introduce two distinct outcome variables \(X_j,Y_j\) and impose, using the copy row,
\(X_j=Y_j,\qquad Y_j=X_j.\)
These equations admit exactly the assignments \((X_j,Y_j)=(0,0)\) and \((1,1)\). They therefore allow an arbitrary truth assignment to the formula variables, represented by the \(X_j\).
Each dependency is between distinct variables. The resulting two-cycles are permitted by the task.
Construct a Boolean circuit computing \(F\), with inputs \(X_1,\ldots,X_n\), unary negation gates, and binary conjunction and disjunction gates. Such a circuit has size polynomial in the formula length: evaluate each clause using two disjunction gates and combine the clause outputs using binary conjunction gates.
Introduce a fresh outcome variable for every gate and implement its equation using Section 2. Denote the circuit’s output variable by \(S\).
Every gate variable is distinct from its input variables, so no self-loop is introduced. Moreover, in any outcome satisfying all gate equations, induction along the circuit’s topological order gives
\(S=F(X_1,\ldots,X_n).\)
Conversely, every assignment to the \(X_j\) extends uniquely to the gate variables by evaluating the circuit.
Introduce two further fresh variables \(A,B\), and impose
\(A=\neg B,\qquad B=A\lor S.\)
Implement these equations using the negation and disjunction rows.
If \(S=0\), the equations require \(A=\neg B\) and \(B=A\), which are inconsistent.
If \(S=1\), the assignment \(A=0,B=1\) satisfies both equations.
Thus the acceptance gadget has a solution exactly when \(S=1\).
Suppose \(F\) is satisfiable. Choose a satisfying assignment, set \(X_j=Y_j\) to its value on \(Z_j\), and evaluate every circuit gate. Then \(S=1\). Setting \(A=0,B=1\) satisfies the acceptance gadget. All constructed equations hold, so Section 2 shows that the resulting outcome is a weak local winner.
Conversely, suppose the constructed society has a weak local winner. Section 2 forces every constructed equation to hold. The acceptance gadget forces \(S=1\), and the circuit equations give \(S=F(X_1,\ldots,X_n)\). Consequently, the values of the \(X_j\) constitute a satisfying assignment of \(F\).
We have proved
\(F\text{ is satisfiable}\quad\Longleftrightarrow\quad\text{the constructed society has a weak local winner}.\)
There are polynomially many outcome variables. Each type lists at most two preference-table rows per variable, because its indegree is at most one. All masses are fixed positive dyadic rationals summing to one.
The three types are distinct: at variable \(B\), type \(1\) has parent \(A\), type \(2\) has parent \(S\), and type \(3\) has no parent and prefers \(1\). Thus the support has exactly three types.
The construction has polynomial bit length and takes polynomial time. It proves \(\mathrm{NP}\)-hardness for \(d=1\), and therefore for every fixed \(d\geq1\). Together with Section 1, this establishes \(\mathrm{NP}\)-completeness. Allowing half-mass ties does not affect the reduction, because its instances have no such ties.
When \(d=0\), every type’s preference for each variable is unconditional. Compute
\(q_i=\sum_{t:\,\text{type }t\text{ prefers }1\text{ at }i}\mu_t.\)
Choose \(x_i=1\) when \(q_i\geq1/2\), and choose \(x_i=0\) otherwise.
If \(x_i=1\), the opposing mass is \(1-q_i\leq1/2\). If \(x_i=0\), the opposing mass is \(q_i<1/2\). Hence the constructed outcome is a weak local winner.
The exact-arithmetic procedure from Section 1 computes all these choices in time polynomial in \(m,\tau,L\). Thus both existence and witness construction are polynomial-time for \(d=0\). For fixed \(d\geq1\), a polynomial-time general decision algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the task. For every fixed \(d\geq 1\), existence is \(\mathrm{NP}\)-complete, even with exactly three supported types and the stated fixed rational masses. For \(d=0\), existence is guaranteed and a witness can be constructed in polynomial time. No substantive or expositional gaps require repair.
The definition of \(f_{t,i}(x)\) is valid: each local table specifies a unique preferred bit for every parent assignment.
The no-self-loop hypothesis is used correctly. Flipping variable \(i\) leaves all its parents unchanged, so the preferred bit is evaluated in the same context at both endpoints of the neighboring pair.
Since preferences are strict and binary, each type supports exactly one endpoint. Thus the opposing mass is precisely \(1-W_i(x)\), and the equivalence
\[
x\text{ is a weak local winner}
\quad\Longleftrightarrow\quad
W_i(x)\geq \tfrac12\text{ for every }i
\]
is correct, including equality.
The common-denominator computation is also sound:
There are \(m\tau\) table evaluations. The explicit representation and fixed indegree ensure polynomial-time evaluation. The certificate has \(m\) bits, so the claimed membership in \(\mathrm{NP}\) follows.
The three masses sum to one. Their pairwise sums are \(3/4,5/8,5/8\), while every individual mass is below \(1/2\). Consequently, weighted majority equals ordinary majority of the three preferred bits.
No subset of these masses sums to \(1/2\). Therefore no local comparison in the constructed society produces a half-mass tie.
Each specified preference is a valid strict binary local table with at most one parent per type. The construction bounds indegree in each individual CP-net, exactly as the task requires.
The gate calculations are correct:
The stated equivalence between weak local winners and simultaneous satisfaction of the implemented equations follows from Section 1 and the absence of ties.
The restriction to formulas with at least one variable and one clause preserves hardness. The displayed fresh-variable clause is tautological and does not alter satisfiability. This uses the usual convention that a three-literal clause may contain repeated literals.
The assignment-variable construction is correct. The equations \(X_j=Y_j\) and \(Y_j=X_j\) admit precisely the two stated assignments. Dependencies are between distinct variables, and the resulting cycles are explicitly permitted by the task.
The formula circuit has polynomial size. Introducing a fresh variable for each gate prevents self-loops, including when a formula repeats an input literal. The claimed evaluation property follows by induction through the circuit’s topological order. The uniqueness claim concerns gate values after fixing the inputs and is correct.
The acceptance gadget is checked correctly:
Both directions of the reduction are complete. A satisfying formula assignment extends to all constructed variables and yields a weak local winner. Conversely, any weak local winner satisfies every implemented equation, forces \(S=1\), and therefore supplies a satisfying assignment of the original formula.
Every constructed variable receives a local preference table in each of the three types. Each table has at most two rows, and all parent references are to distinct outcome variables.
The number of variables, table rows, and bits needed to encode parent identifiers is polynomial in the formula length. The fixed masses introduce only constant encoding overhead.
The three types are genuinely distinct. At \(B\), their preferred-bit functions are respectively \(A\), \(S\), and the constant \(1\), with the stated different parent sets. Since \(A\) and \(S\) are distinct fresh variables, this distinction is valid.
Thus the output is a valid support representation with exactly three positive-mass types. Hardness for indegree at most one immediately applies to every allowed bound \(d\geq1\). Combined with membership in \(\mathrm{NP}\), this proves the claimed completeness result.
When preferences are unconditional, the computed quantity \(q_i\) does not depend on the chosen outcome. The proposed coordinate choices satisfy the required opposing-mass bound:
Exact ties are handled correctly. The arithmetic analysis from Section 1 applies directly, establishing polynomial-time witness construction in \(m,\tau,L\).
The attribution is accurate: Theorem 4 of [Li, Vo and Kowalczyk (2011)](https://www.ifaamas.org/Proceedings/aamas2011/papers/B5_R64.pdf) states polynomial-time verification and an NP-completeness claim for finding weak local Condorcet winners under constant-bounded indegree. The present proof establishes the requested decision result independently, so its correctness does not depend on that paper’s proof or its wording about finding the entire set.
No repair or additional clarification is necessary. The distinction between \(d=0\) and \(d\geq1\) is a parameter distinction, not a dependence on input encoding; the appropriate complexity status is therefore “hardness.”
⟨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.