×

Expressive efficiency of two kinds of specific CP-nets. (English) Zbl 1360.68815

Summary: CP-nets (conditional preference networks) are a graphical model for compactly expressing conditional ceteris paribus (all other things being equal) preference statements on multi-attribute domains. In this paper, we investigate the expressive efficiency of two kinds of binary-valued CP-nets, the first kind is set-structured CP-nets, and the second kind is equal difference CP-nets. For the first kind, we prove that it can express \(3^n - 2^n\) preference relations with \( n\) preference rules, and has an expressive efficiency of \((3^n - 2^n) / n\). For the second kind, we show that it can express a total order of \(2^{n - 1} \ast(2^n - 1)\) preference relations with \(2^n - 1\) preference rules, and has an expressive efficiency of \(2^{n - 1}\). For the future research, we propose an open problem: given an acyclic CP-net \(N\) with the in-degree sequence of \((d_1, d_2, \ldots, d_n)\), how many preference relations can be expressed by \( N?\)

MSC:

68T30 Knowledge representation
91B08 Individual preferences

Software:

CP-nets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartolini, I.; Ciaccia, P.; Patella, M., The skyline of a probabilistic relation, IEEE Trans. Knowl. Data Eng., 25, 1656-1669 (2013)
[2] Benthem, V.; Girard, P.; Roy, O., Everything else being equal: a modal logic for ceteris paribus preferences, J. Philos. Logic, 38, 83-125 (2009) · Zbl 1171.03009
[3] Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; Poole, D., Cp-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements, J. Artif. Intell. Res., 21, 135-191 (2004) · Zbl 1080.68685
[4] Bouveret, S.; Endriss, U.; Lang, J., Conditional importance networks: a graphical language for representing ordinal, monotonic preferences over sets of goods, (Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009) (2009), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco), 67-72
[5] Brafman, R.; Domshlak, C., Preference handling-an introductory tutorial, AI Mag., 30, 58-86 (2009)
[6] Brafman, R.; Domshlak, C.; Shimony, S., On graphical modeling of preference and importance, J. Artif. Intell. Res., 25, 389-424 (2006) · Zbl 1182.68325
[7] Carbajal, J. C.; McLennan, A.; Tourky, R., Truthful implementation and preference aggregation in restricted domains, J. Econ. Theor., 148, 1074-1101 (2013) · Zbl 1285.91038
[8] Chen, S. M.; Lin, T. E.; Lee, L. W., Group decision making using incomplete fuzzy preference relations based on the additive consistency and the order consistency, Inf. Sci., 259, 1-15 (2014) · Zbl 1329.91031
[9] Chevaleyre, Y.; Endriss, U.; Lang, J., Expressive power of weighted propositional formulas for cardinal preference modelling, (Institute for Logic, Language and Computation (ILLC) (2006), University of Amsterdam)
[10] Chevaleyre, Y.; Koriche, F.; Lang, J.; Mengin, J.; Zanuttini, B., Learning ordinal preferences on multiattribute domains: the case of cp-nets, (Preference Learning (2011), Springer-Verlag New York Inc.), 273-296 · Zbl 1214.68277
[11] Coste-Marquis, S.; Lang, J.; Liberatore, P.; Marquis, P., Expressive power and succinctness of propositional languages for preference representation, KR 2004, 4, 203-212 (2004)
[12] Domshlak, C.; Hüllermeier, E.; Kaci, S.; Prade, H., Preferences in ai: an overview, Artif. Intell., 175, 1037-1052 (2011)
[13] Fishburn, P., Preference structures and their numerical representations, Theor. Comput. Sci., 217, 359-383 (1999) · Zbl 0914.68181
[14] Goldsmith, J.; Lang, J.; Truszczynski, M.; Wilson, N., The computational complexity of dominance and consistency in cp-nets, J. Artif. Intell. Res., 33, 403-432 (2008) · Zbl 1182.68089
[15] Gonzales, C.; Perny, P.; Dubus, J. P., Decision making with multiple objectives using gai networks, Artif. Intell., 175, 1153-1179 (2011) · Zbl 1231.91070
[16] Kaci, S.; van der Torre, L., Reasoning with various kinds of preferences: logic, non-monotonicity, and algorithms, Ann. Oper. Res., 163, 89-114 (2008) · Zbl 1172.03318
[17] Kohlas, J.; Pouly, M.; Schneuwly, C., Generic local computation, J. Comput. Syst. Sci., 78, 348-369 (2012) · Zbl 1255.68156
[18] Lafage, C.; Lang, J., Logical representation of preferences for group decision making, (7th International Conference on Principles of Knowledge Representation and Reasoning (KR2000) (2000), Morgan Kaufman Publishers, Springer: Morgan Kaufman Publishers, Springer Berlin), 457-470
[19] Lang, J., Logical preference representation and combinatorial vote, Ann. Math. Artif. Intell., 42, 37-71 (2004) · Zbl 1061.68147
[20] Lang, J., Logical representation of preferences, Decis. Making Process Concept. Method., 321-363 (2009)
[21] Lang, J.; Mengin, J., The complexity of learning separable ceteris paribus preferences, (Proceedings of the 21st International Jont Conference on Artifical Intelligence, vol. 9 (2009), Morgan Kaufman Publishers Inc.), 848-853
[22] Levandoski, J. J.; Eldawy, A.; Mokbel, M. F.; Khalefa, M. E., Flexible and extensible preference evaluation in database systems, ACM Trans. Database Syst., 38, 17:1-17:43 (2013)
[23] Li, M.; Vo, Q.; Kowalczyk, R., Efficient heuristic approach to dominance testing in cp-nets, (The 10th International Conference on Autonomous Agents and Multiagent systems. The 10th International Conference on Autonomous Agents and Multiagent systems, AAMAS 2011, vol. 1 (2011), International Foundation for Autonomous Agents and Multiagent Systems: International Foundation for Autonomous Agents and Multiagent Systems Richland, SC), 353-360
[24] Liu, F., (Reasoning About Preference Dynamics, vol. 354 (2011), Springer) · Zbl 1230.03003
[25] Mattei, N.; Pini, M. S.; Rossi, F.; Venable, K. B., Bribery in voting with cp-nets, Ann. Math. Artif. Intell., 1-26 (2013) · Zbl 1282.91095
[26] Oloriz, E.; Candeal, J. C.; Indurain, E., Representability of interval orders, J. Econ. Theor., 78, 219-227 (1998) · Zbl 0895.90023
[28] Rossi, F.; Venable, K.; Walsh, T., Preferences in constraint satisfaction and optimization, AI Mag., 29, 58-68 (2008)
[29] Santhanam, G.; Basu, S.; Honavar, V., Representing and reasoning with qualitative preferences for compositional systems, J. Artif. Intell. Res., 42, 211-274 (2011) · Zbl 1234.68454
[31] Stefanidis, K.; Koutrika, G.; Pitoura, E., A survey on representation, composition and application of preferences in database systems, ACM Trans. Database Syst., 36, 19:1-19:45 (2011)
[32] Wilson, N., Computational techniques for a simple theory of conditional preferences, Artifi. Intell., 175, 1053-1091 (2011) · Zbl 1225.68250
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.