From Social Group Utility Maximization to Personalized Location Privacy in Mobile Networks

With increasing popularity of location-based services (LBSs), there have also been growing concerns for location privacy. To protect location privacy in an LBS, mobile users in physical proximity can work in concert to collectively change their pseudonyms, in order to hide spatial-temporal correlation in their location traces. In this paper, we leverage mobile users' social tie structure to motivate them to participate in pseudonym change. Drawing on a social group utility maximization framework, we cast users' decision making of whether to change pseudonyms as a socially aware pseudonym change game (SA-PCG). The SA-PCG further assumes a general anonymity model that allows a user to have its specific anonymity set for personalized location privacy. For the SA-PCG, we show that there exists a socially aware Nash equilibrium (SNE), and quantify the system efficiency of SNEs with respect to the optimal social welfare. Then, we develop a greedy algorithm that myopically determines users' strategies, based on the social group utility derived from only the users whose strategies have already been determined. We show that this algorithm efficiently finds an SNE that enjoys desirable properties: 1) it is socially aware coalition-proof, and thus is also Pareto-optimal; 2) it achieves higher social welfare than any SNE for the socially oblivious pseudonym change game. We further quantify the system efficiency of this SNE with respect to the optimal social welfare. We also show that this SNE can be achieved in a distributed manner. Numerical results using real data corroborate that social welfare can be significantly improved by exploiting social ties.