Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games
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.
© 2014 INFORMS. Received: April 12, 2013; Published Online: May 27, 2014. This research was supported by AFOSR [Grants FA9550-09-1-0538, FA9550-12-1-0359], ONR [Grant N00014-12-1-0643], and NSF [Grants CNS-0846025, CCF-1101470].
Submitted - 1402.3610.pdf