Distributed resource allocation through utility design - Part II: applications to submodular, supermodular and set covering problems
share
A fundamental component of the game theoretic approach to distributed control is the design of local utility functions. In Part I of this work we showed how to systematically design local utilities so as to maximize the induced worst case performance. The purpose of the present manuscript is to specialize the general results obtained in Part I to a class of monotone submodular, supermodular and set covering problems. In the case of set covering problems, we show how any distributed algorithm capable of computing a Nash equilibrium inherits a performance certificate matching the well known 1-1/e approximation of Nemhauser. Relative to the class of submodular maximization problems considered here, we show how the performance offered by the game theoretic approach improves on existing approximation algorithms. We briefly discuss the algorithmic complexity of computing (pure) Nash equilibria and show how our approach generalizes and subsumes previously fragmented results in the area of optimal utility design. Two applications and corresponding numerics are presented: the vehicle target assignment problem and a coverage problem arising in distributed caching for wireless networks.
READ FULL TEXT