Approximation Ratio for Preference Aggregation Using Tree CP-Nets (aamas25-00016)

Given a finite-support rational distribution μ over complete tree or \(1\)-bounded CP-net types on fixed binary attributes, choose for each attribute an input CPT minimizing weighted swap disagreement and assemble them into an aggregate CP-net \hat N. Does \(D_μ(\hat N)≤(4/3)\mathrm{OPT}_μ\), where \(D_μ(N)=\sum_M μ_M f_\mathrm{swap}(N,M)\)?

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; masses satisfy \(\sum_M\mu_M=1\). State running times in the number of attributes \(m\), support size \(\tau\), and total input bit length \(L\).
Each type is a complete CP-net on the same \(m\ge2\) binary attributes, with strict CPT preferences and at most one parent per attribute; cycles are permitted. A parent cannot be the attribute itself. Tree CP-nets are included.
A swap is an unordered pair of outcomes differing in exactly one attribute; its orientation is determined directly by that attribute's CPT. Let \(f_{\mathrm{swap},j}(N,M)\) count swaps of attribute \(j\) oriented differently by \(N\) and \(M\), and let \(f_{\mathrm{swap}}=\sum_{j=1}^m f_{\mathrm{swap},j}\).
Define \(D_\mu(N)=\sum_M\mu_M f_{\mathrm{swap}}(N,M)\) and \(\mathrm{OPT}_\mu=\min_N D_\mu(N)\), where the minimum ranges over all complete CP-nets on these attributes, allowing arbitrary parent sets and cycles.
For each attribute \(j\), choose a CPT occurring at that attribute in the support that minimizes \(\sum_M\mu_M f_{\mathrm{swap},j}(N,M)\), and assemble the chosen CPTs into \(\widehat N\). Ties may be resolved arbitrarily; the assembled graph need not be a tree or acyclic.
Does this rule run in time polynomial in \(m,\tau,L\) and guarantee \(D_\mu(\widehat N)\le\frac{4}{3}\mathrm{OPT}_\mu\) for every such society and every minimizing tie choice?
For finite multisets of complete \(1\)-bounded CP-nets, choosing the best input CPT independently at each attribute gives a polynomial-time \(\frac{4}{3}\)-approximation; the bound is tight. [Ali, Ogundare, Yang and Zilles (2025)](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p78.pdf)
No separately stated guarantee for binary-rational mass inputs was located in the literature search.

1. Result

Yes. The rule guarantees \(D_\mu(\widehat N)\le \frac43\mathrm{OPT}_\mu\) for every minimizing tie choice. With standard binary encoding of rational numerators and denominators, a conservative running-time bound is \(O\!\left(L+m\tau^2(L+m)^2\right)\) bit operations.

The approximation guarantee follows by exact scaling from the multiset theorem; the algorithm operates directly on the weighted support.

2. Separating the attributes

For a CPT \(C\) at attribute \(j\), let \(\delta_j(C,C')\) be the number of attribute-\(j\) swaps on which \(C\) and \(C'\) disagree. Write \(C_{M,j}\) for the CPT of type \(M\), and define

\(d_j(C)=\sum_M\mu_M\delta_j(C,C_{M,j}),\qquad o_j=\min_C d_j(C),\)

where the minimum permits every parent set excluding \(j\).

Each assignment to the other \(m-1\) attributes specifies exactly one unordered attribute-\(j\) swap. A complete CPT with all those attributes as parents can prescribe its orientation independently for every assignment. Consequently, every possible orientation function is feasible locally, and the local minimum exists.

For every complete CP-net \(N\),

\(D_\mu(N)=\sum_{j=1}^m d_j(C_{N,j})\ge \sum_{j=1}^m o_j.\)

Conversely, choose a minimizing CPT for each attribute and assemble them. This is feasible because cycles and arbitrary parent sets are allowed. Thus

\(\mathrm{OPT}_\mu=\sum_{j=1}^m o_j.\)

This argument concerns direct swap orientations only; it requires no consistency of a transitive preference relation.

3. Extending the multiset guarantee to rational masses

The local form of the known theorem is: for any nonempty finite multiset \(\mathcal P\) of complete \(1\)-bounded CPTs at one attribute,

\(\min_{C\in\mathcal P}\sum_{T\in\mathcal P}\delta_j(C,T)\le \frac43\min_C\sum_{T\in\mathcal P}\delta_j(C,T),\)

where the right-hand minimum allows arbitrary parent sets. This is the best-input-CPT guarantee established by [Ali, Ogundare, Yang and Zilles, Theorem 5.1 and its preceding formulation](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p78.pdf).

Write each positive mass as \(\mu_M=p_M/q_M\), with positive integer numerator and denominator. Set

\(Q=\prod_M q_M,\qquad a_M=p_M(Q/q_M).\)

Then \(a_M\) is a positive integer, \(a_M/Q=\mu_M\), and normalization gives \(\sum_M a_M=Q\).

For each attribute \(j\), form a *mathematical* multiset \(\mathcal P_j\) containing \(a_M\) copies of \(C_{M,j}\). For every candidate CPT \(C\), including unrestricted ones,

\(\sum_{T\in\mathcal P_j}\delta_j(C,T)=\sum_M a_M\delta_j(C,C_{M,j})=Qd_j(C).\)

Because every \(a_M\) is positive, the CPTs occurring in \(\mathcal P_j\) are exactly those occurring at attribute \(j\) in the support. Therefore

\(\min_{C\in\mathcal P_j}\sum_{T\in\mathcal P_j}\delta_j(C,T)=Q\min_{C\text{ occurring in the support}}d_j(C),\)

and the unrestricted multiset optimum equals \(Qo_j\).

All theorem hypotheses hold: the multiset is finite and nonempty, its CPTs are complete and \(1\)-bounded, and there are \(m\ge2\) binary attributes. A one-parent CPT whose rows agree can equivalently be represented as an unconditional CPT, without changing any disagreement or candidate cost. Cycles elsewhere in an input graph have no effect on the local theorem.

Applying the theorem and dividing by \(Q>0\) yields

\(d_j(\widehat C_j)\le \frac43o_j.\)

Every minimizing tie choice has this same local objective value, so the inequality holds for every such choice. If \(o_j=0\), positivity of all masses implies that a locally optimal CPT agrees with every support CPT on every swap; hence all support CPTs agree with each other and the selected cost is also zero.

Summing over attributes proves

\(D_\mu(\widehat N)=\sum_jd_j(\widehat C_j)\le \frac43\sum_jo_j=\frac43\mathrm{OPT}_\mu.\)

4. Polynomial-time implementation

The multisets above need not be constructed.

For two input CPTs \(C,C'\) at attribute \(j\), let \(P,P'\) be their parent sets and \(S=P\cup P'\). Since both CPTs are \(1\)-bounded, \(|S|\le2\). For an assignment \(x\) to \(S\), let \(b_C(x|_P)\) denote the value preferred by \(C\). Then

\(\delta_j(C,C')=2^{m-1-|S|}\sum_{x\in\{0,1\}^{S}}\mathbf1\!\left[b_C(x|_P)\ne b_{C'}(x|_{P'})\right].\)

Indeed, each assignment to \(S\) extends to exactly \(2^{m-1-|S|}\) assignments to the other attributes, and therefore to that many swaps. The formula examines at most four assignments.

Compute \(Q\) and the integers \(a_M\). For every attribute and every support candidate, compute the integer score

\(s_j(C)=\sum_M a_M\delta_j(C,C_{M,j})=Qd_j(C),\)

and select any candidate of minimum score.

There are at most \(m\tau^2\) pairwise disagreement computations and score terms. The binary length of \(Q\) is \(O(L)\), and \(a_M\le Q\). Every score is bounded by \(Q2^{m-1}\), so all score arithmetic uses \(O(L+m)\) bits.

Using schoolbook integer arithmetic, denominator preprocessing costs \(O(\tau L^2)\), and scoring and comparisons cost at most \(O\!\left(m\tau^2(L+m)^2\right)\). Including input reading gives the stated bound. The output contains only \(m\) selected input CPTs and is polynomial in size.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves the assigned question. The rational-mass extension is valid, the algorithm avoids expanding the support into a multiset, and the stated bit-complexity bound is sound. No major or minor mathematical issues were found.

• The cited theorem matches the required local guarantee.

The prover states the theorem as an inequality between the minimum disagreement of an input CPT and the unrestricted local optimum. This matches the paper’s formulation immediately before Section 4. Although Theorem 5.1 uses the phrase “tree CPTs,” the surrounding definitions and formulation explicitly cover complete CPTs with at most one parent, including unconditional CPTs. The paper also explicitly permits cyclic input CP-nets and defines disagreement through direct swap orientations. Thus the citation supports the theorem in precisely the form used here. [Ali, Ogundare, Yang and Zilles, Sections 3–5](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p78.pdf)

The prover checks the relevant hypotheses: a finite, nonempty multiset; complete, strict binary CPTs; at most one parent per input CPT; and \(m\ge2\). The unrestricted optimum in the cited formulation agrees with the optimum used in the proof.

• The separation into attribute objectives is correct.

For each attribute \(j\), assignments to the other \(m-1\) attributes correspond bijectively to its unordered swaps. Allowing all those attributes as parents permits any assignment of strict orientations to these swaps. Hence the local minimum \(o_j\) exists.

The identity
\[ D_\mu(N)=\sum_{j=1}^{m}d_j(C_{N,j}) \]
follows directly from the definition of swap disagreement. It gives the stated lower bound by \(\sum_j o_j\).

Conversely, assembling locally minimizing CPTs is permitted by the task: arbitrary parent sets and cycles are allowed, and no selected parent set contains its own attribute. Therefore the reverse inequality holds, establishing
\[ \mathrm{OPT}_\mu=\sum_{j=1}^{m}o_j. \]
There is no hidden acyclicity or global preference-consistency requirement.

• The rational scaling is exact.

For positive rational masses \(\mu_M=p_M/q_M\), the product \(Q=\prod_Mq_M\) is a positive common denominator. Each \(a_M=p_M(Q/q_M)\) is a positive integer, and normalization gives \(\sum_Ma_M=Q\).

The multiset identity holds for every candidate CPT, including unrestricted candidates:
\[ \sum_{T\in\mathcal P_j}\delta_j(C,T)=Qd_j(C). \]
Consequently, both the restricted candidate minimum and the unrestricted optimum scale by the same positive factor \(Q\).

Positivity ensures that the multiset contains exactly the support’s occurring CPTs as candidates. Repeated identical CPTs introduce multiplicities but do not change the candidate set. No assumption of distinct CPTs is needed.

• The approximation conclusion covers every minimizing tie choice.

Applying the cited theorem and dividing by \(Q\) gives the claimed local inequality. All minimizing support candidates have the same objective value, so the guarantee is independent of tie resolution.

The zero-optimum case is also correctly handled. If \(o_j=0\), every nonnegative disagreement term must vanish because every support mass is positive. Thus all support CPTs agree on every local swap, and every selected candidate has zero local cost.

Summing the local inequalities and using the established decomposition of \(\mathrm{OPT}_\mu\) proves the requested global bound.

• The disagreement computation is correct, including the smallest domain.

The union \(S=P\cup P'\) excludes \(j\), and satisfies
\[ |S|\le\min(2,m-1). \]
Therefore the exponent \(m-1-|S|\) is nonnegative, including when \(m=2\).

Each assignment to \(S\) has exactly \(2^{m-1-|S|}\) extensions to the remaining attributes. The formula therefore counts each unordered attribute-\(j\) swap once. It requires at most four CPT-row comparisons and also handles empty or identical parent sets.

• The running-time bound is valid for the support encoding.

The bit length of \(Q\) is \(O(L)\), since its logarithm is bounded by the sum of the encoded denominator lengths. Normalization gives \(a_M\le Q\).

Each disagreement is at most \(2^{m-1}\), and each candidate score is at most \(Q2^{m-1}\). Thus intermediate nonnegative score sums require only \(O(L+m)\) bits.

There are at most \(m\tau^2\) scoring terms. Schoolbook arithmetic supports the stated scoring bound. The preprocessing bound \(O(\tau L^2)\) is absorbed into \(O(m\tau^2(L+m)^2)\), since \(m\ge2\) and \(\tau\ge1\). Input reading and output construction fit within the total bound.

The potentially enormous multiset is used only mathematically. The implemented algorithm operates on the \(\tau\) support entries, so its runtime is polynomial in the requested parameters.

No repair or additional clarification is needed. The established complexity result is a polynomial-time approximation guarantee; the output does not establish polynomial-time exact optimization.

⟨structured verdict parsed — rendered above⟩