Title: Distributed resource allocation through utility design - Part II: applications to submodular, supermodular and set covering problems,
Abstract: 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.