提出高效算法，解决基于层级模型的偏好语言一致性与最优解计算问题。
Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
- 发现强组合性性质，支持贪婪算法快速判断偏好陈述一致性。
- 证明在特定偏好语言LpqT中，一致性检测与最优解计算均为多项式时间。
- 适用于含严格/非严格、结果与部分元组比较等复杂偏好的场景，适合系统设计者参考。
我们分析了基于层级模型的通用偏好语言中的偏好推理一致性问题。识别出一种称为强组合性的性质，该性质适用于多种自然偏好表述，使得可通过贪心算法判定一组偏好陈述的一致性。同时探讨了不同自然定义下的最优性及其相互关系。基于此框架，我们证明在特定偏好语言LpqT中，一致性测试（即推理）是多项式时间可解的。该语言支持严格与非严格陈述、结果间及部分元组间的比较，涵盖一切俱备条件与强陈述及其组合。此外，不同类型的最优解集计算也被证明为多项式时间；实验结果验证了其有效性。
原文摘要 · Abstract (English)
We analyse preference inference, through consistency, for general preference languages based on lexicographic models. We identify a property, which we call strong compositionality, that applies for many natural kinds of preference statement, and that allows a greedy algorithm for determining consistency of a set of preference statements. We also consider different natural definitions of optimality, and their relations to each other, for general preference languages based on lexicographic models. Based on our framework, we show that testing consistency, and thus inference, is polynomial for a specific preference language LpqT, which allows strict and non-strict statements, comparisons between outcomes and between partial tuples, both ceteris paribus and strong statements, and their combination. Computing different kinds of optimal sets is also shown to be polynomial; this is backed up by our experimental results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。