Constraints and Preferences: The Interplay of Preferences and Algorithms

T. Schiex and M. Cooper

As logic, constraint satisfaction faces the problem of inconsistency which itself naturally leads to the need of expressing preferences. Starting from Rosenfeld in 1976}, which defined fuzzy constraint networks, a variety of extended constraint frameworks have been proposed. Since 1995, several general axiomatic frameworks that try to cover all these proposals have been introduced. In this paper, we show how algorithms and axioms interacts on a specific class of algorithms: arc consistency enforcing algorithms. The generalization of arc consistency to the Valued CSP framework was recently made possible thanks to the addition of an additional axiom that captures the existence of difference between preferences. We show that many usual (and less usual) instances satisfy this axiom. This new axiom naturally suggests a modification of the set of axioms that could simplify both the axiom sets, the algorithms and the proofs on Valued CSP. It consists in shifting from a semi-group to a full group, where the existence of an opposite is guaranteed. We consider this alternate definition and show that it leads to a strong reduction of the framework generality.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.