Introduction
In many artificial intelligence applications, the goal is not to select a single optimal object but to find a composition of objects—a "bundle"—that collectively satisfies a functional objective. Examples include assembling a graduate program of study, configuring a web service pipeline, or planning a complex travel itinerary. This paper presents a formal framework for reasoning with qualitative user preferences to identify the most preferred compositions without requiring the user to provide precise numeric scores.
The Composition Problem
Traditional decision theory often relies on quantitative utility functions. However, humans find it difficult to assign exact numeric values (e.g., "I like this instructor with a score of 0.8"). Instead, qualitative preferences—such as "I prefer Professor Smith over Professor Jones"—are more natural and easier to elicit.
The challenge lies in aggregating these individual preferences across a collection of items. A bundle might be judged by its "weakest link"; for instance, a student might reject an otherwise perfect course schedule if it contains one highly disliked class.
Methodology: Dominance and Algorithms
The authors propose a multi-layered approach to determine the "best" compositions:
- Aggregation Functions: These functions define how to evaluate a composition's value. While "Summation" is used for additive attributes like credits, the authors introduce the "Worst Frontier" function to identify the set of least-preferred elements within a bundle, effectively characterizing a bundle by its weakest components.
- The Dominance Relation ($\succ_d$): This mathematical relation determines if one composition dominates another. It relies on the concept of a "witness" attribute: bundle A dominates bundle B if there exists an attribute where A is strictly better, and for all attributes of equal or greater importance, A is at least as good as B.
- Preference Modeling: Individual preferences are modeled as partial orders, allowing for incomparable items and hierarchical structures.
The framework includes several algorithms to find optimal solutions. While A1 (ComposeAndFilter) is an exhaustive approach, the more sophisticated A4 (InterleaveCompose) prunes the search space during bundle construction. By "interleaving" preference reasoning with composition, it avoids building partial bundles that are already guaranteed to be dominated.
Theoretical Insights and Results
A key theoretical finding is the necessity of interval orders. For the dominance relation to remain transitive (ensuring that if A > B and B > C, then A > C), the user's relative importance of attributes must follow an interval order structure. Random partial orders can lead to preference "loops," making it impossible to identify a clear winner.
The framework was evaluated using simulated problem instances based on Uniform Recursive Trees, modeling search spaces with up to 200 components. The results demonstrated that the interleaving approach (A4) significantly outperforms exhaustive search, particularly when preferences are strict. The authors also provided mathematical proofs for the soundness and completeness of their algorithms.
Conclusion and Future Work
This research provides a robust foundation for automated reasoning in compositional systems using qualitative feedback. While the current model handles static preferences well, future work aims to incorporate conditional preferences (e.g., "I prefer X only if Y is present") and dynamic aggregation functions where component interactions might change the overall value of the bundle.
Summary updated