Cost sharing games are a model for resource allocation problems where players in the game (agents) share the revenue (welfare) resulting from an allocation (outcome of the game). The game involves the agents strategically choosing the resources they want in order to optimize their share of the welfare, and its outcome depends on the distribution rule according to which the welfare is shared. A Nash equilibrium is a natural solution concept for predicting stable outcomes of such strategic-form games. There are many known distribution rules that guarantee the existence of a Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantee the existence of a Nash equilibrium is unknown. This work provides an exact characterization of this space for a specific class of scalable and separable games, which includes a variety of applications such as facility location, routing, network formation, and coverage problems. In particular, we show that the only distribution rules that guarantee the existence of a pure Nash equilibrium for this class of games are (generalized) Shapley values. We also provide an alternate characterization of this space in terms of (generalized) marginal contributions, which is computationally more tractable. As a result, surprisingly, a guaranteed equilibrium exists in a game if it is a potential game --- a very small subspace of games.
Dr. Ragavendran joined Xerox Research Centre India in April 2015, where he is a Research Scientist in the Algorithms and Optimization group. Prior to that, he was a post-doctoral research associate at the University of Colorado, Boulder. He obtained his MS and PhD in Computer Science from the Caltech (Pasadena), and my BTech in Computer Science and Engineering from the IIT Madras. His research interests lie broadly in the domain of applied algorithmic game theory (AGT).