Network Creation Games with 2-Neighborhood Maximization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912226571452416 |
|---|---|
| author | de la Haye, Merlin Lenzner, Pascal Schmand, Daniel Schröder, Nicole |
| author_facet | de la Haye, Merlin Lenzner, Pascal Schmand, Daniel Schröder, Nicole |
| contents | 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 $α$ 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 $Ω(\log(\frac{n}α))$ lower bound for NE, and a tight linear bound for GE for low $α$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06561 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Network Creation Games with 2-Neighborhood Maximization de la Haye, Merlin Lenzner, Pascal Schmand, Daniel Schröder, Nicole Computer Science and Game Theory 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 $α$ 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 $Ω(\log(\frac{n}α))$ lower bound for NE, and a tight linear bound for GE for low $α$. |
| title | Network Creation Games with 2-Neighborhood Maximization |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.06561 |