Abstract
This paper introduces the Incremental-Improvement Approach (IIA), a powerful new framework for representing preferences over sets of items. By defining "atomic" improvements—such as gaining, losing, or trading an element—the authors create a language that is more expressive than traditional set-ordering methods and more concise than standard CP-nets. The framework specifically addresses long-standing issues in selecting optimal arguments within AI argumentation frameworks.
Introduction
In many AI applications, agents must choose between different collections of items, whether they are sets of beliefs, bundles of goods, or groups of winning arguments. However, for a universe of $n$ items, there are $2^n$ possible subsets, making an explicit ranking of every subset computationally impossible for even modest values of $n$.
The standard workaround involves taking a preference ranking of individual items and "lifting" it to the level of sets using classical methods like Hoare or Smyth orderings. However, these methods are often too rigid; for instance, they may force a preference for a larger set even when it is undesirable. Furthermore, existing tools like CP-nets (Conditional Preference networks) are designed for objects with fixed attributes, making them awkward for "atomic" entities without internal structure.
The Incremental-Improvement Approach (IIA)
The authors propose the Incremental-Improvement Approach (IIA) as a centerpiece for bridging this gap. Instead of ranking sets directly, the user specifies rules for "elementary modifications":
- Gaining ($g$): Adding an item to the set.
- Losing ($l$): Removing an item from the set.
- Trading ($t$): Swapping one item for a more preferred one.
These rules can be conditional (e.g., "I want to add item $a$ only if I already have item $b$"). A set $E$ is preferred over $E'$ if there exists a sequence of these "improving flips" that transforms $E'$ into $E$. This approach treats "trading" as a first-class citizen, whereas CP-nets require cumbersome encoding to simulate such swaps.
Application to Argumentation Frameworks
A significant contribution of this work is its application to Argumentation Frameworks (AFs). Previous methods attempted to handle preferences by deleting "attacks" between arguments in a graph, which often led to unintended results. The authors propose keeping the argumentation graph intact and using IIA to select the best set of arguments after the standard logic has run.
As shown in Figure 1, complex relationships between arguments (represented as nodes $a, b, c, d$) can create scenarios where traditional methods find different sets of arguments identical. IIA successfully distinguishes between these sets, resolving known failure cases in preference-based argumentation.
Key Results and Complexity
The authors provide several formal proofs regarding the power and efficiency of IIA:
- Expressive Equivalence: IIA can represent all Hoare and Smyth orderings. While IIA and CP-nets are equivalent in power, IIA is significantly more concise for set-based problems.
- Computational Complexity: Determining if one set is better than another (the dominance problem) in IIA is PSPACE-complete, matching the complexity of CP-nets. However, for restricted cases where each element changes status only once, the complexity drops to NP.
- Predicate Generalization: The authors extend IIA to use predicate logic, allowing preferences to refer to relations between items (e.g., "Trade any element $X$ for a $Y$ that is better than everything currently in the set").
Conclusion
While the PSPACE-completeness of the dominance problem presents a challenge for real-time applications, the IIA framework provides a much-needed flexible language for set preferences. Future work will focus on identifying "tractable fragments"—specific types of preference rules that are easier to compute—and applying the framework to Answer Set Programming (ASP), where selecting between multiple valid answers is a frequent requirement.
Summary updated