Expressive Power of Weighted Propositional Formulas for Cardinal Preference Modelling

Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme

Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme (2006), Expressive Power of Weighted Propositional Formulas for Cardinal Preference Modelling, in Welty, Christopher, Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR-06), AAAI Press : Palo Alto (USA), p. 145-152

Type

Communication / Conférence

Date

2006

Conference country

UNITED KINGDOM

Book title

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR-06)

Book author

Welty, Christopher

Publisher

AAAI Press

Published in

Palo Alto (USA)

ISBN

978-1-57735-271-6

Pages

145-152

Metadata

Show full item record

Author(s)

Chevaleyre, Yann
Endriss, Ulle
Lang, Jérôme

Abstract (EN)

As proposed in various places, a set of propositional formulas, each associated with a numerical weight, can be used to model the preferences of an agent in combinatorial domains. If the range of possible choices can be represented by the set of possible assignments of propositional symbols to truth values, then the utility of an assignment is given by the sum of the weights of the formulas it satisfies. Our aim in this paper is twofold: (1) to establish correspondences between certain types of weighted formulas and well-known classes of utility functions (such as monotonic, concave or k-additive functions); and (2) to obtain results on the comparative succinctness of different types of weighted formulas for representing the same class of utility functions.

Subjects / Keywords

expressive power comparative succinctness; computational complexity; logic-based languages; Preference representation