Strategic Network Formation through an Intermediary / 447
Elliot Anshelevich, Onkar Bhardwaj, Koushik Kar
PDF

Settings in which independent self-interested agents form connections with each other are extremely common, and are usually modeled using network formation games. We study a natural extension of network formation games in which the nodes cannot form connections themselves, but instead must do it through an intermediary, and must pay the intermediary to form these connections. The price charged by the intermediary is assumed to be determined by its operating costs, which in turn depend on the total amount of connections it facilitates. We investigate the existence and worst-case efficiency (price of anarchy) of stable solutions in these settings, and especially when the intermediary uses common pricing schemes like proportional pricing or marginal cost pricing. For both these pricing schemes we prove existence of stable solutions and completely characterize their structure, as well as generalize these results to a large class of pricing schemes. Our main results are on bounding the price of anarchy in such settings: we show that while marginal cost pricing leads to an upper bound of only 2, i.e., stable solutions are always close to optimal, proportional pricing also performs reasonably well as long as the operating costs of the intermediary are not too convex.