| paper | d4-conf-ecai-2010-0231 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\). Explicit generation can require \(2^m\) outcomes, and generation with exact minimization is possible in \(2^m\operatorname{poly}(m,\tau,L)\) time. The stated Pareto-optimality guarantee fails for this recursion. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) binary variables, a rational distribution \(\mu\) over complete acyclic binary CP-net types, and a fixed tie-break for selecting \(Y\), run CDCP’s candidate-generation phase using the positive-mass types. Compute its shortlist \(Q_\mu\) and a member minimizing \(R_\mu(o)=\max_{t\in\operatorname{supp}(\mu)}\operatorname{rank}_t(o)\); establish whether every \(o\in Q_\mu\) is Pareto-optimal for all types in \(\operatorname{supp}(\mu)\).
Each type is a complete acyclic binary CP-net, including its dependency graph and conditional preference tables; \(\mu_t\) is its population mass. The procedure branches on assignments to variables and ranks shortlisted assignments by \(R_\mu\); assignments remain discrete in \(\{0,1\}^m\). The paper’s max-rank and unanimous Pareto criteria make the procedure depend on \(\operatorname{supp}(\mu)\), not the mass magnitudes.
Covers Theorem 1’s Pareto guarantee and Theorem 2’s per-call branch bound for a society supported on complete CP-net types. It leaves open the total recursion runtime, rank-query complexity, experimental near-Minimax results, and extensions to other CP-net variants.
The strongest mirror is the paper’s recursive CDCP procedure over a population with many people but few distinct, complete CP-net preferences. Let a type \(t\) be one full acyclic binary CP-net, including its dependency graph and every conditional preference table. The continuous society is a rational distribution \(\mu\) over those types, with support size \(\tau\). A plausible regime is a large organization choosing a shared configuration with \(m\) binary settings: many thousands of users, but preferences elicited from a library of tens or hundreds of recurring CP-net templates.
The decision is still one complete assignment \(o\in\{0,1\}^m\). For each type \(t\), use the paper’s rank \(\operatorname{rank}_t(o)\), the longest improving-flip path from that type’s optimal outcome to \(o\). The continuous counterpart of its fairness criterion is
\[
R_\mu(o)=\max_{t:\mu_t>0}\operatorname{rank}_t(o).
\]
Pareto optimality is also evaluated over the positive-mass types: no other assignment may be strictly preferred by every such type. This is the natural extension of the paper’s worst-off-agent objective. It deliberately does not replace that objective with average rank or discount a type because its mass is small.
My lead question is Mass-CDCP Shortlisting. Its instance is \(V\), a rational distribution \(\mu\) over finitely many acyclic binary CP-net types, and a fixed tie-breaking rule for the paper’s eligible choices of \(Y\). Run the recursive candidate-generation phase with each type treated as a preference class, carrying that type through the same branch conditions as the paper. The solution is the resulting set \(Q_\mu\) of complete assignments. The paper’s second phase then returns an assignment in \(Q_\mu\) minimizing \(R_\mu\), with a fixed tie-break for equal ranks. This mirrors the procedure’s actual shortlist-based choice; it does not claim to solve exact Minimax over every assignment.
The first anchor is Theorem 1, proved in this paper: every outcome generated by CDCP P1 is Pareto-optimal. In full, each generated complete assignment has no other complete assignment that every involved agent strictly prefers under their CP-net semantics; since the procedure chooses its final outcome from those candidates, that choice is Pareto-optimal too. In the mirror, the corresponding question is whether the type-level shortlist consists entirely of assignments that are Pareto-optimal for the positive-mass types. The answer is the direct type-level extension of the theorem’s guarantee.
I expect Mass-CDCP Shortlisting to be tractable when \(\tau\) is modest, but that is a research hypothesis, not a result of this paper. The useful second anchor is Theorem 2, also proved here: in a call with \(s\) involved agents and \(l\) unassigned variables, the number of distinct combinations of preferred values on the selected set \(Y\) is at most \(\min\{2^{s-1},2^l\}\). Its continuous counterpart is the local Mass-CDCP Branch Enumeration problem: given a recursive state \(z\), its positive-mass type support \(S\), and the selected \(Y\), output the distinct combinations on \(Y\). With \(s\) replaced by the number of involved types, the theorem suggests a tractable, support-parameterized bound for this step. The further question is whether the full recursion has an \(f(\tau)\operatorname{poly}(m,L)\) bound, and how expensive the ranking queries are. Theorem 2 alone does not settle either.
These are formal algorithmic anchors, not complexity-class results: the paper does not prove that a problem is in P or FPT, or that it is NP-hard. Nor does the mirror continuize the outcome space: assignments remain discrete, and the paper’s experiments and fairness measurements are not asymptotic guarantees. The scope here is the recursive aggregation procedure and its Pareto guarantee, not an exact global Minimax algorithm or the paper’s empirical runtime claims.
The weakest point is that the mass values themselves do not affect either the worst-case rank or unanimous Pareto optimality; only whether a type has positive mass matters. That is faithful to the paper’s max-over-agents fairness criterion, but it limits the benefit of modeling mass continuously. The scenario is convincing only when exact repeated CP-net types are plausible; with idiosyncratic conditional preferences, \(\tau\) may approach the population size. The paper also notes that dominance testing for arbitrary CP-nets is PSPACE-complete, citing prior work, so the continuous population does not make difficult ranking queries disappear. The positive case is narrower: where a large population truly shares a small support of complete preference types, CDCP’s candidate generation has a natural high-multiplicity version, and its named theorems give that version concrete properties to investigate.
The paper gives no named theorem about the complexity of a computational problem. Theorem 1 is a Pareto-optimality guarantee; Theorem 2 bounds the number of branches in one recursive call. That leaves a real algorithmic paper to study, but it means the proposed anchors are not continuous counterparts of a complexity result established here.
Mass-CDCP Shortlisting adds no mass-dependent computation. For this procedure, a type’s complete CP-net determines every relevant choice: which variables it elicits, whether its preferences conflict with others, which branches it joins, and its rank for an outcome. Replacing repeated copies of a CP-net by one representative leaves those decisions unchanged. Thus the shortlist \(Q_\mu\) depends on \(\operatorname{supp}(\mu)\), not on the rational masses; likewise, \(R_\mu(o)=\max_{t\in\operatorname{supp}(\mu)}\operatorname{rank}_t(o)\). The proposed problem is CDCP on the distinct CP-nets, with the masses carried as unused input.
That makes the Theorem 1 mirror an immediate change of quantifier: “every agent” becomes “every positive-mass type.” A representative of each type already gives the same Pareto condition, so the theorem transfers without a population limit, fractional optimization, or a new computational question. The stronger version—asking whether the exact global Minimax assignment is tractable for a type distribution—would be a legitimate question about CP-nets, but the paper does not establish a complexity result for that problem, and the masses still disappear.
Theorem 2 is the closest computational anchor, but its bound concerns branch enumeration in a single state, not the runtime of the full recursion. Counting distinct types instead of individual copies may sharpen that local bound. Proving an \(f(\tau)\operatorname{poly}(m,L)\) bound for the whole procedure could be useful, but it is parameterized analysis of CDCP by its number of distinct inputs. The paper’s algorithm already operates on agent sets; writing those sets as a weighted distribution does not create the question. Nor does Theorem 2 show that the full recursion has the proposed bound.
There are ways to make mass affect the objective—for example, minimizing expected rank or a rank quantile. But those replace the paper’s worst-off fairness criterion with a different welfare rule. The paper offers no reason to prefer one such mass-sensitive rule, and its ordinal CP-net semantics do not supply a canonical cardinal interpretation of average rank. Keeping the paper’s criterion preserves the mirror, but makes masses irrelevant.
A small library of exact CP-net templates is possible, as the proponent’s configuration scenario suggests. The limitation is that a “type” here includes the entire dependency graph and every conditional preference table; small support is a substantial modeling assumption, and any rare positive-mass type still counts fully under both the max-rank and Pareto criteria. I cannot rule out a useful application-specific study of such cohorts. The negative case is narrower: these anchors do not show that continuizing the population creates a distinct computational problem. The strongest remaining research question is about support-parameterizing an existing CP-net algorithm, and whether that belongs in ChoCo is where this case is weakest.
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.