Jean-Guy Mailly

Efficient computation of hard reasoning tasks is a key issue in abstract argumentation. One recent approach is to define approximate algorithms, i.e. methods that provide an answer that may not always be correct, but outperform the exact algorithms regarding the computation runtime. One such approach proposes to use the grounded semantics, which is polynomially computable, as a starting point for determining whether arguments are (credulously or skeptically) accepted with respect to various other extension-based semantics. In this paper, we push further this idea by defining a general family of approaches to evaluate the acceptability of arguments which are not in the grounded extension, neither attacked by it. These approaches rely on gradual semantics to evaluate these arguments. We also propose an approach using an heuristic based on the number of arguments attacked by or attacking an argument, and we show that this last approach, although seemingly different, is actually also an instance of our general family of approaches based on gradual semantics. We have implemented our approaches and provided an empirical study in which we discuss the results and compare our approach with the state-of-the-art approximate algorithms.

Recent advancements in algorithms for abstract argumentation make it possible now to solve reasoning problems even with argumentation frameworks of large size, as demonstrated by the results of the various editions of the International Competition on Computational Models of Argumentation (ICCMA). However, the solvers participating to the competition may be hard to use for non-expert programmers, especially if they need to incorporate these algorithms in their own code instead of simply using the command-line interface. Moreover, some ICCMA solvers focus on the ICCMA tracks, and do not implement algorithms for other problems. In this paper we describe pygarg, a Python implementation of the SAT-based approach used in the argumentation solver CoQuiAAS. Contrary to CoQuiAAS and most of the participants to the various editions of ICCMA, pygarg incorporates all problems that have been considered in the main track of any edition of ICCMA. We show how to easily use pygarg via a command-line interface inspired by ICCMA competitions, and then how it can be used in other Python scripts as a third-party library.

The International Competition on Computational Models of Argumentation (ICCMA) focuses on reasoning tasks in abstract argumentation frameworks. Submitted solvers are tested on a selected collection of benchmark instances, including artificially generated argumentation frameworks and some frameworks formalizing real-world problems. This paper presents the novelties introduced in the organization of the Third (2019) and Fourth (2021) editions of the competition. In particular, we proposed new tracks to competitors, one dedicated to dynamic solvers (i.e., solvers that incrementally compute solutions of frameworks obtained by incrementally modifying original ones) in ICCMA’19 and one dedicated to approximate algorithms in ICCMA’21. From the analysis of the results, we noticed that i) dynamic recomputation of solutions leads to significant performance improvements, ii) approximation provides much faster results with satisfactory accuracy, and iii) classical solvers improved with respect to previous editions, thus revealing advancement in state of the art.

Timed Argumentation Frameworks (TAFs) allow taking into account the availability of arguments and attacks in abstract argumentation. We propose a new reasoning approach for TAFs, where a standard Dung-style AF can be associated with each timepoint. We show that, although this framework is more expressive than Dung’s framework, our approach does not lead to an increase in computational complexity for most reasoning problems and classical extension-based semantics.

Assumption-Based Argumentation (ABA) is a prominent formalism for structured argumentation, widely applied in domains such as healthcare, law, and robotics. Despite its inherent computational complexity, ABA has seen the development of effective techniques that successfully address key tasks, including evaluating the acceptability of literals and computing framework extensions. These approaches typically involve translating the initial ABA framework into an intermediate formalism, such as an Answer Set Program or an Abstract Argumentation Framework, which is then encoded into a Boolean satisfiability (SAT) problem. However, this translation can lead to large and complex intermediate representations, posing challenges for state-of-the-art SAT solvers. In this work, we propose a Counterexample-Guided Abstraction Refinement (CEGAR) approach that bypasses the initial translation step, at the cost of incrementally discovering certain ABA constraints that are not explicitly captured in the initial SAT encoding. We analyze the performance of our method and demonstrate that it outperforms state-of-the-art approaches on specific problem classes, while remaining competitive with the best existing solvers more broadly.

Automated negotiation aims at finding agreements between agents with conflicting goals. Existing utility-based approaches guarantee agents satisfaction with negotiation outcomes, especially in multi-issue negotiations where concession mechanisms lead to win-win results. However, they lack explainability and do not consider agents’ beliefs. On the other hand, argument-based approaches provide reasons for accepting or rejecting offers but do not include utility modeling for offers or enable concession mechanisms in multi-issue settings. We propose a novel hybrid approach combining both types of approaches. The utility-based component enables agents to make concessions on complex negotiation objects to achieve win-win outcomes, while the argumentation component ensures that accepted offers align with the agents’ personal argumentation theories. These theories represent their beliefs, encoding various profiles, ethical considerations, social norms, or legal principles.

We propose the combination of two known extensions of Dung’s abstract Argumentation Frameworks (AFs): Incomplete Argumentation Frameworks (IAFs), where the existence of arguments and attacks may be uncertain, and Higher-Order Argumentation Frameworks (HOAFs), where attacks can be directed not only towards arguments but also towards attacks. As a result, we obtain Incomplete Higher-Order Argumentation Frameworks (IHOAFs), where attacks on attacks can also be uncertain. We take some important initial steps in the formal understanding of this novel framework by providing: (i) the definition of a conservative notion of completion, the hypothetical removal of uncertainty used to reason about argument acceptability in other formalisms for incomplete argumentation; (ii) complexity results for argument acceptability problems; (iii) an analysis of the previous two points in a well-behaved variant of dynamic logic.

In the realm of abstract argumentation, Incomplete Argumentation Frameworks (IAFs), i.e. argumentation frameworks such that some arguments and attacks can be uncertain, have received much attention in the last decade. The most classical reasoning approach consists in using completions, which are argumentation frameworks representing all the possible ways to decide about the actual existence of the uncertain elements. Standard decision problems (like verifying whether a set of arguments is acceptable) can be adapted in two variants: verifying whether the property of interest holds for some completion, or for each completion. In this setting, all completions represent equally plausible scenarios for the agent, which is not always a realistic hypothesis in real world situations. In this paper, we propose IAFs with Plausibility (pIAFs), a generalization of the IAF model where the agent is able to reason about the relative plausibility of completions. We study the complexity of the usual decision problems of IAFs, adapted to this new model. We also introduce new decision problems concerning the relative plausibility of extensions and provide complexity upper bounds for these new problems as well.