Local Search Heuristics for Schelling Games on Graphs (completed)

Starting Date: Beginning of June
Prerequisites: CS2860 Algorithms and Complexity
Will results be assigned to University: No

Schelling games were recently introduced and studied as a novel class of strategic games inspired by the Schelling’s model of residential segregation. These games are played on an undirected graph that represent the topology of a residential area. In addition, we are given a set of agents partitioned into multiple types. Each agent occupies a vertex of the graph, where no two agents can occupy the same vertex at the same time. The agents are allowed to move on the graph/swap locations with the different agent and the goal of each agent is to maximize the fraction of the neighbours that are of the same type as the agent. Hence, an agent j might be willing to move from position A to position B if the fraction of the neighbors in B having the same type as j is larger than the corresponding fraction in position A. A Nash equilibrium for this game is a situation were no agent can (ex)change their position and strictly improve the fraction of the neighbors of the same type. It was shown that Nash equilibria do not always exist in Schelling games. 

Research Goals.

  • Explore different graph classes and identify which ones possess a Nash equilibrium.
  • Design algorithms for finding a Nash equilibrium if it exists.
  • Study local search heuristics like Best Response and and Local Swaps, and their convergence to Nash equilibria.
  • Study how the structure of the underlying graph affects the running time of these heuristics.

Depending on the outcome of the project, we can submit our findings to  a conference related to Algorithmic Game Theory or Artificial Intelligence.