Building coalitions between autonomous domains and managing the negotiation process between multiple security policies in a multi-domain environment is a challenging task. The negotiation process requires efficient modeling methods for the determination of secure access states and demands support from automated tools aiming to support administrators and to minimize human intervention; thus making the whole process more efficient and less error-prone. In this paper we define a framework that enables the representation of policy merging between autonomous domains, as a constraint satisfaction problem, while remaining neutral in regard to the policy language. Role and permission hierarchies are modeled using the constraint programming formalism. Policy mappings are utilized in order to enable cross-organizational role assignment. Further optimization on policy mappings is achieved by casting the problem to a partially ordered multi-criteria shortest path problem.Full Text at Springer, may require registration or fee