Abstract:

Simple, distributed and iterative algorithms, popularly known as the message passing algorithms, have emerged as the architecture of choice for engineered networks as well as cannonical behavioral model for societal and biological networks. Despite their simplicity, message passing algorithms have been surprisingly effective. In this talk, I will try to argue in favor of such algorithms by means of two results in the context of designing efficient medium access in wireless networks and modeling agent behavior in road transportation networks.

Design of efficient medium access control (MAC) algorithms or protocols for resolving contention among various transmitters has been of great interest since the advent of Aloha network in 1970s. Despite a long history, a sastifactory solution has remained allusive till recently. In the first part of my talk, I will provide such an efficient MAC protocol for arbitrary wireless network. It blends the classical Metropolis Hastings sampling mechanism with insights obtained from analysis of time-varying queuing dynamics or Markov process to obtain desired protocol. Methodically, it provides a framework for designing efficient message-passing scheduling algorithm for a large class of network resource allocation problems including switch scheduling and optical network scheduling.

In societal networks like road transportation, it is essential to understand behavior of humans (or drivers) to better design them. Game theoretic modeling based on hypothesis of rationality has provided an excellent surrogate for such behavioral model. However, it is only reasonable to expect humans to be partly rational. This led to the notion of bounded rationality and a probabilistic learning model known as the logit-response. In the second part of my talk, based on transient analysis of the logit-response, I will exhibit its limitation and propose a new model inspired to capture *herd mentality* of humans. Under this model, we find that despite high dynamics of humans joining and leaving the network, it still operates near NASH equilibrium and resulting into low 'dynamic' price of anarchy.