ISTC Seminar - Professor Munther Dahleh, Dept of EECS, MIT
Title: Fundamental Limitations of Networked Decision Systems
Abstract: (Prof Dahleh) In this talk, I will discuss three problems that emerge in distributed control, computation, and learning. In the first problem, We consider a network of nodes, each having an initial value or measurement, and seeking to acquire an estimate of a given function of all the nodes' values in the network. Each node may exchange with its neighbors a finite number of bits every time communication is initiated. In this talk, we present an algorithm for computation of separable functions, under the constraint that communicated messages are quantized, so that with some specified probability, all nodes have an estimate of the function value within a desired interval of accuracy. We derive an upper bound on the computation time needed to achieve this goal, and show that the dependence of the computation time on the network topology, via the "conductance" of the graph representing this topology, matches a lower bound derived from Information Theoretic analysis. Hence, the algorithm's running time is optimal with respect to dependence on the graph structure. In the second problem, We study a model of learning over a complex network with partial observations from the past. This model is motivated by large social networks where people are probabilitically connected through graphs.
In this model, Each individual receives a private signal about the correct action she should take and also observes the action of her neighbors. Assuming rationality of the decision makers, we derive necessary and sufficient conditions on private signals as well as the topology of the neigbours for asymptotic
learning to occur. When these conditions are not met, we demonstrate that learning may not occur and that possibly herding may occur. The latter is an important phenomenon in the study of social networks and characterizes situations where individual decision makers ignore their private information and follow their neighbors. Finally, we discuss decision problems involving combinatorial optimization contrained by physical and dynamic constraints. Such problems are examples of cyber physical systems and have many application in vehicle routing problems.