d4-conf-aaai-2016-0291 (d4-conf-aaai-2016-0291)

Given a common binary feature set \(F\) and a finite support of \(\tau\) permitted complete CP-net types \(N_i\), each acyclic and polynomially connected, with positive binary-rational masses \(\mu_i\) summing to \(1\), let \(p_\mu(y \succ x)=\sum_{i:\,y\succ_{N_i}x}\mu_i\). Does there exist an outcome \(x\in\{0,1\}^{|F|}\) such that \(p_\mu(y\succ x)\le 1/2\) for every distinct outcome \(y\)?

Let \(F\) be a common set of \(m\geq 1\) binary features, with outcomes \(\{0,1\}^{m}\). A type is a complete acyclic CP-net on \(F\), encoded by its dependency DAG and explicit conditional preference tables: every parent assignment specifies a strict order on both values of every feature. Different types may have different DAGs, with no common topological order required.
Polynomial connectedness is a uniform promise: for a fixed polynomial \(q\), every permitted net \(N\) has at most \(q(|N|)\) directed paths between any two distinct features, where \(|N|\) is its encoding length.
Write \(y\succ_N x\) precisely when a nonempty sequence of improving single-feature flips takes \(x\) to \(y\), each flip following the conditional preference table under the current parent values. Outcomes with no improving sequence in either direction are incomparable.
A society is given by its support: the list of the \(\tau\geq 1\) distinct types with positive mass, each mass \(\mu_i\) a binary rational, with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Define \(p_\mu(y\succ x)=\sum_{i:y\succ_{N_i}x}\mu_i\). A weak Condorcet winner is an outcome \(x\) satisfying \(p_\mu(y\succ x)\leq \tfrac12\) for every distinct outcome \(y\); incomparable mass counts toward the total mass, and equality does not constitute defeat.

Is deciding whether this society has a weak Condorcet winner solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite lists of equally weighted agents, weak Condorcet winner existence is \(\Sigma_2^{\mathrm P}\)-complete, with hardness already for six agents; the full treatment also establishes hardness with maximum indegree three. [Verified source](https://doi.org/10.1016/j.artint.2018.12.010)
No result for exactly the rational-mass support formulation was verified.

Result and interpretation

The problem is NP-hard. More precisely, under the uniform polynomial-connectedness promise, the rational-mass support formulation is \(\Sigma_2^{\mathrm P}\)-complete. Hardness holds even with \(\tau\leq 6\) and maximum indegree three.

Here “binary rational” means a rational number whose numerator and denominator are encoded in binary. Polynomial connectedness is understood as the stated uniform class promise; the hardness construction satisfies one fixed polynomial bound.

1. The known hardness theorem applies to these preferences

Lukasiewicz and Malizia’s Theorem 5.12 establishes \(\Sigma_2^{\mathrm P}\)-hardness of existence of a *majority optimal outcome*, already for six equally weighted agents whose CP-nets are complete, binary, acyclic, uniformly polynomially connected, and have maximum indegree three. Their construction is polynomial in the source formula’s size. [Published paper, Theorem 5.12 and Section 5.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

We must check that their winner condition matches the present question. In their definitions, individual dominance is reachability by improving flips, and majority dominance means that the number preferring \(y\) to \(x\) exceeds the combined number preferring \(x\) to \(y\) or finding them incomparable. Thus, for a profile of \(n\) agents, majority dominance means

\( |\{j:y\succ_{N_j}x\}|>n/2. \)

A majority optimal outcome has no incoming majority dominance. This is exactly the weak Condorcet condition in the question, including the treatment of incomparability and equality. [Published paper, Sections 2.1–2.2](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

2. Compressing agents into rational-mass support preserves every defeat

Lemma. An explicitly listed, equally weighted profile can be converted in polynomial time into a society of distinct types with rational masses, preserving its entire defeat relation.

Proof. Let the profile be \(N_1,\ldots,N_n\). Partition its indices according to identical CP-nets, comparing DAGs and conditional preference tables under the common feature labels.

Let \(T_1,\ldots,T_\tau\) be the distinct nets, and let

\( c_i=|\{j:N_j=T_i\}|,\qquad \mu_i=c_i/n. \)

Each mass is positive, their sum is one, and their binary rational encodings have length \(O(\log n)\). For every pair of distinct outcomes,

\( p_\mu(y\succ x) =\sum_{i:y\succ_{T_i}x}\frac{c_i}{n} =\frac{|\{j:y\succ_{N_j}x\}|}{n}. \)

Consequently,

\( p_\mu(y\succ x)>\tfrac12 \quad\Longleftrightarrow\quad |\{j:y\succ_{N_j}x\}|>n/2. \)

The defeat relations—and hence the sets of weak Condorcet winners—are identical.

The conversion changes no net, so it preserves completeness, binary domains, acyclicity, indegree bounds, and the uniform path-count bound. Canonicalizing the explicit tables and comparing nets takes polynomial time in the profile’s encoding length. This proves the lemma.

Apply this conversion to the six-agent hardness construction. Its output satisfies \(\tau\leq 6\), and every mass is \(c_i/6\). The feature count remains \(m\), and the resulting total length \(L\) is polynomial in the source formula’s length.

This gives a polynomial many-one reduction to the precise support formulation. Therefore, the problem is \(\Sigma_2^{\mathrm P}\)-hard and, in particular, NP-hard. A deterministic algorithm running in \(\operatorname{poly}(m,\tau,L)\) would imply \(\mathrm P=\mathrm{NP}\).

3. Polynomial bounds on improving sequences

For completeness, the weighted formulation also has a matching upper bound.

Lemma. In a binary acyclic CP-net \(N\) satisfying the path-count promise, every improving sequence has length at most

\( m\bigl(1+(m-1)q(|N|)\bigr). \)

Proof. Fix a finite improving sequence, and let \(f(v)\) count its flips of feature \(v\).

Between successive flips of parents of \(v\), the parent assignment is constant. The strict binary preference at \(v\) is therefore fixed, so \(v\) can improve at most once during that interval. Hence

\( f(v)\leq 1+\sum_{u\in\operatorname{Pa}(v)}f(u). \)

Define \(h(v)\), in topological order, by

\( h(v)=1+\sum_{u\in\operatorname{Pa}(v)}h(u). \)

Induction gives \(f(v)\leq h(v)\). The same recurrence shows that \(h(v)\) counts all directed paths ending at \(v\), including the trivial path at \(v\): every nontrivial path has a unique last edge.

Writing \(P_N(u,v)\) for the number of directed paths from \(u\) to \(v\), we obtain

\( h(v)=1+\sum_{u\neq v}P_N(u,v) \leq 1+(m-1)q(|N|). \)

Summing \(f(v)\leq h(v)\) over the \(m\) features proves the bound.

4. Membership in \(\Sigma_2^{\mathrm P}\)

Choose a fixed nondecreasing polynomial \(Q\) majorizing \(q\), and put

\( B=m\bigl(1+(m-1)Q(L)\bigr). \)

Since \(|N_i|\leq L\), every individual dominance has an improving-sequence witness of length at most \(B\).

For a given outcome \(x\), a certificate that it is defeated consists of:

• an outcome \(y\neq x\);
• a subset \(S\subseteq\{1,\ldots,\tau\}\);
• for each \(i\in S\), a nonempty improving sequence from \(x\) to \(y\) in \(N_i\).

The verifier checks every sequence against its explicit conditional preference tables and checks

\( \sum_{i\in S}\mu_i>\tfrac12. \)

Soundness. Verified sequences establish \(y\succ_{N_i}x\) for all \(i\in S\). Positivity of the masses then gives \(p_\mu(y\succ x)>\tfrac12\).

Completeness. If \(y\) defeats \(x\), take \(S\) to be all types for which \(y\succ_{N_i}x\), and supply their bounded improving sequences.

The certificate contains at most \(\tau B\) flips. A straightforward verifier, scanning explicit tables as needed, runs in

\( O\bigl(\tau B(m+L)+\tau L^2\bigr). \)

For the arithmetic bound, write \(\mu_i=a_i/b_i\) and use the common denominator \(D=\prod_i b_i\). Its bit length is at most \(O(L)\). Exact addition and comparison can therefore be performed within the stated polynomial bound using elementary integer arithmetic.

Thus, being defeated is in \(\mathrm{NP}\), and being a weak Condorcet winner is in \(\mathrm{coNP}\). Guessing an \(m\)-bit outcome and checking this condition with an \(\mathrm{NP}\) oracle places existence in \(\Sigma_2^{\mathrm P}\).

Together with the reduction above, this proves \(\Sigma_2^{\mathrm P}\)-completeness for the rational-mass support problem.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned question. Its reduction establishes NP-hardness for the rational-mass support formulation, and its upper-bound argument establishes \(\Sigma_2^{\mathrm P}\)-completeness under the uniform polynomial-connectedness promise. I found no mathematical gaps requiring repair.

1. The cited hardness theorem applies

Theorem 5.12 does establish \(\Sigma_2^{\mathrm P}\)-hardness of majority-optimal outcome existence for polynomially connected classes of acyclic binary CP-net profiles, with maximum indegree three and at most six agents. Section 5.3 supplies a six-agent construction computable in polynomial time. [Published paper, Theorem 5.12 and Section 5.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

The encoding and structural hypotheses match the task: the paper uses total, strict conditional preference tables represented explicitly; all agents rank the same features; and a common topological order is not required. Its definition of polynomial connectedness supplies a single polynomial bound for a class, measured against each constituent net’s encoding size. Thus the citation supports the uniform promise, rather than merely an instance-dependent assertion. [Published paper, Sections 2.2–2.3](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

2. The winner definitions coincide

The paper’s individual dominance is improving-flip reachability. Its majority comparison includes incomparable agents on the opposing side, and majority optimality means absence of an incoming majority defeat. [Published paper, Sections 2.1–2.2](https://kclpure.kcl.ac.uk/portal/files/147926248/1_s2.0_S0004370218303266_main_1_.pdf)

For distinct outcomes, individual acyclicity ensures that the forward-preference, reverse-preference, and incomparability sets partition the agents. Consequently, the paper’s comparison is equivalent to strictly more than half of all agents preferring the challenger.

The prover therefore transfers the correct winner notion. Incomparable mass remains in the denominator, and equality at one half is correctly treated as nondefeat.

3. Compression into distinct support types is valid

Every step of the compression lemma checks out:

• Equality of encoded CP-nets can be checked in polynomial time by comparing feature labels, DAGs, and canonically ordered explicit tables.
• Each multiplicity \(c_i\) is positive, and the multiplicities sum to \(n\).
• The masses \(c_i/n\) have binary numerator-and-denominator encodings of length \(O(\log n)\).
• Grouping identical nets preserves the displayed weighted dominance probability for every pair of outcomes.

Thus the conversion preserves the entire defeat relation, including its strict threshold, and consequently preserves winner existence in both directions.

The conversion leaves each retained net unchanged, so all structural restrictions and the path-count promise survive. Applied to the six-agent construction, it produces \(\tau\leq 6\), masses \(c_i/6\), and polynomial total encoding length. This is a valid polynomial many-one reduction.

No expansion of arbitrary rational masses into an explicitly listed electorate is needed; the reduction proceeds in the other direction.

4. The improving-sequence bound is correct

The flip-count inequality
\(f(v)\leq 1+\sum_{u\in\operatorname{Pa}(v)}f(u)\)
is justified. Parent flips divide the sequence into at most one more interval than their total number. Within each interval, the parent assignment and strict binary preference are fixed, allowing at most one improving flip of \(v\).

Acyclicity permits the stated topological induction. The recurrence for \(h(v)\) counts directed paths ending at \(v\), including its trivial path: every nontrivial path has a unique last edge. Hence the displayed path-count expression and the bound
\(m(1+(m-1)q(|N|))\)
are correct.

The base case of a root feature gives \(h(v)=1\). For \(m=1\), the total bound is also \(1\). No omitted edge case breaks the argument.

5. The defeat certificate is sound and complete

A fixed nondecreasing polynomial majorant \(Q\) makes the witness bound \(B\) polynomial in \(m,L\), uniformly across the support.

The certificate specifies a distinct challenger, a subset of support indices, and nonempty improving sequences with the required endpoints. Checking the sequences establishes dominance for every selected type. Positive masses then make the threshold check sound.

Conversely, any genuine defeat has a certificate consisting of all supporting types and their bounded sequences. This proves completeness without requiring certificates of nondominance or incomparability.

The subset must have its ordinary meaning of distinct indices; repeated indices cannot contribute mass repeatedly. The prover’s notation already specifies a subset, so this is satisfied.

6. Arithmetic, running time, and complexity classification

The proposed verification time
\(O(\tau B(m+L)+\tau L^2)\)
is a valid conservative polynomial bound. Explicit table scanning suffices for flip verification.

The product of denominators has bit length \(O(L)\), because their individual encoding lengths are included in the total input length. Exact scaled sums and threshold comparisons therefore fit the stated elementary-arithmetic bound.

The resulting complexity implications are valid: defeat is in NP, winner verification is in coNP, and existentially guessing an outcome with an NP-oracle check places existence in \(\Sigma_2^{\mathrm P}\). Combined with the reduction, this proves the claimed completeness.

The statement that a deterministic polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\) is appropriately conditional. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩