Learning attack relations in abstract argumentation from extension examples

Abstract

We study an inverse problem for Dung abstract argumentation. A finite argument set $A$, $|A|=n$, is fixed, an attack relation is unknown, and each observation labels a candidate subset $S\subseteq A$ according to whether it is an extension under a chosen semantics. We formulate prediction from such extension-membership examples in the realizable probably approximately correct model and separate information-theoretic generalization from the computational task of finding a compatible relation. For every extension-based semantics, the Vapnik–Chervonenkis (VC) dimension of the induced hypothesis class satisfies $\operatorname{VC}(\mathcal{H}_\sigma )\le n(n-1)$ under our default irreflexive convention ($n^{2}$ if self-attacks are allowed). For the conflict-free semantics, we prove the exact value $\choose n2$ in the irreflexive case and $\max \{n,\binom n2\}$ when loops are allowed. We also characterize conflict-free observational equivalence and obtain the exact number of distinct loop-allowed classifiers. For the admissible, stable, complete and preferred semantics, an explicit directed gadget yields $\operatorname{VC}(\mathcal{H}_\sigma )\ge \lfloor n/3\rfloor ^{2}$, so their dimensions are $\varTheta (n^{2})$. Bounded in-degree gives sparsity-sensitive upper and lower bounds; below the dense threshold they differ by at most a logarithmic factor. Computationally, we give a direct polynomial-time characterization and witness construction for the conflict-free consistency problem, and self-contained polynomial-size Boolean satisfiability encodings for the admissible and stable consistency problems. These encodings are a zero-loss specialization of earlier argumentation-framework synthesis work rather than a replacement for it. Finally, we formalize noisy observations through agnostic risk and show how one relaxation variable per example turns the encodings into weighted partial maximum satisfiability instances that minimize example-level empirical $0$–$1$ loss. Worked examples, diagrams, convention tables and full proofs make explicit what can be predicted, what cannot be identified and where the statistical and computational claims differ.