|
|
|
| Algebraic Representation and Model Solving Algorithm for CP-nets |
| LIU Jing-Lei, LIU Zhao-Wei, SUN Xue-Jiao, WU Shuan-Hu |
| School of Computer Science and Technology, Yantai University, Yantai 264005 |
|
|
|
|
Abstract Conditional preference networks (CP-nets)is a popular language which represents qualitative conditional preference relation. Aiming at the problem that graphical representation is not enough to fulfill operations on CP-nets, an algebraic representation of CP-nets is offered with the well-known adjacent list approach. In the approach, vertical nodes are organized by topological order, and horizontal nodes are organized by their parents. Particularly, conditional preference table of nodes are represented by main disjunctive normal form of proposition logic. A direct model solving algorithm is devised later, and an indirect model solving algorithm is gotten based on relation operation on direct model. In short, the representation approach reveals that CP-nets can be not only represented by simple and intuitive graphical approach, but also represented by compacted algebraic approach.
|
|
Received: 08 October 2010
|
|
|
|
|
|
[1] Brafman R, Domshlak C. Preference Handling-An Introductory Tutorial. AI Magazine, 2009, 30(1): 58-86
[2] Boutilier C, Brafman R, Domshlak C, et al. CP-Nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements. Journal of Artificial Intelligence Research, 2004, 21: 135-191
[3] Koriche F, Zanuttini B. Learning Conditional Preference Networks with Queries // Proc of the 21st International Joint Conference on Artificial Intelligence. Pasadena, USA, 2009: 1930-1935
[4] Koriche F, Zanuttini B. Learning Conditional Preference Networks. Artificial Intelligence, 2010, 174(11): 685-703
[5] Conitzer V. Making Decisions Based on the Preferences of Multiple Agents. Communications of the ACM, 2010, 53(3): 84-94
[6] Lin Fangzhen, Tang Pingzhong. Computer-Aided Proofs of Arrows and Other Impossibility Theorems. Artificial Intelligence, 2009, 173(8/9): 1041-1053
[7] Lang J. Logical Preference Representation and Combinatorial Vote. Annals of Mathematics and Artificial Intelligence, 2004, 42(1/2/3): 37-71
[8] Conitzer V, Sandholm T, Lang J. When Are Elections with Few Candidates Hard to Manipulate. Journal of the ACM, 2007, 54(3): 1-33
[9] Zuckerman M, Procaccia A D, Rosenschein J S. Algorithms for the Coalitional Manipulation Problem. Artificial Intelligence, 2009, 173(8/9): 392-412
[10] Liu Jinglei, Zhang Wei, Wang Lingling. Algebra Property and Application of Coalition Structure Graph. Pattern Recognition and Artificial Intelligence, 2009, 22(6): 841-847 (in Chinese)
(刘惊雷,张 伟.王玲玲.联盟结构图的代数性质及应用.模式识别与人工智能, 2009, 22(6): 841-847 )
[11] Domshlak C, Prestwich S, Rossi F, et al. Hard and Soft Constraints for Reasoning about Qualitative Conditional Preferences. Journal of Heuristics, 2006, 12(4/5), 263-285
[12] Zhang Zhizheng, Xing Hancheng, Wan Zhenzhen, et al. A Preference Logic Based on Various Kinds of Preferences. Journal of Software, 2007, 18(11): 2728-2739 (in Chinese)
(张志政,邢汉承,王蓁蓁,等.一种基于多类型偏好的偏好逻辑.软件学报, 2007, 18(11): 2728-2739)
[13] Yuan Chongyi, Qu Wanling. Discrete Mathematics and Its Applications. Beijing, China: China Machine Press, 2001: 393-396 (in Chinese)
(袁崇义,屈婉玲.离散数学及其应用.北京:机械工业出版社, 2001: 393-396)
[14] Wicker A W, Doyle J. Interest-Matching Comparisons Using CP-Nets // Proc of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada, 2007, II: 1914-1915 |
|
|
|
2011, Vol. 24 
