d4-conf-aaai-2016-0291

The strongest mirror is to make the population a distribution over complete CP-net preference types, then ask whether the resulting electorate has a weak or strong Condorcet winner. This is a particularly direct high-multiplicity version of the paper’s model: an mCP-net is already a collection of agents’ CP-nets, and its majority semantics aggregates their pairwise preferences.

Let the common set of binary features be \(F\), with outcomes \(X=\{0,1\}^{|F|}\). A type is one complete standard CP-net over \(F\): it specifies the agent’s conditional preferences, including the network structure and CP tables. A society is a finite support of \(\tau\) such types, \(N_1,\ldots,N_\tau\), with positive binary-rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\). Each mass is the fraction of the population with that exact preference type. Require each type to meet the paper’s acyclic, binary, polynomially connected assumptions.

For outcomes \(x,y\in X\), define \(p_\mu(x\succ y)\) as the total mass of types whose CP-net says \(x\) dominates \(y\); define \(p_\mu(x\bowtie y)\) similarly for incomparability. The paper’s majority rule becomes \(p_\mu(x\succ y)>1/2\): its supporter mass must exceed the combined opponent and incomparable mass. Outcomes remain discrete binary assignments. Only the population has been continuized.

This is plausible for a large group making a combinatorial choice, such as users choosing bundles described by many binary product attributes. Many users may share a conditional-preference template even when the space of possible bundles is huge. In particular, the paper’s hardness constructions use at most six CP-nets, so a population of \(N\) users can consist of six large cohorts, each sharing one type. Thus \(N\) can be much larger than \(\tau\), while the combinatorics reside in the feature and outcome space.

There is also an exact bridge to the discrete setting. Any discrete electorate maps to masses equal to its type counts divided by its population size. Conversely, rational masses can be realized by taking a common denominator and making the corresponding number of copies of each type. Every pairwise mass comparison then agrees exactly with the discrete vote. The denominator may be large relative to its bit-length, which is precisely the high-multiplicity regime.

Theorem 15 is my lead anchor. As printed, it states: “Let \(M\) be an mCP-net. Deciding whether \(M\) has a weak Condorcet winner is \(\Sigma_2^P\)-complete. Hardness holds even on 6CP-nets.” The paper proves this result; it gives a proof sketch here, with the quantified-formula hardness used in the reduction coming from cited prior work.

The continuous problem, Continuous Weak-CW Existence, is: given the feature set and a rational distribution \(\mu\) over \(\tau\) permitted CP-net types, does there exist an outcome \(x\in X\) such that, for every \(y\ne x\), \(p_\mu(y\succ x)\le 1/2\)? A yes-instance’s solution is such an outcome \(x\). This asks whether some configuration cannot be defeated by a strict majority. I consider it the strongest mirror because it preserves the paper’s group-level existence question directly.

I expect hardness to transfer, in Class B. An instance of the paper’s six-agent construction gives each constituent CP-net mass \(1/6\); repeated cohorts preserve those same shares for arbitrarily large populations. The reduction’s combinatorics are in the feature structure, not in population multiplicity. With binary-rational weights, I also expect the \(\Sigma_2^P\) upper bound to carry over: the weighted majority comparison can be checked using exact rational arithmetic once the relevant CP-net dominance witnesses are supplied. A useful follow-up is whether the same completeness result holds for arbitrary masses when \(\tau\le 6\), and what the smallest hard support size is.

Theorem 14 supplies a second, more tightly supported anchor. It states: “Let \(M\) be an mCP-net. Deciding whether an outcome \(\alpha\) is a weak Condorcet winner is co-NP-complete. Hardness holds even on 2CP-nets.” This is also a result of this paper, not a cited classification.

Its continuous counterpart, Continuous Weak-CW Verification, takes the same distribution \(\mu\) and a specified outcome \(x\), and asks whether every other outcome \(y\) satisfies \(p_\mu(y\succ x)\le 1/2\). Here the proposed solution is the yes/no answer for the supplied \(x\). The discrete two-agent hardness instance maps to two types of mass \(1/2\) each, so the hardness transfers even with support at most two. I expect the continuous problem to remain co-NP-complete. A further question is how unequal masses at support size two affect the boundary, including whether one type’s mass above \(1/2\) yields additional structure.

Theorem 17 anchors the strong-winner variant. It states: “Let \(M\) be an mCP-net. Deciding whether \(M\) has a Condorcet winner is \(\mathrm{DP}_2\)-complete. Hardness holds even on 6CP-nets.” Here \(\mathrm{DP}_2\) is the class of intersections of a \(\Sigma_2^P\) language and a \(\Pi_2^P\) language. This is another theorem proved by the paper, with proof details sketched rather than imported as an existing classification.

The continuous problem, Continuous Strong-CW Existence, asks whether there is an outcome \(x\) such that \(p_\mu(x\succ y)>1/2\) for every other outcome \(y\). A yes-instance’s solution is that strongly preferred outcome. Again, equal masses \(1/6\) reproduce the paper’s hard instances and can describe six large cohorts, so I expect the hardness to transfer. My expectation is \(\mathrm{DP}_2\)-completeness, though the weighted version’s upper-bound proof should be checked rather than assumed. A natural further question is whether weighted tie cases change the classification, or whether restrictions on the types’ CP-net structures make strong-winner existence tractable.

The mirror covers these three majority-voting questions only; it does not claim to continuize all the paper’s results. It also keeps the paper’s incomparability semantics intact instead of converting each CP-net into a total ranking.

My weakest point is that the fixed-support hardness embeddings establish hardness using equal-mass finite electorates. They show that the continuous model contains the paper’s hard cases, but they do not show that arbitrary fractional masses create a new algorithmic phenomenon. Exact sharing of complete CP-nets may also be a restrictive assumption in some user populations. The case survives because the relevant regime is large cohorts sharing full preference descriptions, and the mirror is a genuine distributional version of the paper’s aggregation problem. Whether its answers match the discrete ones is itself a result to establish, not a reason to dismiss the question.