| Summary: | 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. Cost is incurred to a node from three sources: (1) traffic related costs; (2) maintaining links to other nodes; and (3) payments made to other nodes (from contracts). Two models for traffic related costs are studied: cost that arises from routing packets and cost that is related to distance, or latency. We define a network to be stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together.
We study such games under a natural form of myopic local best-response dynamics. In each step there are two stages. During the first stage, an exogenously designated node u considers all possible unilateral deviations. Then, during the second stage, it considers forming a new contract with a node v in its neighborhood. That contract can be accepted or rejected by v. Both nodes choose their actions to maximize their prospective payoff after the second stage, and consider the current network state when making a decision. These dynamics generalize best-response dynamics and allow some flexibility to the deviating nodes. We characterize certain assumptions under which these dynamics converge to a pairwise stable network topology; our assumptions are satisfied by the contractual model that corresponds to uniform cost sharing.
Notably, for both cost models that we consider, our dynamics select efficient pairwise stable equilibria. These are notable results since some pairwise stable outcomes can be highly inefficient, so our dynamics act as a decentralized procedure for selection of desirable equilibria. |
