Belief Propagation

Belief Propagation (BP) is a fundamental message passing algorithm to compute marginals from joint distribution where the underlying random variables have dependency structure defined through a graph. It is known that BP is exact on trees and on graphs with at most one loop. In this series of papers we look at different aspects of BP such as multi-agent BP with decentralized information, convergence of BP to global optimum of Bethe energy function and more.

Mean field games

Mean field games is a model that approximates Nash equilibria in large player games of incomplete information. It consists of solving a coupled set of forward (Fokker Planck Kolmogorov) and backward (HJB) fixed-point equations that are coupled across time. In this series of papers, we show that such games can be solved by solving a smaller fixed point equation for each time t, which significantly reduces the complexity of finding mean field equilibria. [Video]

Game Theory and Mechanism/Information Design

Nash introduced the concept of Nash equilibrium that provides a mathematical framework to study strategic behavior. We argue that some Nash equilibria are more plausible than the others, the ones that are more robust to irrational players. We define a notion of alpha-robustness such that if at least N-alpha-1 players are playing the equilibrium strategies (and alpha players play arbitrary strategies), then no user wants to unilaterally deviate. We provide sufficient conditions for the existence of such equilibria.  [Video]

Mechanism design is an engineering side of game theory that builds systems such that when acted upon by strategic users, they take actions as intentioned by the system designer. Myerson's optimal auction and the VCG mechanism, while conceptually and mathematically being quite simple, provide solutions to real world problems that are implemented in practice and thus have significant impact. In the same spirit, we design a private good mechanism for large scale users with the objective of social welfare which generalizes the VCG mechanism when the number of players is large, such as in a society.
We also study dynamic information design. [Video]

Multi-agent team decision problems

There are many instances when players with different information are trying to control a system. Witsenhausen's counterexample is one of the classic work which shows that the results of complete information don't easily flow through in these problems and such problems are quite challenging .  In this line of work, we present structural results to find optimum policies when the players have different information. Specifically we consider the case when players don't have any common information and to the best of our knowledge, is the first such work that provides a concept of state for such systems. The fundamental issue in such problems is that due to lack of common information there is an infinite regress of higher order beliefs. However, by a clever construct I show that for the LQG case, the update and thus the dynamics of the 1st order beliefs can be made same as that of 2nd order and so on and thus it is sufficient to keep track of one layer of beliefs. This addresses a fundamental problem in the control of these systems and a problem that has been discussed many times in the economics literature as well.

Communication channels with noisy feedback

Shannon proved there exists a fundamental capacity of a communication channel such that one can achieve an arbitrarily low probability of error for all rates below this capacity. Communication is a $1.7 trillion (per annum) industry worldwide which includes cell phones, the internet, optical communication, and space communication. However, all communication is one-way. We don’t use feedback in communication in any meaningful way. While it is known that feedback doesn't increase capacity,  it can significantly increase the error exponents and could simplify coding and decoding. However, so far there is no mathematical framework to study such channels with noisy feedback, because of which it hasn't been used in practice so far in any meaningful way.  In this work, we provide a sequential decomposition framework to study such channels which is the first mathematical treatment of such channels that allows a concept of state and a methodology to find optimal Markovian strategies with respect to this state. [Video]

Capacity of Multiple access channel with feedback

While we know the capacity of a point-to-point channel with and without feedback and have achievable codes to achieve that, Shannon's capacity and capacity-achieving schemes of networked communication systems are not always known. In particular, the capacity of MAC with feedback has been an open problem for 65 years. Using recent developments in decentralized stochastic control, I pose the capacity achieving in a MAC with noiseless feedback as a stochastic optimization problem to provide a single letter capacity expression through a dynamic program, which provides the first analytical method to compute the capacity of this channel, and opens door to studying more such multi-user channels with feedback.

Network Games

In the past few years, information design has emerged as a powerful tool parallel to mechanism design. In this line of work, we study a new dimension we call network design where the principal agent has the ability to design connections among the selfish agents such that the corresponding Nash equilibrium of the networked game coincide with the outcome desired by the principal agent. [Video]

In related work on network games, we combine ideas from random matrix theory (RMT) and linear quadratic games to show a phase transition in such games with respect to perturbation in the adjacency matrix of the network.

To the best of our knowledge, this is the first such line of work that combines ideas from game theory and RMT to characterize such a phenomenon of phase transitions in the real world, and opens door to studying many such phenomena in real life through the intersection of these fields. [Video]

Learning in games with fully rational agents

Learning in games is an important problem of how agents learn to play Nash equilibrium. There are many ways this question has been addressed so far, either using heuristics such as fictitious play, or some notion of the rationality of the agents. However, most of these algorithms are either just heuristics or myopic best responses and there are questions as to why selfish rational agents would play such a learning algorithm. This question is even more important today with technology playing a huge role in decision making and significant advancements have been made at the intersection of machine learning, artificial intelligence with game theory, where machines with high computation power can arguably be fully rational. In this work, we design a decentralized learning algorithm with fully rational selfish agents such that (a) the algorithm converges to the Nash equilibrium of the static game and (b) the algorithm itself is an equilibrium of the dynamic learning process. To the best of our knowledge, this is the first such algorithm with these two properties.