  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 defined by a
social network rather than a partition into types.

Computer Science and Game Theory