Abstract
Conditional preference networks (CP-nets) have received significant attention for modeling preferences over combinations of features. However, dominance testing, the problem of inferring from a CP-net whether one outcome is always preferred over another, is NP-hard, requiring exponential time in practice. In this paper, we introduce the use of independent relaxed subproblems as a heuristic for faster inference from CP-nets. We show how to relax the constraints in the conditional preference tables and partition the network, yielding smaller subproblems that can be solved easily. The lengths of these solutions can then be added together to provide a heuristic for informed search algorithms such as A* and applied to dominance testing in CP-nets. We prove that the resulting additive heuristic function is admissible and consistent, guaranteeing optimality and completeness. We show from experiments on randomly generated binary and multivalued CP-nets that our method performs better than the state of the art, and can further be combined with other pruning techniques, resulting in greatly improved performance for dominance testing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Since the dependency graph is directed, each \(N_i\) is a weak component of N [10].
- 2.
We used the random generation method described by Allen et al. [3].
- 3.
Korf and Felner describe these cached solutions as a disjoint pattern database [11].
- 4.
Our code and data are available at https://github.com/thomas-allen-ai/dtrelax.
References
Ahmed, S., Mouhoub, M.: A divide and conquer algorithm for dominance testing in acyclic CP-nets. In: Proceedings of the 31st IEEE ICTAI, pp. 392–399 (2019)
Alashaikh, A., Alanazi, E.: Conditional preference networks for cloud service selection and ranking with many irrelevant attributes. IEEE Access 9, 131214–131222 (2021)
Allen, T.E., Goldsmith, J., Justice, H.E., Mattei, N., Raines, K.: Uniform random generation and dominance testing for CP-nets. J. Artif. Intell. Res. 59, 771–813 (2017)
Bistarelli, S., Fioravanti, F., Peretti, P.: Using CP-nets as a guide for countermeasure selection. In: Proceedings of the 2007 ACM SAC, pp. 300–304. ACM (2007)
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)
Cadilhac, A., Asher, N., Benamara, F., Lascarides, A.: Grounding strategic conversation: Using negotiation dialogues to predict trades in a win-lose game. In: Proceedings of the EMNLP 2013, pp. 357–368 (2013)
Cafaro, M., Mirto, M., Aloisio, G.: Preference-based matchmaking of grid resources with CP-nets. J. Grid Comput. 11(2), 211–237 (2013)
Floyd, R.: Algorithm 97: shortest path. Commun. ACM 345 (1962)
Goldsmith, J., Lang, J., Truszczyński, M., Wilson, N.: The computational complexity of dominance and consistency in CP-nets. J. Artif. Intell. Res. 33(1), 403–432 (2008)
Knuth, D.E.: The art of computer programming, volume 4, pre-fascicle 12A: components and traversal (2022)
Korf, R.E., Felner, A.: Disjoint pattern database heuristics. Artif. Intell. 134(1), 9–22 (2002)
Laing, K., Thwaites, P.A., Gosling, J.P.: Rank pruning for dominance queries in CP-nets. J. Artif. Intell. Res. 64, 55–107 (2019)
Li, M., Vo, Q.B., Kowalczyk, R., et al.: Efficient heuristic approach to dominance testing in CP-nets. In: AAMAS, pp. 353–360 (2011)
Loreggia, A., Mattei, N., Rossi, F., Venable, K.B.: Value alignment via tractable preference distance, chap. 18, pp. 249–261. Chapman and Hall/CRC (2018)
Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc. (1984)
Rossi, F., Mattei, N.: Building ethically bounded AI. Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 0101, pp. 9785–9789 (2019)
Rossi, F., Venable, K.B., Walsh, T.: mCP nets: representing and reasoning with preferences of multiple agents. In: Proceedings of the 19th AAAI Conference on Artificial Intelligence, pp. 729–734 (2004)
Tange, O.: GNU parallel: the command-line power tool. USENIX Mag. 36(1), 42–47 (2011)
Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)
Acknowledgments
The authors wish to thank Michael Ramage, who contributed to the codebase, and David Toth for assisting with computational resources.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland
About this paper
Cite this paper
Jiang, L., Allen, T.E. (2025). Independent Relaxed Subproblems for Dominance Testing in CP-Nets. In: Freeman, R., Mattei, N. (eds) Algorithmic Decision Theory. ADT 2024. Lecture Notes in Computer Science(), vol 15248. Springer, Cham. https://doi.org/10.1007/978-3-031-73903-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-73903-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-73902-6
Online ISBN: 978-3-031-73903-3
eBook Packages: Computer ScienceComputer Science (R0)