| paper | d4-conf-atal-2018-0267 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\Sigma_3^P\)-complete, hence \(\mathrm{NP}\)-hard, even with indegree at most three, \(\tau\leq 8\), and positive masses that are multiples of \(1/8\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.2
statement extracted from the paper’s text layer
Given a finite binary feature set \(F\), a support of \(\tau\) distinct acyclic binary CP-net types \(N_t\) over \(F\), and positive rational masses \(\mu_t\) summing to one, decide whether some outcome \(\alpha \in \{0,1\}^F\) is not max-dominated by any other outcome. For outcomes \(\beta,\alpha\), define \(P^+_\mu(\beta,\alpha)\), \(P^-_\mu(\beta,\alpha)\), and \(P^?_\mu(\beta,\alpha)\) as the masses of types that respectively prefer \(\beta\), prefer \(\alpha\), or find them incomparable; max-dominance holds when \(P^+_\mu(\beta,\alpha) > \max(P^-_\mu(\beta,\alpha),P^?_\mu(\beta,\alpha))\). Use the paper's polynomial-connectivity restriction, with indegree at most three for the hardness subcase.
Each type is a complete CP-net policy shared by a fraction \(\mu_t\) of the robot population. Outcomes remain discrete assignments to the plan's binary features; the decision variable is an outcome \(\alpha\), and the question is whether it is undominated under mass-weighted max voting.
The mirror covers the max-optimal existence result of Theorem 6.2 and also gives a population version of Theorem 5.1. It leaves the single-CP-net rank results, the other rank-voting results, and max-optimum existence aside.
The strongest mirror is the paper’s max-voting result. Consider a large group of autonomous robots coordinating on a shared plan, the kind of setting the paper itself uses to motivate group planning. The features describe binary properties of the plan, and each robot’s CP-net describes its conditional preferences over those properties. Robots with the same role and policy have the same CP-net; their type is that complete preference model. A deployment might have many robots but only a small number \(\tau\) of such types. The outcome remains a discrete plan. What becomes continuous is the population: type \(t\) has rational mass \(\mu_t\), the fraction of robots of that type.
This is a direct population mirror of global voting over CP-nets. For two outcomes \(\beta,\alpha\), let \(P^+_\mu(\beta,\alpha)\) be the mass of types whose CP-net prefers \(\beta\) to \(\alpha\); define \(P^-_\mu\) and \(P^?_\mu\) for preferring \(\alpha\) and finding them incomparable. The weighted max-voting rule says \(\beta\) max-dominates \(\alpha\) when
\[
P^+_\mu(\beta,\alpha)>\max\bigl(P^-_\mu(\beta,\alpha),P^?_\mu(\beta,\alpha)\bigr).
\]
The lead question is Continuous Exists-Max-Optimal. An instance consists of a finite binary feature set \(F\), a support of \(\tau\) distinct acyclic binary CP-net types over \(F\), and positive rational masses \(\mu_t\) summing to one. Use the paper’s polynomial-connectivity restriction; for the hardness subcase, also impose indegree at most three. Decide whether there is an outcome \(\alpha\in\{0,1\}^F\) that no other outcome max-dominates. A yes-solution is such an \(\alpha\), with the stated condition holding against every \(\beta\ne\alpha\). This asks for a max-*optimal* outcome, meaning an undominated one, not a max-*optimum* outcome that defeats every other outcome.
The anchor is Theorem 6.2, proved in this paper: deciding whether an \(m\)CP-net has a max-optimal outcome is \(\Sigma^P_3\)-hard, even for polynomially connected classes of acyclic binary \(m\)CP-nets of indegree three with at most eight agents. The paper then combines that hardness with membership in \(\Sigma^P_3\) shown in earlier work, [38], to state that Exists-Max-Optimal is \(\Sigma^P_3\)-complete. The continuous question includes the paper’s instances exactly: give each of the at most eight agents mass \(1/8\), combining duplicate CP-nets into one type if needed. The weighted comparisons then reproduce the original vote counts. So I expect hardness to transfer (Class B), rather than a tractability gain from continuization. The reduction already places its combinatorics in the feature structure, not in a large voter count.
A second, simpler mirror is Continuous Exists-Pareto-Optimum. Use the same instance format. Say \(\beta\) Pareto-dominates \(\alpha\) when every positive-mass type prefers \(\beta\) to \(\alpha\), equivalently when the mass preferring \(\beta\) is one. Decide whether some outcome is not Pareto-dominated by any other outcome; a solution is such an outcome. This is a natural fractional-population version of the paper’s global Pareto voting task.
Its anchor is Theorem 5.1, proved here: Exists-Pareto-Optimum is P-hard, even on \(2\)CP-nets. The paper says membership in P was shown in [38], and therefore the discrete problem is P-complete. In the continuous version, Pareto-optimal existence can be checked by computing each supported type’s individual optimum and checking whether all are the same. That gives a polynomial algorithm in the explicit input size. The equal-mass case with two types embeds the paper’s hardness instances, so I expect this mirror to remain P-complete. This is a second, independent Class B result; it also shows that continuous mass does not remove the sequential computation identified by the paper.
Both mirrors change the population while leaving the combinatorial outcomes discrete. They do not rely on fractional plans, probabilistic CP-nets, sequential voting, or continuous time. In the proposed robot regime, mass means a fraction of a large deployment, and types are exact preference-policy models shared by many units. The paper’s own global-voting semantics makes replacing counts by masses recognizable as the same underlying aggregation question.
The weak point is that the paper’s hardness does not depend on high multiplicity: its headline reduction needs at most eight agents, and its P-hardness result needs only two. Thus these are credible continuous questions, but they are not evidence that continuization unlocks an algorithmic improvement for this paper’s problems. The strongest honest case is that ChoCo can use them to test and document where population continuization *does not* dissolve hardness. For max voting, useful follow-ups include the exact complexity with arbitrary binary-encoded rational masses, and whether restrictions on the number or structure of CP-net types change it.
The strongest case against these mirrors is that they may add little beyond a weighted encoding of the paper’s existing model. For any rational masses \(\mu_t\), choose a common denominator \(Q\) and replace each type \(t\) by \(Q\mu_t\) identical agents. Every weighted comparison then matches the corresponding finite vote count. So the continuous questions introduce no new outcome or preference semantics; their distinct computational issue is the compressed input, where \(Q\) may be enormous relative to the masses’ bit length. That could make the work feel like a high-multiplicity encoding study rather than a new theory of group planning.
That concern is not enough to defeat Continuous Exists-Max-Optimal. A population of robots drawn from a small set of shared policies is a plausible regime, and a CP-net is a complete type for the preference comparisons the paper uses. The mirror has an exact definition: sum the masses of types preferring each outcome, and ask whether some outcome is undominated under the resulting weighted max rule. Theorem 6.2 supplies a sharp test: its hardness reduction uses at most eight agents, so consolidating duplicate CP-nets still leaves support size at most eight. That makes the result a poor candidate for a multiplicity-driven tractability gain, but the programme explicitly treats documenting that boundary as worthwhile. “The answer may be hardness” cannot rule out the question.
The Pareto mirror has a more substantial weakness. With every supported type assigned positive mass, an outcome is Pareto-optimal exactly when the supported types’ individual optimum outcomes all agree. The actual mass values do not matter: an arbitrarily small positive mass still has veto power. Thus this mirror chiefly asks about the support, not the distribution over it. Theorem 5.1 already makes that support question computationally nontrivial, even with two CP-nets. An almost-everywhere formulation would naturally ignore zero-mass types, but with finite support it leads to the same test. This makes Pareto the least compelling *mass-sensitive* anchor; it does not make the question ill-posed.
So the negative case can argue that the Pareto extension has little specifically continuous content, and that both proposals may amount to weighted mCP-nets with a compressed input. It cannot honestly rule out the stronger max-voting mirror in every scenario: the paper’s own robot-planning motivation admits a plausible high-multiplicity version, the population remains the continuous object, and the decision problem is precise. My case against a worthwhile mirror is therefore weak overall.
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.