Introduction
In the field of Artificial Intelligence, representing and reasoning about an agent's preferences is a fundamental challenge. Over the years, researchers have developed a vast "zoo" of formalisms to handle this, ranging from CP-nets and Answer Set Optimization (ASO) to Logic Programs with Ordered Disjunction (LPODs). While these systems are powerful, they often lack a common mathematical foundation, making it difficult to compare them or understand how they behave when integrated into larger systems.
This paper introduces Abstract Preference Frameworks (APFs), a generalized algebraic toolkit designed to unify these diverse formalisms. By abstracting away the specific syntax of individual languages, the authors provide a rigorous way to study two critical properties: Strong Equivalence—the ability to swap one theory for another in any context without changing the outcome—and Separability—the ability to cleanly decouple hard constraints from soft preferences.
The Abstract Preference Framework (APF)
To provide a unified view, the authors define an APF as a quadruple $\sigma = \langle L, I, \iota, \geq \rangle$. This structure consists of:
- $L$ (Theories): A set of theories organized as a join-semilattice, allowing for the combination of different preference sets.
- $I$ (Outcomes): The space of all possible outcomes or interpretations.
- $\iota$ (Feasibility): A function mapping a theory to its set of "feasible" outcomes (the hard constraints).
- $\geq$ (Preorder): A function mapping a theory to a preorder that ranks the outcomes (the soft preferences).
By defining these components abstractly, the framework can accommodate various existing systems. The authors also introduce specific postulates, such as the Filter property and Promotion properties, which act as sanity checks to ensure the framework behaves predictably under extension and combination.
Strong Equivalence and Modularity
A central problem in Knowledge Representation is determining when two theories are truly identical. While two theories might produce the same "best" outcomes in isolation, they may diverge when new information is added. This leads to the concept of Strong Equivalence: two theories $T_1$ and $T_2$ are strongly equivalent if, for any additional theory $T'$, the combined systems $(T_1 \cup T')$ and $(T_2 \cup T')$ yield the same preferred outcomes.
The authors provide general characterization theorems (Theorems 7 and 8) that allow researchers to verify strong equivalence by examining the internal structure of the theories rather than testing them against every possible extension. A key technical contribution here is the introduction of Potentially Intended Outcomes ($\mu(x)$), which characterizes the outcomes that could become feasible as a theory is extended. This concept is vital for navigating the non-monotonic nature of many preference systems.
Separability: Decomposing Constraints and Preferences
Many preference languages "mix" the rules that define what is possible (generators) with the rules that define what is preferred (selectors). This mixing can make reasoning and optimization difficult. The APF framework allows for a formal study of Separability—the mathematical "unmixing" of these components.
The paper demonstrates that if a framework is separable, strong equivalence in a complex, mixed system can be reduced to checking equivalence in two simpler, one-dimensional frameworks: one for constraints and one for preferences. This reduction significantly simplifies the verification of modularity in complex AI systems.
Case Study: Logic Programs with Ordered Disjunction (LPODs)
To demonstrate the utility of the APF, the authors apply it to Logic Programs with Ordered Disjunction (LPODs). LPODs are a popular formalism where rules like $A \vee B \leftarrow C$ imply that $A$ is preferred over $B$ if $C$ holds. Traditionally, these rules blur the line between generating answer sets and ranking them.
The authors formally prove (Theorem 10) that the preference framework of LPODs is indeed separable. This structural proof provides a new way to analyze LPODs, showing they can be decomposed into pure generator and selector components, which has significant implications for how these programs are optimized and executed.
Conclusion and Future Work
The Abstract Preference Framework succeeds in unifying diverse systems like penalty logic, possibilistic logic, and ASO problems under a single mathematical umbrella. It establishes the "gold standard" for modularity through strong equivalence and provides a rigorous path for decomposing complex preference theories.
However, the authors note several avenues for future research:
- Relaxing Conditions: The current requirements for separability involve strict mathematical homomorphisms that may not exist in all niche formalisms.
- Ranked Preferences: The current APF focuses on a relatively flat structure. Extending the framework to handle hierarchical or "ranked" preferences (e.g., prioritizing safety over cost) is a necessary next step.
- Redundancy: Future work will look at finding "non-redundant" versions of generators and selectors to create even more efficient representations of preference theories.
Summary updated