Approximation Algorithms for Preference Aggregation Using CP-Nets (aaai24-28911)

Given binary attributes, a target attribute \(V_n\), a finite support of complete CPT types \(q=(P_q,\theta_q)\) with rational masses \(\mu_q\), and a supplied parent set \(P\) from the support, output a CPT \(N\) with parent set contained in \(P\) minimizing \(F_\mu(N)=\sum_q \mu_q \Delta(N,q)\), where \(\Delta\) counts disagreeing swaps over \(V_n\).

There are \(m=n\geq 1\) binary attributes, with target \(V_n\) and potential parents \(U=\{V_1,\ldots,V_{n-1}\}\). A complete CPT type \(q=(P_q,\theta_q)\) has \(P_q\subseteq U\) and an explicitly listed table \(\theta_q:\{0,1\}^{P_q}\to\{0,1\}\); value \(b\) means the strict preference \(b\succ 1-b\) in that context.
A society is given by its support: the list of the \(\tau\geq 1\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; require \(\sum_q\mu_q=1\). Let \(L\) be the total input bit length, including the explicit CPT tables and masses.
The input also supplies \(P=P_{q_0}\) for some support type \(q_0\). A feasible output is an explicitly listed complete CPT \(N=(S,\theta_N)\) with \(S\subseteq P\); empty parent sets are allowed.
Each \(x\in\{0,1\}^{U}\) identifies one swap over \(V_n\), namely the outcome pair differing only in \(V_n\). Define \(\Delta(N,q)=|\{x\in\{0,1\}^{U}:\theta_N(x|_S)\neq\theta_q(x|_{P_q})\}|\) and \(F_\mu(N)=\sum_q\mu_q\Delta(N,q)\). Any minimizer is acceptable, including when preferences tie in aggregate.

Can an exact minimizer of \(F_\mu\) over these feasible CPTs be produced in time polynomial in \(m,\tau,L\), or is this optimization problem NP-hard?

For an unweighted finite list of complete CPTs, exact optimization subject to a supplied input parent set is polynomial-time; the stated running time is \(O(2^{|P|}\sum_s 2^{|P_s|})\). [Verified source](https://arxiv.org/html/2312.09162).
No published result settling this exact rational-mass version was located in the search.

Result

An exact minimizer can be produced in deterministic time polynomial in \(m,\tau,L\). Rational masses can be handled by exact integer arithmetic; there is no need to expand them into repeated voters.

1. It suffices to use the supplied parent set

Write \(u=|U|=m-1\) and \(k=|P|\).

Every feasible CPT \(N=(S,\theta_N)\), with \(S\subseteq P\), has an equivalent complete CPT on \(P\): define

\(\widehat{\theta}_N(a)=\theta_N(a|_S)\quad\text{for every }a\in\{0,1\}^{P}.\)

For every \(x\in\{0,1\}^{U}\), this gives

\(\widehat{\theta}_N(x|_P)=\theta_N(x|_S).\)

Consequently, the two CPTs have identical disagreement with every support type, and hence identical objective values. Conversely, every complete CPT on \(P\) is feasible because \(P\subseteq P\).

Thus it suffices to optimize over all functions \(\theta:\{0,1\}^{P}\to\{0,1\}\). Redundant parents are permitted by the stated definition.

2. Compute the weighted votes within each context

For \(a\in\{0,1\}^{P}\), define the block

\(X_a=\{x\in\{0,1\}^{U}:x|_P=a\}.\)

These blocks partition \(\{0,1\}^{U}\), and each has size \(2^{u-k}\). A CPT on \(P\) assigns one preference bit to each block.

For each support type \(q\), count the table rows that prefer \(1\) and agree with \(a\) on the shared parents:

\(c_q(a)=\bigl|\{y\in\{0,1\}^{P_q}:\theta_q(y)=1,\ y|_{P\cap P_q}=a|_{P\cap P_q}\}\bigr|.\)

This count is obtained by scanning the explicitly listed table of \(q\).

For any compatible row \(y\), the assignments \(a\) and \(y\) jointly fix exactly the attributes in \(P\cup P_q\). There are therefore exactly \(2^{u-|P\cup P_q|}\) assignments \(x\) extending both. Different table rows give disjoint sets of extensions. Hence

\(C_q(a):=\bigl|\{x\in X_a:\theta_q(x|_{P_q})=1\}\bigr|=c_q(a)\,2^{u-|P\cup P_q|}.\)

Define the weighted number of votes for \(1\) in this block by

\(B(a)=\sum_q\mu_q C_q(a).\)

If the output bit on \(X_a\) is \(0\), its contribution to \(F_\mu\) is \(B(a)\). If the output bit is \(1\), its contribution is

\(\sum_q\mu_q\bigl(2^{u-k}-C_q(a)\bigr)=2^{u-k}-B(a),\)

where the equality uses \(\sum_q\mu_q=1\).

3. Rowwise minimization is globally optimal

Construct a complete CPT \(N^*=(P,\theta^*)\) by setting, for every \(a\),

• \(\theta^*(a)=1\) when \(2B(a)>2^{u-k}\);
• \(\theta^*(a)=0\) otherwise.

At equality, either preference is optimal; the algorithm chooses \(0\).

For any complete CPT \((P,\theta)\), partitioning the swaps into the blocks \(X_a\) gives

\(F_\mu(P,\theta)=\sum_{a\in\{0,1\}^{P}}\bigl[(1-\theta(a))B(a)+\theta(a)(2^{u-k}-B(a))\bigr].\)

Each summand depends only on the corresponding bit \(\theta(a)\). The construction chooses a minimizing bit for every summand, so

\(F_\mu(N^*)=\sum_{a\in\{0,1\}^{P}}\min\{B(a),2^{u-k}-B(a)\}\leq F_\mu(P,\theta).\)

Section 1 then implies \(F_\mu(N^*)\leq F_\mu(N)\) for every feasible CPT \(N\). This proves global optimality.

4. Exact arithmetic has polynomial bit complexity

Write each input mass as \(\mu_q=a_q/d_q\), with positive binary-encoded integers \(a_q,d_q\). Reduction to lowest terms is unnecessary. Define

\(D=\prod_q d_q,\qquad w_q=a_q(D/d_q).\)

Every \(w_q\) is an integer, and normalization implies

\(\sum_q w_q=D.\)

The bit length of \(D\) is at most \(1+\sum_q\operatorname{bitlength}(d_q)\), hence is \(O(L)\). Also, \(0<w_q\leq D\), so every \(w_q\) has \(O(L)\) bits.

For each context, compute the integer

\(Z(a)=\sum_q w_q\,c_q(a)\,2^{u-|P\cup P_q|}=D\,B(a).\)

The preference decision is now the exact integer comparison

\(2Z(a)>D\,2^{u-k}.\)

Since \(0\leq C_q(a)\leq 2^{u-k}\), we have

\(0\leq Z(a)\leq D\,2^{u-k}.\)

All summands and partial sums are nonnegative and bounded by this same quantity. Thus every integer used in these computations has \(O(L+m)\) bits. Products, exact divisions, shifts, additions, and comparisons on these integers take polynomial time using ordinary binary arithmetic.

In particular, although \(D\) can have exponentially large numerical value, its bit length remains polynomial.

5. Enumeration and output size are polynomial

Let

\(A=2^{|P|},\qquad T=\sum_q2^{|P_q|}.\)

Every input table entry explicitly contains a preference bit, so \(T\leq L\). Because \(P=P_{q_0}\) for a support type whose complete table is included,

\(A=2^{|P_{q_0}|}\leq T\leq L.\)

The algorithm enumerates \(A\) contexts and, for each context, scans all \(T\) input table entries. This requires \(AT\) compatibility checks, each taking polynomial time in \(m,L\). It also performs \(O(A\tau+\tau)\) arithmetic operations on integers of \(O(L+m)\) bits.

The output has \(A\) rows. Even if each row explicitly includes its context, its total length is \(O(mA)\), hence polynomial in \(m,L\).

The argument also covers \(P=\varnothing\) and \(m=1\): there is one context, and the algorithm performs an exact weighted-majority comparison.

Conclusion

The rational-mass version is polynomial-time solvable under the stated explicit-table encoding. The supplied unweighted result uses the same fixed-parent-set decomposition; the proof above additionally establishes exact rational arithmetic and its bit complexity. See [Ali, Yang, and Zilles, “Optimal Solution for a Fixed Parent Set”](https://arxiv.org/html/2312.09162#S6).

⟨structured verdict parsed — rendered above⟩

Assessment: proved. The output establishes a deterministic polynomial-time algorithm producing an exact minimizer under the stated explicit-table encoding. No major or minor mathematical issues were found.

• Reduction to the supplied parent set is valid. For every feasible \(S\subseteq P\), the defined extension \(\widehat{\theta}_N(a)=\theta_N(a|_S)\) preserves the preference on every swap. Therefore it preserves each \(\Delta(N,q)\) and the weighted objective. Conversely, a complete CPT on \(P\) is feasible. The task permits redundant parents, so the reduction introduces no additional restriction.

• The block partition and extension counts are correct. The sets \(X_a\) partition all assignments to \(U\), and each has exactly \(2^{u-k}\) elements. Compatibility on \(P\cap P_q\) is precisely the condition needed for \(a\) and \(y\) to have a joint extension. Such compatible assignments fix \(P\cup P_q\), leaving \(u-|P\cup P_q|\) free binary attributes. This exponent is nonnegative because both parent sets lie in \(U\). Distinct table rows give disjoint extension sets, establishing the stated formula for \(C_q(a)\).

• The weighted block costs are correct. Choosing preference \(0\) disagrees exactly with assignments counted by \(C_q(a)\), giving cost \(B(a)\). Choosing preference \(1\) disagrees with their complement in \(X_a\). The identity giving cost \(2^{u-k}-B(a)\) correctly uses the required normalization \(\sum_q\mu_q=1\).

• The minimization rule proves global optimality. The inequality \(2B(a)>2^{u-k}\) is exactly the condition under which preference \(1\) has smaller block cost. At equality, both preferences minimize that cost. Every complete function on \(P\) is permitted, so choices for different rows have no coupling constraints. The displayed objective decomposition therefore justifies minimizing each summand independently. Combined with the reduction in Section 1, this establishes optimality against every feasible CPT.

• Exact rational arithmetic has polynomial bit complexity. The common denominator \(D\) is positive, every division \(D/d_q\) is exact, and \(w_q=D\mu_q\) is an integer. Normalization establishes \(\sum_qw_q=D\). The product defining \(D\) has bit length \(O(L)\), irrespective of its numerical magnitude.

The identity \(Z(a)=DB(a)\) and the comparison \(2Z(a)>D2^{u-k}\) are correct. The bound \(Z(a)\leq D2^{u-k}\) follows from the stated bounds on \(C_q(a)\); positivity also bounds individual summands and partial sums. Counts, intermediate products, shifted values, and comparison operands consequently have \(O(L+m)\) bits. Ordinary exact binary arithmetic suffices.

• Enumeration and output length are polynomial. Explicit preference bits imply \(T\leq L\). The crucial supplied-parent-set assumption gives \(A\leq T\), because the complete table for a support type with parent set \(P\) is present in the input. Thus the \(AT\) table-row checks are polynomially many. Counting during these scans also remains polynomial. The additional weighted arithmetic and the explicitly written output have polynomial cost and length.

• The stated edge cases are covered. Empty parent sets yield one context and well-defined restrictions. When \(m=1\), all parent sets are empty and the extension factor is \(1\). A single support type, constant tables, and exact aggregate ties introduce no exception to the argument.

• The literature reference is supplementary. The cited section describes the fixed-parent-set frequency decomposition, consistent with the prover’s attribution. The rational-mass result is established directly in the submitted argument and does not depend on applying an unstated external theorem. [Ali, Yang, and Zilles, Section 6](https://arxiv.org/html/2312.09162#S6).

Repair feedback: None required. The conclusion depends explicitly on complete tables being listed and on \(P\) occurring as an input parent set; both are hypotheses of the task.

⟨structured verdict parsed — rendered above⟩