×

Representing utility functions via weighted goals. (English) Zbl 1180.91118

Let \(PS\) be a set of propositional symbols and \(L_{PS}\) the propositional language over \(PS\). A weighted goal is a pair \((\phi, w)\), where \(\phi\) is a formula in \(L_{PS}\) and \(w \in \mathbb{R}\). A goalbase \(G\) is a finite set \(\{(\phi_{i}, w_{i})\}_{i}\) of weighted goals. We say that a goalbase \(G\) and an aggregation function \(F: 2^{\mathbb{R}} \rightarrow \mathbb{R}\) generate a utility function \(u_{G,F}: 2^{PS} \rightarrow \mathbb{R}\) as follows: \(u_{G,F}(M) = F(\{w : (\phi, w) \in G \;\text{and} \;M \models \phi \})\). The authors restrict themselves to \(F = \Sigma\), the summation function and often omit \(F\).
Two goalbases \(G\) and \(G'\) are equivalent, denoted by \(G \equiv_{\Sigma} G'\), if they generate the same utility function, i.e., if \(u_{G} = u_{G'}\). A utility function \(u\) is represented in a language \(L\) if there exists a goalbase \(G \in L\) such that \(u = u_{G}\).
First, the authors take up the question of which utility functions can be represented in any given language. Next, when different languages can express the same class of utility functions, one may allow for a more succinct representation than another. Therefore, the authors analyze the relative succinctness of languages. Finally, for each language they study the computational complexity of the problem of finding the most preferred alternative given a utility function expressed in that language.

MSC:

91B14 Social choice
03D15 Complexity of computation (including implicit computational complexity)

Software:

CP-nets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. J. Arrow, A. K. Sen, and K. Suzumura (eds.), Handbook of Social Choice and Welfare (North-Holland, 2002). · Zbl 1307.91009
[2] Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet, A short introduction to computational social choice. In: Proc. 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007)(J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, and F. Plasil, eds.) LNCS Vol. 4362, pp. 51-69 (Springer-Verlag, 2007). · Zbl 1131.91316
[3] J. Doyle, and M. P. Wellman, Preferential semantics for goals. In: Proc. 9th National Conference on Artificial Intelligence (AAAI-1991), pp. 698-703 (AAAI Press, 1991).
[4] Boutilier, CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements, Journal of Artifcial Intelligence Research (JAIR) 21 pp 135– (2004) · Zbl 1080.68685
[5] Lang, Logical preference representation and combinatorial vote, Annals of Mathematics and Artificial Intelligence 42 pp 37– (2004) · Zbl 1061.68147
[6] F. Bacchus, and A. J. Grove, Utility independence in a qualitative decision theory. In: Proc. 5th International Conference on Principles of Knowledge Representation and Reasoning (KR-1996), pp. 542-552 (Morgan Kaufmann, 1996).
[7] P. La Mura, and Y. Shoham, Expected utility networks. In: Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI-1999), pp. 366-373 (Morgan Kaufmann, 1999).
[8] C. Boutilier, F. Bacchus, and R. Brafman, UCP-networks: A directed graphical representation of conditional utilities. In: Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI-2001), pp. 56-64 (Morgan Kaufmann, 2001).
[9] C. Gonzales, and P. Perny, GAI networks for utility elicitation. In: Proc. 9th International Conference on Principles of Knowledge Representation and Reasoning (KR-2004), pp. 224-234 (AAAI Press, 2004).
[10] C. Boutilier, R. Dearden, and M. Goldszmidt, Exploiting structure in policy construction. In: Proc. 14th International Joint Conference on Artificial Intelligence (IJCAI-1995), pp. 1104-1113 (Morgan Kaufmann, 1995).
[11] Bistarelli, Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison, Constraints 4 pp 199– (1999) · Zbl 0946.68143
[12] N. Nisan, Bidding languages for combinatorial auctions. In: Combinatorial Auctions (P. Cramton, Y. Shoham, and R. Steinberg, eds.) (MIT Press, 2006).
[13] C. Boutilier, and H. H. Hoos, Bidding languages for combinatorial auctions. In: Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), pp. 1211-1217 (Morgan Kaufmann, 2001).
[14] Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence 135 pp 1– (2002) · Zbl 0984.68039
[15] Pinkas, Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge, Artificial Intelligence 77 pp 203– (1995)
[16] C. Lafage, and J. Lang, Logical representation of preferences for group decision making. In: Proc. 7th International Conference on Principles of Knowledge Representation and Reasoning (KR-2000), pp. 457-468 (Morgan Kaufmann, 2000).
[17] J. Uckelman, and U. Endriss, Preference modeling by weighted goals with max aggregation. In: Proc. 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-2008), pp. 579-587 (AAAI Press, 2008).
[18] S. Coste-Marquis, J. Lang, P. Liberatore, and P. Marquis, Expressive power and succinctness of propositional languages for preference representation. In: Proc. 9th International Conference on Principles of Knowledge Representation and Reasoning (KR-2004), pp. 203-212 (AAAI Press, 2004).
[19] P. Haddawy, and S. Hanks, Representations for decision-theoretic planning: Utility functions for deadline goals. In: Proc. 4th International Conference on Principles of Knowledge Representation and Reasoning (KR-1994), pp. 71-82 (Morgan Kaufmann, 1992).
[20] F. Dupin de Saint-Cyr, J. Lang, and T. Schiex, Penalty logic and its link with Dempster-Shafer theory. In: Proc. 10th Conference on Uncertainty in Artificial Intelligence (UAI-1994), pp. 204-211 (Morgan Kaufmann, 1994).
[21] S. Ieong, and Y. Shoham, Marginal contribution nets: A compact representation scheme for coalitional games. In: Proc. 6th ACM Conference on Electronic Commerce (EC-2005), pp. 193-202 (ACM Press, 2005).
[22] E. Elkind, L. A. Goldberg, P. W. Goldberg, and M. 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-1014 (IFAAMAS, 2008). · Zbl 1175.91022
[23] Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2 pp 340– (1964)
[24] Grabisch, k -order additive discrete fuzzy measures and their representation, Fuzzy Sets and Systems 92 pp 167– (1997) · Zbl 0927.28014
[25] V. Conitzer, T. W. Sandholm, and P. Santi, Combinatorial auctions with k -wise dependent valuations. In: Proc. 20th National Conference on Artificial Intelligence (AAAI-05), pp. 248-254 (AAAI Press, 2005).
[26] Chevaleyre, Multiagent resource allocation in k -additive domains: Preference representation and complexity, Annals of Operations Research 163 pp 49– (2008) · Zbl 1170.91418
[27] J. S. Rosenschein, and G. Zlotkin, Rules of Encounter (MIT Press, 1994).
[28] H. Moulin, Axioms of Cooperative Decision Making (Cambridge University Press, 1988). · Zbl 0699.90001
[29] Dempster, Upper and lower probabilities induced by a multivaluated mapping, Annals of Mathematical Statistics 38 pp 325– (1967) · Zbl 0168.17501
[30] G. Shafer, A Mathematical Theory of Evidence (Princeton University Press, Princeton, NJ, 1976). · Zbl 0359.62002
[31] Cadoli, Space efficiency of propositional knowledge representation formalisms, Journal of Artificial Intelligence Research (JAIR) 13 pp 1– (2000) · Zbl 0946.68134
[32] Y. Mansour, Learning Boolean functions via the Fourier transform. In: Theoretical Advances in Neural Computation and Learning (Kluwer, 1994). · Zbl 0845.68093
[33] L. Trevisan, Lecture notes 25, CS278: Computational complexity, UC-Berkeley, December 1, 2004, http://www.cs.berkeley.edu/luca/cs278/notes/lecture25.pdf.
[34] T. Lee, Kolmogorov Complexity and Formula Size Lower Bounds. PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, 2006.
[35] J. Uckelman, and A. Witzel, Logic-based preference languages with intermediate complexity. In: Proceedings of the 4th Multidisciplinary Workshop on Advances in Preference Handling (MPREF-2008), pp. 123-127 (AAAI Press, 2008).
[36] M. R. Garey, and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (W. H. Freeman and Co., 1979). · Zbl 0411.68039
[37] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation (Springer-Verlag, 1999). · Zbl 0937.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.