Network Creation Games: Think Global - Act Local

摘要: We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims central position at minimum cost creating edges. In particular, general (Fabrikant et al., PODC'03) became popular studying structure Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bil\`o SPAA'14), where worst case presented, which came with high efficiency loss terms quality equilibria. Our main contribution is new and more optimistic view on locality: agents are limited their knowledge actions to local ranges, but can probe different strategies finally choose best. study influence our notion hardness computing best responses, convergence equilibria, Moreover, we compare strength versus non-local strategy-changes. results address gap between original variant. On bright side, line observations from model, yet have non-constant lower bound price anarchy.