Abstract

We consider a class of jump games in which agents of different types occupy the nodes of a graph aiming to maximize the variety of types in their neighborhood. In particular, each agent derives a utility equal to the number of types different from its own in its neighborhood. In our variety-seeking jump game, an agent jumps to a previously unoccupied node to improve its utility. We show that the jump game induced by the strategic behavior of the agents may in general have improving response cycles, but is a potential game under any of the following six conditions: there are only two types of agents; or no two agents are of the same type; or there is exactly one empty node; or the graph is of degree at most 2; or the graph is 3-regular and there are two empty nodes; or the graph is a spider graph. Additionally, we show that on trees, cylinder graphs, and tori, there is always an equilibrium. Furthermore, we show tight bounds on the price of anarchy and lower bounds on the price of stability with respect to two different measures of diversity: the social welfare (the total utility of the agents) and the number of colorful edges (edges that connect agents of different types). Finally, we describe our experiments on variety-seeking jump games on cylinder graphs and tori, starting with random or segregated initial assignments, and analyze the resulting final assignments in terms of social welfare, colorful edges, and segregated clusters.