Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent’s connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha \) and the number of agents n. Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\varOmega \left( \log \left( \frac{n}{\alpha }\right) \right) \) lower bound for NE, and a tight linear bound for GE for low  \(\alpha \) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Network Creation Games with 2-Neighborhood Maximization

  • Merlin de la Haye,
  • Pascal Lenzner,
  • Daniel Schmand,
  • Nicole Schröder

摘要

Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent’s connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha \) and the number of agents n. Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\varOmega \left( \log \left( \frac{n}{\alpha }\right) \right) \) lower bound for NE, and a tight linear bound for GE for low  \(\alpha \) .