Generalized efficiency bounds in distributed resource allocation

Game theory is emerging as a popular tool for distributed control of multiagent systems. In order to take advantage of these game theoretic tools the interactions of the autonomous agents must be designed within a game theoretic environment. A central component of this game theoretic design is the assignment of a local objective function to each decision-maker. One promising approach to utility design is assigning each agent an objective function in accordance with the agent´s Shapley value. This method frequently results in games that possess many desirable features including existence and efficiency of pure Nash equilibria. In this paper we explore the relationship between the Shapley value utility design and the resulting efficiency of pure Nash equilibria. To study this relationship we introduce a simple class of resource allocation problems. We then derive an explicit relationship between the structure of the resource allocation problem and the efficiency of the resulting equilibria. Lastly, we derive a bicriteria bound for these resource allocation problems. By bicriteria bound, we mean a bound on the value of the optimal allocation relative to the value of an equilibrium allocation with additional agents.