SG-PAC: Navigating the Privacy Paradox with Stochastic Games

TL;DR

Social network users often want to share their lives while protecting their secrets—a conflict known as the Privacy Paradox. This paper introduces SG-PAC, a framework that treats privacy protection as a General-Sum Stochastic Game. By clustering friends into "roles" and using reinforcement learning, it calculates the optimal balance between social fun and data safety, providing users with dynamic access-control policies that adapt as threats evolve.

The Motivation: Why Static Policies Fail

In modern Online Social Networks (OSNs), your privacy isn't just about what you post; it's about how that information drifts through your friends' networks. Traditional methods like RelBAC rely on static attributes (e.g., "is this person a family member?"). However, "unwanted knowers"—advertisers, data scrapers, or malicious actors—are dynamic. They change their targets and methods.

The authors argue that current models face two major issues:

1. They ignore information propagation characteristics.
2. They cannot dynamically adjust policies when attackers change strategies.

Methodology: The "Game" of Privacy

The researchers framed the interaction between a user (Ego) and attackers (Opponents) as a multi-person, two-camp dynamic game.

1. Quantifying Risk with Entropy

To make a game work, you need a score. The authors proposed a new criterion for privacy-risk measurement using Shannon Entropy. $\Delta H=H(X)-H(X|E)$ Essentially, they measure the "uncertainty" of your private info. If an attacker's actions significantly reduce this uncertainty, the risk is high.

2. Solving the State-Space Explosion: Role Mining

A typical user has hundreds of friends. Analyzing every friend as an independent actor in a game would overwhelm any computer. To fix this, the authors used Role Mining (RMPM) to cluster friends into roles based on their propagation capability (RPC).

Figure 1: The SG-PAC framework architecture, showing the transition from social datasets to role-based game analysis.

3. Finding the Equilibrium (Nash Strategy)

The game is solved using a Stationary Markov Equilibrium. Unlike a "Zero-Sum" game (where one person's gain is exactly the other's loss), a General-Sum game allows for more complex, realistic scenarios where both parties have different payoff structures. They used the OFF-SGSP (Offline Stochastic Game Strategic Planning) algorithm to train the model.

Experimental Evidence

The authors tested SG-PAC on real Facebook and Twitter data from the SNAP collection.

Key Performance Insights:

• Adaptability: In specific Facebook scenarios, the model reached an equilibrium where it recommended revoking access to specific "Roles" with 100% probability because those roles were currently vulnerable to reaching by opponents.
• Discount Factor ($\beta$): As the discount factor increases, the difference in payoffs between good and bad strategies becomes more pronounced. This serves as a "wake-up call" for users in highly active networks—your strategy matters even more there.

Table 4: Expected payoffs for Ego and Opponents across different network states.

Comparison with SOTA

Compared to RelBAC (Static/Relationship-based) and Zero-Sum Games, SG-PAC showed a distinct advantage:

• RelBAC couldn't handle the dynamic nature of information flow.
• Zero-Sum models were found to be too simplistic, often generating "pure" strategies that don't match the nuanced reality of social interactions. SG-PAC provides mixed strategies (probabilities), which are more robust.

Critical Analysis & Conclusion

Takeaway: SG-PAC successfully turns the abstract "Privacy Paradox" into a solvable mathematical problem. By abstracting users into "roles," it makes game-theoretic privacy management practical for real-world use.

Limitations:

• Computational Cost: Training the model can take hours for very large role sets, though the authors suggest multi-threading and lowering accuracy requirements can reduce this to minutes.
• Role Stability: The model assumes roles (friendship clusters) stay relatively stable. If someone's social circle changes drastically every hour, the policy generation might lag.

Future Outlook: The next frontier is applying this to evolutionary game theory, where the strategies of users and platforms evolve over years, potentially shaping the future of how social media platforms design privacy settings by default.