TL;DR
This paper introduces an automated negotiation mechanism for resolving conflicting privacy preferences among multiple users sharing an item on social media. To overcome the computational complexity of this negotiation, they propose several heuristics, demonstrating that one heuristic (GreedyBnB) can achieve near-optimal results with practical execution times.
What Problem Does This Paper Address?
Social media platforms are rife with shared content, like photos, that often involve multiple individuals. A significant challenge arises when these individuals have differing privacy preferences for the same item. Simply merging these preferences can lead to unsatisfactory outcomes. Existing approaches often fail to address these conflicts effectively, either by being too complex for real-time use or by not supporting collaborative decision-making, instead relying on unilateral impositions. This paper tackles the problem of enabling users to collaboratively negotiate and reach a compromise on privacy settings for shared items, specifically addressing the exponential complexity that arises from multiple users and potential conflicts.
Methods
The core of the proposed solution is an automated negotiation mechanism. This mechanism operates in two stages: first, it detects conflicts between the individual privacy policies of co-owners of an item. These policies are based on relationship-based access control, where privacy is defined by the intimacy (strength of relationship) between users, rather than just individual identities or roles. If conflicts are detected, the mechanism proceeds to a negotiation stage.
To handle the inherent complexity of this negotiation, which grows exponentially with the number of conflicting parties, the authors introduce several heuristics:
- Distance-based Heuristic: This heuristic prioritizes actions for target agents based on the difference in intimacy between the negotiating agents and the target agent. It aims to reduce the search space by focusing on actions suggested by the agent with the higher intimacy.
- Greedy Heuristic: This approach iteratively resolves conflicts by making locally optimal choices, aiming to find a global optimum. It uses a partial action vector and greedily selects the action that maximizes the product of utilities at each step.
- GreedyBnB Heuristic: This heuristic combines elements of the Greedy approach with Branch and Bound principles. It explores branches of the search space that the greedy heuristic might have discarded, using the greedy solution as a lower bound for utility. Crucially, this heuristic is designed to be "anytime," meaning it can be interrupted at any point and still provide a valid, albeit potentially suboptimal, solution.
Datasets
Not discussed in the paper. The authors mention generating random data for experiments, including random intimacies, relationship types, and privacy policies, ensuring at least one conflict occurred.
Key Insights and Ideas
- Intimacy as the Cornerstone of Privacy: The paper strongly reinforces the idea that relationship strength (intimacy) is the primary driver of user privacy preferences in social media, aligning with existing empirical evidence.
- The Challenge of Multi-User Privacy: The core problem of conflicting privacy preferences for shared items is a significant and under-addressed issue in current social media privacy management.
- Negotiation as a Solution: An automated negotiation framework is a viable and necessary approach to resolve these multi-user conflicts, moving beyond unilateral decision-making.
- Heuristics are Essential for Scalability: The exponential complexity of negotiation without heuristics makes it impractical for real-world social media. Heuristics are crucial for reducing the search space and enabling timely agreements.
- Anytime Algorithms for Practicality: The GreedyBnB heuristic's "anytime" nature is a key insight, offering a practical trade-off between computation time and solution quality, making it suitable for interactive social media environments.
Key Results
- Heuristics are Necessary: Without heuristics, the negotiation mechanism is computationally infeasible for even a moderate number of target agents (e.g., 200 agents would require considering ~10^50 action vectors).
- Greedy Heuristics Outperform: Both Greedy and GreedyBnB heuristics significantly reduce the number of action vectors considered and execution time compared to the non-heuristic approach.
- GreedyBnB Offers Best Trade-off: The GreedyBnB heuristic, particularly when bounded in execution time (e.g., 500ms), provides the best balance between optimality (low utility loss) and practical execution speed. For 200 agents, it achieved near-optimal results with only a ~3% utility loss in 500ms.
- Distance-based Heuristic Limitations: The distance-based heuristic shows promise for smaller numbers of agents but struggles to scale effectively and can lead to significant utility loss.
- Utility Loss: While heuristics introduce some utility loss compared to the optimal solution, the GreedyBnB heuristic minimizes this loss, especially with sufficient time.
Limitations and Future Work
- Limitations:
- The paper acknowledges that complete approaches (like dynamic programming or branch and bound) were not suitable due to the problem's structure and the difficulty in finding good upper bounds.
- The distance-based heuristic's performance is highly dependent on parameter choices and doesn't scale well.
- The Greedy heuristic, while fast, can lead to a noticeable loss of utility.
- Future Work:
- Investigate how disclosing items can influence and evolve user relationships, and how this might shape future negotiation outcomes.
- Incorporate the intimacy between negotiating parties into the negotiation strategy, as this is known to influence concession behavior.
- Explore more sophisticated anytime algorithm implementations for GreedyBnB to further refine the time-optimality trade-off.
Summary updated