Answer: Every cohort's minimal representation is identifiable with total queries and learner running time polynomial in \(n,\tau,S,L\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe class CACY is attribute-efficiently learnable from equivalence and membership queries over swaps: any concept ≻in CACY can be identified in polynomial time, using at most |N ∗| + 1 equivalence queries and e⌈log n⌉member- ship queries, where N ∗is the minimal representation of ≻, and e is the number of edges in N ∗.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) Boolean attributes and \(\tau\) addressable preference-homogeneous cohorts with known rational masses \(\mu_g>0\) summing to \(1\), each with its own unknown acyclic CP-net, can a learner identify every cohort's minimal representation using cohort-specific equivalence queries and swap membership queries, with total query and running-time bounds polynomial in \(n\), \(\tau\), the total representation size, and the mass bit length \(L\)?
A society is given by its support: a list of \(\tau\geq1\) addressable preference types with positive binary rational masses \(\mu_g\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total mass bit length, and \(m=n\geq1\) is the number of Boolean attributes. Cohort identities and masses are known; preferences are accessible only through queries.
Each cohort's unknown preference relation is represented by an acyclic CP-net on a subset of the attributes. Tables are explicit and possibly incomplete: for each assignment to a node's entire parent set, there is at most one strict preference between its two values. Missing entries authorize neither direction of a flip; omitted attributes have no authorized flips. Dominance is reachability by a nonempty sequence of improving flips.
For a rule \(r=(t:p\succ\bar p)\), let \(|r|=|t|+2\), and let \(|N|=\sum_{r\in N}|r|\). A minimal representation minimizes this size among acyclic CP-nets inducing the same full dominance relation. Write \(N_g^*\) for such a representation and \(S=\sum_g|N_g^*|\).
A swap is an ordered pair of complete outcomes differing in exactly one attribute. A membership query addressed to \(g\) returns whether its first outcome dominates its second. An equivalence query addressed to \(g\) submits an explicit acyclic CP-net and returns Yes exactly when the full dominance relations coincide, otherwise an arbitrary swap on which they disagree. Answers are exact; each oracle call costs one query, and oracle computation is excluded from learner running time.
Can every cohort's minimal representation be identified with total queries and learner running time polynomial in \(n,\tau,S,L\), or is this identification problem NP-hard in the stated oracle model?
For one target, exact learning is polynomial-time with at most \(|N^*|+1\) equivalence queries and \(e\lceil\log_2 n\rceil\) membership queries, where \(e\) counts edges; equivalence queries alone do not suffice even for complete acyclic targets ([Koriche–Zanuttini](https://www.ijcai.org/Proceedings/09/Papers/319.pdf)).
Nearby population work learns an aggregate CP-net from noisy preferences rather than identifying each addressable type ([Labernia et al.](https://fabien.labernia.fr/media/recherche/cp-net_da2pl.pdf)); no source located explicitly treats this mass-supported identification problem.
Every cohort’s minimal representation can be identified with total queries and learner running time polynomial in \(n,\tau,S,L\).
The addressability of cohorts allows independent learning. The point requiring care is that exact identification of a dominance relation must yield a representation of minimum size. We prove that this minimization is polynomial-time for the explicit tables in the question.
Let \(N\) be an acyclic CP-net. An authorized improving flip changes one attribute according to an applicable table entry.
Lemma 1. If outcomes \(a,b\) differ only on attribute \(x\), then \(a\) dominates \(b\) exactly when the flip from \(b\) to \(a\) is authorized directly by \(N\).
Proof. An authorized flip is itself a nonempty improving sequence, proving one direction.
Conversely, suppose an improving sequence leads from \(b\) to \(a\). Fix a topological ordering of the dependency graph, extending it to all attributes by treating omitted attributes as isolated. Let \(y\) be the first attribute in this ordering that changes anywhere in the sequence. No parent of \(y\) changes, so its parent context remains constant. In that context, its table authorizes at most one strict direction. Thus \(y\) changes exactly once and has different initial and final values.
Because the endpoints differ only on \(x\), we have \(y=x\). Consequently, no parent of \(x\) changes. The sequence’s flip of \(x\) therefore occurs under the same parent assignment as in \(b\), and its direction is from \(b(x)\) to \(a(x)\). That flip is authorized directly. \(\square\)
It follows that two acyclic CP-nets agree on every ordered swap exactly when their authorized improving-flip edges agree. Their full dominance relations are the nonempty transitive closures of these edges, so they also agree on every pair of outcomes.
In particular, whenever two full dominance relations differ, some swap witnesses the difference. The equivalence oracle specified in the question is therefore well-defined.
For each attribute \(x\), define its local preference function on assignments \(z\) to all other attributes:
\(f_x(z)\in\{+,-,0\}\).
Here \(+\) means that changing \(x\) from zero to one is authorized, \(-\) means that the reverse change is authorized, and \(0\) means that neither direction is authorized. The tables’ consistency ensures that these states are mutually exclusive. Lemma 1 shows that the full dominance relation determines every \(f_x\).
A coordinate \(y\ne x\) is essential for \(f_x\) if two contexts differing only on \(y\) have different function values. Write \(R_x\) for the set of essential coordinates.
Lemma 2. The function \(f_x\) depends only on \(R_x\), and every parent set representing \(f_x\) contains \(R_x\).
Proof. Changing an inessential coordinate leaves the function value unchanged, by definition. Two contexts agreeing on \(R_x\) can be connected by changing their other coordinates one at a time. Hence their function values agree.
If a representation has parent set \(P_x\), its local preference depends only on \(P_x\). Changing a coordinate outside \(P_x\) cannot affect it, so every essential coordinate belongs to \(P_x\). \(\square\)
Construct a CP-net \(C\) on all attributes as follows. Give \(x\) parent set \(R_x\). For each assignment to \(R_x\), include the corresponding strict preference entry when \(f_x\) is nonzero, and leave the entry missing otherwise.
This construction is well-defined by Lemma 2. Moreover, its graph is a subgraph of any acyclic representation of the target relation, since every such representation contains each essential-parent edge. Thus \(C\) is acyclic. It has the same authorized flips as the target and consequently the same full dominance relation.
Lemma 3. The representation \(C\) has minimum size.
Proof. Let \(Q\) be any equivalent acyclic representation. Consider an attribute \(x\) for which \(f_x\) is not identically zero. Such an attribute cannot be omitted from \(Q\). Let \(P_x\) be its parent set in \(Q\), and let \(k_x\) count assignments to \(R_x\) at which \(f_x\) is nonzero.
By Lemma 2, \(R_x\subseteq P_x\). For each of these \(k_x\) assignments, all of its \(2^{|P_x|-|R_x|}\) extensions to \(P_x\) must have the prescribed strict preference entry in \(Q\). An extension of an assignment where \(f_x=0\) must have a missing entry. Therefore the table’s contribution to the size of \(Q\) is exactly
\(k_x\,2^{|P_x|-|R_x|}(|P_x|+2)\).
Its contribution in \(C\) is
\(k_x(|R_x|+2)\).
The former is at least the latter. Attributes with identically zero local preference contribute zero in both representations. Summing over attributes gives \(|Q|\ge |C|\). \(\square\)
This proves minimum size, as required. Uniqueness of the graph is unnecessary: adding unused nodes or edges into empty tables can leave the specified size unchanged.
Suppose an explicit acyclic representation \(H\) of the target relation has been learned. We can compute the sets \(R_x\) from its sparse tables without enumerating all parent assignments.
For a table on \(x\) with parent set \(P_x\), store its listed assignments and directions in a dictionary, with a missing key interpreted as state \(0\). For each \(y\in P_x\) and each listed assignment \(u\), compare its direction with the state at the assignment obtained by changing only \(y\).
This detects essentiality exactly:
Coordinates outside \(P_x\) are inessential. After computing \(R_x\), project each listed row onto \(R_x\) and remove duplicate rows. Lemma 2 ensures that rows with the same projection have the same direction. The resulting table is exactly the table used in \(C\).
If a table has \(k\) listed rows and \(d\) parents, this procedure makes at most \(kd\) dictionary comparisons. Each comparison and projection operates on strings of length at most \(n\). Thus minimization takes polynomial time in \(n\) and the explicit encoding length of \(H\). By Lemma 3, its output has globally minimum size.
Empty tables and omitted attributes cause no difficulty: retain all attributes if desired and assign empty tables where no flips are authorized.
The single-target theorem supplied in the question states that an acyclic Boolean CP-net dominance relation can be identified in polynomial learner time using at most \(|N^*|+1\) equivalence queries and \(e\lceil\log_2 n\rceil\) membership queries over swaps. Its scope includes incomplete tables and networks on subsets of the attributes. See [Koriche–Zanuttini, Theorem 2](https://www.ijcai.org/Proceedings/09/Papers/319.pdf).
Its hypotheses match the present model:
Lemma 1 also establishes that equivalence on swaps coincides with equivalence of full dominance relations. Oracle computation is excluded from learner time, exactly as required here.
For each cohort \(g\), run this learner using queries addressed to \(g\), then apply the polynomial minimization procedure above. Write \(s_g=|N_g^*|\). For the edge parameter \(e_g\), choose the minimum representation constructed in Section 2.
Every node with a nonempty table has at least one row, so
\(e_g=\sum_x |R_{g,x}|\le \sum_x k_{g,x}(|R_{g,x}|+2)=s_g\),
where empty tables have \(R_{g,x}=\varnothing\). Consequently, the total query bounds are
\(Q_{\mathrm{EQ}}\le \sum_g(s_g+1)=S+\tau\),
and
\(Q_{\mathrm{MQ}}\le \left(\sum_g e_g\right)\lceil\log_2 n\rceil\le S\lceil\log_2 n\rceil\).
These bounds include \(n=1\), when no parent discovery is needed, and cohorts whose dominance relation is empty.
To check learner time, let \(p(n,s)\) be a nondecreasing polynomial upper bound for one cohort’s learning and subsequent minimization. Such a bound exists because the learner runs in polynomial time and therefore produces an explicitly encoded hypothesis of polynomial length. Since \(s_g\le S\),
\(\sum_g p(n,s_g)\le \tau\,p(n,S)\).
Reading the known masses adds time polynomial in \(L\). No query complexity depends on their magnitudes: every positive-mass cohort is directly addressable.
Thus the polynomial-time alternative is established in the stated oracle model. This conclusion does not require an efficient implementation of the equivalence oracle.
⟨structured verdict parsed — rendered above⟩
The argument resolves the task. Its minimization proof is correct, and the cited learning theorem applies to the stated oracle model. I found no mathematical gaps or false steps.
Lemma 1 is valid.
For the converse, the improving sequence is nonempty, so some attribute changes. The earliest such attribute \(y\) in a topological ordering has no parent that changes anywhere in the sequence. Its parent assignment therefore stays fixed.
Under that fixed assignment, the table authorizes at most one direction. Since \(y\) is Boolean, it can change only once: a second change would require the reverse direction. Thus its initial and final values differ. As the endpoints differ only on \(x\), necessarily \(y=x\).
It follows that no parent of \(x\) changes. The sequence contains an authorized flip of \(x\) under its initial parent assignment, in precisely the direction from \(b(x)\) to \(a(x)\). This proves the claimed direct authorization.
Missing entries do not invalidate this reasoning: an attribute that actually changes must have an applicable entry. Omitted attributes cannot change.
Consequently, equality on ordered swaps is equality of authorized flip edges. Taking their nonempty transitive closures gives equality of full dominance relations. The claimed availability of a swap counterexample is therefore justified.
The three-valued local function \(f_x\) is well-defined. At any fixed context, the explicit table authorizes either one direction or neither direction. Lemma 1 establishes that the dominance relation determines this function.
Lemma 2 correctly proves both assertions:
The construction of \(C\) is therefore well-defined. Every edge entering \(x\) in \(C\) occurs in any equivalent acyclic representation. Hence \(C\) is acyclic. It preserves every local function, and therefore every authorized flip and the full dominance relation.
Lemma 3 correctly uses the requirement that rows specify the entire parent assignment. For any equivalent representation \(Q\), each nonzero assignment on \(R_x\) requires exactly \(2^{|P_x|-|R_x|}\) nonzero rows on \(P_x\). Assignments whose local state is zero require missing entries.
Thus the stated contribution
\[
k_x\,2^{|P_x|-|R_x|}(|P_x|+2)
\]
is exact. Since \(R_x\subseteq P_x\), it is at least \(k_x(|R_x|+2)\). Summation proves global minimum size, rather than merely minimality under deletion of rules or edges.
Identically zero functions contribute no rules. The observation that unused nodes or edges into empty tables can preserve size is also correct; uniqueness of the encoded graph is unnecessary.
The sparse-table essentiality test is correct.
Every essentiality witness consists of two parent assignments differing only on one coordinate and having unequal states. At least one state must be nonzero, so at least one assignment appears among the listed rows. Inspecting each listed row and its single-coordinate neighbors therefore detects every essential parent.
Projection onto \(R_x\) is valid by Lemma 2. Equal projections have equal states, and every nonzero reduced context appears as the projection of a listed row. Removing duplicate projected rows consequently produces exactly the required reduced table.
The procedure performs at most \(kd\) dictionary lookups for a table with \(k\) rows and \(d\) parents. Key manipulation and dictionary operations have polynomial cost in the explicit input length. No exponential enumeration of missing contexts is required.
The citation is applicable. The paper defines Boolean CP-nets on subsets of attributes, permits incomplete tables with at most one rule per full parent assignment, and uses dominance membership queries and equivalence queries with counterexamples from the instance class. Theorem 2 supplies polynomial-time identification with the stated equivalence and membership query bounds over swaps. Its accompanying invariant ensures acyclic hypotheses. These match the required oracle interface. [Koriche–Zanuttini, definitions and Theorem 2](https://www.ijcai.org/Proceedings/09/Papers/319.pdf).
The distinction between full-relation equivalence and swap counterexamples is fully handled by Lemma 1.
Applying the learner to an essential-parent minimum representation is legitimate because the oracle exposes the dominance relation, independently of which equivalent representation is selected for analysis.
The bound \(e_g\le s_g\) is correct. Every nonempty reduced table has \(k_{g,x}\ge1\), and an identically zero function has no essential parents. Hence every edge is accounted for by the displayed size bound.
Summing the individual query bounds gives exactly
\[
Q_{\mathrm{EQ}}\le S+\tau,\qquad
Q_{\mathrm{MQ}}\le S\lceil\log_2 n\rceil.
\]
The edge cases are covered:
The running-time argument is valid: polynomial learning time bounds the explicit hypothesis length, and the subsequent minimization is polynomial in that length and \(n\). Summing a nondecreasing polynomial bound across \(\tau\) cohorts remains polynomial in \(n,\tau,S\). Reading masses contributes polynomial time in \(L\); their magnitudes do not affect addressable preference queries.
No additional clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.