2026-07-21T18:40:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:103 2024-03-06T11:06:00Z ddc:004 open_access

Preferences and Domination Goldsmith, Judy Preferences CP-nets PSPACE-complete reductions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Judy Goldsmith 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.04421.4 urn:nbn:de:0030-drops-1038 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.4 eng https://creativecommons.org/licenses/by/4.0/legalcode