Answer: \(\mathrm{NP}\)-hard, even for one fully ranked acyclic binary type of mass one and indegree at most three; fixed-parameter tractable with parameter \(k\). A conservative running-time bound is \(O((L+\tau m+\tau(k+1)^2 2^k)L^2)\) on a bit-cost RAM.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven two outcomes, testing if one dominates the another has the following complexity: • for Pareto, Majority, Max, and Lex: O(m2k); • for Rank: O(m2n+k). To determine if O1 ≻p O2, we must test whether O1 ≻ O2 or O1 ≈O2 for all m partial CP nets. Each of these tests takes at most O(2k) time. To determine if O1 ≻maj O2, we must also test whether O1 ≻O2 for all m partial CP nets.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a common set of binary features, a finite list of supported acyclic partial CP-net types with rational masses \(\mu_t\) summing to \(1\), and outcomes \(\alpha,\beta\), classify each type’s comparison of \(\alpha\) and \(\beta\). Let \(P,N,I\) be the total masses of types reporting \(\alpha\succ\beta\), \(\beta\succ\alpha\), and incomparability, respectively. Decide whether \(P>N+I\).
A society is given by its support: a list of \(\tau\geq1\) acyclic partial CP-net types, each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) binary features. Type \(t\) uses a subset \(V_t\); its ranked features have explicit conditional preference tables giving a strict total order for every parent assignment, while its unranked features have no preference table. Every feature is ranked by some supported type. Put \(k=\max_t|V_t|\), and let \(L\) be the total input bit length.
A flip changes one feature, holding all others fixed. A ranked-feature flip is worsening when its table prefers the old value. For an unranked-feature flip, compare the positions of each child's fixed value in that child's old and new conditional orders: the flip is worsening if every child moves to a strictly worse position, and indifferent if every child's position stays unchanged. A childless unranked flip is indifferent, never worsening; all other unranked flips are unavailable in the chains below.
For outcomes restricted to \(V_t\), define \(\alpha\succ_t\beta\) by a chain from \(\alpha\) to \(\beta\) of worsening or indifferent flips containing at least one worsening flip. Define \(\alpha\approx_t\beta\) by an all-indifferent chain, allowing the empty chain; they are incomparable when neither strict comparison nor indifference holds.
Given distinct complete outcomes \(\alpha,\beta\), let \(P,N,I\) be the masses of types reporting, respectively, \(\alpha\succ_t\beta\), \(\beta\succ_t\alpha\), and incomparability. Indifferent types abstain. The decision problem asks whether \(P>N+I\); equality gives a negative answer.
State running times in \(m,\tau,L,k\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
If it is \(\mathrm{NP}\)-hard, is it fixed-parameter tractable with parameter \(k\)?
For a finite society of \(a\) agents, majority dominance has a reported \(O(a2^k)\) algorithm ([Rossi–Venable–Walsh](https://cgi.cse.unsw.edu.au/~twalsh/rvwaaai2004.pdf)).
Discrete majority dominance is also \(\mathrm{NP}\)-hard even for one fully ranked acyclic binary CP-net of indegree at most three ([Lukasiewicz–Malizia](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)). No result specifically treating the rational-mass partial-CP-net problem was located.
The decision problem is \(\mathrm{NP}\)-hard, even with one fully ranked supported type of mass \(\mu_1=1\), whose dependency graph has indegree at most three. It is also fixed-parameter tractable with parameter \(k\).
A conservative running-time bound, accounting for binary arithmetic on a bit-cost RAM, is
\(T(m,\tau,L,k)=O\!\left(\bigl(L+\tau m+\tau(k+1)^2 2^k\bigr)L^2\right).\)
Consequently, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\). Both claims are proved below.
Fix a supported type, and write \(V\) for its feature set. List its ranked features as \(X_1,\ldots,X_r\), in the order induced by a topological ordering of its acyclic dependency graph.
For an outcome \(x\) on \(V\), let \(\rho_i(x)\in\{0,1\}\) denote the position of its value of \(X_i\) in the conditional order selected by \(x\): the preferred value has position zero, and the other value has position one. Define
\(\Phi(x)=\sum_{i=1}^{r}2^{r-i}\rho_i(x).\)
If there are no ranked features, set \(\Phi(x)=0\).
Lemma. Every worsening flip strictly increases \(\Phi\), and every indifferent flip preserves \(\Phi\).
Proof. First consider a worsening flip of ranked feature \(X_j\). Its parents remain fixed, so \(\rho_j\) changes from zero to one. The only other conditional positions that can change belong to children of \(X_j\), which occur later in the topological ordering. Thus all \(\rho_i\) with \(i<j\) remain unchanged. Even if every later coordinate decreases, the potential increases by at least
\(2^{r-j}-\sum_{i=j+1}^{r}2^{r-i}=1.\)
Next consider a flip of an unranked feature. Ranked values remain fixed, and their conditional positions can change only at children of the flipped feature. By the prescribed semantics, a worsening flip has at least one child and strictly worsens every child’s position. Thus at least one coordinate increases, and none decreases. An indifferent flip leaves every child’s position unchanged, including vacuously when there are no children. Therefore it preserves every coordinate of \(\Phi\). This proves the lemma. \(\square\)
It follows that \(x\succ_t y\) implies \(\Phi(x)<\Phi(y)\), whereas \(x\approx_t y\) implies \(\Phi(x)=\Phi(y)\). Hence neither opposite strict comparisons nor strict comparison and indifference can coexist.
Indifferent flips are reversible: equality of the old and new positions is symmetric. Therefore \(\approx_t\) is symmetric; reflexivity follows from the empty chain, and transitivity follows by concatenation.
Consequently, each type reports exactly one of forward strict preference, reverse strict preference, indifference, or incomparability. This also handles equal restricted outcomes: they are indifferent and cannot be strictly comparable.
We use the following established result: dominance testing for an explicitly represented, fully ranked acyclic binary CP-net is \(\mathrm{NP}\)-hard even when its indegree is at most three. This is [Lukasiewicz–Malizia, Theorem 3.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf).
Given such a dominance instance, consisting of a CP-net and distinct outcomes \(\alpha,\beta\), construct the society as follows:
This construction preserves the explicit tables and dependency graph and takes polynomial time. All required hypotheses hold: the mass is a positive binary rational, the support masses sum to one, the graph is acyclic, and every feature is ranked.
Because every feature is ranked, the allowed chains contain only ordinary worsening flips. Since the outcomes are distinct, they cannot be indifferent. Section 1 excludes opposite strict comparisons occurring simultaneously. Thus:
Therefore \(P>N+I\) holds exactly when the source dominance instance is affirmative. This is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness under the claimed restrictions.
Fix type \(t\), put \(n_t=|V_t|\leq k\), and let \(a_t=\alpha|_{V_t}\) and \(b_t=\beta|_{V_t}\).
Construct two graphs with vertex set \(\{0,1\}^{n_t}\):
Both graphs have \(2^{n_t}\) vertices and at most \(n_t2^{n_t}\) directed edges.
By definition, \(b_t\) is reachable from \(a_t\) in \(H_t\) exactly when \(a_t\approx_t b_t\).
Moreover,
\(a_t\succ_t b_t\quad\Longleftrightarrow\quad b_t\text{ is reachable from }a_t\text{ in }G_t\text{ but not in }H_t.\)
For the forward implication, a strict chain gives reachability in \(G_t\), and Section 1 excludes indifference. For the reverse implication, a path in \(G_t\) that contained no worsening edge would be a path in \(H_t\). Therefore any witnessing path must contain a worsening edge.
Two graph searches consequently determine the signed contribution
\(s_t=\begin{cases}0,&a_t\approx_t b_t,\\1,&a_t\succ_t b_t,\\-1,&\text{otherwise}.\end{cases}\)
In the last case the type reports either reverse preference or incomparability; both count against the queried majority. Hence
\(\sum_{t=1}^{\tau}s_t\mu_t=P-N-I.\)
The answer is affirmative exactly when this sum is strictly positive.
After parsing the explicit tables into arrays indexed by parent assignments, precompute every ranked feature’s conditional position at every local outcome. For type \(t\), there are at most \(n_t2^{n_t}\) such positions. Extracting a parent assignment takes at most \(O(n_t)\) elementary operations, giving \(O((n_t+1)^2 2^{n_t})\) operations.
Using these positions, a ranked flip is checked in constant time. An unranked flip is checked by comparing its children’s positions at the old and new outcomes. At each outcome, checking all unranked flips costs at most the number of dependency arcs, which is \(O(n_t^2)\). The childless case is classified as indifferent, exactly as required.
Thus graph construction and both searches take
\(O((n_t+1)^2 2^{n_t})\)
elementary RAM operations. Across the support, including input parsing and a straightforward projection of the complete outcomes for each type, the bound is
\(O\!\left(L+\tau m+\tau(k+1)^2 2^k\right).\)
Write the explicitly encoded mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive binary integers. Define
\(D=\prod_{t=1}^{\tau}q_t,\qquad B=\sum_{t=1}^{\tau}s_tp_t(D/q_t).\)
Each division is exact, and
\(B=D(P-N-I).\)
Because \(D>0\), testing \(B>0\) gives precisely the required answer, including a negative answer at equality.
The binary length of \(D\) is at most one plus the sum of the denominator lengths, hence \(O(L)\). Each summand has magnitude \(\mu_tD\), and every partial sum has magnitude at most
\(D\sum_{t=1}^{\tau}\mu_t=D.\)
Thus all these integers have \(O(L)\) bits. Schoolbook multiplication and division yield a conservative total arithmetic bound of \(O(\tau L^2)\) bit operations.
The graph algorithm uses addresses and counters of \(O(k+\log(L+2))\) bits. Since complete outcomes are explicitly given, \(k\leq m=O(L)\); charging \(O(L^2)\) bit operations per elementary graph operation gives the stated overall bound
\(O\!\left(\bigl(L+\tau m+\tau(k+1)^2 2^k\bigr)L^2\right).\)
This has the form \(f(k)\operatorname{poly}(L)\), proving fixed-parameter tractability. In particular, the algorithm processes the \(\tau\) supported types directly; it does not expand rational masses into individual agents.
The reported finite-society bound concerns explicit agents; see [Rossi–Venable–Walsh, Theorem 5](https://cgi.cse.unsw.edu.au/~twalsh/rvwaaai2004.pdf). The proof above establishes the parameterized result directly for the rational-mass representation, including its flip semantics and exact threshold arithmetic.
The requested classification is therefore settled: \(\mathrm{NP}\)-hard and fixed-parameter tractable in \(k\). This does not assert \(\mathrm{NP}\)-completeness, which would additionally require an upper bound placing the unrestricted problem in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output establishes the requested \(\mathrm{NP}\)-hardness and fixed-parameter tractability in \(k\). There is one minor cost-accounting overstatement; it does not invalidate the stated running-time bound. No additional mathematical argument is needed.
The potential is well-defined: acyclicity supplies a topological ordering, and binary strict conditional orders give positions \(\rho_i(x)\in\{0,1\}\).
For a worsening ranked-feature flip at \(X_j\):
The critical calculation is correct:
\[
2^{r-j}-\sum_{i=j+1}^{r}2^{r-i}=1.
\]
Thus even the largest possible decrease in later coordinates cannot cancel the increase at \(X_j\).
For an unranked worsening flip, the argument uses exactly the task’s semantics: there is at least one child, every child’s position strictly worsens, and other ranked positions remain unchanged. Hence the potential strictly increases. Indifferent flips preserve all positions, including the childless case.
Consequently, strict chains increase the potential and indifferent chains preserve it. This correctly excludes both opposite strict comparisons and coexistence of strict comparison with indifference.
Indifferent flips are reversible because equality of the two positions is symmetric. The claims of reflexivity and transitivity also follow from the permitted empty chain and concatenation. Equal restricted outcomes therefore abstain and cannot be strictly comparable.
Assessment: Correct, including the case of no ranked features.
The cited result is accurate. Lukasiewicz–Malizia’s Theorem 3.3 establishes dominance-testing hardness for acyclic binary CP-nets with indegree three, even under the additional restriction of single connectivity. Their standard CP-nets have ranked features and explicit conditional tables. These instances satisfy the restrictions needed here. [Source: Sections 2.2–2.3 and Theorem 3.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf).
The construction satisfies every society requirement:
Ordinary CP-net dominance agrees with the prover’s worsening-chain comparison: reversing an improving sequence gives the corresponding worsening sequence. There are no indifferent flips in the fully ranked restriction. Distinct outcomes therefore cannot be indifferent.
The two cases in the reduction are exhaustive. Forward dominance gives \(P=1\) and \(N=I=0\); its absence gives \(P=0\) and \(N+I=1\). Thus the strict threshold is equivalent to the source decision.
Assessment: Correct polynomial-time many-one reduction. Omitting the source’s stronger single-connectivity restriction causes no problem.
The graph definitions match the allowed flips. Each vertex has at most \(n_t\) outgoing flip edges, giving the stated vertex and edge bounds.
Reachability in \(H_t\) characterizes indifference, provided—as the proof’s definition requires—reachability includes a path of length zero.
The equivalence
\[
a_t\succ_t b_t
\quad\Longleftrightarrow\quad
b_t\text{ is reachable from }a_t\text{ in }G_t
\text{ but not in }H_t
\]
is justified in both directions. The forward direction uses the established incompatibility of strict comparison and indifference. The reverse direction correctly observes that a path containing no worsening edge would also belong to \(H_t\).
Two searches suffice to determine the contribution \(s_t\). No reverse search is needed because reverse preference and incomparability both contribute negatively. The identity
\[
\sum_t s_t\mu_t=P-N-I
\]
therefore follows exactly.
Assessment: Correct, including coincident restricted outcomes and empty local feature sets.
Precomputing conditional positions at every local outcome has the claimed conservative cost. Explicit tables permit indexing by parent assignments, whose extraction takes at most \(O(n_t)\) elementary operations.
The flip checks correctly distinguish ranked worsening flips, unranked worsening flips, indifferent flips, and unavailable flips.
Minor issue: The sentence “At each outcome, checking all unranked flips costs at most the number of dependency arcs” omits the work of visiting unranked features themselves. For example, one childless unranked feature requires a check despite there being zero arcs.
The stated bound already absorbs this overhead. The minimum clarification is to describe the cost as \(O(n_t+|E_t|)\) per outcome, where \(E_t\) is the dependency-arc set. This leaves the claimed \(O((n_t+1)^2 2^{n_t})\) bound unchanged.
The support-wide parsing, projection, graph construction, and search bound is otherwise valid.
The common denominator \(D\) is positive, every division \(D/q_t\) is exact, and
\[
B=D(P-N-I).
\]
Testing \(B>0\) therefore implements the required threshold, with equality correctly rejected.
The bit-length claims are sound. The denominator product has \(O(L)\) bits. Since the positive masses sum to one, every summand and every partial signed sum has magnitude at most \(D\). The integers used in the arithmetic consequently have \(O(L)\) bits, and the stated schoolbook arithmetic bound is conservative.
The address-length bound is also sufficient for the exponentially sized graphs. Explicit complete outcomes ensure \(k\leq m=O(L)\); the explicit support ensures \(\tau=O(L)\). Thus the final running time has the required form \(f(k)\operatorname{poly}(L)\).
Assessment: Correct exact arithmetic and fixed-parameter tractability conclusion.
The Rossi–Venable–Walsh citation is contextual; the algorithm proved here does not depend on importing its finite-agent bound. The final qualification that \(\mathrm{NP}\)-completeness has not been established is appropriate.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.