Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting (d4-journals-ai-2019-0024)

Given a common binary-feature domain \(\Omega=\{0,1\}^n\), an explicit finite list \(T\) of acyclic polynomially connected CP-net types, and rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), decide whether there exists an outcome \(\alpha\in\Omega\) such that every \(\beta\in\Omega\setminus\{\alpha\}\) satisfies \(\sum_{t:\,\beta\succ_t\alpha}\mu_t\le\tfrac12\).

An outcome is an element of \(\Omega=\{0,1\}^m\), where \(m=n\ge1\) is the number of features; every outcome is feasible.
A society is given by its support: an explicit list \(T\) of \(\tau\) distinct CP-net types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type ranks every feature and has an acyclic dependency graph and explicit complete conditional preference tables giving a strict order on \(\{0,1\}\) for every assignment to its parents. No common topological order is required.
Polynomial connectivity is a uniform promise: a fixed polynomial \(p\) bounds the number of directed paths between any two distinct features by \(p(\lVert N_t\rVert)\), where \(\lVert N_t\rVert\) is the type's encoding length.
Write \(\beta\succ_t\alpha\) when a nonempty sequence of improving flips leads from \(\alpha\) to \(\beta\); each flip changes one feature to its locally preferred value under its current parent assignment.
An outcome \(\alpha\) is majority optimal if \(\sum_{t:\,\beta\succ_t\alpha}\mu_t\le\tfrac12\) for every \(\beta\ne\alpha\). Incomparable types contribute no supporting mass; exactly half does not constitute dominance.

Is deciding whether a majority-optimal outcome exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For explicit finite agent profiles, existence of a majority-optimal outcome is \(\Sigma_2^{\mathrm P}\)-complete; hardness holds with at most six agents and indegree at most three under the stated connectivity and acyclicity restrictions. [Lukasiewicz–Malizia](https://doi.org/10.1016/j.artint.2018.12.010)
No separate complexity result for the rational-mass formulation was verified.

Result

The problem is \(\mathrm{NP}\)-hard. In fact, with rational masses encoded by binary numerators and denominators, it is \(\Sigma_2^{\mathrm P}\)-complete under the stated uniform connectivity promise.

The hardness transfer preserves majority comparisons exactly; it does not require expanding rational masses into an agent population.

Hardness: aggregate identical agents

We use the stated finite-profile theorem: existence of a majority-optimal outcome is \(\Sigma_2^{\mathrm P}\)-hard for acyclic binary CP-nets that rank every feature, have indegree at most three, and belong to a polynomially connected class, even with at most six agents. The paper’s majority rule requires strictly more than half of all agents to support dominance, including incomparable agents in the population total. Thus its rule agrees with the question’s rule. See [Lukasiewicz–Malizia, Theorem 5.12](https://doi.org/10.1016/j.artint.2018.12.010).

Let \(\mathcal P=(N_1,\ldots,N_a)\) be such a finite profile, where \(1\le a\le6\). Group identical CP-net types. Write the resulting distinct types as \(T=\{N^{(1)},\ldots,N^{(\tau)}\}\), and let \(c_j\) be the number of agents of type \(N^{(j)}\). Assign mass \(\mu_j=c_j/a\).

These masses are positive rationals with binary encodings, and \(\sum_{j=1}^{\tau}\mu_j=1\). For every pair of distinct outcomes \(\alpha,\beta\), we have the exact identity

\(\displaystyle \sum_{j:\,\beta\succ_{N^{(j)}}\alpha}\mu_j =\frac{|\{i:\beta\succ_{N_i}\alpha\}|}{a}.\)

Consequently, the mass supporting \(\beta\) over \(\alpha\) exceeds \(\tfrac12\) if and only if strictly more than half of the original agents support that comparison. Incomparability and exact ties are preserved.

It follows, for each outcome \(\alpha\), that \(\alpha\) is majority optimal in the rational-mass society if and only if it is majority optimal in \(\mathcal P\). Existence is therefore preserved.

Grouping identical explicit CP-nets takes polynomial time by comparing their graph and table encodings. The output contains at most six types, and the masses have constant bit length. No CP-net is modified, so acyclicity, complete strict tables, indegree bounds, and the uniform path bound are preserved. The outcome domain also remains unchanged.

This is a polynomial-time many-one reduction. Hence the rational-mass problem is \(\Sigma_2^{\mathrm P}\)-hard, and therefore \(\mathrm{NP}\)-hard, already when \(\tau\le6\).

Upper bound: polynomial dominance certificates

We prove that individual dominance has polynomial-size certificates under the uniform connectivity promise.

Fix a type \(N\) and a finite improving-flip sequence. For each feature \(v\), let \(f_v\) count its flips. Between two consecutive flips of \(v\), some parent of \(v\) must change: with a fixed parent assignment, the strict binary preference permits at most one improving flip. The intervals between consecutive flips are disjoint, so

\(\displaystyle f_v\le1+\sum_{u\in\operatorname{Pa}(v)}f_u.\)

Because the dependency graph is acyclic, define recursively in a topological order

\(\displaystyle P_v=1+\sum_{u\in\operatorname{Pa}(v)}P_u.\)

Induction gives \(f_v\le P_v\). Moreover, \(P_v\) counts all directed paths ending at \(v\), including the empty path at \(v\): every nonempty path has a unique final edge from a parent.

There are \(m-1\) possible distinct starting features. The promise therefore gives

\(\displaystyle P_v\le1+(m-1)p(\lVert N\rVert).\)

Thus every finite improving-flip sequence has length at most

\(\displaystyle \sum_v f_v\le m+m(m-1)p(\lVert N\rVert),\)

which is polynomial in the input length because \(p\) is fixed. A certificate lists the flipped features. Its validity is checked by updating the outcome and consulting the explicit conditional preference tables.

Now fix an outcome \(\alpha\). A certificate that \(\alpha\) is not majority optimal consists of:

• An outcome \(\beta\ne\alpha\).
• A subset \(S\subseteq T\) with \(\sum_{t\in S}\mu_t>\tfrac12\).
• An improving-flip sequence from \(\alpha\) to \(\beta\) for every \(t\in S\).

The certificate has polynomial size. Its mass inequality can also be checked in polynomial time using exact rational arithmetic: the product of the supplied denominators has bit length at most their total input bit length, so a common-denominator calculation remains polynomial.

The certificate is sound because all types in \(S\) support dominance. It is complete because, whenever \(\alpha\) is defeated, we can choose all supporting types and provide their polynomial-length sequences.

Therefore testing majority optimality is in \(\mathrm{coNP}\). Guessing an outcome \(\alpha\) and checking its majority optimality with a \(\mathrm{coNP}\) oracle puts existence in \(\Sigma_2^{\mathrm P}\).

Together with the reduction, this proves \(\Sigma_2^{\mathrm P}\)-completeness. In particular, a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned question. The aggregation reduction proves \(\Sigma_2^{\mathrm P}\)-hardness, and the certificate argument proves membership under the stated uniform connectivity promise. I found no major or minor mathematical issues.

• The cited hardness theorem applies. Theorem 5.12 establishes hardness for majority-optimal existence with at most six agents, binary acyclic CP-nets, indegree at most three, and a polynomially connected class. The paper uses complete types ranking every feature and does not require a common topological order. Its connectivity definition uses one polynomial for the entire class, matching the uniform promise. Its majority rule counts incomparable agents in the population total, so dominance requires strictly more than half of all agents. These hypotheses and definitions match the task. [Lukasiewicz–Malizia, Sections 2 and 5.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

• Aggregation preserves every relevant comparison. For each type, its multiplicity divided by the total number of agents equals its assigned mass. The displayed identity is therefore exact for every pair of distinct outcomes. It preserves strict majority dominance, incomparability contributions, and equality at one half. Consequently, it preserves majority optimality outcome by outcome and preserves existence in both directions.

• The reduction satisfies the representation requirements. Each multiplicity is positive, the masses sum to one, and numerator–denominator encodings have constant length because there are at most six agents. Comparing explicit graphs and tables to group identical types is polynomial. Retaining the original CP-nets preserves their feature domains, tables, acyclicity, indegree bounds, and uniform connectivity bound. The output is a valid polynomial-size instance with distinct listed types.

• The flip-count inequality is correct. Immediately after an improving flip of a binary feature, that feature has its preferred value under the current parent assignment. Another improving flip requires an intervening parent change. The intervals between consecutive flips are disjoint, so each requires a separate parent-flip occurrence. This justifies

\[ f_v\le 1+\sum_{u\in\operatorname{Pa}(v)}f_u. \]
It also holds when the feature flips zero times. A parentless feature flips at most once.

• The recursive bound and path interpretation are correct. Acyclicity makes the recursion defining \(P_v\) well-defined. Topological induction gives \(f_v\le P_v\). Partitioning nonempty paths by their final edge gives exactly the stated recursion for paths ending at \(v\), with one additional empty path. Every nonempty path starts at a feature distinct from \(v\). Thus the uniform promise yields the claimed bound

\[ P_v\le 1+(m-1)p(\lVert N\rVert). \]
Summing over features gives the stated polynomial bound on every finite improving sequence. For \(m=1\), it correctly reduces to at most one flip.

• Individual dominance certificates are verifiable in polynomial time. A sequence of feature indices determines all intermediate outcomes from the starting outcome. The verifier can check each improving flip against the explicit table and check that the final outcome is the specified target. Distinct endpoints ensure an accepted sequence is nonempty. The fixed polynomial promise makes certificate length polynomial in the explicit input length.

• The defeat certificate is sound, complete, and polynomial-size. A subset of types with mass strictly above one half, each with a verified sequence to the same challenger, proves defeat. Conversely, whenever defeat occurs, the set of all supporting types supplies such a certificate. There are at most \(\tau\) sequences, each polynomially bounded. Exact rational addition and comparison remain polynomial: the product of selected denominators has bit length bounded by their total encoded length, and summing numerators adds only polynomially many bits.

• The complexity conclusions follow. Defeat is in \(\mathrm{NP}\), so majority optimality is in \(\mathrm{coNP}\). Existentially guessing an \(m\)-bit outcome and using a \(\mathrm{coNP}\) oracle places existence in \(\Sigma_2^{\mathrm P}\). Together with the many-one reduction, this establishes the claimed completeness for the promised problem. The final implication that a polynomial-time algorithm would give \(\mathrm P=\mathrm{NP}\) is valid.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩