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

Abstract

Cost sharing games, traditionally studied in economics in the context of cooperative game theory, has garnered recent interest in the computer science community in the noncooperative setting, where individually strategic agents choose resources based on how the welfare (cost or revenue) generated at each resource (which depends on the set of agents that choose the resource) is distributed. The focus is on finding distribution rules that lead to stable allocations, which is formalized by the concept of Nash equilibrium.

Files

Additional details