Tamer Basar, University of Illinois at Urbana-Champaign

Abstract: Distributed decision making with decentralized information is a topic that has long been of interest to researchers in several different fields, including control, communications, economics, game theory, biology, and computer science, to list a few. An overarching issue in distributed decision making is how to architect communication (message passing) and coordination networks, with associated protocols, so that they would support with minimum overhead effective, purposeful interactions of agents (decision makers) with private, local information. The goal is for these interactions to lead to a desirable outcome that would have been achieved if the totality of the information available to the agents had been shared and centrally utilized at the outset. Some typical outcomes in this context are the optimal solution in a stochastic team, Nash equilibrium in a stochastic game, robust decentralized controller in a large scale system, optimum detection policy in a decentralized hypothesis testing problem, and fair allocation of bandwidth in a communication network. Recently, computation of the average has emerged as providing a simple yet broadly applicable paradigm for such problems, with applications ranging from information fusion in sensor networks, and load balancing in processor networks, to clock synchronization, and multi-agent coordination and flocking. In its simplest form, this involves a distributed network of agents, each of which initially has a numerical value, which they update iteratively employing a distributed averaging algorithm built on the messages received from neighbors. Consensus is reached when all agents agree on the true value of the average.

This plenary talk will first provide a relatively broad perspective on distributed decision making or computation with decentralized information. Subsequently, it will discuss the distributed averaging problem on arbitrary connected graphs, particularly when communication links are subject to finite rate constraints, which necessitates quantization of the numerical values being exchanged and stored. Such a discretized distributed averaging problem models several scenarios of interest, such as averaging in a network with finite capacity channels and load balancing in processor networks. The talk will present randomized, fully distributed algorithms which achieve consensus to the extent that the discrete nature of the problem permits. It will also provide, for some special networks, bounds on the expected convergence time of these algorithms, which are polynomial in the number of nodes,. The talk will conclude with some open problems in this area.