A New Axiomatic Framework for Prioritized Fuzzy Constraint Satisfaction Problems

Abstract

The paper introduces an axiomatic framework for prioritized fuzzy constraint satisfaction problems (PFCSPs), in which the notion of global satisfaction degree is based on three intuitive axioms. First, if a constraint with the highest priority in a PFCSP is completely violated by a variable assignment, the variable assignment cannot be a solution to the PFCSP. Second, a PFCSP with all constraints having the same priority should degenerate into a non-prioritized FCSP. Third, the global satisfaction degree of a PFCSP must be monotonic with respect to that of the corresponding FCSP. However, the precedent scheme for PFCSPs in [2, 1] satisfies only our last axiom but not the first two directly, especially in the case where the priorities of constraints are determined by voting. Also, our framework improves the precedent scheme on the scale for priorities. Thus, some issues in the precedent scheme can easily been handled in our framework. Besides, we discuss methods to construct various global satisfaction degrees that satisfy our axioms. In [2, 1], there is no similar discussion. Actually, the global satisfaction degree in [2, 1] is given by a special formula, while ours by a sort of more general formulas. Moreover, by our methods some new formulas for global satisfaction degree different from that in [2, {cx1|1}] have been constructed. In addition, our results show that a PFCSP can be transformed equivalently into an FCSP, and so techniques developed for solving FCSPs can be adopted for solving PFCSPs. The idea behind our framework could be used to prioritize some other fuzzy problems.

The work described in this paper was supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (RGC Ref. No. CUHK4304/98E). The work is also partially supported by the Postdoctoral Fellowship Scheme of the Chinese University of Hong Kong.