Introduction
In the realm of decision-support and recommender systems, the challenge of "incomplete pictures" is pervasive. Users rarely provide a comprehensive ranking of all possible options, leaving systems to infer missing preferences from a limited set of observations. While many existing methods rely on simple weighted sums or specific structures like CP-nets, this research investigates the computational landscape of Hierarchical Constraint Logic Programming (HCLP) models.
HCLP models utilize a lexicographic ordering to compare alternatives. In this framework, criteria are organized into levels of importance. When comparing two options, the system examines the most important criteria first; if a tie occurs, it proceeds to the next level. The central challenge is Preference Inference: given a set of known preferences ($\Gamma$) and a query preference ($\phi$), does every hierarchical model that satisfies $\Gamma$ also satisfy $\phi$? Because a user's internal "importance ordering" is typically unknown, the system must reason across the entire space of valid hierarchies.
The HCLP Framework
The authors define HCLP structures where alternatives are evaluated based on "costs" across various criteria. The research investigates three primary constraints on the set of possible models ($\mathcal{M}$):
- General Case ($t > 1$): Levels of importance can contain multiple criteria (e.g., "Price and Quality are equally important, and both are more important than Color").
- Total Order Case ($t = 1$): Each level of importance contains exactly one criterion.
- Fixed Equivalence Case: The sets of equally important criteria are pre-defined by a fixed relation.
Complexity Results: The Polynomial Boundary
A significant contribution of this work is identifying the "complexity threshold" for preference inference. The authors demonstrate that the problem's difficulty escalates rapidly based on the structure of the hierarchy:
- Hardness in the General Case: For any scenario where more than one criterion can occupy the same importance level ($t > 1$), HCLP-Deduction is coNP-complete. This result is established through a reduction from the 3-SAT problem, showing that even allowing just two criteria to be "equally important" makes the problem computationally difficult.
- Efficiency in Restricted Cases: When criteria are strictly ordered ($t=1$), the problem becomes computationally tractable. The authors provide a greedy algorithm,
Cons-check, which verifies consistency and inference in $O(|\Gamma||\mathcal{C}|)$ time, where $|\Gamma|$ is the number of input preferences and $|\mathcal{C}|$ is the number of criteria. - Fixed Structures: Inference also remains polynomial if the "importance buckets" (equivalence classes) are fixed in advance, regardless of how many criteria they contain.
Algorithmic Insights and Expressive Power
The Cons-check algorithm functions similarly to a topological sort, iteratively selecting criteria that do not contradict the existing preference set. This greedy approach is sufficient for the $t=1$ case to find a valid model if one exists.
Beyond basic inference, the paper introduces the Maximal Inconsistency Base (MIB). In real-world applications, users are often inconsistent. The MIB allows a system to pinpoint exactly which subset of input preferences causes a contradiction within the hierarchical framework, facilitating better user feedback and error correction.
Furthermore, the authors highlight the expressive power of HCLP. Despite its structured nature, it can represent complex disjunctive ordering statements, such as "at least one criterion in set A is more important than all criteria in set B."
Limitations and Future Directions
While the paper provides a robust theoretical foundation, it notes several limitations that pave the way for future work:
- Fixed Evaluations: The current model assumes that the "costs" or evaluation values for every alternative on every criterion are known and fixed. In many scenarios, these values might be uncertain or subjective.
- Language Complexity: The focus is on a relatively simple preference language. The authors suggest investigating more expressive languages, such as those allowing conditional dependencies, to determine where the new "polynomial boundary" lies.
- Learning vs. Inference: There is a distinction between preference learning (finding a single best-fit model) and preference inference (reasoning about all valid models). Integrating these two paradigms remains an open challenge.
Conclusion
This research clarifies the computational limits of hierarchical preference models. By proving that strict ordering allows for efficient inference while even minor relaxations lead to coNP-completeness, the authors provide a roadmap for designing more efficient and theoretically sound decision-support systems.
Summary updated