The Computational Complexity of Dominance and Consistency in CP-Nets

How to model contrary-to-duty with GCP-nets

Preferences are ubiquitous in our everyday life. They are essential in the decision making process of individuals. Recently, they have also been employed to represent ethical principles, normative systems or guidelines. In this work we focus on a ceteris paribus semantics for deontic logic: a state of affairs where a larger set of respected prescriptions is preferable to a state of affairs where some are violated. Conditional preference networks (CP-nets) are a compact formalism to express and analyse ceteris paribus preferences, with some desirable computational properties. In this paper, we show how deontic concepts (such as contrary-to-duty obligations) can be modeled with generalized CP-nets (GCP-nets) and how to capture the distinction between strong and weak permission in this formalism. To do that, we leverage on an existing restricted deontic logic that will be mapped into conditional preference nets.

Cutting Cycles of Conditional Preference Networks with Feedback Set Approach

As a tool of qualitative representation, conditional preference network (CP-net) has recently become a hot research topic in the field of artificial intelligence. The semantics of CP-nets does not restrict the generation of cycles, but the existence of the cycles would affect the property of CP-nets such as satisfaction and consistency. This paper attempts to use the feedback set problem theory including feedback vertex set (FVS) and feedback arc set (FAS) to cut cycles in CP-nets. Because of great time complexity of the problem in general, this paper defines a class of the parent vertices in a ring CP-nets firstly and then gives corresponding algorithm, respectively, based on FVS and FAS. Finally, the experiment shows that the running time and the expressive ability of the two methods are compared.