| paper | d4-conf-aaai-2026-2027 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Exact computation is NP-hard for every fixed \(\sigma\in\{\mathrm{gr},\mathrm{co},\mathrm{pr},\mathrm{st}\}\), even with \(\tau=1\) and no attacks or supports. A polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite list of types \(t\), binary rational masses \(\mu_t\) summing to \(1\), a shared argument set \(A\), a goal \(g\in A\), a semantics \(\sigma\), and for each type a CPBAF \(\Delta_t\) with world probabilities \(I_t\) and a fixed extension-selection distribution \(\rho_t(E\mid w)\), compute \(M^\sigma(g)=\sum_t\mu_t\sum_{w\in pw(\Delta_t)}I_t(w)\sum_{\substack{E\in\sigma(w)\g\in E}}\rho_t(E\mid w)\).
A society is a finite-support distribution \(\mu\) over complete CPBAF profiles sharing an argument vocabulary and goal. Each type retains its own within-agent world uncertainty and extension-selection rule; the target is the population mass whose selected extension accepts \(g\).
The mirror covers probabilistic acceptance and explanation-based acceptance, including exact hardness and the stated approximation results. It leaves the paper’s argumentation semantics, explanation properties, and probability elicitation questions unchanged.
I see a narrow but credible mirror: a large deliberation platform running argumentation models for many stakeholders. Everyone reasons over the same issue and goal argument \(g\), but stakeholders fall into a modest number \(\tau\) of complete evidence and reliability profiles. A type \(t\) specifies its full CPBAF \(\Delta_t\), including its arguments, attacks, supports, conditional probabilities, and extension-selection rule. Agents of that type are identical in every respect the query uses. The rational mass \(\mu_t\) is their fraction of the population, with \(\sum_t\mu_t=1\).
There are two distinct distributions here. The mass \(\mu_t\) describes the population. Within a type, \(I_t(w)\) describes the probability of a possible argumentation world, and \(\rho_t(E\mid w)\) describes how an extension is selected for that world. For explanation-based acceptance, \(\rho_t\) is the paper’s explanation-based distribution. The population quantity is
\[ M^\sigma(g)=\sum_{t}\mu_t \sum_{w\in pw(\Delta_t)} \sum_{\substack{E\in\sigma(w)\\g\in E}} I_t(w)\rho_t(E\mid w). \]
It is the mass of agents whose selected extension accepts \(g\), or equivalently the expected fraction accepting \(g\) in a large cohort. This is an evaluation problem, so it has no intervention variable or optimization objective: its solution is the value \(M^\sigma(g)\). The input lists the \(\tau\) profiles and their binary rational masses; relevant parameters include \(m=|A|\), \(\tau\), the total profile-description size, and the bit length \(L\).
A plausible regime is a large online policy consultation with a shared argument vocabulary and common public sources, where many participants share standardized evidence and reliability profiles. There could be hundreds of profiles among hundreds of thousands of participants. This is a scenario, not a claim that every argumentation application has high multiplicity.
My lead is Cohort Probabilistic Acceptance, the exact computation of \(M^\sigma(g)\) for a listed cohort and a fixed extension-selection rule. Its anchor is Theorem 3, proved in this paper: for each \(\sigma\in\{gr,co,st,pr\}\), computing \(\Pr A[\sigma]\) is FP\(\#\)P-hard, even for acyclic CPBAFs and for any chosen PDF over extensions. The mirror is precise: set \(\tau=1\) and \(\mu_t=1\), and the cohort answer is exactly the paper’s \(\Pr A[\sigma]\) answer. Thus this is a Class B mirror: the paper’s hardness carries over, already at a single type. That reduction also explains why the mirror is substantive despite its narrow scope: it asks whether the acceptance computation remains hard when read as an acceptance rate in a high-multiplicity population.
A distinct question is Relative Cohort Acceptance Estimation: given the same listed cohort, return \(\hat M\) such that \(\Pr(|\hat M-M^\sigma(g)|\leq\epsilon M^\sigma(g))\geq 1-\delta\), in time polynomial in the input size, \(1/\epsilon\), and \(\ln(1/\delta)\). Its anchor is Theorem 4, proved in this paper: unless \(\mathrm{NP}\subseteq\mathrm{BPP}\), no FPRAS exists for \(\Pr A[\sigma]\), for any \(\sigma\in\{gr,co,st,pr\}\), even on acyclic CPBAFs. Again, the single-type cohort is the original problem, so this is Class B hardness transfer. It marks a useful boundary for the population question: estimating a very small accepting share with relative error can remain hard even when additive estimation is possible in a restricted setting.
The positive algorithmic companion is Additive Explanation-Based Cohort Acceptance. Its instance is the same explicit list of profiles, but each profile uses the paper’s explanation-based PDF; the question is to return \(\hat M\) with \(\Pr(|\hat M-M^\sigma(g)|\leq\epsilon)\geq1-\delta\). The anchor is Theorem 6, proved in this paper: \(\Pr E[\sigma]\) has an FPARAS when \(\sigma=gr\), or when \(\sigma\in\{gr,co,st,pr\}\) and the input CPBAF is odd-cycle-free. For a cohort, require that restriction for every type. Sampling a type by \(\mu_t\), then a world and explanation as in the paper’s algorithm, gives a sample whose acceptance indicator has mean \(M^\sigma(g)\); additive sampling estimates that mean. This is Class A in the stated regime. Further questions include which structural parameters of the argumentation graph or conditional-dependency graph permit tractable exact computation, and how approximation behaves for cohorts mixing odd-cycle-free and unrestricted profiles.
The mirror covers the paper’s acceptance computations, especially \(\Pr A[\sigma]\) and \(\Pr E[\sigma]\). It does not try to continuize the argumentation semantics, the explanation definitions, or probability elicitation. Nor does it treat the paper’s existing world probabilities as the population mass: uncertainty within each agent type remains part of the model, while \(\mu\) describes the distribution of people.
The weakest point is that the paper frames uncertainty over possible worlds of an argumentation framework, not variation across a population. In the proposed scenario, each stakeholder’s acceptance rate is computed from that internal uncertainty and the extension-selection rule. The authors might regard the outer cohort as an application layer around their problem rather than a new question they set out to study. The single-type hardness anchor makes the relationship exact, but also exposes that limitation: the population can be highly numerous while adding no new complexity. I still think the mirror is defensible because it gives a concrete high-multiplicity interpretation and a precise aggregate quantity, while making clear that the paper’s main computational challenge lies within each type.
The strongest negative case is that the proposed cohort sits outside the paper’s computational object. CPBAF has one framework; its probabilities describe uncertainty about that framework’s possible worlds, and its explanation rule distributes probability over extensions. Turning each complete CPBAF into a “person type” adds an outer population average, but the paper does not model people who deliberate together or a collective decision made from their responses.
That objection reaches Theorem 3’s Cohort Probabilistic Acceptance and Theorem 4’s relative approximation question in the same way. Their inputs are lists of separate inference problems with weights. The population layer combines their answers; the hard computation remains inside each framework. Even the proponent’s improved version—one shared issue and argument vocabulary, with types differing only in their conditional probabilities—still averages individual acceptance probabilities. That could be useful as a survey statistic, but it is a new application layer rather than a population problem the paper itself formulates.
Theorem 6 gives the strongest apparent mirror: sample a type, a world, and an explanation, then estimate the expected accepting share. But that construction inherits the paper’s explanation sampler and adds no interaction among the masses. The resulting additive estimate is a natural way to report a cohort statistic, yet its tractability comes from the per-framework sampling procedure; the continuous population contributes only the weights.
This case is not decisive. The program’s gate is whether the authors would recognize the population question as theirs, and a deliberation platform reporting what fraction of stakeholders accept a shared goal argument is plausible. The proponent also cleanly separates population mass from uncertainty within each type. I cannot honestly claim to have defeated that best version: the objection is that the mirror is an outer aggregation of the paper’s problem, not that the aggregate is incoherent or impossible. The negative case is therefore weak against the stated burden.
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.