| paper | d4-conf-ijcai-2021-0071 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 16
statement extracted from the paper’s text layer
Given a common finite argument set \(A\) and a finite support \(T\), each type \(t\) supplies a framework \(AF_t=(A,R_t)\), a query \(q_t\), \(P_t=PSC(AF_t)\), and a positive binary-rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Compute exactly \(M=\sum_{t\in T}\mu_t\mathbf{1}[q_t\in E_{\mathrm{id}}(AF_t)]\).
The population consists of caseholders grouped by complete case type \(t=(AF_t,q_t,P_t)\), with mass \(\mu_t\). For each type, compute \(E_{\mathrm{id}}(AF_t)\) from its supplied \(P_t\), then sum the masses whose query belongs to that ideal extension. Proposition 16 yields polynomial-time per-type computation, followed by exact rational aggregation.
The population acts only at the reporting layer: each type’s acceptance is computed independently, and its \(P_t\) is supplied.
fatal: False
Covers conditional ideal-extension extraction and the mass-weighted share of accepted queries across case types; leaves the paper’s skeptical-acceptance characterization, CDAS algorithm, computation of the super-cores, and experimental comparisons outside the mirror.
The positive case is narrow: it is a batch version of one polynomial-time subproblem in the paper, rather than a continuization of its central skeptical-acceptance result.
My lead anchor is Proposition 16, proved in this paper: *given the preferred super-core \(PSC(AF)\), the ideal extension \(E_{\mathrm{id}}\) can be computed in polynomial time*. The condition matters: this is a result about extracting the ideal extension once the super-core is known, not a polynomial-time result for computing it from an arbitrary framework. The paper’s central Theorem 11 characterizes skeptical acceptance, and Theorem 12 proves the CDAS algorithm sound and complete; neither states a complexity classification of the kind required for an anchor. The \(\Pi^P_2\)-completeness claim in the introduction is attributed to earlier work and is not a numbered result of this paper.
Ideal-Extension Share over Typed Cases. An instance has a common finite argument set \(A\), and a support \(T\) of \(\tau\) case types. Each type \(t\) consists of an argumentation framework \(AF_t=(A,R_t)\), a query argument \(q_t\), and its preferred super-core \(P_t=PSC(AF_t)\), supplied as part of the instance. Its mass \(\mu_t\) is a positive binary rational, with \(\sum_{t\in T}\mu_t=1\). The question is to compute the exact fraction
\[
M=\sum_{t\in T}\mu_t\,\mathbf{1}\!\left[q_t\in E_{\mathrm{id}}(AF_t)\right].
\]
A solution can give each type’s ideal extension and the resulting rational \(M\); equivalently, for a supplied rational threshold \(\rho\), it can answer whether \(M\geq\rho\).
Here the population is people whose cases are assessed using argumentation, such as applicants appealing the same kinds of standardized decisions. Many people may have cases with the same complete framework and query, while the number of distinct templates \(\tau\) is modest. Type membership captures everything relevant to this question: holders of a type have the same attack relation, query, and supplied super-core. The mass is their share of the population. Proposition 16 gives a polynomial-time computation for each type, followed by exact rational aggregation, so this mirror is tractable in \(|A|\), \(\tau\), and the input bit length. It is a Class A style result, though the tractability comes directly from the paper’s conditional polynomial-time result; the aggregation itself adds no new optimization structure.
The scope is deliberately limited to ideal-extension extraction from a supplied preferred super-core. It does not mirror the paper’s main question of skeptical acceptance, and it does not claim that continuization changes that question’s complexity.
The weak point is that this is a population of cases, not a continuous population inside one argumentation framework. It asks for the share of caseholders whose query is in the ideal extension of their case’s framework. That is a plausible batch application of the authors’ computation, but a referee could reasonably regard it as aggregating repeated instances rather than a continuous analogue of the paper’s central reasoning problem. Requiring the super-core as input narrows the mirror further. I would defend it as a modest, recognizable application of a named result—not as evidence that the paper’s main complexity story changes in the continuum.
Proposition 16 is a genuine named result: given \(PSC(AF)\), the ideal extension can be computed in polynomial time. So I would not dismiss the anchor on the ground that the paper has no computational result. The problem is what its proposed population makes that result compute.
In “Ideal-Extension Share over Typed Cases,” each type is a separate framework and query. The output is a statistic over independent instances, not the ideal extension or skeptical acceptance of one shared framework. That could be useful for reporting outcomes across a caseload, but it is a distribution over problem instances. Supplying \(PSC(AF_t)\) for every type also conditions the task on a derived property of each framework; without those super-cores, the proposal has not mirrored the work needed to determine the cases’ outcomes. Applying Proposition 16 once per type and summing the answers is a batch use of the result, rather than a continuous-population version of the paper’s reasoning problem.
The better single-framework mirror would assign mass to a population of people who contribute, endorse, or instantiate arguments in one common debate, then ask what share of that mass falls within the ideal extension. But abstract argumentation represents arguments as vertices, with attacks between them; it does not represent their proponents or how many people hold them. If people with the same argument role are collapsed into types, their masses do not affect conflict-freeness, defense, or maximality. The ideal extension is found on the type-level attack graph, and the share is then a weighted sum. If instead mass is meant to affect which arguments are accepted, that calls for a mass-sensitive semantics beyond the one Proposition 16 computes.
This leaves an awkward choice. Treat people’s cases as separate frameworks, and the proposal becomes a distribution over independent instances. Treat arguments as the population, and the weights measure support for graph vertices without entering the paper’s semantics. In neither case does the population become the object the paper reasons about. A more elaborate story about repeated argumentation templates does not fix that mismatch: repeated templates still form graph instances or argument roles, not a population whose distribution governs ideal acceptance.
That is a strong objection to this anchor, but not an airtight universal case. A caseload share could be a sensible deployment question, and the authors might recognize it as an application of their algorithm. The negative case is strongest if “continuous mirror” means a population-level computational problem within one argumentation framework; it is weaker if aggregating many independent decision instances counts.
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.