This paper examines how service providers may resolve the trade-off between their personalization efforts and users? individual privacy concerns through negotiations. The analysis includes the identification of relevant and negotiable privacy dimensions for different usage domains. Based on a formalization of the user?s privacy revelation problem, we model the negotiation process as a Bayesian game where the service provider faces different types of users. Finally an extension to P3P is proposed that allows a simple expression and implementation of negotiation processes.