  This paper studies the existence of pure Nash equilibria in resource graph
games, which are a general class of strategic games used to succinctly
represent the players' private costs. There is a finite set of resources and
the strategy set of each player corresponds to a set of subsets of resources.
The cost of a resource is an arbitrary function that depends on the load vector
of the resources in a specified neighborhood. As our main result, we give
complete characterizations of the cost functions guaranteeing the existence of
pure Nash equilibria for weighted and unweighted players, respectively.
  1. For unweighted players, pure Nash equilibria are guaranteed to exist for
any choice of the players' strategy space if and only if the cost of each
resource is an arbitrary function of the load of the resource itself and linear
in the load of all other resources where the linear coefficients of mutual
influence of different resources are symmetric.
  2. For games with weighted players, pure Nash equilibria are guaranteed to
exist for any choice of the players' strategy space if and only if the cost of
a resource is linear in all resource loads, and the linear factors of mutual
influence are symmetric, or there is no interaction among resources and the
cost is an exponential function of the local resource load.
  3. For the special case that the players' strategy sets are matroids, we show
that pure Nash equilibria exist under a local monotonicity property, even when
cost functions are player-specific. We point out an application of this result
to bilevel load balancing games, which are motivated by the study of network
infrastructures that are resilient against external attackers and internal
congestion effects.
  4. Finally, we derive hardness results for deciding whether a given strategy
is a pure Nash equilibrium for network routing games and matroid games,
respectively.
