Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting

This paper admits a strong continuous mirror. The cleanest move is to continuize the population of CP-net agents while leaving the combinatorial outcome space and CP-net semantics untouched.

Fix binary features \(F_1,\ldots,F_n\), with outcome space \(\Omega=\{0,1\}^n\). A voter type \(t\) is a complete CP-net description: its dependency graph, all CP-tables, and hence its induced dominance relation \(\succ_t\) over \(\Omega\). A continuous society is a finite-support distribution \(\mu\) over such types, with rational masses \(\mu_t\ge 0\) summing to \(1\). The mass is the fraction of the population using that CP-net policy; it is not uncertainty over outcomes.

For distinct outcomes \(\alpha,\beta\), define

\[ p_\mu(\beta,\alpha) = \sum_{t:\,\beta\succ_t\alpha}\mu_t. \]

Because a CP-net either entails \(\beta\succ_t\alpha\), entails \(\alpha\succ_t\beta\), or leaves the outcomes incomparable, the paper’s majority condition has the direct weighted form

\[ \beta\succ^\mu_{\mathrm{maj}}\alpha \quad\Longleftrightarrow\quad p_\mu(\beta,\alpha)>\frac12. \]

The continuous Pareto condition is

\[ \beta\succ^\mu_{\mathrm{Par}}\alpha \quad\Longleftrightarrow\quad \beta\succ_t\alpha \text{ for every }t\in\operatorname{supp}(\mu). \]

The decision variable is still an integral outcome \(\alpha\in\Omega\), not a fractional outcome or a probabilistic lottery. The objective is to identify an outcome that is majority optimal, majority optimum, or Pareto optimal under the mass-weighted global vote.

This has a convincing high-multiplicity regime. Imagine a large population of product-configuration users, robot policies, or software agents whose preferences are generated from a small number of standardized CP-net templates. There may be \(N=6q\) agents but only \(\tau\le 6\) CP-net types, each type representing a large cohort with identical conditional preferences. The paper’s agents need not share a common topological order, so this remains global voting over possibly non-\(\mathcal O\)-legal profiles.

The finite-to-continuous dictionary is exact. Given a finite profile \((N_1,\ldots,N_k)\), assign mass \(1/k\) to each agent type, merging equal CP-nets if necessary. Replicating every agent \(q\) times gives a population of \(kq\) agents with exactly the same \(\mu\). For every pair of outcomes, the discrete majority comparison is identical to the weighted comparison, and Pareto comparisons are identical on the support. Thus these are genuine high-multiplicity versions, not merely analogies.

My lead anchor is Corollary 5.13, proved in this paper. It states that, for every polynomially connected class of acyclic \(m\)CP-nets, deciding whether an \(m\)CP-net has a majority optimal outcome is \(\Sigma_2^P\)-complete. The lower bound comes from Theorem 5.12, which proves \(\Sigma_2^P\)-hardness even for binary acyclic polynomially connected \(m\)CP-nets of indegree at most \(3\) and with at most six agents; the upper bound comes from Theorem 5.10.

The corresponding continuous problem is:

Continuous Majority-Optimality Existence. An instance consists of a common set of binary features, a finite list of acyclic polynomially connected CP-net types \(T\), and rational masses \(\mu\) over \(T\). Does there exist an outcome \(\alpha\in\Omega\) such that, for every \(\beta\neq\alpha\),

\[ \sum_{t:\,\beta\succ_t\alpha}\mu_t\le\frac12? \]

A solution is such an outcome \(\alpha\), if one exists.

I expect this problem to be \(\Sigma_2^P\)-complete for finite rational support. The lower bound transfers immediately from Theorem 5.12 using at most six types with mass \(1/6\), and those six types can each be replicated arbitrarily many times. Membership has the same structure as in the paper: guess \(\alpha\), and use a co-\(\mathrm{NP}\) test to verify that no \(\beta\) obtains a strict weighted majority. The hardness is Class B: the combinatorics live in the CP-net feature structure and the quantified choice of outcomes, not in population multiplicity.

The second anchor is Corollary 5.17, also proved here. It states that deciding whether a given outcome is majority optimum is \(\Pi_2^P\)-complete for polynomially connected classes of acyclic \(m\)CP-nets. Theorem 5.16 gives the \(\Pi_2^P\) upper bound and proves hardness even for binary acyclic nets of indegree at most \(3\) with at most three agents; Theorem 5.14 supplies the generic upper-bound argument.

The continuous problem is:

Continuous Majority-Optimum Testing. Given the same weighted CP-net population and a candidate outcome \(\alpha\), decide whether, for every \(\beta\neq\alpha\),

\[ \sum_{t:\,\alpha\succ_t\beta}\mu_t>\frac12. \]

Thus \(\alpha\) must globally majority dominate every other outcome, with incomparable types counted against it exactly as in the paper. This is the continuous strong-Condorcet question for a CP-net population. I expect \(\Pi_2^P\)-completeness, already with three types of mass \(1/3\). Again, the paper’s reduction survives by replicating each of its three agents. This is a particularly strong mirror because the continuum does not weaken the problem: even a society with three preference archetypes can retain the full second level of the polynomial hierarchy.

A third, worthwhile anchor is Corollary 4.7. It states that deciding whether an outcome is Pareto optimal is \(\mathrm{coNP}\)-complete for polynomially connected classes of acyclic \(m\)CP-nets. Theorem 4.4 proves membership in co-\(\mathrm{NP}\), while Theorem 4.6 proves hardness even for binary acyclic nets of indegree at most \(3\) with at most two agents.

Its continuous counterpart is:

Continuous Pareto-Optimality Testing. Given \(T\), rational \(\mu\), and \(\alpha\in\Omega\), decide whether there is no \(\beta\neq\alpha\) satisfying

\[ \sum_{t:\,\beta\succ_t\alpha}\mu_t=1. \]

Equivalently, no outcome is preferred to \(\alpha\) by every positive-mass type. I expect co-\(\mathrm{NP}\)-completeness, already with two types of mass \(1/2\). This mirrors the paper’s Pareto problem without introducing fractional outcomes or changing CP-net dominance.

The original authors should recognise all three questions immediately. Their paper studies global voting over a finite profile of CP-nets; the mirror replaces cardinality of a set of agents by its population mass. It preserves the feature domain, improving-flip semantics, incomparability, acyclicity, bounded indegree, and the distinction between Pareto and majority voting. It is therefore not a new problem obtained by making the outcome space continuous. It is the high-multiplicity version of exactly their population-level aggregation problems.

The mirror does not cover every result in the paper, and it should not try to. It covers the central majority-optimal existence problem, the stronger majority-optimum certification problem, and the Pareto-optimality problem. The paper’s Corollary 5.21 also naturally generates a fourth question: continuous existence of a majority optimum. Its finite analogue is \(\Pi_2^P\)-hard and belongs to \(\mathrm{DP}_2\), so the continuous version should inherit the lower bound and likely the same upper-bound shape, although the exact classification remains open.

The weakest point is empirical rather than mathematical: exact equality of CP-net types may be a strong assumption for heterogeneous human voters. The mirror is most persuasive for standardized software agents, repeated stakeholder classes, or large cohorts using common preference templates. Also, these anchors are Class B rather than evidence that continuization makes the problem easier; the paper’s hardness already holds with only two, three, or six agent types. But that is not a defect in the mirror. It is precisely the useful conclusion: for these global CP-net aggregation tasks, population multiplicity is not where the hardness lives, and the continuous high-multiplicity problem remains the authors’ problem in a mathematically exact sense.