| paper | Uniform Random Generation and Dominance Testing for CP-Nets |
| authors | Thomas E. Allen, J. Goldsmith, Hayden Elizabeth Justice, Nicholas Mattei, Kayla Raines |
| venue | JAIR 2017 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorems 21 and 22 are genuine algorithmic results, but they compute a sampler for one CP-net type and its weights, not a population-level quantity. Recasting the uniform culture as \(\mu\) and sampling an infinitesimal agent leaves the algorithm and question unchanged; the paper already presents that distribution as a statistical culture. The proposed \(\theta\)-mass dominance problem would be a worthwhile new mirror, but it is not a result of this paper, so no anchor survives.
fails bit b-already — the paper is already native to the continuum
The proposed \(\mu\)-sampler uses no population mass, multiplicity, or aggregate decision variable: it is exactly the paper's sampler for a single CP-net type.
fatal: True
The proposed construction would cover only Theorems 21–22 and the culture-generation discussion; it leaves the flipping-length analysis, Conjecture 26, depth-limited dominance algorithms, and SAT encoding without a valid population-continuous mirror.
The strongest positive case is narrow but genuine: an exact high-multiplicity mirror of the paper’s CP-net profile-generation problem. I would not claim that the paper’s dominance-testing results themselves have a proved continuous analogue, because its PSPACE-completeness statement is cited from Goldsmith et al. (2008), and Conjecture 26 is not a theorem.
My lead anchor is Theorem 21, proved in this paper, supported by Theorem 22, also proved here. Theorem 21 states that, for every \(n,c,d\), Random-CP-net generates every allowed acyclic CP-net with \(n\) variables, \(d\)-valued domains, maximum in-degree \(c\), complete CPTs, and non-degenerate conditional preferences with exactly uniform probability \(1/a_{n,c,d}\), where \(a_{n,c,d}\) is the number of such CP-nets. The algorithm constructs the dagcode and CPT-code sequentially, choosing each partial extension with probability proportional to the number of valid completions, and samples non-degenerate CPTs uniformly. The paper proves that the resulting telescoping product gives probability \(1/a_{n,c,d}\) for every CP-net. Theorem 22 states that the auxiliary Compute-distribution procedure, which computes the conditional weights used by the sampler, runs in time and space polynomial in \(n\). The paper presents the resulting generation method as polynomial-time under its bounded-in-degree setting.
The corresponding continuous problem is:
Uniform CP-Net Society Generation\(_\infty\). Fix variables \(V=\{X_1,\ldots,X_n\}\), domain size \(d\), and in-degree bound \(c\). Let \(\mathcal N_{n,c,d}\) be the finite set of acyclic CP-net types satisfying those restrictions, including the entire dependency graph and every CPT entry. A continuous society is a mass distribution \(\mu\) over \(\mathcal N_{n,c,d}\), where \(\mu_N\) is the fraction of agents having CP-net type \(N\). The target society is the impartial-culture distribution
\[ \mu^{\mathrm{IC}}(N)=\frac{1}{a_{n,c,d}} \qquad\text{for every }N\in\mathcal N_{n,c,d}. \]
Given \(n,c,d\), construct an exact succinct representation of this society: namely, a randomized procedure \(G\) such that, for a uniformly selected infinitesimal agent, \(G\) returns type \(N\) with probability \(\mu^{\mathrm{IC}}(N)\). Equivalently, for every subset \(S\subseteq\mathcal N_{n,c,d}\),
\[ \Pr[G\in S]=\sum_{N\in S}\mu^{\mathrm{IC}}(N). \]
A solution is therefore an exact sampler or culture oracle, not an approximation and not an enumeration of all types. The action variable is the sampler’s successive choice of parent-set code and CPT code; its objective is to realize precisely the prescribed mass law.
The mirror is motivated by a plausible high-multiplicity regime. Consider a large product-configurator, recommender, educational-planning, or voting platform in which every agent evaluates the same finite set of binary or small-domain features. Agents may repeatedly fall into the same preference archetypes: the same dependency graph, the same conditional preference tables, and hence the same CP-net. The type is complete for this problem because two agents with the same graph and CPTs are indistinguishable for dominance testing and preference aggregation. The number of agents can be millions or asymptotically infinite while \(n,d,c\) remain fixed or grow slowly. Thus the society has many clones of finitely many CP-net types, exactly the high-multiplicity regime.
This is not merely changing the word “vote” to “mass.” The paper itself discusses profiles of CP-net preferences and explicitly develops impartial culture, impartial anonymous culture, and urn models in Section 3.5. Its finite profile is a sample from a culture; the mirror takes the aggregate culture law as the society itself, so sampling noise and the arbitrary profile size disappear. For a finite rational approximation, if \(M\mu_N\) is integral for every \(N\), one obtains a finite profile by giving type \(N\) exactly \(M\mu_N\) cloned agents. The continuous society is the exact high-multiplicity object underlying those profiles.
I would classify this mirror as Class A. The exact mass law has an implicit exponentially large type space, but Theorems 21 and 22 show how to construct and sample from it without listing every CP-net. The continuum does not fractionalize outcomes: outcomes remain integral assignments in \(D^n\), and every agent still has an ordinary CP-net. What changes is that the population profile is represented by exact type masses rather than by a long list of named agents.
The mirror covers only the paper’s uniform-generation and statistical-culture results in Sections 3 and 3.5. It does not claim a continuous version of the paper’s empirical conjecture about maximum flipping length, its SAT encoding, or its cited PSPACE-completeness result for dominance testing.
The natural follow-up problem is more socially substantive:
\[ \mathrm{Mass\text{-}Dominance}_\infty: \]
given a distribution \(\mu\) over CP-net types, outcomes \(o,o'\), and a threshold \(\theta\), decide whether
\[ \sum_{N:\,N\models o\succ o'}\mu_N\ge \theta. \]
A depth-limited version would replace \(N\models o\succ o'\) with \(N\models o\succ_k o'\). This asks whether at least a \(\theta\)-fraction of the continuous society regards \(o\) as dominating \(o'\). It is an obvious computational-social-choice extension of the paper, but it is not a named result proved there, so I would present it as a new question rather than an anchor. Its complexity could involve counting or weighted aggregation over the exponential CP-net type space and is not settled by Theorem 21.
The weakest point is representation. The paper’s theorem gives a polynomial-time sampler for an implicitly represented distribution; it does not output the explicit vector \((\mu_N)_{N\in\mathcal N_{n,c,d}}\), whose support may be enormous. If ChoCo insists that every mass must be explicitly listed, the polynomial claim disappears. Moreover, in a finite real population the number of possible CP-net types may exceed the population size, making uniform culture an artificial regime unless \(n,c,d\) are fixed while the population becomes very large.
So this is not a flagship continuous bribery-style mirror with an LP and an active mass-transfer variable. It is a thinner, representation-sensitive Class-A mirror. But it is author-recognizable, grounded in the paper’s central named algorithmic result, and faithful to its actual object: generating a large population of compact preference types without bias.
The strongest objection is that Theorem 21 does not concern a population-level computational problem. It samples one syntactic CP-net \(N\) from the finite set \(\mathcal N_{n,c,d}\), with probability \(1/a_{n,c,d}\). Theorem 22 merely computes the conditional weights needed by that sampler. Neither theorem contains an agent count, population mass, collective outcome, winner, threshold, transfer, or aggregate objective.
The proposed continuous question therefore asks for a sampler whose output law is \(\mu_N=1/a_{n,c,d}\). That sampler is exactly Random-CP-net from the paper. The same procedure generates one agent, \(M\) agents, or samples from a notional continuum; \(M\) never enters the computation. Calling each draw an “infinitesimal agent” adds no continuous object or high-multiplicity phenomenon. Section 3.5 already describes the relevant object as a statistical culture, so the proposed mirror is essentially a reinterpretation of the paper’s own distribution, not a new continuous-population problem.
The high-multiplicity story itself is defensible: a large platform could contain many agents sharing the same CP-net. But that only establishes that such a society can exist. It does not make Theorem 21 a useful continuization, because the theorem does not exploit repeated types or compute anything about their aggregate mass. If the paper’s finite profiles are replaced by the exact law \(\mu\), one also removes the sampling variation that motivates the paper’s experimental methodology.
The best repair would be to ask something like whether \(\theta\) mass of a CP-net society satisfies a dominance relation, namely whether \(\sum_{N:N\models o\succ o'}\mu_N\ge\theta\). That would finally make the population continuous in a computationally substantive way. But it is a new weighted-counting or aggregation problem, not a mirror of Theorems 21 or 22. The sampler supplies samples, not the exact mass of the relevant set; an explicit mass vector defeats the claimed succinctness. Moreover, uniformity over CP-net descriptions need not be uniformity over behaviorally distinct preference relations, so even the natural type space requires a modelling choice absent from the paper.
This defeats the stated anchor: Theorem 21 gives a culture oracle, not a continuous social-choice computation, while Theorem 22 is only its bookkeeping lemma. The negative case is nevertheless not airtight universally. A threshold or collective-dominance problem over recurring CP-net archetypes could be a worthwhile new ChoCo problem. I cannot honestly claim that every such scenario fails; only that it is no longer the continuous mirror actually anchored in this paper’s named results.
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.