On dynamics in basic network creation games.

*(English)*Zbl 1233.91071
Persiano, Giuseppe (ed.), Algorithmic game theory. 4th international symposium, SAGT 2011, Amalfi, Italy, October 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24828-3/pbk). Lecture Notes in Computer Science 6982, 254-265 (2011).

Summary: We initiate the study of game dynamics in the Sum Basic Network Creation Game, which was recently introduced by N. Alon et al. [“Basic network creation games”, in: Proc. of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2010, 106–113 (2010)]. In this game players are associated to vertices in a graph and are allowed to “swap” edges, that is to remove an incident edge and insert a new incident edge. By performing such moves, every player tries to minimize her connection cost, which is the sum of distances to all other vertices. When played on a tree, we prove that this game admits an ordinal potential function, which implies guaranteed convergence to a pure Nash Equilibrium. We show a cubic upper bound on the number of steps needed for any improving response dynamic to converge to a stable tree and propose and analyse a best response dynamic, where the players having the highest cost are allowed to move. For this dynamic we show an almost tight linear upper bound for the convergence speed. Furthermore, we contrast these positive results by showing that, when played on general graphs, this game allows best response cycles. This implies that there cannot exist an ordinal potential function and that fundamentally different techniques are required for analysing this case. For computing a best response we show a similar contrast: On the one hand we give a linear-time algorithm for computing a best response on trees even if players are allowed to swap multiple edges at a time. On the other hand we prove that this task is NP-hard even on simple general graphs, if more than one edge can be swapped at a time. The latter addresses a proposal by Alon et al. [loc. cit.].

For the entire collection see [Zbl 1225.91006].

For the entire collection see [Zbl 1225.91006].