IEEE Transactions on Automatic Control, Vol.54, No.8, 1765-1778, 2009
Network Formation: Bilateral Contracting and Myopic Dynamics
We consider a network formation game where nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths ( if possible). Cost is incurred to a node from four sources: 1) routing traffic; 2) maintaining links to other nodes; 3) disconnection from destinations the node wishes to reach; and 4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together ( a variation on the notion of pairwise stability). We study such a game under a form of myopic best response dynamics. In choosing their action, nodes optimize their single period payoff only. We characterize a simple set of assumptions under which these dynamics converge to a stable network; we also characterize an important special case, where the dynamics converge to a star centered at a node with minimum cost for routing traffic. In this sense, our dynamics naturally select an efficient equilibrium.