Potential Games are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games
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.
Copyright is held by the author/owner(s). This research was supported by AFOSR grants #FA9550-09-1-0538 and #FA9550-12-1-0359, ONR grant #N00014-12-1-0643, and NSF grants #CNS-0846025 and #CCF-1101470.
Submitted - 2013_costsharing.pdf