Overcoming the Limitations of Utility Design for Multiagent Systems
Cooperative control focuses on deriving desirable collective behavior in multiagent systems through the design of local control algorithms. Game theory is beginning to emerge as a valuable set of tools for achieving this objective. 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. Our first set of results illustrates the complexity associated with such a task. In particular, we prove that if we restrict the class of utility functions to be local, scalable, and budget-balanced then 1) ensuring that the resulting game possesses a pure Nash equilibrium requires computing a Shapley value, which can be computationally prohibitive for large-scale systems, and 2) ensuring that the allocation which optimizes the system level objective is a pure Nash equilibrium is impossible. The last part of this paper demonstrates that both limitations can be overcome by introducing an underlying state space into the potential game structure.
© 2013 IEEE. Manuscript received May 24, 2011; revised October 24, 2011; accepted May 22, 2012. Date of publication January 04, 2013; date of current version May 20, 2013. This work was supported by AFOSR grants #FA9550-09-1-0538 and #FA9550-12-1-0359, ONR grant #N00014-12-1-0643, and NSF grant #CCF-0830511. The conference version of this paper appeared in . Recommended by Associate Editor H. S. Chang.