Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games

• 成果类型: Article
• 署名作者: Gopalakrishnan, Ragavendran; Marden, Jason R.; Wierman, Adam
• 署名单位: University of Colorado System; University of Colorado Boulder; California Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0651
• 发表日期: 2014
• 页码: 1252-1296
• 关键词: Network design; Shapley value; price; allocation; STABILITY; multicast

摘要

We consider the problem of designing distribution rules to share welfare (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a (pure) Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantees the existence of a Nash equilibrium is unknown. Our work provides an exact characterization of this space for a specific class of scalable and separable games that includes a variety of applications such as facility location, routing, network formation, and coverage games. Given arbitrary local welfare functions W, we prove that a distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is equivalent to a generalized weighted Shapley value on some ground welfare functions W, which can be distinct from W. However, if budget-balance is required in addition to the existence of a Nash equilibrium, then W' must be the same as W. We also provide an alternate characterization of this space in terms of generalized marginal contributions, which is more appealing from the point of view of computational tractability. A possibly surprising consequence of our result is that, in order to guarantee equilibrium existence in all games with any fixed local welfare functions, it is necessary to work within the class of potential games.