Joint ICWS Seminar & Topics in Systems Seminar
----------------------------------------------

On Network Formation Dynamics with Bilateral Contracts

Professor Shie Mannor
McGill University

Tuesday, May 6, 2008
3:30 p.m.
141 Coordinated Science Lab

Abstract:

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. Each
contract is endowed with a utility transfer. 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). We consider two models for traffic related costs: one
where cost arises from routing packets; and another where cost is
related to latency or number of hops. As a solution concept, we
define a network to be stable if no single node wishes to
unilaterally deviate, and no pair of nodes can profitably deviate
together; our definition is a variation on the notion of pairwise
stability. Our starting point is the identification of the set of
stable networks, showing that arbitrarily inefficient networks may be
stable. Our focus in this talk is on studying such games under myopic
local best response dynamics. We consider different dynamics focusing
on two desiderata: locality of information and selection of an
efficient equilibrium.

With these desiderata in mind we propose the following dynamics. The
network evolves in discrete steps, each consisting of 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 the target node. While
the designated node u chooses its actions to maximize its payoff at
the end of both stages, the target node v chooses a myopic best
response to maximize its payoff given the network after the first
stage.

We characterize a simple set of assumptions under which these
dynamics will converge to a pairwise stable network topology; as an
example, our assumptions are satisfied by a contractual model
motivated by bilateral Rubinstein bargaining with infinitely patient
players. We study the convergence rates as well as the efficiency of
the limit networks for the two models for traffic related costs.

Shie Mannor received his Ph.D. degree in electrical engineering from
the Technion-Israel Institute of Technology, in 2002. From 1996 to
2000, he was a researcher with the Intelligence Corps in the Israeli
Defense Forces. During the spring semester of 2002, he was a lecturer
at the Technion Electrical Engineering Department. From 2002 to 2004,
he was a postdoctoral associate in the Laboratory for Information and
Decision Systems at M.I.T. Since 2004 he has been an Assistant
Professor of the Department of Electrical and Computer Engineering at
McGill University where he holds the Canada Research Chair in Machine
Learning. His research interests include machine learning, planning,
control and optimization in dynamic environments, multi-agent
systems, and networks. He was a Fulbright scholar in 2002.

-----------------------------------------------------------------------

ICWS Seminar Series is supported by a grant from Rockwell Collins