d4-conf-aaai-2005-0275

I would lead with Mass-Majority Approximate CP-Net Configuration, a narrow mirror of the paper’s approximate optimization result.

Imagine a product platform choosing one feasible configuration for a very large customer base. Each customer has a conditional preference type: a complete binary CP-net over the same features and dependency graph. A type records the customer’s preference in every parent context, so customers of one type are indistinguishable for this decision. The society is a distribution \(\mu\) over the \(\tau\) types, with rational masses summing to \(1\). A plausible regime is millions of customers represented by a modest number of preference types.

For each feature and parent context, pool the types’ conditional preferences by mass-weighted majority. If more than half the mass prefers \(1\) to \(0\), the pooled CP-net \(N_\mu\) prefers \(1\); if more than half prefers \(0\), it prefers \(0\); a tie means indifference. The platform’s decision variable is one configuration \(o\in\{0,1\}^n\), subject to shared hard product constraints \(C\). The question is to return every feasible configuration for which there is no better feasible configuration reachable through a chain of feasible worsening flips in \(N_\mu\). There is no numerical objective: as in the paper, the solution is a set of undominated feasible outcomes.

My anchor is Theorem 4, proved in this paper. It says that, for a possibly cyclic constrained CP-net \(\langle N,C\rangle\), an outcome is feasible and approximately optimal exactly when it satisfies \(C\cup\operatorname{opt}^*(N,C)\). In other words, the paper constructs approximate optimality constraints whose satisfying assignments are precisely the feasible outcomes with no feasible improving chain into them. The theorem is a constraint characterization rather than a numbered complexity-class result; the paper’s accompanying text says that checking a specified outcome is polynomial-time, while deciding whether any feasible approximately optimal outcome exists is NP-complete. My mirror asks that same underlying question for \(N_\mu\), not whether the encoding itself is hard.

The expectation is Class B: hardness transfers. The pooling step just sums rational masses for each local comparison, which is polynomial in the support size and input bit length. But with \(\tau=1\), mass \(1\), the mirror is exactly the paper’s constrained approximate optimization problem; any CP-net instance can be repeated across an arbitrarily large homogeneous population. Thus the NP-complete existence question remains hard even in a high-multiplicity regime. The reduction’s combinatorics live in the features and constraints, not in population size. Further questions include whether the hardness persists under restrictions on the feature graph or the constraint structure, and how exact feasible Pareto optimization compares with this approximate semantics in the pooled model.

This covers only Theorem 4’s approximate outcomes and existence question. It does not claim to mirror the paper’s exact Hard-Pareto algorithm or its weighted CSP approach.

The weak point is the aggregation rule. The paper reasons with one CP-net and does not define mass-weighted majority pooling across CP-nets. Still, it explicitly discusses cycles arising when preferences from several agents are collected, and the pooled object remains the same kind of constrained CP-net the paper optimizes. I think the authors could recognize this as a sensible continuous-population extension of their problem, though they might regard the choice of pooling semantics as a new modeling step rather than a direct continuization.