Variety-Seeking Jump Games on Graphs

Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, Alexandros A. VoudourisIJCAI 2025 · DOI

TL;DR

This paper introduces and analyzes "variety-seeking jump games" on graphs where agents aim to maximize the diversity of types in their neighborhood. They prove that while these games don't always guarantee an equilibrium, they do under specific conditions (e.g., two agent types, limited graph degree, or specific graph structures like trees). The work also establishes tight bounds on the "price of anarchy," measuring the loss of diversity in equilibrium compared to the optimal scenario.

What Problem Does This Paper Address?

The paper tackles a variation of the classic Schelling segregation model. While Schelling's original model focused on agents preferring to be near others of the same type (homophily), this work explores the opposite: agents who actively seek diversity in their neighbors. This "variety-seeking" behavior is motivated by real-world phenomena where diversity is valued for social harmony and efficiency. The core challenge is to understand if and when stable configurations (equilibria) emerge in such diversity-seeking games, and how "good" these equilibria are in terms of maximizing overall diversity. Specifically, they investigate whether these games always admit a Nash equilibrium and how to quantify the loss of diversity when agents act selfishly compared to a globally optimal assignment.

Methods

The paper employs game-theoretic analysis, focusing on "jump games" where agents can move to empty nodes to improve their utility. A key concept is the "potential game," where the existence of an equilibrium is guaranteed if a potential function can be identified. The authors use this to prove equilibrium existence under certain conditions. They also analyze "improving response cycles" (IRCs), which are sequences of moves that lead back to the starting state without reaching an equilibrium, demonstrating that such cycles can exist in these games. To quantify the quality of equilibria, they introduce two metrics: "social welfare" (total utility of all agents) and "colorful edges" (edges connecting agents of different types). They then derive bounds on the "price of anarchy" for these metrics, which measures the ratio of the optimal diversity to the worst equilibrium diversity.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using abstract graph structures and agent types.

Key Insights and Ideas

  • Diversity as a Driver: The paper shifts the focus from homophily (seeking similarity) to heterophily (seeking diversity) in agent-based models, reflecting real-world preferences for varied neighborhoods.
  • Equilibria Aren't Guaranteed, But Often Achievable: While the game can exhibit improving response cycles (preventing guaranteed equilibrium existence), they prove that equilibria do exist under several practical conditions, including when there are only two types of agents, or when the graph has limited connectivity (degree at most 2).
  • Graph Structure Matters: The specific topology of the graph significantly influences whether equilibria exist. Trees, cylinders, and tori are shown to always have equilibria, suggesting that well-connected or structured graphs facilitate stable diverse arrangements.
  • Quantifying Diversity Loss (Price of Anarchy): The paper provides tight bounds on how much diversity can be lost due to selfish agent behavior. The "price of anarchy" can be linear in the number of agents or types, highlighting that individual optimization doesn't always lead to globally optimal diversity.
  • Two Faces of Diversity: The analysis uses both "social welfare" (sum of individual utilities) and "colorful edges" (direct connections between different types) as measures of diversity, showing that bounds can differ depending on the chosen metric.

Key Results

  • Impossibility Result: The paper demonstrates that variety-seeking jump games can have improving response cycles, meaning equilibria are not guaranteed for all configurations.
  • Existence Results: Equilibria are guaranteed to exist under the following conditions:
  • Exactly two types of agents.
  • Exactly one empty node.
  • The graph has a degree of at most 2.
  • The graph is 3-regular with exactly two empty nodes.
  • The graph is a tree, cylinder, or torus.
  • Price of Anarchy Bounds:
    • For social welfare: Upper bound is $O(n)$ in general and $O(k)$ for symmetric types. Lower bound is $\Omega(k)$ for symmetric types.
  • For colorful edges: Upper bound is $O(n)$ even for symmetric types. Lower bound is $\Omega(\delta)$ for $\delta$-regular graphs with symmetric types.
  • Price of Stability: A lower bound of approximately $3/2 - \epsilon$ is shown for both social welfare and colorful edges, indicating that even the "best" equilibrium might not be optimal.

Limitations and Future Work

  • Equilibrium Existence Conjecture: The authors conjecture that equilibria always exist when there are only two empty nodes, regardless of graph structure, but a formal proof is missing. Preliminary experiments support this.
  • Price of Stability Tightness: While lower bounds for the price of stability are provided, tighter bounds for both objectives are an open question.
  • Other Diversity Measures: The paper suggests exploring other objective functions to measure diversity, such as "degree of integration."
  • General Graph Structures: While specific graph classes are analyzed, a comprehensive understanding of equilibrium existence across all graph types remains an area for future research.

Summary updated

BibTeX
@inproceedings{narayanan2025variety,
  author = {Lata Narayanan and Jaroslav Opatrny and Shanmukha Tummala and Alexandros A. Voudouris},
  title = {{Variety-Seeking Jump Games on Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/446},
}
Figure