Title: Distributed resource allocation through utility design - Part I: optimizing the performance certificates via the price of anarchy,
Abstract: Game theory has emerged as a novel approach for the coordination of
multiagent systems. A fundamental component of this approach is the design of a
local utility function for each agent so that their selfish maximization
achieves the global objective. In this paper we propose a novel framework to
characterize and optimize the worst case performance (price of anarchy) of any
resulting equilibrium as a function of the chosen utilities, thus providing a
performance certificate for a large class of algorithms. More specifically, we
consider a class of resource allocation problems, where each agent selects a
subset of the resources with the goal of maximizing a welfare function. First,
we show that any smoothness argument is inconclusive for the design problems
considered. Motivated by this, we introduce a new approach providing a tight
expression for the price of anarchy (PoA) as a function of the chosen utility
functions. Leveraging this result, we show how to design the utilities so as to
maximize the PoA through a tractable linear program. In Part II we specialize
the results to submodular and supermodular welfare functions, discuss
complexity issues and provide two applications.