Diversity-seeking jump games in networks

<jats:title>Abstract</jats:title> <jats:p>Recently, strategic games inspired by Schelling’s influential model of residential segregation have been studied in the TCS and AI literature. In these games, agents of <jats:italic>k</jats:italic> different types occupy the nodes of a network topology aiming to maximize their utility, which is a function of the fraction of same-type agents they are adjacent to in the network. As such, the agents exhibit similarity-seeking strategic behavior. In this paper, we introduce a class of strategic jump games in which the agents are <jats:italic>diversity-seeking</jats:italic>: The utility of an agent is defined as the fraction of its neighbors that are of <jats:italic>different</jats:italic> type than itself. We show that in general it is computationally hard to determine the existence of an equilibrium in such games. However, when the network is a tree, diversity-seeking jump games always admit an equilibrium assignment. For regular graphs and spider graphs with a single empty node, we prove a stronger result: The game is potential, that is, the improving response dynamics always converge to an equilibrium from any initial placement of the agents. We also show (nearly tight) bounds on the price of anarchy and price of stability in terms of the social welfare (the total utility of the agents).</jats:p>