Abstract
We consider strategic games that are inspired by
Schelling’s model of residential segregation. In our
model, the agents are partitioned into k types and
need to select locations on an undirected graph.
Agents can be either stubborn, in which case they
will always choose their preferred location, or
strategic, in which case they aim to maximize the
fraction of agents of their own type in their neighborhood. We investigate the existence of equilibria in these games, study the complexity of finding
an equilibrium outcome or an outcome with high
social welfare, and also provide upper and lower
bounds on the price of anarchy and stability. Some
of our results extend to the setting where the preferences of the agents over their neighbors are de-
fined by a social network rather than a partition into
types