Mathematical Logic Quarterly 55 (4):341-361 (2009)

Ulle Endriss
University of Amsterdam
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
Keywords computational social choice  Preference representation  computational complexity
Categories (categorize this paper)
DOI 10.1002/malq.200810024
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,864
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Upper and Lower Probabilities Induced by a Multi- Valued Mapping.Arthur Dempster - 1967 - Annals of Mathematical Statistics 38:325-339.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Local Utility Functions.Peter Bardsley - 1993 - Theory and Decision 34 (2):109-118.
Invariant Multiattribute Utility Functions.Ali E. Abbas - 2010 - Theory and Decision 68 (1-2):69-99.
Risk and Tradeoffs.Lara Buchak - 2014 - Erkenntnis 79 (S6):1091-1117.
Two Errors in The?Allais Impossibility Theorem?Mark J. Machina - 1995 - Theory and Decision 38 (3):231-250.
Subjectively Weighted Linear Utility.Gordon B. Hazen - 1987 - Theory and Decision 23 (3):261-282.


Added to PP index

Total views
7 ( #1,019,513 of 2,433,130 )

Recent downloads (6 months)
1 ( #463,753 of 2,433,130 )

How can I increase my downloads?


My notes