Temporal network creation games: the impact of non-locality and terminals
摘要
Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting, and agents might only want to ensure reachability of a subset of nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.