Introduction
In the field of multi-agent systems, "hedonic games" model scenarios where agents form coalitions (teams) and their utility depends solely on the members of their own group. Traditional models, such as Additively Separable Hedonic Games (ASHG), assume agents have specific preferences for every other individual in the population. However, in many real-world contexts—such as forming research teams or squads in online games—agents often care more about the roles they perform and the overall team composition than the specific identities of their teammates.
This paper introduces Roles and Teams Hedonic Games (RTHG), a model that captures role-based and composition-based preferences while maintaining agent anonymity. This approach is particularly useful for "cold-start" scenarios where agents lack prior knowledge of one another.
Methodology
The RTHG model is formalized with the following components:
- Population ($P$): The set of agents.
- Team Size ($m$): A fixed size for every team.
- Roles ($R$): Specific functions agents can perform.
- Compositions ($C$): Valid combinations of roles forming a team.
- Utility ($U$): A function where an agent’s payoff depends on their assigned role within a specific team composition.
The authors investigate two primary optimization objectives: MaxSum (maximizing total utility) and MaxMin (maximizing the utility of the least happy coalition to ensure fairness). To address these, they developed a Greedy Heuristic that uses agent preferences as "votes" for team compositions and a Local Search algorithm to identify "individually stable" partitions—arrangements where no agent is incentivized to move to another team.
Key Results and Discussion
The authors mathematically proved that both MaxSum and MaxMin RTHG problems are NP-complete, meaning they cannot be solved perfectly in polynomial time as the population grows. Consequently, the performance of heuristic approaches is critical.
As shown in the evaluation of 240 randomly generated instances, the Greedy Heuristic performed exceptionally well, particularly in finding near-optimal MaxSum partitions, maintaining over 95% optimality even as the population size increased.
However, a "scaling gap" was observed with the Local Search algorithm. As the population size increased, the gap between the stable solutions found by local search and the true mathematical optima grew. This suggests a significant trade-off in large systems between achieving individual stability (keeping everyone satisfied enough not to leave) and maximizing the collective good.
Conclusion and Future Work
RTHG provides a robust framework for team formation based on roles rather than identities. Future work includes validating the model using large-scale real-world data from League of Legends to correlate optimal RTHG compositions with win rates. Additionally, the authors plan to explore dynamic preferences and stronger notions of stability, such as "Core stability," where groups of agents can collectively decide to form new teams.
Summary updated