[Nrg-l] Game Theory presentation - Wednesday Nov 12 @ 2:30pm

Jorge Londoño jmlon at cs.bu.edu
Tue Nov 11 19:09:26 EST 2008

Dear all,

Tomorrow we will have this presentation at 2:30pm, MCS 135:

Network Formation: Bilateral Contracting and Myopic Dynamics
Esteban D. Arcaute, Ramesh Johari, and Shie Mannor
IEEE Transactions on Automatic Control

Available online: 

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. Further, we show that these
assumptions are satisfied by a contractual model motivated by the
bilateral Rubinstein bargaining model.


More information about the Nrg-l mailing list