Distributed Control and Game Design: From Strategic Agents to Programmable Machines

Abstract

Large scale systems are forecasted to greatly impact our future lives thanks to their wide ranging applications including cooperative robotics, mobility on demand, resource and task allocation, supply chain management, and many more. While technological developments have paved the way for the realization of such futuristic systems, we have a limited grasp on how to coordinate the behavior of their individual components to achieve the desired global objective. With the objective of advancing our understanding, this thesis focus on the analysis and coordination of large scale systems without the need of a centralized authority. At a high level, we distinguish these systems depending on wether they are composed of cooperative or non-cooperative subsystems. In regard to the first class, a key challenge is the design of local decision rules for the individual components to guarantee that the collective behavior is desirable with respect to a global objective. Non-cooperative systems, on the other hand, require a more careful thinking in that the designer needs to take into account the self-interested nature of the agents. In both cases, the need for distributed protocols stems from the observation that centralized decision making is prohibited due to the scale and privacy requirement associated with typical systems. In the first part of this thesis, we focus on the coordination of a large number of non-cooperative agents. More specifically, we consider strategic decision making problems where each agent's objective is a function of the aggregate behavior of the population. Examples are ubiquitous and include social and traffic networks, demand-response markets, vaccination campaigns, to name just a few. We present two cohesive contributions. First, we compare the performance of an equilibrium allocation with that of an optimal allocation, that is an allocation where a common welfare function is maximized. We propose conditions under which all Nash equilibrium allocations are efficient, i.e., are desirable from a macroscopic standpoint. In the journey towards this goal, we prove a novel result bounding the distance between the strategies at a Nash and at a Wardrop equilibrium that might be of independent interest. Second, we show how to derive scalable algorithms that guide agents towards an equilibrium allocation, i.e., a stable configuration where no agent has any incentive to deviate. When the corresponding equilibria are efficient, these algorithms attain the global objective and respect the agents' selfish nature. In the second part of this thesis, we focus on the coordination of cooperative agents. We consider large-scale resource allocation problems, where a number of agents need to be allocated to a set of resources, with the goal of jointly maximizing a given submodular or supermodular set function. Applications include sensor allocation problems, distributed caching, data summarization, and many more. Since this class of problems is computationally intractable, we aim at deriving tractable algorithms for attaining approximate solutions, ideally with the best possible approximation ratio. We approach the problem from a game-theoretic perspective and ask the following question: how should we design agents' utilities so that any equilibrium configuration recovers a large fraction of the optimum welfare? In order to answer this question, we introduce a novel framework providing a tight expression for the worst-case performance (price of anarchy) as a function of the chosen utilities. Leveraging this result, we show how to design utility functions so as to optimize the price of anarchy by means of a tractable linear program. The upshot of our contribution is the design of algorithms that are distributed, efficient, and whose performance is certified to be on par or better than that of existing (and centralized) schemes.