Coalitional Games in OSN: A Strategic Approach to Anonymous Privacy Management

TL;DR

This research tackles the "Co-ownership Privacy Conflict" in Online Social Networks (OSNs). Instead of relying on a central server, the authors propose a decentralized protocol where owners of shared data form a coalition. Using Cooperative Game Theory and Threshold RSA, they create a system where users access data anonymously, and the "workload" of maintaining this privacy is distributed fairly among owners based on their device capabilities and social standing.

Problem & Motivation: The Tragedy of the Shared Photo

In modern OSNs, privacy is usually a solo sport. You set your settings, and I set mine. But what happens when we share a resource—like an album of photos from a joint vacation? Current systems fail to address these conflicting preferences.

The authors argue that privacy management is inherently a collaborative yet rational process. Users won't participate if the computational cost (especially on smartphones) outweighs the social benefit. Previous works like the Clarke-Tax voting protocol focused on utility but didn't account for the varying "bargaining power" and hardware constraints of participants.

Methodology: Privacy Through the Lens of Game Theory

The core of the paper is a 4-phase protocol integrated with a Transferable Utility (TU) Game model.

1. The Cryptographic Backbone

The protocol uses a decentralized version of the Persiano et al. credential system. By applying Joint Random Secret Sharing (JRSS), $n$ founders generate RSA parameters without a central dealer. To grant access to a requester, at least $t+1$ owners must provide partial signatures.

2. The Fairness Engine: Shapley Value

The standout contribution is the formalization of the Credential Assignment phase as a TU-game. The researchers use the Shapley Value—a way to fairly distribute total gains and costs in a coalition—to determine how much "effort" each owner should contribute.

The cost-benefit function factors in:

• $u_i$: The personal utility of the system running smoothly.
• $b_i$: The gain from helping a friend of a fellow owner.
• $c_i$: The computational cost (PC vs. Smartphone).
• ${\Gamma }_i$: The number of friendship connections (social influence).

Figure 1: The Credential Assignment phase requiring (t+1) signatures.

Experiments & Results: Who Shoulders the Burden?

The authors categorized users into three types: Beginners, Buddies (favor their own friends), and Socializers (high utility for overall network flow).

Key findings from the simulations:

• Device Impact: Users on PCs assume a larger share of the "global cost" compared to those on smartphones, which allows the network to remain inclusive for mobile users.
• Social Connectivity: The more friends an owner has (${\Gamma }_i$), the higher their Shapley value. In a 3-player scenario where one player had 10x more friends, their contribution share jumped to 51.04% (see Table 2).
• Threshold Effect: As the security threshold $t$ grows closer to $n$, the difference between various user types' contributions diminishes, creating a more "democratic" but potentially more expensive environment.

Figure 2: Changes in Shapley Value as threshold (t) increases.

Critical Insight & Conclusion

This paper shifts the focus from "how to encrypt" to "how to motivate." By proving that a decentralized protocol can be fair (in the Myerson sense of balanced contributions), the authors provide a roadmap for building sustainable, owner-less privacy layers in social apps.

Limitations: While the theoretical framework is robust, the computational overhead of zero-knowledge proofs on 2012-era smartphones—and the scalability of JRSS for thousands of users—remains a concern. However, as "Socializer" behavior becomes the norm in decentralized spaces, this coalitional approach offers a mathematically grounded way to manage the inherent tension between transparency and privacy.