Representing Utility Functions via Weighted Goals
Representing Utility Functions via Weighted Goals
复制标题
通过加权目标表示效用函数
DOI：
10.1002/malq.200810024
复制
发表时间：
2009
影响因子：
0.3
通讯作者：
Jérôme Lang
中科院分区：
文献类型：
--
作者：
Joel Uckelman;Y. Chevaleyre;Ulrich Endriss;Jérôme Lang
基于效用函数的加权命题公式，我们分析了一族语言的表现力、简洁性和复杂性。这种形式的偏好建模的核心思想是将数值权重与命题公式中指定的目标相关联，并将备选方案的效用价值计算为其满足的目标权重的总和。基于这一思想，我们定义了大量的表示语言，每种语言的特征都有一组对公式语法和权重范围的限制。我们的目标有三个。首先，对于每种语言，我们尝试确定它可以表达的效用函数的类别。其次，当不同的语言可以表达同一类效用函数时，一种语言可能比另一种语言更简洁地表示。因此，我们分析了语言的相对简洁性。第三，对于每种语言，我们研究了在给定用该语言表示的效用函数的情况下寻找最优选备选方案问题的计算复杂性(Wiley-VCH Verlag GmbH&Co.KGaA，Weinheim)
We analyze the expressivity, succinctness, and complexity of a family of languages based on weighted propositional formulas for the representation of utility functions. The central idea underlying this form of preference modeling is to associate numerical weights with goals specified in terms of propositional formulas, and to compute the utility value of an alternative as the sum of the weights of the goals it satisfies. We define a large number of representation languages based on this idea, each characterized by a set of restrictions on the syntax of formulas and the range of weights. Our aims are threefold. First, for each language we try to identify the class of utility functions it can express. Second, when different languages can express the same class of utility functions, one may allow for a more succinct representation than another. Therefore, we analyze the relative succinctness of languages. Third, for each language we study the computational complexity of the problem of finding the most preferred alternative given a utility function expressed in that language (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)