• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Representing Utility Functions via Weighted Goals

Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme; Uckelman, Joel (2009), Representing Utility Functions via Weighted Goals, Mathematical Logic Quarterly, 55, 4, p. 341-361. http://dx.doi.org/10.1002/malq.200810024

Type
Article accepté pour publication ou publié
Date
2009
Journal name
Mathematical Logic Quarterly
Volume
55
Number
4
Publisher
Johann Ambrosius Barth
Pages
341-361
Publication identifier
http://dx.doi.org/10.1002/malq.200810024
Metadata
Show full item record
Author(s)
Chevaleyre, Yann
Endriss, Ulle
Lang, Jérôme
Uckelman, Joel
Abstract (EN)
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
Subjects / Keywords
Computational complexity; Preference representation; computational social choice

Related items

Showing items related by title and author.

  • Thumbnail
    Expressive Power of Weighted Propositional Formulas for Cardinal Preference Modelling 
    Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme (2006) Communication / Conférence
  • Thumbnail
    Multiagent Resource Allocation with K -additive Utility Functions 
    Maudet, Nicolas; Estivie, Sylvia; Endriss, Ulle; Chevaleyre, Yann (2004) Communication / Conférence
  • Thumbnail
    On maximal classes of utility functions for efficient one-to-one negotiation 
    Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2005) Communication / Conférence
  • Thumbnail
    Restricted Classes of Utility Functions for Simple Negotiation Schemes: Sufficiency, Necessity and Maximality 
    Maudet, Nicolas; Endriss, Ulle; Chevaleyre, Yann (2008) Chapitre d'ouvrage
  • Thumbnail
    Multiagent Resource Allocation with K-additive Utility Functions 
    Chevaleyre, Yann; Endriss, Ulle; Estivie, Sylvia; Maudet, Nicolas (2004) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo