On the Windfall and price of friendship: Inoculation strategies on social networks

Dominic Meier, Yvonne-Anne Pignolet, Stefan Schmid, Roger Wattenhofer

TL;DR

This paper introduces a game-theoretic framework to study how social connections influence individual decisions in a virus inoculation game. They quantify the "Windfall of Friendship" (WoF), showing that caring about friends generally improves social welfare, but this benefit isn't always monotonic with stronger ties. The work also highlights that social networks can lead to longer convergence times to equilibrium, a "price of friendship."

What Problem Does This Paper Address?

Traditional game theory often assumes purely selfish agents. However, in real-world social networks, people are influenced by their friends' well-being. This paper addresses the gap between these models by developing a framework to analyze how altruistic considerations towards friends impact strategic decisions and overall social welfare in a network context. Specifically, they investigate a virus inoculation game where players decide whether to pay for protection, considering not only their own costs but also the costs incurred by their friends. This is particularly relevant given the increasing prevalence of network-based threats like viruses and worms.

Methods

The authors introduce a novel game-theoretic model that incorporates "friendship" by modifying players' cost functions. A "Friendship Factor" (F) quantifies how much a player considers their friends' costs. They define two types of perceived costs:

  • Absolute Perceived Cost: A player's perceived cost is their actual cost plus a weighted sum of their friends' actual costs.
  • Relative Perceived Cost: A player's perceived cost is their actual cost plus a weighted sum of their friends' actual costs, where the weight is normalized by the number of friends.

They then analyze "friendship Nash equilibria" (FNE) based on these perceived costs and compare them to standard Nash equilibria (where F=0). Key analytical tools include:

  • Windfall of Friendship (WoF): The ratio of the worst Nash equilibrium's social cost to the worst FNE's social cost. A WoF > 1 indicates a benefit from friendship.
  • Potential Function Argument: Used to prove convergence of best-response sequences in certain network structures.
  • Reduction to NP-hard problems: Used to establish the computational complexity of finding equilibria.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations on synthetic graph structures (star graphs, complete graphs, Kleinberg graphs).

Key Insights and Ideas

  • Friendship is Generally Beneficial: Caring about friends (positive F) consistently leads to better social outcomes (WoF > 1) compared to purely selfish behavior. This means social connections can mitigate the inefficiencies of selfish systems.
  • Non-Monotonicity of Benefits: Surprisingly, the "Windfall of Friendship" doesn't always increase with stronger social ties (larger F). In some scenarios, particularly with absolute perceived costs, increasing F can initially improve welfare but then plateau or even slightly decrease it before potentially rising again. This challenges the intuitive notion that "more friendship is always better."
  • The "Price of Friendship": While friendship improves equilibrium outcomes, it can significantly increase the time it takes for the system to reach an equilibrium. This "price" is measured in the number of best-response rounds.
  • Equilibria are Computationally Hard: Finding the best or worst friendship Nash equilibrium is NP-complete, suggesting that efficiently determining optimal or worst-case social outcomes in these networks is challenging.
  • Strategic Placement Matters: Simulations suggest that the benefit of friendship isn't just about having more secure players, but also about where those secure players are located in the network, influencing the overall spread of the virus.

Key Results

  • WoF > 1: The paper proves that the Windfall of Friendship is always greater than 1 for the virus inoculation game, meaning social welfare improves with friendship.
  • Upper Bound on WoF: For complete graphs ($K_n$), the WoF is bounded by 4/3, and this bound is tight. For star graphs ($S_n$), the WoF can grow linearly with the number of players ($n$) in some cases.
  • Convergence Times: Simulations show that convergence times are significantly longer in social networks compared to purely selfish ones, often more than doubling.
  • NP-Completeness: Computing the best and worst pure friendship Nash equilibria is proven to be NP-complete for any friendship factor F.

Limitations and Future Work

  • Limited Game Scope: The analysis is primarily focused on a virus inoculation game. The authors suggest extending the framework to other games, such as potential games or games exhibiting Braess paradox.
  • Simplified Social Influence: The models consider direct friendship ties. Future work could explore more complex social influence, like caring about friends of friends.
  • Behavioral Models: The current models assume rational players. Incorporating behavioral models beyond pure rationality could provide richer insights.
  • General Graph Structures: While simulations on Kleinberg graphs are presented, a deeper theoretical understanding of convergence and equilibria on more complex, general graph structures remains an open question.
  • Practical Implications: While the paper touches on practical implications for system design, further exploration of how to leverage or mitigate these social dynamics in real-world systems is warranted.

Summary updated

Abstract

This article investigates selfish behavior in games where players are embedded in a social context. A framework is presented which allows us to measure the Windfall of Friendship, i.e., how much players benefit (compared to purely selfish environments) if they care about the welfare of their friends in the social network graph. As a case study, a virus inoculation game is examined. We analyze the corresponding Nash equilibria and show that the Windfall of Friendship can never be negative. However, we find that if the valuation of a friend is independent of the total number of friends, the social welfare may not increase monotonically with the extent to which players care for each other; intriguingly, in the corresponding scenario where the relative importance of a friend declines, the Windfall is monotonic again. This article also studies convergence of best-response sequences. It turns out that in social networks, convergence times are typically higher and hence constitute a price of friendship. While such phenomena may be known on an anecdotal level, our framework allows us to quantify these effects analytically. Our formal insights on the worst case equilibria are complemented by simulations shedding light onto the structure of other equilibria.
BibTeX
@article{meier2014windfall,
  author = {Dominic Meier and Yvonne-Anne Pignolet and Stefan Schmid and Roger Wattenhofer},
  title = {{On the Windfall and price of friendship: Inoculation strategies on social networks}},
  journal = {Computer Networks},
  year = {2014},
  url = {https://openreview.net/forum?id=oErIr1mfXnmX},
}
Figure