| paper | d4-conf-aaai-2016-0546 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Expected polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given \(n\) attributes, domain size \(d\), and indegree bound \(c\), let \(\Omega_{n,c,d}\) be the paper’s set of labeled acyclic CP-nets with complete, nondegenerate conditional preference tables and indegree at most \(c\). For the continuous society with \(\mu_N=1/|\Omega_{n,c,d}|\) for each \(N\in\Omega_{n,c,d}\), output a type \(N\) sampled exactly according to \(\mu\).
Types are the CP-nets \(N\in\Omega_{n,c,d}\); each has mass \(\mu_N=1/|\Omega_{n,c,d}|\). The society is specified compactly by \((n,c,d)\), and the computational task is exact sampling of one member’s type.
The sampler draws one type from a compactly specified law and computes no aggregate property of the population; this limits the mirror to sampling, though the paper’s stated social-choice culture motivation supports that task.
fatal: False
The mirror covers the uniform-generation result in Theorem 14 and its counting and probability tables in Theorem 15. It does not cover CP-net reasoning or decisions computed from aggregate voter mass.
The strongest mirror I can defend is a synthetic preference culture for a very large population. Suppose an online platform is evaluating group-decision or preference-reasoning tools for products with \(n\) attributes and \(d\) options per attribute. Each user’s complete preference type is a CP-net, with at most \(c\) dependencies per attribute. Users with the same CP-net are indistinguishable for the questions being studied. For a controlled benchmark, define \(\Omega_{n,c,d}\) to be the set of labeled acyclic CP-nets in the paper’s model, with complete, nondegenerate CPTs and indegree at most \(c\). The continuous society is \(\mu_N=1/|\Omega_{n,c,d}|\) for each \(N\in\Omega_{n,c,d}\).
This is credible as a *synthetic* population, not as a claim that real users are uniformly distributed over CP-nets. The paper itself motivates generation by experiments, testing, and social-choice simulations. The high-multiplicity regime is many users sharing a modest number of preference types. For example, with two binary attributes and \(c=1\), this family has 12 types; a platform with millions of users could have many users of each type. Larger families may have far more types, so this scenario works best when the agenda and dependency bound are modest.
My lead is Uniform CP-net Voter Sampling. Its instance is \((n,c,d)\), which implicitly defines \(\Omega_{n,c,d}\) and the continuous society \(\mu\). The task is to output a voter type \(N\) with probability exactly \(\mu_N\); a solution is a randomized algorithm with that output distribution. This is the continuous-population reading of the paper’s generation task: the generated CP-net is the preference type of a randomly selected member of a fixed continuous culture.
The anchor is Theorem 14, proved in this paper. It states that Algorithm 6 generates every CP-net in the specified family with probability exactly \(1/a_{n,c,d}\), where \(a_{n,c,d}\) is the number of such CP-nets. Thus it samples exactly from \(\mu\). I expect this mirror to be tractable in the paper’s parameter regime. It is also the strongest anchor: it directly solves the sampling task, rather than merely supplying a useful subroutine.
A second, narrower mirror is Uniform-culture census. Given \((n,c,d)\), the task is to compute the exact size \(a_{n,c,d}\) of the culture and the conditional masses needed to sample a CP-net as its dagcode and CPTs are built. A solution is the normalizing count together with those exact conditional probabilities. Theorem 15, also proved here, states that Algorithm 5 computes its tables of feasible choices and weights in time and space polynomial in \(n\). This too points toward tractability, and it supplies the probability calculations used by the lead sampler. Its stated polynomial bound needs care as a bit-complexity claim when \(c\) and \(d\) vary: exact counts can be large, so fixed small \(c,d\) is the clearest regime for the mirror.
The mirror covers the paper’s uniform-generation and preprocessing results, not CP-net reasoning or a social-choice decision problem over the resulting population. It raises natural follow-ups: can one compute other exact population marginals, such as the mass of types containing a given dependency, or efficiently generate a fixed-size electorate with exactly prescribed type counts?
My weakest point is that the paper generates a random preference model, while the mirror interprets that model as a voter type in a population. To use Theorems 14 and 15, the culture must be specified compactly by \((n,c,d)\); an explicit support list would make sampling trivial but could be exponentially large. That is a real representational step beyond the programme’s usual support-list input. The authors could plausibly recognize the benchmark-culture interpretation given their stated experimental and social-choice motivations, but this is a modest mirror of a generation problem—not a case that discrete hardness dissolves in a continuum. The paper offers no named hardness result to anchor such a claim.
The strongest negative is that the two anchors describe a *law for generating preference models*, not a computation over a society. The paper studies which CP-nets can be generated and how to sample them without bias. It does not take an electorate as input or compute anything about what that electorate would decide.
For Theorem 14, the best version of the mirror is coherent: treat each CP-net in \(\Omega_{n,c,d}\) as a voter type, and let \(\mu\) assign each type equal mass. But asking for a random voter’s type uses only the sampling law \(\mu\); the rest of the population plays no role. If the support is listed explicitly, sampling from it is just sampling from a list. If it is specified compactly by \((n,c,d)\), the computational task is the paper’s original uniform CP-net generator with a population interpretation added. A more substantive continuous question—such as computing a winner or the cost of changing the electorate—would involve aggregate mass, but neither Theorem 14 nor its sampling algorithm answers it.
Theorem 15 has the same gap. Its recurrence counts allowable CP-net structures and supplies the weights used by the generator. Calling those counts a census of a uniform culture does not turn them into a social-choice computation. With an explicit support, a census of a type property is a scan of that support; with the compact description, counting returns to the paper’s combinatorial enumeration problem. Population marginals or election outcomes could make worthwhile follow-up questions, but they would need their own model and results. They are not mirrors established by Theorem 15.
This is a limited negative case, though. The proposed uniform culture is a sensible synthetic high-multiplicity regime, and Theorem 14’s distribution can be read directly as the mass function of a continuous society. If sampling a random member of such an implicit society counts as a worthwhile mirror, I cannot honestly say that anchor is defeated. The case against rests on the narrower claim that this reading adds population semantics without adding a computation over population mass; it does not establish that no useful continuous question can be built from the paper’s setup.
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.