The creation of dynamic coalitions is a challenging task, seen from a security perspective. Due to the presence of conflicting requirements and specifications, the policy negotiation and policy merging processes call for the use of efficient techniques to resolve ambiguities. Constraints and constraint programming on the other hand, are useful means for representing a wide range of access control states and access control problems. In this paper we utilize constraints to represent access control policies in a multi-domain environment. In contrast to monolithic (crisp) constraint satisfaction techniques, we extend the applicability of constraints for access control, by examining soft constraints and partial constraint satisfaction. We also introduce a security framework based on fuzzy constraints that allows the determination of preferences for the participating domains.