| Title | : | Potential Games are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games |
| Speaker | : | Ragavendran Gopalakrishnan (Xerox Research Center India) |
| Details | : | Thu, 6 Aug, 2015 2:00 PM @ BSB 361 |
| Abstract: | : | Abstract: Cost sharing games are a model for resource allocation
problems where agents (players in the game) share the 'welfare' (cost
or revenue) resulting from an allocation (outcome of the game) among
themselves. The game involves the agents strategically choosing the
resources they want in order to optimize their share of the welfare
(minimize cost or maximize revenue), and its outcome depends on the
distribution rule according to which the welfare is shared. A (pure)
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 (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 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 more appealing from
the point of view of computational tractability. A possibly surprising
consequence of our characterization is that, in order to guarantee
equilibrium existence in all games, it is necessary to work within the
class of so-called potential games, a very small subspace of games for
which an equilibrium exists, with useful static and dynamic
properties. About the Speaker: Ragavendran joined Xerox Research Centre India (XRCI) 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 California Institute of Technology, Pasadena, and his BTech in Computer Science and Engineering from the Indian Institute of Technology Madras. His research interests lie broadly in the domain of applied algorithmic game theory (AGT). His recent focus has been on research problems in AGT that are motivated by somewhat non-traditional applications, such as distributed control, and heterogeneous multi-server queuing systems. |
