**Learning and Dynamics in
Network Formation Games**
**Abstract:**
We consider network games where nodes are allowed to
strategically change the topology of the network. In the
proposed game, 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 (latency and carrying
traffic); (2) maintaining links to other nodes; and (3) payments
made to other nodes (from contracts). As a static 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 focus in this talk is on
studying such games under certain learning dynamics based on
variations of local best response dynamics. We consider
different learning dynamics focusing on two desiderata: locality
of information and selection of an efficient equilibrium.
With these desiderata in mind we consider a couple of natural
learning dynamics. We first show that myopic best response
dynamics may diverge or converge to an extremely inefficient
outcome. We then consider other dynamics 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 show that
this myopic rule leads to a socially efficient equilibrium.
Further, the convergence
rate turns out to be polynomial in the number of nodes under
certain natural assumptions on the node selection process.
**Biography: **
I graduated from the Technion with a BSc
in Electrical Engineering and BA in mathematics (both summa cum
laude) in 1996. After that I spent almost four years as an
intelligence officer with the Israeli Defence Forces. I was
involved in a few ventures in the high-tech industry. I earned
my PhD in Electrical Engineering from the Technion at 2002,
under the supervision of
Nahum Shimkin.
I was then a Fulbright postdoctoral associate with LIDS (MIT)
working with
John Tsitsiklis
for two years. I joined the
Department of Electrical and Computer
Engineering in
McGill University
on July 2004, where I hold a
Canada Research Chair
in Machine Learning. I am married to Tally and father to Liam. |