TITLE: Game Theory: A Modern Approach to Multiagent Coordination

SPEAKER: James Marden

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. A central component of this game theoretic approach is the assignment of utility functions to the individual agents. Here, the goal is to assign utility functions within an “admissible” design space such that the resulting game possesses desirable properties, e.g., existence and efficiency of pure Nash equiibria.  Our first set of results 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 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.  One of the interesting consequences of this characterization is that guaranteeing the existence of a pure Nash equilibrium necessitates the use of a game structure termed “potential games”.  To conclude this talk, we will discuss some preliminary results pertaining to characterizing the efficiency of pure Nash equilibria for such resource allocation problems. Here, we provide an analysis of two utility/cost sharing methodologies: the Shapley value and marginal contribution.  Somewhat surprisingly, it turns out that the Shapley value provides better efficiency guarantees than the marginal contribution for a broad class of systems.  This result suggests that performing a distributed gradient ascent on the true system level objective functions, which can be viewed as a marginal contribution design, may lead to inefficiencies in the resulting system behavior. 

Bio:  Jason Marden is an Assistant Professor in the Department of Electrical, Computer, and Energy Engineering at the University of Colorado.  He received a BS in Mechanical Engineering in 2001 from UCLA, and a PhD in Mechanical Engineering in 2007, also from UCLA, under the supervision of Jeff S. Shamma, where he was awarded the Outstanding Graduating PhD Student in Mechanical Engineering.  After graduating from UCLA, he served as a junior fellow in the Social and Information Sciences Laboratory at the California Institute of Technology until 2010 when he joined the University of Colorado.  In 2012, he received the Donald P. Eckman award and an AFOSR Young Investigator Award.  His research interests focus on game theoretic methods for feedback control of distributed multiagent systems.