Game Theory: A Modern Approach to Multiagent Coordination

Abstract

The central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to a given system level objective. Game theory is beginning to emerge as a valuable set of tools for achieving this goal as many popular multiagent systems can be modeled as games, e.g., sensor coverage, consensus, task allocation, among others. Game theory is a well-established discipline in the social sciences that is primarily used for modeling social behavior. Traditionally, the preferences of the individual agents' are modeled as utility functions and the resulting behavior is assumed to be an equilibrium concept associated with these modeled utility functions, e.g., Nash equilibrium. This is in stark contrast to the role of game theory in engineering systems where the goal is to design both the agents' utility functions and an adaptation rule such that the resulting global behavior is desirable. The transition of game theory from a modeling tool for social systems to a design tool for engineering promotes several new research directions that we will discuss in this talk. In particular, we will focus on the question of how to design admissible agent utility functions such that the resulting game possesses desirable properties, e.g., the existence and efficiency of pure Nash equilibria. Our motivation for considering pure Nash equilibria stems from the fact that adaptation rules can frequently be derived which guarantee that the collective behavior will converge to such pure Nash equilibria. Our first result focuses on ensuring the existence of pure Nash equilibria for a class of separable resource allocation problems that can model a wide array of applications including facility location, routing, network formation, and coverage problems. Within this class, we prove that weighted Shapley values completely characterize the space of local utility functions that guarantee the existence of a pure Nash equilibrium. That is, if a utility design cannot be represented as a weighted Shapley value, then there exists a game for which a pure Nash equilibrium does not exist. Another concern is distributed versus centralized efficiency. Once distributed agents have settled on an equilibrium, the resulting performance need not be the same as from a centralized design (cf., so-called "price-of-anarchy"). We compare different utility design methods and their resulting effect on efficiency. Finally, we briefly discuss online adaptation rules leading to equilibrium.