Answer: \(\Sigma_3^P\)-complete, hence \(\mathrm{NP}\)-hard, even with indegree at most three, \(\tau\leq 8\), and positive masses that are multiples of \(1/8\).
Theorem 6.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet M be an mCP-net. Deciding whether there is a max optimal outcome in M is ΣP 3-hard. Hardness holds even on polynomially connected classes of acyclic and binary mCP-nets whose indegree is three, and the number of agents is bounded to 8. Exists-Max-Optimal is also in ΣP 3 [38], hence it is ΣP 3-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite binary feature set \(F\), a support of \(\tau\) distinct acyclic binary CP-net types \(N_t\) over \(F\), and positive rational masses \(\mu_t\) summing to one, decide whether some outcome \(\alpha \in \{0,1\}^F\) is not max-dominated by any other outcome. For outcomes \(\beta,\alpha\), define \(P^+_\mu(\beta,\alpha)\), \(P^-_\mu(\beta,\alpha)\), and \(P^?_\mu(\beta,\alpha)\) as the masses of types that respectively prefer \(\beta\), prefer \(\alpha\), or find them incomparable; max-dominance holds when \(P^+_\mu(\beta,\alpha) > \max(P^-_\mu(\beta,\alpha),P^?_\mu(\beta,\alpha))\). Use the paper's polynomial-connectivity restriction, with indegree at most three for the hardness subcase.
Let \(F\) be a finite feature set with \(m=|F|\). All outcomes in \(\{0,1\}^{F}\) are feasible. A society is given by its support: \(\tau\) distinct acyclic binary CP-nets \(N_t\), 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.
Each CP-net has explicitly listed conditional preference tables specifying a strict order on \(\{0,1\}\) for every parent assignment; no common topological order is required. Write \(\beta\succ_t\alpha\) when a nonempty sequence of improving flips leads from \(\alpha\) to \(\beta\). Distinct outcomes are incomparable when neither dominates the other.
The nets belong to a polynomially connected class: one fixed polynomial \(p\), independent of the instance, bounds the number of directed paths between any two features of every \(N_t\) by \(p(\|N_t\|)\), where \(\|N_t\|\) is its encoding length. Include the subcase in which every net has indegree at most three.
For distinct \(\beta,\alpha\), define \(P^+_\mu(\beta,\alpha)=\sum_{t:\beta\succ_t\alpha}\mu_t\), \(P^-_\mu(\beta,\alpha)=\sum_{t:\alpha\succ_t\beta}\mu_t\), and \(P^?_\mu(\beta,\alpha)=\sum_{t:\beta\not\succ_t\alpha,\,\alpha\not\succ_t\beta}\mu_t\). Outcome \(\beta\) max-dominates \(\alpha\) iff \(P^+_\mu(\beta,\alpha)>\max\{P^-_\mu(\beta,\alpha),P^?_\mu(\beta,\alpha)\}\); ties give no dominance. A max-optimal outcome has no distinct max-dominator.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether this society has a max-optimal outcome in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, including under the indegree-at-most-three restriction?
For finite lists of equally weighted agents, existence of a max-optimal outcome is \(\Sigma^P_3\)-complete; hardness holds on polynomially connected acyclic binary nets with indegree at most three and at most eight agents. [Verified discrete result](https://ifaamas.org/Proceedings/aamas2018/pdfs/p1540.pdf)
The later full treatment confirms this discrete classification. No result explicitly treating this rational-mass support formulation was located. [Full treatment](https://cris.unibo.it/retrieve/5b7f4550-209d-4418-8357-05127a8b0322/aij2202-ComplexityMCP-NetsMaxRank.pdf)
The problem is \(\Sigma_3^P\)-complete, hence \(\mathrm{NP}\)-hard, even when every net has indegree at most three, the support size satisfies \(\tau\leq 8\), and every mass is a positive multiple of \(1/8\). Thus a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The hardness proof transfers the given discrete theorem to distinct rational-mass support. The upper bound handles the masses directly, without expanding them into agent copies.
The published reduction establishes \(\Sigma_3^P\)-hardness of max-optimal-outcome existence for lists of exactly eight equally weighted agents. Its nets are acyclic and binary, have explicitly represented preference tables and indegree at most three, and belong to a fixed polynomially connected family. These are precisely the structural hypotheses needed here. See [Lemma 6.5 and Theorem 6.6 of the full treatment](https://cris.unibo.it/retrieve/5b7f4550-209d-4418-8357-05127a8b0322/aij2202-ComplexityMCP-NetsMaxRank.pdf).
We use this established theorem; the transfer to rational-mass support is proved next.
Let \(M=(N_1,\ldots,N_8)\) be an instance produced by that reduction. Group identical CP-nets together. Denote the distinct nets by \(T_1,\ldots,T_\tau\), and let \(k_t\) be the number of occurrences of \(T_t\). Set
\(\displaystyle \mu_t=\frac{k_t}{8}.\)
Then \(\tau\leq 8\), every mass is positive, and \(\sum_t\mu_t=1\). These masses are dyadic rationals, so the construction also satisfies the interpretation of “binary-rational” as requiring finite binary expansions.
Fix distinct outcomes \(\beta,\alpha\). Define the discrete vote counts
\(\displaystyle c^+(\beta,\alpha)=|\{i:\beta\succ_{N_i}\alpha\}|,\qquad c^-(\beta,\alpha)=|\{i:\alpha\succ_{N_i}\beta\}|,\)
and let \(c^?(\beta,\alpha)\) count agents for whom the outcomes are incomparable.
All occurrences of the same net give the same comparison. Consequently,
\(\displaystyle P_\mu^+(\beta,\alpha)=\frac{c^+(\beta,\alpha)}8,\qquad P_\mu^-(\beta,\alpha)=\frac{c^-(\beta,\alpha)}8,\qquad P_\mu^?(\beta,\alpha)=\frac{c^?(\beta,\alpha)}8.\)
Multiplication by the positive number \(8\) therefore gives
\(\displaystyle P_\mu^+>\max\{P_\mu^-,P_\mu^?\}\quad\Longleftrightarrow\quad c^+>\max\{c^-,c^?\}.\)
This equivalence preserves strict inequalities and ties. Hence the discrete instance and the constructed society have exactly the same max-dominance relation, and therefore exactly the same max-optimal outcomes.
The transformation is polynomial-time: canonicalize the explicitly listed representations, compare the eight nets, and record their multiplicities. Equality here is equality of the CP-net objects—their graphs and tables—not equivalence testing of their induced dominance relations.
No graph or preference table is changed. Thus acyclicity, binary domains, indegree at most three, and the fixed polynomial connectivity bound are preserved. This proves \(\Sigma_3^P\)-hardness for the rational-mass formulation.
We prove the certificate bound needed for membership.
Fix a net \(N\) and any finite improving-flip sequence. For each feature \(v\), let \(f_v\) count its flips in that sequence.
Between two consecutive flips of \(v\), at least one parent of \(v\) must flip. Indeed, with its parent assignment fixed, a binary feature has one strictly preferred value. After improving to that value, it cannot improve again until its parent assignment changes. Therefore
\(\displaystyle f_v\leq 1+\sum_{u\in\operatorname{Pa}(v)}f_u.\)
Because the dependency graph is acyclic, define recursively, in topological order,
\(\displaystyle h_v=1+\sum_{u\in\operatorname{Pa}(v)}h_u.\)
Induction gives \(f_v\leq h_v\). Moreover, \(h_v\) counts all directed paths ending at \(v\), including the length-zero path at \(v\): every nonempty such path has a unique final edge.
The connectivity hypothesis consequently implies
\(\displaystyle h_v\leq 1+(m-1)p(\|N\|).\)
Thus every improving sequence has length at most
\(\displaystyle \sum_v f_v\leq m+m(m-1)p(\|N\|).\)
Choose a fixed nondecreasing polynomial \(q\) dominating \(p\). Since \(\|N\|\leq L\), a uniform certificate-length bound is
\(\displaystyle B=m+m(m-1)q(L).\)
A certificate specifies the flipped features. Starting from the claimed initial outcome, each flip can be checked against the explicit preference table, and the final outcome can be checked against the claimed target. Verification takes \(O((B+1)(L+m))\) time by straightforward table scanning. Therefore individual dominance belongs to \(\mathrm{NP}\) on the promised class.
The same bound also rules out cycles in the improving-outcome graph: repeating a cycle would produce finite improving sequences of arbitrarily large length. Thus, for distinct outcomes, the two dominance directions cannot both hold.
For fixed distinct outcomes \(\beta,\alpha\), ask an \(\mathrm{NP}\) oracle the two dominance questions for each support net. This uses \(2\tau\) nonadaptive oracle calls. Their answers determine all three comparison categories exactly.
The mass calculations require only polynomial time. To see this explicitly, write \(\mu_t=a_t/b_t\), and set
\(\displaystyle D=\prod_{t=1}^{\tau}b_t,\qquad w_t=a_t(D/b_t).\)
The total encoded length of the numerators and denominators is at most \(L\), so these integers have \(O(L)\) bits. Comparing the three masses is equivalent to comparing the corresponding sums of integer weights \(w_t\). Computing the weights and comparisons takes \(O(\tau L^2)\) time using elementary integer arithmetic.
Hence pairwise max-dominance is in \(\mathrm{P}^{\mathrm{NP}}\), with \(2\tau\) oracle calls and polynomial additional time in \(m,\tau,L\).
An outcome \(\alpha\) fails to be max-optimal exactly when some distinct outcome \(\beta\) max-dominates it. Guessing \(\beta\) and performing the preceding oracle computation puts non-optimality in \(\Sigma_2^P\). Consequently, checking max-optimality belongs to \(\Pi_2^P\).
Finally, guess an outcome \(\alpha\), represented by \(m\) bits, and check its max-optimality with a \(\Pi_2^P\) oracle. This proves that existence belongs to \(\Sigma_3^P\). Together with Section 2, it establishes the claimed completeness.
A direct exhaustive algorithm also gives a running time explicitly in \(m,\tau,L\).
For each support net, construct its improving-outcome graph, which has \(2^m\) vertices and at most \(m2^m\) edges. Run graph reachability from every outcome to obtain all individual dominance comparisons. Then inspect every ordered pair of distinct outcomes, calculate its weighted max-dominance status, and mark its dominated outcome. A max-optimal outcome exists exactly when some outcome remains unmarked.
With elementary arithmetic and straightforward graph representations, a conservative bound is
\(\displaystyle O\!\left(\tau(m+1)^2\,4^m\,L^2\right).\)
For \(m=0\), there is just one outcome, which is automatically max-optimal. This degenerate case does not affect the hardness result.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The claimed \(\Sigma_3^P\)-completeness, including the restriction to indegree at most three, is supported by the cited theorem and the argument written. I found no major or minor issues requiring repair.
Lemma 6.5 explicitly supplies a polynomial-time reduction producing exactly eight agents, binary acyclic nets, indegree three, and a polynomially connected family. Theorem 6.6 establishes \(\Sigma_3^P\)-completeness of max-optimal-outcome existence. Thus using denominator eight is justified; the prover has not silently strengthened an “at most eight” statement. [Full treatment, Lemma 6.5 and Theorem 6.6](https://cris.unibo.it/retrieve/5b7f4550-209d-4418-8357-05127a8b0322/aij2202-ComplexityMCP-NetsMaxRank.pdf)
The source also specifies explicit preference tables, permits different topological orders across agents, and defines max dominance using the same strict comparison against the reverse-preference and incomparability counts. Its definition of optimality matches the task’s absence of a distinct dominator. [Full treatment, Sections 2.1–2.2](https://cris.unibo.it/retrieve/5b7f4550-209d-4418-8357-05127a8b0322/aij2202-ComplexityMCP-NetsMaxRank.pdf)
Every multiplicity satisfies \(k_t\geq 1\), and \(\sum_t k_t=8\). Therefore the constructed masses are positive, sum to one, and have finite binary expansions.
For each ordered pair of distinct outcomes, identical nets contribute identical comparison categories. Consequently, each weighted category equals its discrete count divided by eight. Scaling all three categories by the same positive factor preserves strict inequalities and ties.
This establishes equivalence for every ordered pair, hence preserves exactly which outcomes have a max-dominator. Both yes-instances and no-instances are preserved.
Comparing explicitly represented graphs and tables requires no dominance-equivalence test. Canonicalization and grouping are polynomial-time, and retaining unchanged nets preserves all structural restrictions. The hardness transfer is valid.
The inequality \(f_v\leq 1+\sum_{u\in\operatorname{Pa}(v)}f_u\) follows from binary strict preferences: between consecutive improving flips of the same feature, its parent assignment must change. The intervals between consecutive flips are disjoint, so parent flips are not counted repeatedly for that feature.
Acyclicity makes the recursive definition of \(h_v\) well-defined. Topological induction establishes \(f_v\leq h_v\).
The interpretation of \(h_v\) as the number of directed paths ending at \(v\), including its trivial path, is correct. Each nonempty path has a unique final edge. There are at most \(m-1\) other possible starting features, giving the stated bound \(h_v\leq 1+(m-1)p(\|N\|)\).
Summing over features yields the claimed sequence-length bound. Replacing \(p\) by a fixed nondecreasing polynomial majorant \(q\) legitimately gives a bound uniform in the total input length \(L\).
A list of flipped features determines the successive outcomes because each feature is binary. Each improving flip and the final endpoint can be checked from the explicit tables.
The bound \(B\) counts flips; encoding their feature indices uses \(O(B\log(m+1))\) bits for \(m\geq 1\), which remains polynomial. The stated verification time accommodates reading those indices and scanning tables.
Repeating any improving cycle would contradict the bound on every finite improving sequence. Thus the improving-outcome graph has no directed cycles, and distinct outcomes cannot dominate each other in both directions. This justifies treating the three comparison categories as exhaustive and disjoint.
The product \(D=\prod_t b_t\) has bit length bounded by the sum of the denominator bit lengths, hence \(O(L)\). Each \(w_t=a_t(D/b_t)\) also has \(O(L)\) bits.
The category sums are exact integer representations of the corresponding masses with common denominator \(D\). No rounding occurs, so strict comparisons and ties are handled correctly.
Sequential multiplication, exact division, multiplication by numerators, and summation fit the conservative bound \(O(\tau L^2)\) using elementary arithmetic. This argument handles binary-encoded rational masses without expanding them into agent copies.
For fixed distinct outcomes, the \(2\tau\) individual dominance queries are polynomially many and nonadaptive. Their answers and the exact mass arithmetic decide max dominance in \(\mathrm{P}^{\mathrm{NP}}\).
Guessing a distinct max-dominator and performing that computation places non-optimality in \(\mathrm{NP}^{\mathrm{NP}}=\Sigma_2^P\). Complementation therefore places optimality in \(\Pi_2^P\).
Finally, guessing the \(m\)-bit candidate outcome and querying optimality places existence in \(\mathrm{NP}^{\Pi_2^P}=\Sigma_3^P\). The quantifiers and oracle levels are correct.
Combining membership with the reduction proves the claimed completeness. The restricted hardness instances satisfy both \(\tau\leq 8\) and the specified mass restriction.
Each improving-outcome graph has \(2^m\) vertices and at most \(m2^m\) edges. Reachability from every vertex determines all individual dominance comparisons.
Inspecting every ordered pair and marking its dominated outcome implements precisely the definition of max optimality. The stated bound \(O(\tau(m+1)^2 4^m L^2)\) conservatively accommodates graph construction, reachability, representation costs, and exact weighted comparisons.
When \(m=0\), the unique outcome has no distinct competitor and is max-optimal, as stated.
No additional lemma, clarification, or repair is needed. The output establishes hardness for the rational-mass formulation and answers the requested complexity question.
⟨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.