| paper | Approximation Algorithms for Preference Aggregation Using CP-Nets |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 14
statement extracted from the paper’s text layer
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\).
A finite distribution of CP-net/CPT types; the aggregate chooses one orientation for each context over P; the objective is rational-mass-weighted swap disagreement, solved by independent weighted majorities.
Theorem 14 establishes no tractability result for compactly encoded or implicit distributions, so richer distribution representations would require separate analysis.
fatal: False
The mirror covers swap-based, attribute-wise CPT aggregation and the approximation results in Theorems 4, 6, 13, and 14; it leaves unrestricted compact aggregation, Theorem 2's output-size obstruction, and global outcome-pair aggregation largely untouched.
There is a credible positive case, with Theorem 14 as the strongest anchor. This paper’s aggregation problem is unusually well suited to a high-multiplicity mirror because its input is already anonymous and its objective is additive over voters.
For the paper’s fixed target attribute \(V_n\), let a type be a complete CPT \(q=(P_q,\theta_q)\), where \(P_q\subseteq\{V_1,\ldots,V_{n-1}\}\) and \(\theta_q\) gives the preferred value of \(V_n\) in every parent context. A society is a rational distribution \(\mu\) over such CPT types. For an aggregate CPT \(N\), define
\[ F_\mu(N)=\sum_q \mu_q\,\Delta(N,q), \]
where \(\Delta(N,q)\) is the number of swaps over \(V_n\) on which \(N\) and \(q\) disagree. This is exactly the paper’s objective after normalization: if \(q\) occurs \(w_q\) times in a discrete profile of size \(W\), then \(F_\mu(N)=f_T(N)/W\). The outcome space and the swap relation remain discrete; only the voter population becomes continuous.
A plausible regime is a large recommender or product-configuration population: millions of users, departments, or customer accounts, but a few hundred or thousand recurring preference templates. Each template can encode conditional preferences such as “if feature \(A\) is selected, prefer option 1 over option 0 for \(B\).” Users sharing a template are genuinely indistinguishable for this problem. Their mass is their proportion of the user population. This is not a weakened version of the authors’ model: it is their tuple of CP-nets with repeated inputs grouped by multiplicity.
My lead mirror is Continuous Fixed-Parent-Set CPT Aggregation. Given rational masses \(\mu_q\), and a parent set \(P\) chosen from the input parent sets, output a CPT \(N_P\) with \(\operatorname{Pa}(N_P,V_n)\subseteq P\) minimizing \(F_\mu(N_P)\). A solution is the complete rule table for \(N_P\), together with its objective value.
This is the weighted version of Algorithm 2. For every context \(\gamma\) over \(P\), count, with mass weights, how many swaps consistent with \(\gamma\) receive each of the two possible votes from the population. Set the aggregate rule in that context to the weighted majority orientation. The decisions for different contexts are independent, so this produces the exact optimum under the parent-set restriction.
This is anchored by Theorem 13, proved in this paper, which establishes correctness, and Theorem 14, also proved here, which gives runtime
\[ O\!\left(2^{|P|}\sum_q |\operatorname{CPT}(q)|\right). \]
When \(P\) is one of the input parent sets, or more generally when \(|P|\) is bounded by the largest input parent-set size, the algorithm is polynomial in the explicit weighted profile. Running it over every input parent set gives the continuous analogue of Algorithm 1, and Theorem 14 says that this procedure is polynomial-time.
I would classify this mirror as Class A. The tractability is not caused by replacing preferences with something easier. It comes from the same structural fact used in the paper: once the aggregate parent set is fixed, the objective decomposes context by context and the exponential-looking optimization is just weighted majority computation.
A second, broader mirror is Continuous Representative-Type Aggregation. Given \(\mu\), output one type \(q\) from the support of \(\mu\) minimizing \(F_\mu(q)\), and compare it with
\[ \operatorname{OPT}_\infty(\mu)=\min_N F_\mu(N), \]
where the minimum ranges over all aggregate CPTs. This is precisely the paper’s “best input CPT” approximation, except that a type rather than an individually named voter is selected.
The relevant anchor is Theorem 4. The theorem is printed in this paper but its upper and lower bounds are transferred from Endriss and Grandi (2014). Its continuous version should retain the factor-2 guarantee: by averaging and the triangle inequality,
\[ \mathbb E_{q\sim\mu}[F_\mu(q)] =\mathbb E_{q,r\sim\mu}[\Delta(q,r)] \le 2\,F_\mu(N^\star). \]
Therefore some support type has expected disagreement at most twice the unrestricted optimum. The paper’s \(2-\varepsilon\) lower-bound family also transfers: it uses binary CPTs, and its uniform rational profile can be replicated arbitrarily many times to create a genuine high-multiplicity population. This is again Class A as an approximation problem, with the factor essentially tight.
The same mirror covers the paper’s Theorem 6 as a stronger promised case. If the population has equal mass on symmetric CPT types with pairwise disjoint parent sets, then selecting any support type gives a \(4/3\)-approximation. Theorem 6 is proved in this paper, via Lemmas 7–12. Equal-mass cohorts are still a legitimate continuous society: one can have arbitrarily many users in each template class.
The scope is deliberately limited. These mirrors cover the paper’s swap-based CPT aggregation for one target attribute, which the paper itself identifies as sufficient for attribute-wise aggregation. They do not claim to continuize arbitrary outcome-pair aggregation, mCP-net reasoning, PCP-nets, or sequential voting.
The main weakness is that the positive result is partly a weighted reformulation of algorithms already based on frequency counts. A skeptical referee could say that the continuous problem contributes a high-multiplicity parameterization rather than a fundamentally new algorithmic phenomenon. That criticism has force. Moreover, I would not rely heavily on Proposition 3’s printed “linear-time” claim without qualification, since the output size depends on the union of parent sets and hence on the chosen representation. The safer claim is the explicit polynomial regime of Theorems 13–14.
The positive case nevertheless survives because the full unrestricted problem remains faithful and nontrivial. Theorem 2, cited from Ali et al. (2021), shows that an optimal aggregate CPT can require exponentially many rules. That obstruction persists under a rational population distribution; continuization does not magically remove it. The resulting research questions are worthwhile: classify unrestricted aggregation by the number of distinct types and parent-set width, determine whether compact decision-diagram outputs help, test whether the \(4/3\) bound survives unequal masses, and develop a precise discrete-to-continuous approximation theorem.
The strongest negative case is that the proposed mirror is legitimate but not genuinely continuous in the programme’s sense. The paper has already quotiented out individual identity: its objective is an additive sum of disagreements between CP-nets. If a type \(q\) occurs \(w_q\) times and \(\mu_q=w_q/W\), then
\[ F_\mu(N)=\sum_q\mu_q\Delta(N,q) =\frac{1}{W}\sum_q w_q\Delta(N,q). \]
Thus every rational “continuous” instance is exactly the original finite instance with repeated CP-nets grouped and the objective normalized. Population mass is only a coefficient; it is never manipulated, constrained, or used to define feasibility.
This is fatal to Theorem 14 as a genuinely continuous anchor. The weighted version of Algorithm 2 is correct, but it is obtained by replacing integer frequency counts with rational weighted counts. Theorem 13 and the runtime proof of Theorem 14 transfer line by line. With an explicitly listed finite support, the proposed problem is simply weighted binary aggregation over CPT rules. It is a sound high-multiplicity encoding, but there is no new computational object for continuization to expose.
One might strengthen the mirror by allowing \(\mu\) to be given compactly rather than as an explicit support list. That does not rescue this anchor cleanly. The algorithm would then require an oracle or inference procedure for the mass of types voting each way in each context. Any resulting difficulty comes from the chosen representation of the distribution—factorized probabilities, circuits, generative models—not from the continuous population itself. Theorem 14 provides no result for that model, and different encodings produce different problems.
Theorem 4 is no stronger. Its continuous analogue is the ordinary weighted 1-median argument:
\[ \mathbb E_{q,r\sim\mu}[\Delta(q,r)] \le 2F_\mu(N^\star). \]
For a finite support this is just the paper’s theorem with repeated voters compressed. The proposed \(2-\varepsilon\) lower bound is even less informative as a continuous result: replication merely multiplies both objective values by the same factor. It establishes no limiting phenomenon and no new approximation question. If one insists on an atomless population, the CP-net type space for fixed attributes is finite, so achieving that requires changing the type model—say, to probabilistic or parameterized CP-nets—which is no longer the paper’s problem.
Theorem 6 likewise survives only as a weighted restatement of its finite counting argument. Equal-mass symmetric cohorts are perfectly admissible, but the conclusion is driven by the artificial uniform occurrence of voting configurations and disjoint parent sets, not by population continuity. Unequal masses would make a more interesting question, but then the \(4/3\) proof no longer supplies an anchor; one would be studying a new weighted binary-aggregation theorem.
Theorem 2 does not repair the case. Its exponential aggregate CPT is a representation-size obstruction caused by the parent structure and the number of attributes. It persists under a distribution over the same finitely many types, but that persistence says nothing specifically about a continuous society. A study of compact aggregate representations, decision diagrams, or parent-set width could be worthwhile, but its subject would be structured preference representation, not continuization.
There is also a modelling mismatch that the proponent understates. A complete CP-net is not a ranking of alternatives: it is generally a partial preference relation, and this paper deliberately aggregates only local swap orientations because global comparisons are difficult. One can treat CP-nets as voter types for a broader combinatorial-preference programme, but then the mirror is no longer a direct instance of the central ranking-population model. Converting CP-nets into complete rankings requires extra choices that change the objective.
So the negative case is that every faithful mirror is merely a weighted finite-profile reformulation, while every genuinely richer version requires a new distribution representation or a new preference model. I would not call that a proof that no worthwhile project exists. The high-multiplicity regime is plainly sensible here, and the proponent has identified valid Class-A questions. But I would reject the stronger claim that this paper offers a distinctive continuous-computational mirror: its results support weighted aggregation, not a substantive continuization programme.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.