Abstract: This paper introduces the Conditional Preference-based Argumentation Framework (CPAF), an extension of Dung’s Abstract Argumentation Framework (AF) that incorporates context-dependent preferences. While traditional AFs and Preference-based AFs (PAFs) handle static conflicts and absolute preferences, they fail to capture the nuanced "if-then" nature of human reasoning. We present a formal semantics for CPAF, demonstrate its superior expressiveness through an "inexpressibility" proof, and show that it maintains the same computational complexity as simpler preference models.
Introduction
Formal argumentation provides a robust mathematical framework for modeling disputes and decision-making. In Dung’s seminal Abstract Argumentation Framework (AF), arguments are nodes in a graph, and attacks are directed edges. Sets of arguments that can be accepted together are determined by various semantics. However, a significant limitation of standard AFs is their inability to handle preferences that change based on the context of accepted arguments.
The Challenge of Conditional Preferences
Consider the "Lunch Menu" problem: a diner prefers red wine over white wine if they are eating meat, but prefers white wine if they are eating fish. In a standard AF, one might attempt to model this by adding attack edges. For instance, an attack from "fish" to "red wine" might be added to ensure that if "fish" is accepted, "red wine" is rejected in favor of "white wine."
As shown in Figure 2, trying to "force" these preferences into the attack graph often leads to counterintuitive results. The authors prove that certain conditional preferences are mathematically inexpressible in standard AFs without losing logical consistency or intended meaning. This necessitates a framework where preferences are treated as first-class citizens alongside attacks.
The CPAF Model
The authors define the Conditional Preference-based Argumentation Framework (CPAF) as a triple $\langle A, \Omega, \Gamma \rangle$. Here, $A$ is the set of arguments, $\Omega$ is the attack relation, and $\Gamma$ is a set of conditional preference rules of the form: $$a_1 > a_2 \leftarrow body$$ This rule states that $a_1$ is preferred to $a_2$ provided the arguments in the body are also accepted.
Key Innovations:
- Selection-based Semantics: CPAF does not modify the underlying attack graph. Instead, it first identifies all valid extensions of the base AF and then uses the conditional preferences as a filter to select the "best" extensions.
- Flat vs. Closed Interpretations: The framework supports both a "Flat" interpretation (rules are literal) and a "Closed" interpretation (accounting for the transitive closure of triggered preferences).
- Well-formedness: To ensure stability, the authors introduce constraints that prevent circular dependencies between preferences and the conditions that trigger them.
Complexity and Expressiveness
A major contribution of this work is the "Inexpressibility" proof, which formally demonstrates that CPAF can represent scenarios that are impossible for standard AFs or PAFs. Despite this increased modeling power, the authors show that CPAF does not incur a "computational penalty." The complexity of the verification problem—checking if a set of arguments is a "best" extension—remains the same as in standard PAFs, ranging from P to $\Pi^p_2$-complete depending on the chosen semantics.
Conclusion
CPAF bridges the gap between rigid logical structures and the nuanced nature of human decision-making. By separating objective evidence (attacks) from subjective desires (conditional preferences), it provides a modular and expressive framework for AI reasoning. Future work will explore dynamic environments and the integration of CPAF with social choice theory for group decision-making.
Summary updated