Efficient heuristic approach to dominance testing in CP-nets

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)


CP-net (Conditional Preference Network) is one of the extensively studied languages for representing and reasoning with preferences. The fundamental operation of dominance testing in CP-nets, i.e.determining whether an outcome is preferred to another, is very important in many real-world applications. Current techniques for solving general dominance queries is to search for improving flipping sequence from one outcome to another as a proof of the dominance relation in all rankings satisfying the given CP-net. However, it is generally a hard problem even for binary-valued, acyclic CP-nets and tractable search algorithms exist only for specific problem classes. Hence, there is a need for efficient algorithms and techniques for dominance testing in more general problem settings. In this paper, we propose a heuristic approach, called DT*, to dominance testing in arbitrary acyclic multi-valued CP-nets. Our proposed approach guides the search process efficiently and allows significant reduction of search effort without impacting soundness or completeness of the search process. We present results of experiments that demonstrate the computational efficiency and feasibility of our approach to dominance testing.
Original languageEnglish
Title of host publicationAAMAS 2011
Subtitle of host publicationProceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems
EditorsKagan Tumer, Pinar Yolum, Liz Sonenberg, Peter Stone
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems
Number of pages8
ISBN (Print)9780982657171
Publication statusPublished - 2011
Externally publishedYes
EventInternational Conference on Autonomous Agents and Multiagent Systems - Taipei, Taiwan
Duration: 2 May 20116 May 2011


ConferenceInternational Conference on Autonomous Agents and Multiagent Systems


  • CP-nets
  • Dominance Testing
  • Heuristic

Cite this