Fundamental limitations in multiagent coordination

The goal in networked control of multiagent systems is to derive desirable collective behavior through the design of local control algorithms. The information available to the individual agents, either through sensing or communication, invariably defines the space of admissible control laws. Hence, informational restrictions impose constraints on achievable performance guarantees. The first part of this talk will provide one such constraint with regards to the efficiency of the resulting stable solutions for a class of networked resource allocation problems with submodular objective functions. When the agents have full information regarding the resources, the efficiency of the resulting stable solutions is guaranteed to be within 50% of optimal. However, when the agents have only localized information about the resources, which is a common feature of many well-studied control designs, the efficiency of the resulting stable solutions can be 1/n of optimal, where n is the number of agents. Consequently, such schemes in general cannot guarantee that a system comprised of n agents can perform better than a system comprised of just a single agent. The second part of this talk will focus on identifying how augmenting the information to the agents can impact achievable performance guarantees.