{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T16:45:31Z","timestamp":1769273131803,"version":"3.49.0"},"reference-count":37,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T00:00:00Z","timestamp":1247788800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 (\u00a9 2009 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200810024","type":"journal-article","created":{"date-parts":[[2009,7,18]],"date-time":"2009-07-18T07:49:09Z","timestamp":1247903349000},"page":"341-361","source":"Crossref","is-referenced-by-count":21,"title":["Representing Utility Functions via Weighted Goals"],"prefix":"10.1002","volume":"55","author":[{"given":"Joel","family":"Uckelman","sequence":"first","affiliation":[]},{"given":"Yann","family":"Chevaleyre","sequence":"additional","affiliation":[]},{"given":"Ulle","family":"Endriss","sequence":"additional","affiliation":[]},{"given":"J\u00e9r\u00f4me","family":"Lang","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2009,7,17]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"K. J.Arrow A. K.Sen andK.Suzumura(eds.) Handbook of Social Choice and Welfare (North\u2010Holland 2002)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"Y.Chevaleyre U.Endriss J.Lang andN.Maudet A short introduction to computational social choice. In: Proc. 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u20102007)(J. van Leeuwen G. F. Italiano W. van der Hoek C. Meinel H. Sack and F. Plasil eds.) LNCS Vol. 4362 pp. 51\u201369 (Springer\u2010Verlag 2007).","DOI":"10.1007\/978-3-540-69507-3_4"},{"key":"e_1_2_1_4_2","unstructured":"J.Doyle andM. P.Wellman Preferential semantics for goals. In: Proc. 9th National Conference on Artificial Intelligence (AAAI\u20101991) pp. 698\u2013703 (AAAI Press 1991)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1613\/jair.1234","article-title":"CP\u2010nets: A tool for representing and reasoning with conditional ceteris paribus preference statements","volume":"21","author":"Boutilier C.","year":"2004","journal-title":"Journal of Artifcial Intelligence Research (JAIR)"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:AMAI.0000034522.25580.09"},{"key":"e_1_2_1_7_2","unstructured":"F.Bacchus andA. J.Grove Utility independence in a qualitative decision theory. In: Proc. 5th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20101996) pp. 542\u2013552 (Morgan Kaufmann 1996)."},{"key":"e_1_2_1_8_2","unstructured":"P.La Mura andY.Shoham Expected utility networks. In: Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI\u20101999) pp. 366\u2013373 (Morgan Kaufmann 1999)."},{"key":"e_1_2_1_9_2","unstructured":"C.Boutilier F.Bacchus andR.Brafman UCP\u2010networks: A directed graphical representation of conditional utilities. In: Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI\u20102001) pp. 56\u201364 (Morgan Kaufmann 2001)."},{"key":"e_1_2_1_10_2","unstructured":"C.Gonzales andP.Perny GAI networks for utility elicitation. In: Proc. 9th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20102004) pp. 224\u2013234 (AAAI Press 2004)."},{"key":"e_1_2_1_11_2","unstructured":"C.Boutilier R.Dearden andM.Goldszmidt Exploiting structure in policy construction. In: Proc. 14th International Joint Conference on Artificial Intelligence (IJCAI\u20101995) pp. 1104\u20131113 (Morgan Kaufmann 1995)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026441215081"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"N.Nisan Bidding languages for combinatorial auctions. In: Combinatorial Auctions (P. Cramton Y. Shoham and R. Steinberg eds.) (MIT Press 2006).","DOI":"10.7551\/mitpress\/9780262033428.003.0010"},{"key":"e_1_2_1_14_2","unstructured":"C.Boutilier andH. H.Hoos Bidding languages for combinatorial auctions. In: Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI\u20102001) pp. 1211\u20131217 (Morgan Kaufmann 2001)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00159-X"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00032-V"},{"key":"e_1_2_1_17_2","unstructured":"C.Lafage andJ.Lang Logical representation of preferences for group decision making. In: Proc. 7th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20102000) pp. 457\u2013468 (Morgan Kaufmann 2000)."},{"key":"e_1_2_1_18_2","unstructured":"J.Uckelman andU.Endriss Preference modeling by weighted goals with max aggregation. In: Proc. 11th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20102008) pp. 579\u2013587 (AAAI Press 2008)."},{"key":"e_1_2_1_19_2","unstructured":"S.Coste\u2010Marquis J.Lang P.Liberatore andP.Marquis Expressive power and succinctness of propositional languages for preference representation. In: Proc. 9th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20102004) pp. 203\u2013212 (AAAI Press 2004)."},{"key":"e_1_2_1_20_2","unstructured":"P.Haddawy andS.Hanks Representations for decision\u2010theoretic planning: Utility functions for deadline goals. In: Proc. 4th International Conference on Principles of Knowledge Representation and Reasoning (KR\u20101994) pp. 71\u201382 (Morgan Kaufmann 1992)."},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"F.Dupin de Saint\u2010Cyr J.Lang andT.Schiex Penalty logic and its link with Dempster\u2010Shafer theory. In: Proc. 10th Conference on Uncertainty in Artificial Intelligence (UAI\u20101994) pp. 204\u2013211 (Morgan Kaufmann 1994).","DOI":"10.1016\/B978-1-55860-332-5.50031-6"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"S.Ieong andY.Shoham Marginal contribution nets: A compact representation scheme for coalitional games. In: Proc. 6th ACM Conference on Electronic Commerce (EC\u20102005) pp. 193\u2013202 (ACM Press 2005).","DOI":"10.1145\/1064009.1064030"},{"key":"e_1_2_1_23_2","unstructured":"E.Elkind L. A.Goldberg P. W.Goldberg andM.Wooldridge A tractable and expressive class of marginal contribution nets and its applications. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008) pp. 1007\u20131014 (IFAAMAS 2008)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00531932"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-0114(97)00168-1"},{"key":"e_1_2_1_26_2","unstructured":"V.Conitzer T. W.Sandholm andP.Santi Combinatorial auctions withk\u2010wise dependent valuations. In: Proc. 20th National Conference on Artificial Intelligence (AAAI\u201005) pp. 248\u2013254 (AAAI Press 2005)."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-008-0335-0"},{"key":"e_1_2_1_28_2","unstructured":"J. S.Rosenschein andG.Zlotkin Rules of Encounter (MIT Press 1994)."},{"key":"e_1_2_1_29_2","doi-asserted-by":"crossref","unstructured":"H.Moulin Axioms of Cooperative Decision Making (Cambridge University Press 1988).","DOI":"10.1017\/CCOL0521360552"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698950"},{"key":"e_1_2_1_31_2","unstructured":"G.Shafer A Mathematical Theory of Evidence (Princeton University Press Princeton NJ 1976)."},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00010-2"},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"Y.Mansour Learning Boolean functions via the Fourier transform. In: Theoretical Advances in Neural Computation and Learning (Kluwer 1994).","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"e_1_2_1_34_2","unstructured":"L.Trevisan Lecture notes 25 CS278: Computational complexity UC\u2010Berkeley December 1 2004 http:\/\/www.cs.berkeley.edu\/\u223cluca\/cs278\/notes\/lecture25.pdf."},{"key":"e_1_2_1_35_2","unstructured":"T.Lee Kolmogorov Complexity and Formula Size Lower Bounds. PhD thesis Institute for Logic Language and Computation University of Amsterdam 2006."},{"key":"e_1_2_1_36_2","unstructured":"J.Uckelman andA.Witzel Logic\u2010based preference languages with intermediate complexity. In: Proceedings of the 4th Multidisciplinary Workshop on Advances in Preference Handling (MPREF\u20102008) pp. 123\u2013127 (AAAI Press 2008)."},{"key":"e_1_2_1_37_2","unstructured":"M. R.Garey andD. S.Johnson Computers and Intractability: A Guide to the Theory of NP\u2010completeness (W. H. Freeman and Co. 1979)."},{"key":"e_1_2_1_38_2","doi-asserted-by":"crossref","unstructured":"G.Ausiello P.Crescenzi G.Gambosi V.Kann A.Marchetti\u2010Spaccamela andM.Protasi Complexity and Approximation (Springer\u2010Verlag 1999).","DOI":"10.1007\/978-3-642-58412-1"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810024","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200810024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T23:18:52Z","timestamp":1699917532000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200810024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,17]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1002\/malq.200810024"],"URL":"https:\/\/doi.org\/10.1002\/malq.200810024","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,17]]}}}