Fundamental limitations of networked decision systems

Summary form only given. As communication devices and embedded systems become ever more ubiquitous and integrated with everyday life, the need for understanding the fundamental limitations and capabilities of networked decision systems becomes more critical. The challenge in this research area stems from the fact that there are many different types of networked systems that are slated to perform various kinds of tasks. While, up to now, there does not exist a single paradigm that can address limitations and capabilities of such systems in a unified manner, there does exist simple enough abstractions that can provide significant insights into the influence of the network topology and communication bandwidth in combination with local private information on distributed computation, learning, and decision making. In this talk, we present several instances of such abstractions. In the first instance, we discuss the problem of distributed computation over a noisy transport layer, and highlight how the network topology impacts the time-complexity of computation. In the second instance, we present a simple model of sequential decision making that arises in social networks such as voting and viral marketing whereby decision makers observe the actions of a subset of the previous decision makers and make a rational decision combining these observations with their private information. Finally, in the third instance, we present a formulation of the stochastic shortest path problem whereby the agent traversing the graph can obtain side information about the graph weights. In all of these instances, we highlight emerging challenges and open problems.