Network Creation Games with Local Information and Edge Swaps

Abstract

In the swap game (SG) selfish players, each of which is associated to a vertex, form a graph by edge swaps, i.e., a player changes its strategy by simultaneously removing an adjacent edge and forming a new edge (Alon et al., 2013). The cost of a player considers the average distance to all other players or the maximum distance to other players. Any SG by $n$ players starting from a tree converges to an equilibrium with a constant Price of Anarchy (PoA) within $O(n^3)$ edge swaps (Lenzner, 2011). We focus on SGs where each player knows the subgraph induced by players within distance $k$. Therefore, each player cannot compute its cost nor a best response. We first consider pessimistic players who consider the worst-case global graph. We show that any SG starting from a tree (i) always converges to an equilibrium within $O(n^3)$ edge swaps irrespective of the value of $k$, (ii) the PoA is $\Theta (n)$ for $k=1,2,3$, and (iii) the PoA is constant for $k\ge 4$. We then introduce weakly pessimistic players and optimistic players and show that these less pessimistic players achieve constant PoA for $k\le 3$ at the cost of best response cycles.

References in corpus (1)

• Locality-based Network Creation Games