An ever-growing number of XML-based languages are used to describe Web Service related issues such as security (WS-Security Policy), access control (XAC- ML), or privacy (P3P-WS). While it is desirable to specify policies in a declarative way, these languages expose great diversity in both syntax and semantics making it hard to realize a unified system. Our contribution to this problem is twofold. First, we present an expressive formal notation for policies. Second, we show how requester-, provider-, and third-party policies can be used for choosing a suitable service while making sure that all relevant policies are obeyed.