Integrated preferences in logic and abstract argumentation

Abstract

Preferences are an important notion in Artificial Intelligence and many of its subfields such as Knowledge Representation and Reasoning (KR). A key challenge when it comes to preferences (or soft-constraints) in KR is how they can be best represented alongside knowledge about truth (hard-constraints), and what effect they should have in view of the given hard-constraints. In this thesis, we study two KR-formalisms featuring preferences, namely choice logics, which extend classical propositional logic with additional non- classical choice connectives, and abstract argumentation with preferences, where the attack relation between arguments is influenced by a given preference ordering. While choice logics and abstract argumentation are quite different from each other, they have in common that hard- and soft-constraints are tightly interlinked. This motivates us to identify the the notion of integrated preferences, where hard- and soft-contraints are represented and/or resolved jointly instead of separately. To better understand integrated preferences in KR, we examine the syntactic, semantic, and computational properties of choice logics and abstract argumentation with preferences.Regarding argumentation, we consider four so-called preference reductions from the literature and study their effects in two settings. Firstly, we introduce Conditional Preference-based Argumentation Frameworks (CPAFs), a novel formalism capable of expressing and reasoning with conditional preferences in abstract argumentation. We formally study CPAFs, and show that the choice of preference reduction has an impact on the behavior of semantics and the computational complexity of main reasoning tasks. Secondly, we generalize Claim-augmented Argumentation Frameworks (CAFs) by introducing Preference-based CAFs (PCAFs). Since the introduction of preferences to CAFs means that the important property of well-formedness can not be guaranteed, we analyze PCAFs from a syntactic, semantic, and computational perspective to better understand the impact of preferences in claim-based argumentation. Our syntactic analysis shows that some of the structure associated with well-formedness remains intact even after preferences have been resolved. Moreover, our semantic and computational analysis shows that, for some of the preference reductions, advantageous properties associated with well-formedness can still be guaranteed in view of preferences.In choice logics, we study the important notion of preferred model entailment with regards to logical, computational, and proof-theoretic properties. To this end, we consider Qualitative Choice Logic (QCL), Conjunctive Choice Logic (CCL), and Lexicographic Choice Logic (LCL), as well as several preferred model semantics, i.e., methods of determining the preferred models of a choice logic theory. We prove that preferred model entailment for choice logics satisfies key logical properties for non-montonic entailment. Our results also show that the computational complexity of preferred model entailment is located on the second level of the poylnomial hierarchy, with the exact complexity depending both on the choice logic and preferred model semantics. Moreover, we introduce the first sequent calculi for preferred model entailment in choice logics and prove soundness and completeness.Finally, we investigate the relationship between choice logics and abstract argumentation by translating QCL-theories to Argumentation Frameworks with Collective Attacks (SETAFs). We prove that the original QCL-theory is in semantic correspondence to the constructed SETAF, and we show that our translation can be used to decide preferred model entailment in QCL. Moreover, we argue that our construction has advantages compared to an already existing translation from Prioritized QCL-theories to Value-based AFs since it is purely syntactic and polynomial in both size and runtime.