The price of selfish behavior in bilateral network formation

Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study the quality (price of anarchy) of equilib-rium networks in a game where links require the consent of both participants and are negotiated bilaterally, and compare these networks to those generated by an earlier model due to Fabrikant et al. [10] in which links are formed unilaterally. We provide a partial characterization of stable and efficient networks in the bi-lateral network formation game, and provide examples of stable networks that are not Nash graphs in the unilateral game. We develop an upper and lower bound on the price of anarchy of the bilateral game. An empirical analysis demonstrates that the av-erage price of anarchy is better in the bilateral connection gam