| Report ID: | 07-02-272354-33 |
| Initial Submission Date: | 2007-02-27 |
| Title: | Network Formation: Bilateral Contracting and Myopic Dynamics |
| Summary: | We consider a network formation game where a finite number of 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 best strategy, nodes optimize their single period
payoff only. We characterize a simple set of assumptions under which
these dynamics will converge to a pairwise stable network topology; 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. Further, we show that these assumptions are satisfied by
a contractual model motivated by bilateral Rubinstein bargaining with
infinitely patient players.
|
| Authors: | Arcaute, Esteban; Dallal, Eric; Johari, Ramesh; Mannor, Shie |
| Contact email: | ramesh.johari@stanford.edu |
| | Number of views : 1002 Number of downloads : 337 |
