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.

Shie Mannor