Distributed Welfare Games

• 成果类型: Article
• 署名作者: Marden, Jason R.; Wierman, Adam
• 署名单位: University of Colorado System; University of Colorado Boulder; California Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1137
• 发表日期: 2013
• 页码: 155-168
• 关键词: theoretic approach; power-control; wireless; algorithms

摘要

Game-theoretic tools are becoming a popular design choice for distributed resource allocation algorithms. A central component of this design choice is the assignment of utility functions to the individual agents. The goal is to assign each agent an admissible utility function such that the resulting game possesses a host of desirable properties, including scalability, tractability, and existence and efficiency of pure Nash equilibria. In this paper we formally study this question of utility design on a class of games termed distributed welfare games. We identify several utility design methodologies that guarantee desirable game properties irrespective of the specific application domain. Lastly, we illustrate the results in this paper on two commonly studied classes of resource allocation problems: coverage problems and coloring problems.