d4-journals-jair-2019-0073

There is one limitation in the paper’s anchors: it has no numbered theorem or corollary asserting a complexity class. Its introduction says dominance queries are NP-hard even for binary variables and acyclic preference structures, but cites Boutilier et al. (2004a) and Goldsmith et al. (2008); that claim is background from other work, not a numbered result proved here. The strongest named computational anchor for a positive mirror is Corollary 3, proved in this paper. It gives a sound pruning rule for the dominance queries the authors study.

My lead mirror is Continuous CP-Net Pairwise Support. Its instance has a shared set \(V\) of Boolean features, a support \(T\) of \(\tau\) complete, strict, acyclic CP-net types \(N_t\) over those features, and rational masses \(\mu_t>0\) summing to \(1\). It also has two outcomes \(o,o'\) and a rational threshold \(q\in[0,1]\). The question is whether

\[ \sum_{t\in T:\,N_t\models o\succ o'}\mu_t \ge q. \]

The answer is yes or no. Equivalently, one could compute the exact mass of types whose CP-net entails that \(o\) is preferred to \(o'\). A type is the full CP-net—structure and conditional preference tables—so agents within a type are indistinguishable for this query. Mass is their fraction of the population; identities and one-person granularity do not enter.

Corollary 3 says, in full, that for a CP-net \(N\) over variables \(V\), outcomes \(o_1,o_2\), and \(D=\{X\in V:o_1[X]\ne o_2[X]\}\),

\[ N\models o_1\succ o_2 \quad\Longrightarrow\quad r(o_1)-r(o_2)\ge\sum_{X\in D}L(X)>0, \]

where

\[ L(X)=AF_X(d_X+1)\frac{1}{n_X} -\sum_{Y\in Ch(X)}AF_Y(d_Y+1)\frac{n_Y-1}{n_Y}. \]

Here \(n_X=|\operatorname{Dom}(X)|\), \(Ch(X)\) is the set of children of \(X\), \(d_X\) is the number of descendant paths from \(X\), and \(AF_X\) is the ancestral factor defined in the paper. The paper proves this result; it is not a cited theorem. Its supporting Theorem 1, also proved here, says that \(N\models o\succ o'\) implies \(r(o)>r(o')\). Corollary 3 strengthens that rank comparison with a lower bound, which Section 5 uses to prune dominance-search branches. This mirror covers that dominance-query and rank-pruning result, not the paper’s broader claims about consistently ordering all outcomes.

A plausible regime is a large travel or product recommendation service with a fixed feature schema and a small catalog of elicited preference templates. Millions of customers might be distributed across a few dozen exact CP-net types. The service can ask whether at least \(q\) of customers have a *logically entailed* preference for one configuration over another. The outcomes remain discrete assignments; the continuous object is the population distribution over CP-net types. This is a co-modification of the model that preserves the authors’ underlying dominance query for each type. The paper itself motivates CP-nets with product configuration and recommender systems, so the population-level pairwise-support question is a plausible extension they could recognize.

I expect this mirror to be Class B: hardness transfers. With one type of mass \(1\) and \(q=1\), the question is exactly the original CP-net dominance query. Thus the NP-hardness reported in the introduction transfers directly; it is cited from prior work, not proved here. The paper’s Section 4 says that an individual outcome rank can be computed in \(O(n^4)\) time, and Section 5 reports experimental gains from rank pruning. Neither fact establishes a polynomial-time dominance algorithm: the continuous query still requires deciding dominance for each relevant type. Its natural worst-case cost is \(\tau\) such queries plus polynomial-time aggregation of the rational masses, and it remains NP-hard already at \(\tau=1\). The hardness lies in the feature dependencies and dominance search, not in population multiplicity.

The weakest point is that this paper studies a person’s preferences, whereas the mirror adds a population-level support question. Exact CP-net types may also be large enough that real users fragment into many distinct types, defeating the hoped-for gap between population size and support size. And entailed preference is deliberately conservative: users whose CP-nets leave \(o\) and \(o'\) incomparable do not count as supporting either direction. Those limits do not erase the mirror, but they make its high-multiplicity regime less compelling than one built from simpler ballot types. Follow-up questions include whether repeated pairwise queries across a fixed type support can reuse rank and search work, and how the problem changes when the requested result includes the mass of users who prefer the reverse outcome or regard the two outcomes as incomparable.