Tiered Coalition Formation Game Stability and Simulation

Nathan ArnoldAAAI 2024 · DOI

TL;DR

This paper explores "tiered coalition formation games" (TCFGs), a framework for modeling competition where preferences aren't always transitive (e.g., A beats B, B beats C, but C beats A). The authors introduce a new game variant and stability concept, aiming to find "tier lists" that represent agent power while promoting social welfare and fairness. They are also developing a simulation using Pokémon data to compare theoretical findings with real-world competitive dynamics.

What Problem Does This Paper Address?

Many real-world competitive scenarios, from hiring decisions to video game matchups, exhibit intransitive preferences. Traditional game theory often assumes transitivity, which can oversimplify or misrepresent these situations. Tiered coalition formation games (TCFGs) were introduced to model these intransitive environments, where agents form cooperative groups and aim for stable "tier lists" reflecting their relative strengths. However, the original TCFG framework produced overly simplistic, singleton tiers. This paper addresses the need for more nuanced TCFG models that can handle non-deterministic outcomes, allow for multi-agent tiers, and promote social welfare and fairness, while also investigating the computational complexity of finding stable outcomes and comparing theoretical predictions to empirical data.

Methods

The authors extend Siler's original TCFG framework by introducing a new preference framework that better captures underlying power structures and a variant game called k-tiered coalition formation games, which restricts the number of tiers to k. They also propose a new stability concept, "socially conscious stability," designed to promote social welfare and fairness. For finding stable tier lists, they have developed an algorithm that aims for high utility and fairness. To evaluate their theoretical work, they are developing a simulation of "Pokémon Red and Blue Versions" to generate probabilistic outcomes from one-on-one matches. This simulation will then be used to create empirical tier lists for comparison with their theoretical models.

Datasets

The paper discusses using data derived from simulations of "Pokémon Red and Blue Versions" as a primary dataset for evaluation. This simulated data will be generated by a program that accurately simulates game states and actions. The goal is to use these simulated match outcomes to estimate win probabilities between Pokémon, which will then form the basis for constructing tier lists. The authors also plan to compare their findings with existing real-world tier lists managed by the Pokémon community website, Smogon.

Key Insights and Ideas

  • Beyond Strict Transitivity: The core insight is that real-world competition often defies simple transitive ordering, and TCFGs provide a valuable tool for modeling this complexity.
  • Socially Conscious Stability: The introduction of "socially conscious stability" is a key innovation, moving beyond individual agent satisfaction to consider broader notions of social welfare and fairness in tier list formation.
  • Computational Challenges: The paper highlights significant theoretical challenges, particularly the conjecture that deciding the existence of a Nash stable outcome in k-TCFGs might be NP-complete, indicating potential computational bottlenecks.
  • Bridging Theory and Practice: The simulation of Pokémon battles represents a crucial step in validating theoretical TCFG concepts against empirical data, aiming to understand how real-world competitive dynamics align with or diverge from theoretical predictions.
  • Evolving Metagames: The authors anticipate that their Pokémon simulation will shed light on how evolving metagames, influenced by roles and dominating agents, impact preferences and stability in TCFGs.

Key Results

The paper reports on theoretical progress, including the formalization of k-tiered coalition formation games and the socially conscious stability concept, proving that k-TCFGs are always stabilizable under this new concept. They have also developed an algorithm to find such stable tier lists with high utility and fairness. Experimental results from this algorithm have been presented in prior work (FLAIRS 2022 and a journal article). While specific quantitative results from the Pokémon simulation are pending completion, the authors expect to compare their theoretical tier lists with real-world Smogon tier lists and observe potential inconsistencies.

Limitations and Future Work

The authors acknowledge that not all k-TCFGs with probabilistic preferences admit a Nash stable outcome, and the complexity of determining this is currently unknown, with a conjecture that it is NP-complete. It remains an open question whether all k-TCFGs admit a core stable outcome, though the authors conjecture yes. A significant limitation is that Siler's proof of polynomial-time complexity for finding stable singleton tier lists does not hold under probabilistic preferences, and the authors are seeking a polynomial-time method for this. Future work will focus on proving the NP-completeness conjecture, establishing the existence of core stable outcomes, and developing a polynomial-time algorithm for stable singleton tier lists under probabilistic preferences. The Pokémon simulation is a major ongoing effort to empirically validate their theoretical findings and explore the impact of evolving metagames.

Summary updated

BibTeX
@inproceedings{arnold2024tiered,
  author = {Nathan Arnold},
  title = {{Tiered Coalition Formation Game Stability and Simulation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30389},
}
Figure