Privacy in the digital world is an important problem which is becoming even more pressing as new collaborative applications are developed. The lack of privacy preserving mechanisms is particularly problematic in federated identity management contexts. In such a context, users can seamlessly interact with a variety of federated web services, through theuse of single-sign-on mechanisms and the capability of sharing personal data among these web services. We argue that comprehensive privacy policies should be stated by federated service providers and proactively checked by these providers, before disclosing users’ data to federated partners. To address such requirements, we introduce mechanisms and algorithms for policy compliance checking between federated service providers, based on an innovative policy subsumption approach. We formally introduce and analyze our approach.