| paper | d4-conf-ijcai-2016-0310 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 1 is a learning-theoretic information-complexity result, but the proposed μ is a distribution over questions, not over agents’ preference types. Replacing the single target CP-net with a distribution of CP-nets and learning aggregate endorsements would change the problem and is not classified by this theorem. No continuous-population question anchored in the result survives.
fails bit b-none — no population with multiplicity to relax
The proposed mirror relies on Theorem 1’s VC-dimension results; the paper’s teaching, recursive teaching, mistake-bound, and membership-query results also concern learning one target concept, not a population of preference types.
The strongest case is narrow: a continuous PAC-learning problem for a large cohort whose members share one CP-net preference model but receive different comparison questions. The paper has no numbered result classifying a problem as polynomial-time or NP-hard. Its closest named computational-learning anchor is Theorem 1, proved in this paper: it computes the VC dimension of these learning classes, a measure that controls PAC sample complexity.
The theorem states that \(\mathrm{VCD}(C_{\mathrm{unb}})=m^n-1\) for unbounded acyclic CP-nets, and \(\mathrm{VCD}(C_{\mathrm{sep}})=(m-1)n\) for separable CP-nets. For acyclic CP-nets with indegree at most \(k\), it gives \(\mathrm{VCD}(C_{\mathrm{ac}})\ge (m-1)M\), where \(M=(n-k)m^k+\sum_{i=0}^{k-1}m^i\). That bound is exact for \(k=0\) and \(k=n-1\). The paper also states that the VCD result extends to incomplete CP-nets.
Call the mirror Cohort-PAC-CP(\(k\)). Fix \(n\) attributes, each with a domain of size \(m\), and a maximum CP-net indegree \(k\). A large institution has a shared but unknown target \(N^*\in C_{\mathrm{ac}}\), representing a standardized preference policy. Its members are assigned swap questions \(x\in X_{\mathrm{swap}}\), asking whether one outcome is preferred to another. A member’s complete type for this task is the shared policy together with their assigned question. Let \(\mu_x\) be the fraction of the cohort assigned question \(x\), with rational masses on support \(S\) of size \(\tau\). The discrete counterpart has \(N\) members, with \(\mu_x=n_x/N\), in a regime where \(N\gg\tau\).
The learner receives passive, independent samples from this society: a question \(x\) and the target’s answer \(\ell_{N^*}(x)\), which is \(1\) exactly when \(N^*\) entails that swap. It must output a proper hypothesis \(\widehat N\in C_{\mathrm{ac}}\) whose mass-weighted error
\[
R_\mu(\widehat N)=\sum_{x\in S}\mu_x\,\mathbf{1}[\widehat N(x)\ne N^*(x)]
\]
is at most \(\epsilon\) with probability at least \(1-\delta\). The problem is to characterize the worst-case number of respondent samples required and determine whether a proper learner can achieve that bound with running time polynomial in the relevant input parameters. A solution is such a learner together with matching or near-matching sample bounds and its running-time classification.
This is a credible learning-theoretic mirror because the paper itself defines PAC learning from examples and uses VCD to assess how many examples learning requires. Theorem 1 gives a concrete prediction: for fixed \(k\), its lower bound is polynomial in \(n\) and \(m\), and standard finite-class bounds give polynomial sample complexity in that regime; for unrestricted indegree, the exact value \(m^n-1\) signals exponentially large worst-case sample requirements as \(n\) grows. I would expect the fixed-\(k\) version to be tractable in sample complexity. The theorem does not establish a polynomial-time proper learner, so that is a separate question rather than a consequence to claim.
The soft spot is that this cohort’s masses describe the distribution of questions, not a heterogeneous population of preference types. The target policy is shared, and the different types arise from assigned survey prompts. The authors should recognize the PAC learning question, but a referee could reasonably judge that this is a weaker population mirror than one in which mass represents different agent preferences. Further questions include whether an efficient proper learner exists and what the tight sample bounds are for intermediate \(k\), where Theorem 1 supplies only a lower bound.
Theorem 1 is a real learning-theoretic result, so I would not dismiss it as merely axiomatic. But its object is a class of possible *single target* CP-nets and the swap examples on which that target is queried. Its VC dimension measures how many example labels the class can realize. The large-cohort mirror changes the distribution of those examples, not the population of preferences: everyone still has the same unknown \(N^*\), while \(\mu_x\) records how many people receive question \(x\). That is a query-sampling distribution, not a society distributed over preference types. Treating the assigned question as part of each respondent’s type makes the setup fit a distributional notation, but does not make question assignments meaningful social differences.
This matters because PAC learning already allows examples to be drawn from a distribution. In the proposed mirror, rational masses over questions restate that sampling model; they add no high-multiplicity axis to Theorem 1. If the task instead charges the mass of respondents queried, the exact membership answers in the paper’s model make the cost degenerate: any positive mass can reveal the same answer, so the infimum mass needed for a query is zero. If it charges per query, it recovers the original query-count problem and the size of the respondent population is irrelevant. Adding noisy or differing answers could make cohort size matter, but that changes the learning model.
A more credible population version would give agents different CP-net preferences, with \(\mu_N\) the fraction holding each type. One could then ask for the aggregate endorsement rate of a swap,
\[
q_\mu(x)=\sum_N \mu_N\,\mathbf{1}[N\text{ entails }x],
\]
or try to recover the distribution \(\mu\). Those are sensible continuous-population questions, but they replace the target concept with a mixture or an aggregate prediction function. Theorem 1’s VCD concerns the former class of individual concepts; it does not classify the complexity of learning mixtures, recovering their masses, or predicting their aggregate labels. Those tasks need their own model and results. The same basic mismatch affects the paper’s teaching and mistake bounds: they count information needed to identify one concept, not a distribution of agents’ concepts.
So the proponent’s framing is the cleanest route from Theorem 1 to a large cohort, and it does not continuize the population in the programme’s sense. The strongest genuine population framing is potentially worthwhile, but it is a new learning problem rather than a continuous mirror of a result in this paper. That is a strong case against this paper as a ChoCo mirror, though not a proof that no useful population-learning model could be built from CP-nets.
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.