d4-conf-ijcai-2009-0246 (d4-conf-ijcai-2009-0246)

Given attributes \(V\) with finite domains, a supported distribution \(\mu\) over one-shot comparison reports \(e=(x,y)\), and a rational quota \(q\), determine whether there is a separable CP-net \(N\) such that at least \(q\) mass is individually compatible with it: \(\sum_{e=(x,y):\,\exists\text{ a completion }\succ\supseteq\succ_N\text{ with }x\succ y}\mu_e\ge q\).

Let \(V=\{X_1,\ldots,X_m\}\), with explicitly listed nonempty finite domains \(D_i\), and let \(D=\prod_i D_i\) and \(s=\sum_i|D_i|\).
A society is given by its support: the list of the \(\tau\) report types \(e=(x,y)\), where \(x,y\in D\) and \(x\ne y\), each with positive binary rational mass \(\mu_e\); require \(\sum_e\mu_e=1\). Here \(\tau\) is the support size, not the number of possible reports.
A separable CP-net \(N\) chooses a strict linear order \(\succ_i\) on each \(D_i\). Its induced relation \(\succ_N\) is the transitive closure of the comparisons \(x\succ_N y\) between outcomes differing only on attribute \(i\), with \(x_i\succ_i y_i\).
A completion is a strict linear order on \(D\) extending \(\succ_N\). A report \((x,y)\) is individually compatible with \(N\) if some completion ranks \(x\) above \(y\); different reports may use different completions.
Given a binary rational quota \(q\in[0,1]\), decide whether some \(N\) satisfies \(\sum_{e=(x,y):\,e\text{ individually compatible with }N}\mu_e\ge q\). Let \(L\) be the total input bit length.

Is this decision problem solvable in polynomial time in \(m,\tau,s,L\), or is it NP-hard?

For finite sets of reports, deciding whether a separable CP-net is individually compatible with every report is NP-complete even for binary attributes. The same classification holds for arbitrary explicitly listed finite domains.

Result

The decision problem is NP-complete, already for binary attributes. More precisely, every fixed rational quota \(q\in(\tfrac12,1]\) gives an NP-complete problem, whereas every valid instance with \(q\le\tfrac12\) is a YES-instance.

The hardness proof uses the NP-completeness premise supplied in the question.

1. Characterizing individual compatibility

For each coordinate, write \(a\succeq_i b\) when either \(a=b\) or \(a\succ_i b\).

Lemma. For distinct outcomes \(x,y\),
\[ y\succ_N x \quad\Longleftrightarrow\quad y_i\succeq_i x_i\text{ for every }i. \]

Proof. Along a sequence of improving coordinate changes from \(x\) to \(y\), every coordinate can only improve in its strict linear order. Thus \(y_i\succeq_i x_i\) for every \(i\).

Conversely, suppose these coordinate comparisons hold. Starting from \(x\), change each coordinate on which \(x\) and \(y\) differ to its value in \(y\). Every such change is an improvement. Since \(x\ne y\), at least one change occurs, and the resulting sequence proves \(y\succ_N x\). ∎

The induced relation is acyclic: assigning each domain value an integer rank increasing with preference, every improving step strictly increases the sum of coordinate ranks.

A report \((x,y)\) is individually compatible precisely when \(y\not\succ_N x\). Indeed, if \(y\succ_N x\), every completion places \(y\) above \(x\). Otherwise, adding the requirement that \(x\) precede \(y\) creates no directed cycle: such a cycle would require an existing directed path from \(y\) to \(x\). The resulting finite acyclic graph has a topological ordering, which is the required completion.

Consequently, the lemma and strictness of the coordinate orders give the useful criterion
\[ (x,y)\text{ is individually compatible with }N \quad\Longleftrightarrow\quad \exists i:\ x_i\succ_i y_i. \]

Thus compatibility can be checked without enumerating the outcome space \(D\).

2. Membership in NP

A certificate lists the strict linear order on every explicitly listed domain. Its length is polynomial in \(s\) and \(L\).

After recording each value’s position in its coordinate order, check every report using the criterion above. This requires at most \(m\tau\) coordinate comparisons.

The compatible masses can also be summed and compared with \(q\) exactly in polynomial time. For example, use the product of their denominators and the denominator of \(q\) as a common denominator. Its bit length is at most the sum of the input denominator lengths, hence is \(O(L)\); the resulting integer arithmetic has polynomial bit complexity.

Therefore the decision problem belongs to NP.

3. Hardness at quota one

Use the supplied premise that deciding whether one separable CP-net is individually compatible with every report in an explicitly given finite set is NP-complete, even for binary attributes.

Given such an instance with \(t\ge1\) reports, retain its attributes, domains, and reports, and assign every report mass \(1/t\). Set \(q=1\). These positive rational masses sum to one and have polynomial encoding length.

For any \(N\), its compatible mass equals one exactly when all reports are individually compatible: omitting even one report reduces the mass by at least \(1/t\). Hence the transformation preserves YES- and NO-instances.

An empty source report set is automatically a YES-instance and can be mapped to a fixed YES-instance consisting of one binary attribute and one report of mass one.

This proves NP-hardness, and therefore NP-completeness, already with binary attributes, equal masses, and \(q=1\).

4. The threshold at one half

Quotas at most one half

Choose any separable CP-net \(N\), and let \(\overline N\) reverse every coordinate order.

For every report \((x,y)\), some coordinate differs. On that coordinate, either \(x_i\succ_i y_i\) in \(N\), or that comparison holds in \(\overline N\). Thus every report is compatible with at least one of these two networks.

Writing \(W(N)\) for compatible mass, this proves
\[ W(N)+W(\overline N)\ge1. \]
At least one network therefore has compatible mass at least \(\tfrac12\). Every valid instance with \(q\le\tfrac12\) is a YES-instance.

Every fixed rational quota above one half

Fix a rational \(r\in(\tfrac12,1)\). Reduce again from the supplied all-reports compatibility problem, with \(t\ge1\) reports.

Add a binary attribute \(A\) with domain \(\{0,1\}\). Replace every original report \((x,y)\) by \(((x,0),(y,0))\), assigning it mass
\[ \frac{2r-1}{t}. \]
Choose any original outcome \(z\), and add the two reports
\[ ((z,1),(z,0)),\qquad ((z,0),(z,1)), \]
each with mass \(1-r\). Set the quota to \(r\).

All masses are positive, and their sum is
\[ (2r-1)+2(1-r)=1. \]

Exactly one of the two added reports is compatible with any separable CP-net: they differ only on \(A\), whose order is strict. Their total compatible contribution is therefore always \(1-r\).

Each transformed original report has equal values on \(A\), so its compatibility depends exactly on the original coordinate orders. If \(k\) original reports are compatible, the new compatible mass is
\[ 1-r+(2r-1)\frac{k}{t}. \]
Because \(2r-1>0\) and \(k\le t\), this quantity reaches the quota \(r\) exactly when \(k=t\).

The construction has polynomial size and preserves binary domains. Empty source instances can again be mapped to a fixed YES-instance. Thus the problem is NP-complete for every fixed rational quota in \((\tfrac12,1)\); the preceding reduction covers quota one.

Accordingly, the general problem is NP-complete and has no polynomial-time algorithm unless \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned problem correctly: the decision problem is NP-complete, already for binary attributes. The additional classification by fixed quota is also correct. No major or minor issues were found.

• Characterization of the induced relation.

The lemma is correct for distinct outcomes. Every improving coordinate change increases that coordinate in its fixed linear order, so a sequence of such changes implies coordinatewise weak preference. Conversely, changing each differing coordinate directly to its value in the preferred outcome gives a permitted sequence. The restriction \(x\ne y\) ensures that this sequence contains at least one strict improvement.

Singleton domains cause no difficulty: their coordinates never differ.

• Acyclicity and individual compatibility.

The rank-sum argument correctly establishes acyclicity. Integer ranks increasing with local preference exist because each domain is finite and linearly ordered.

The completion argument is valid. With edges directed from the outcome ranked above to the outcome ranked below, adding the requirement that \(x\) precede \(y\) creates a cycle precisely when there is already a path from \(y\) to \(x\). The assumption \(y\not\succ_N x\) excludes that path. The stated finite acyclic graph property then supplies a topological ordering extending all required comparisons.

Consequently, incompatibility is exactly \(y\succ_N x\). Negating the lemma’s coordinatewise condition gives a coordinate where \(y_i\not\succeq_i x_i\); strict totality makes this equivalent to \(x_i\succ_i y_i\). The resulting compatibility criterion is correct.

• Membership in NP.

Listing a permutation of every explicitly given domain is a polynomial-size certificate. A verifier can check that each list contains exactly the domain’s values and record their positions in polynomial time.

The bound of at most \(m\tau\) coordinate comparisons follows directly from the compatibility criterion. No enumeration of the product outcome space is needed.

The exact-arithmetic argument is also correct. The product of the relevant denominators, including the quota denominator, has bit length bounded by their total input bit length. Scaling, adding the numerators, and comparing the resulting integers therefore take polynomial time. Empty compatible subsets have mass zero and pose no exception.

• Reduction at quota one.

The reduction legitimately uses the NP-completeness premise explicitly supplied in the task.

For a nonempty source set containing \(t\) reports, retaining the reports and assigning mass \(1/t\) produces positive rational masses summing to one. Their total encoding length is polynomial. Because the source reports form a set, the output remains a list of distinct support types.

At quota one, the compatible mass is \(k/t\), where \(k\) is the number of compatible reports. It meets the quota exactly when \(k=t\). Thus both directions of the reduction hold.

The empty source set is correctly handled by a fixed YES-instance. The construction preserves binary domains, establishing NP-hardness for the stated restricted case. Combined with membership in NP, this proves the main claim.

• Quotas at most one half.

Reversing every local order is a valid operation on arbitrary finite domains. For each report, distinctness guarantees a differing coordinate. Exactly one of the two opposite orders favors the report on that coordinate, so at least one network makes the report individually compatible.

Summing this coverage statement with the positive report masses correctly yields \(W(N)+W(\overline N)\ge1\). Hence at least one network achieves mass at least \(1/2\). This includes equality at the threshold and all smaller permitted quotas.

• Every fixed rational quota strictly between one half and one.

The construction satisfies the input requirements. Since \(1/2<r<1\), both \((2r-1)/t\) and \(1-r\) are positive, and the displayed normalization calculation is correct.

An original outcome \(z\) exists because all domains are nonempty. The two added reports are distinct from each other and from every transformed original report: the added reports differ on the new coordinate, whereas transformed original reports agree there.

Exactly one added report is compatible, contributing \(1-r\). The new coordinate cannot affect compatibility of transformed original reports because its values agree. Thus the compatible mass is exactly
\(1-r+(2r-1)k/t\).

Its difference from the quota is \((2r-1)(k/t-1)\). Since \(2r-1>0\) and \(k\le t\), meeting the quota is equivalent to \(k=t\), as claimed.

For fixed rational \(r\), the masses have polynomial encoding length. Binary domains remain binary. The empty-source exception and quota-one endpoint are both covered.

• Scope and final conclusion.

Binary-domain hardness applies to the general explicitly listed finite-domain problem, and the NP verification applies throughout that general setting. The output therefore establishes NP-completeness of the requested decision problem and correctly states the consequence concerning polynomial-time algorithms unless \(\mathrm P=\mathrm{NP}\).

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩