d4-conf-ijcai-2009-0246

The strongest mirror I see is a large, one-shot preference study. Each respondent compares two multi-attribute alternatives and reports \(x \succ y\). The report \(e=(x,y)\) is the respondent’s type for this task: respondents with the same report are indistinguishable to the learner. A platform might collect millions of reports from a recurring menu of bundle comparisons, so the number \(M\) of respondents can greatly exceed the support size \(\tau\). The society is a distribution \(\mu\) over those report types, with rational masses \(\mu_e>0\) summing to \(1\). In a finite study, \(\mu_e\) is the fraction of respondents making report \(e\).

Here is the lead problem, Weak-Mass SCP Learning. An instance consists of attributes \(V=\{X_1,\ldots,X_n\}\), their finite domains \(D_i\), a supported set of reports \(\mathcal E\subseteq D\times D\), where \(D=\prod_i D_i\), rational masses \(\mu_e\), and a rational quota \(q\in[0,1]\). The question is whether there is a separable CP-net \(N\)—a linear local preference order on each \(D_i\)—such that at least mass \(q\) of reports is individually consistent with \(N\). Formally, does some \(N\) satisfy
\[ \sum_{e=(x,y)\in\mathcal E:\ \exists\text{ a completion }\succ\supseteq\succ_N\text{ with }x\succ y}\mu_e\ \ge q? \]
A solution is that \(N\). At \(q=1\), this asks whether the support is weakly separable. For smaller quotas, it asks what fraction of the respondent population one shared separable model can fit.

The lead anchor is Proposition 2, proved in this paper: deciding whether a set of examples over binary attributes is weakly separable is NP-complete. The paper proves hardness by reduction from 3-SAT, mapping clauses to examples so that the formula is satisfiable exactly when the examples are weakly separable. The \(q=1\) case of Weak-Mass SCP Learning recovers that decision problem: give every example positive rational mass, for instance equal mass. The paper also explains that finding the SCP structure that best fits examples under weak compatibility amounts to MAXSAT; the quota formulation makes that fitting objective a population fraction.

I would expect this problem to be Class B: hardness transfers. The reduction’s combinatorics live in the attribute set and the separable model’s local orders, not in the number of respondents. Replacing integer report counts by rational population proportions does not fractionalize the model \(N\). This is a credible continuous question, though it is not a prediction that continuization makes it tractable.

A second, distinct mirror is Strong-Mass SCP Learning. It has the same instance format, but asks whether there is a separable CP-net \(N\) and one completion \(\succ\) of its induced partial order such that
\[ \sum_{e=(x,y)\in\mathcal E:\ x\succ y}\mu_e\ \ge q. \]
A solution is \(N\) together with such a completion; it is enough to certify the completion on the alternatives appearing in the reports, provided that ordering and \(\succ_N\) can be extended to the full alternative space. This keeps the paper’s stronger requirement: all reports counted toward the quota must fit one shared complete preference order.

Its anchor is Proposition 4, also proved here: checking whether \(E\) is strongly separable is NP-complete. The proof reduces from weak separability: for each input example, it adds a binary auxiliary attribute and constructs a corresponding example, with the resulting set strongly separable exactly when the original set is weakly separable. At quota \(q=1\), Strong-Mass SCP Learning is precisely the paper’s strong-separability decision question on the support. I again expect hardness to transfer, for the same reason: the hardness is carried by the preference structure and attributes.

The weak mirror is my stronger case. Its individual-report interpretation fits a crowd study particularly naturally, and its weighted fitting objective follows the paper’s own discussion of finding a structure compatible with as many examples as possible. The strong mirror is worth keeping because the paper treats strong compatibility as a separate, substantive notion, not a relabeling of weak compatibility. The authors also explicitly discuss examples pooled from multiple users and distinguishing individual from group compatibility, which supports treating the reports as a population.

This proposal covers the paper’s results on weak and strong separability and their associated fitting questions. It does not continuize the alternative space or replace the learning task with elicitation; the continuous object is the population of respondents, represented by masses on report types. Natural follow-up questions include how approximation behaves for weighted fitting, what happens when reports differ on only a bounded number of attributes, and which algorithms are possible when parameterized by \(n\), \(\tau\), and the mass bit length \(L\).

The weakest point is the choice of population type. A reported pairwise comparison is a complete type only in a one-shot study where the task uses just that respondent’s one report. If the same people answer many queries and the learner needs to preserve which reports came from the same person, a type may need to include a whole bundle of reports; that is a different mirror. Also, the hardness anchors survive at \(q=1\), so the positive case is that these are legitimate continuous-population computational questions—not that continuous mass necessarily dissolves their hardness.