  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 guarantee 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, which includes a variety of applications such as facility location,
routing, network formation, and coverage games. Given arbitrary local welfare
functions W, we prove that a distribution rule guarantees equilibrium existence
for all games (i.e., all possible sets of resources, agent action sets, etc.)
if and only if it is equivalent to a generalized weighted Shapley value on some
"ground" welfare functions W', which can be distinct from W. However, if
budget-balance is required in addition to the existence of a Nash equilibrium,
then W' must be the same as W. 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 result is that, in order to guarantee equilibrium
existence in all games with any fixed local welfare functions, it is necessary
to work within the class of potential games.
