| paper | d4-conf-aaai-2004-0149 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for one fully ranked acyclic binary type of mass one and indegree at most three; fixed-parameter tractable with parameter \(k\). A conservative running-time bound is \(O((L+\tau m+\tau(k+1)^2 2^k)L^2)\) on a bit-cost RAM. · discrete side: parameterized · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a common set of binary features, a finite list of supported acyclic partial CP-net types with rational masses \(\mu_t\) summing to \(1\), and outcomes \(\alpha,\beta\), classify each type’s comparison of \(\alpha\) and \(\beta\). Let \(P,N,I\) be the total masses of types reporting \(\alpha\succ\beta\), \(\beta\succ\alpha\), and incomparability, respectively. Decide whether \(P>N+I\).
The society is a distribution \(\mu\) over complete preference types: each type is an acyclic partial CP net over the common outcome features, and its mass is the fraction of agents with that net. The query takes two outcomes, aggregates the types’ comparison votes by mass, and returns yes or no; there is no optimization objective.
Covers Theorem 5’s Majority dominance query; leaves the optimal-outcome results and the other voting semantics aside.
A credible mirror is weighted-majority dominance for a continuum population of CP-net types. Picture a large organization choosing a shared configuration or policy described by binary features. Members’ preferences are represented by acyclic partial CP nets drawn from a small catalogue of exact templates: people of one type share the same dependency structure and preference tables. If there are \(N\) members but only \(\tau\) supported types, let \(\mu_t\) be the fraction with type \(t\), with \(\sum_t\mu_t=1\). Each type’s net fully describes the preferences relevant to the decision.
The precise problem is: given the feature set, the list of supported CP-net types and their rational masses, and two outcomes \(\alpha,\beta\), decide whether \(\alpha\) is majority-better than \(\beta\). Define \(P\), \(N\), and \(I\) as the total masses of types that say, respectively, \(\alpha\succ\beta\), \(\beta\succ\alpha\), or find the outcomes incomparable. The answer is yes exactly when \(P>N+I\), matching the paper’s majority semantics with voter counts replaced by population fractions. A solution is the yes/no comparison. There is no scalar objective to maximize: the underlying task is the paper’s dominance query.
My anchor is Theorem 5, proved in this paper. It states that testing whether one outcome dominates another takes \(O(m2^k)\) time under Pareto, Majority, Max, and Lex semantics, and \(O(m2^{n+k})\) under Rank semantics, where \(m\) is the number of agents, \(n\) the number of binary features, and \(k\) the number of features in the largest partial CP net. I rely on its Majority result. In the mirror, each supported type can be evaluated once and its vote contributes its mass. This gives \(O(\tau2^k\operatorname{poly}(L))\) time, where \(L\) is the input bit length for the rational masses and preference descriptions. Thus the problem is fixed-parameter tractable in \(k\), and polynomial when \(k\) is bounded. It depends on the number of distinct types, not the number of people.
The authors would plausibly recognize this as their problem: it retains their conditional preference models, common outcomes, and majority comparison, changing how the population is represented. It is a restricted but natural instance regime, not a claim that every mCP-net application has few types. It also respects the high-multiplicity meaning of type: members grouped together are identical in every preference detail used by the query.
The expected classification is Class B for unrestricted feature structure. With a single supported type of mass \(1\), the weighted-majority comparison reduces exactly to that CP net’s dominance relation. The paper’s background states that dominance is NP-hard even for acyclic CP nets, citing Domshlak and Brafman (2002), and notes that the \(m=1\) case inherits CP-net complexity results. That cited hardness is not my numbered anchor; Theorem 5 is. But it gives the mirror a clear boundary: the population representation compresses repeated types, while hardness driven by the feature structure survives even at \(\tau=1\). Further questions include whether useful structural restrictions on the CP nets give polynomial algorithms, and whether comparison remains tractable under bounded \(k\) as \(\tau\) and the total feature count grow.
This case covers Theorem 5’s Majority dominance result, not the paper’s optimal-outcome results or its other voting semantics. Its weakest point is that the computational gain is mainly aggregation: the paper’s own algorithm is already linear in the number of agents, and repeated identical CP nets could be grouped in a discrete implementation too. So this is a sound population-level mirror, but not a claim that continuization by itself removes the paper’s central hardness.
The strongest case against this mirror is that mCP nets can make agents structurally different in ways that a preference-type label may not capture. An agent’s partial net can have private features and visible features whose values come from other agents’ nets. In regimes where those dependencies are wired to particular people or positions, copying a “type” may require adding new outcome variables or changing the dependency graph. The resulting population is not a distribution over a fixed, small catalogue of interchangeable agents; its type space can grow with the population. Theorem 5’s \(O(m2^k)\) bound then still describes an explicitly listed set of agents, not a compressed society.
The proponent’s common-configuration example avoids that problem by giving everyone the same outcome features and drawing agents from a finite catalogue of complete CP-net templates. That is a real improvement over a literal reading of the paper, but it narrows away much of the formalism’s agent-specific structure. Its continuous majority query is then a weighted tally of local dominance judgments. This may be a thin research target: the discrete algorithm already evaluates those judgments agent by agent, and grouping identical templates is direct preprocessing. It offers little reason to use the continuous-optimization machinery that motivates part of ChoCo.
Those points do not defeat the mirror. The narrowed setting is still a plausible large-population regime, and majority semantics depends only on how much mass votes each way. Theorem 5 is a named computational result, and the paper’s cross-agent features do not prevent a shared-feature subcase. Treating denominator expansion or easy aggregation as a collision would also mistake a high-multiplicity formulation for prior continuous work.
So the honest negative case is weak on the central question. It can argue that this is a low-yield, structurally narrow mirror, but it cannot support the universal claim that no worthwhile scenario exists. The shared-feature, finite-template version remains a defensible mirror of Theorem 5.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.