Admissibility in Strength-based Argumentation: Complexity and Algorithms (Extended Version with Proofs)
This work addresses foundational issues in formal argumentation theory for researchers in AI and logic, though it appears incremental as it builds on existing StrAF frameworks.
The paper tackles the adaptation of admissibility-based semantics to Strength-based Argumentation Frameworks (StrAFs), showing that existing strong admissibility definitions fail to satisfy Dung's fundamental lemma and proposing an alternative definition that corrects this issue. The result includes computational analysis showing similar complexity to standard frameworks and an experimental evaluation demonstrating scalability for computing and enumerating extensions.
Recently, Strength-based Argumentation Frameworks (StrAFs) have been proposed to model situations where some quantitative strength is associated with arguments. In this setting, the notion of accrual corresponds to sets of arguments that collectively attack an argument. Some semantics have already been defined, which are sensitive to the existence of accruals that collectively defeat their target, while their individual elements cannot. However, until now, only the surface of this framework and semantics have been studied. Indeed, the existing literature focuses on the adaptation of the stable semantics to StrAFs. In this paper, we push forward the study and investigate the adaptation of admissibility-based semantics. Especially, we show that the strong admissibility defined in the literature does not satisfy a desirable property, namely Dung's fundamental lemma. We therefore propose an alternative definition that induces semantics that behave as expected. We then study computational issues for these new semantics, in particular we show that complexity of reasoning is similar to the complexity of the corresponding decision problems for standard argumentation frameworks in almost all cases. We then propose a translation in pseudo-Boolean constraints for computing (strong and weak) extensions. We conclude with an experimental evaluation of our approach which shows in particular that it scales up well for solving the problem of providing one extension as well as enumerating them all.