DagSemProc.04421.4.pdf
- Filesize: 239 kB
- 10 pages
Document
Preferences and Domination
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 4421
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-03-24
Cite AsGet BibTex
Judy Goldsmith. Preferences and Domination. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.04421.4
https://doi.org/10.4230/DagSemProc.04421.4
Abstract
CP-nets are a succinct formalism for specifying preferences over a multi-featured domain. A CP-net consists of a directed graph, with nodes representing the features of the domain, and edges indicating conditional preferences.
An instance in the domain is an assignment of values to the features. An instance alpha is preferred to an instance beta if there are a sequence of "improving flips" from alpha to beta, where an improving flip changes the value of one feature to a more-preferred value, based on the values of the parents of that feature. We say alpha dominates beta if such a sequence exists.
We show that recognizing dominance is PSPACE hard for cyclic CP-nets.
Keywords
- Preferences
- CP-nets
- PSPACE-complete
- reductions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads