Generalized efficiency bounds in distributed resource allocation
Authors:
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 59 (3) , 2233-2238
Abstract
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.Keywords
This publication has 24 references indexed in Scilit:
- Autonomous Vehicle-Target Assignment: A Game-Theoretical FormulationJournal of Dynamic Systems, Measurement, and Control, 2007
- Using game theory to analyze wireless ad hoc networksIEEE Communications Surveys & Tutorials, 2005
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- Uncertainty-aware and coverage-oriented deployment for sensor networksJournal of Parallel and Distributed Computing, 2004
- Exact and Heuristic Methods for the Weapon Target Assignment ProblemSSRN Electronic Journal, 2003
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Fictitious play for finding system optimal routings in dynamic traffic networksTransportation Research Part B: Methodological, 2000
- Potential GamesGames and Economic Behavior, 1996
- The Evolution of ConventionsEconometrica, 1993
- Potential, Value, and ConsistencyEconometrica, 1989