Abstract
The United Nations' 2030 Agenda for Sustainable Development requires that all countries collaborate to fight adversarial factors to achieve peace and prosperity for humans and the planet. This scenario can be formulated as an adversarial team game in AI literature, where a team of players play against an adversary. However, previous solution concepts for this game assume that team players have the same utility functions, which cannot cover the real-world case that countries do not always have the same utility function. This paper argues that studying adversarial team games should not ignore the difference in utility functions of team players. We show that ignoring the difference in utility functions of team players could cause the computed equilibrium to be unstable. To show the benefit of considering the difference in utility functions of team players, we introduce a novel solution concept called Co-opetition Equilibrium (CoE) for the adversarial team game. In this game, team players with different utility functions (i.e., cooperation between team players) correlate their actions to play against the adversary (i.e., competition between the team and the adversary). We further introduce the team-maximizing CoE, which is a CoE but maximizes the team's utility among all CoEs. Both equilibria can overcome the issue caused by ignoring the difference in utility functions of team players. We further show the opportunities for theoretical and algorithmic contributions based on our position of considering the difference in utility functions of team players.
Introduction
Adversarial team games model scenarios where a group of players (a team) coordinates to compete against an adversary. This framework is highly relevant to global challenges, such as the United Nations' 2030 Agenda for Sustainable Development, where nations must collaborate to combat adversarial factors like climate change or poverty. However, a significant limitation in existing AI literature is the assumption that all team members share an identical utility function.
In reality, team members often have divergent interests. For instance, while multiple countries may agree on the goal of carbon reduction, their individual economic priorities and costs vary significantly. Ignoring these differences can lead to "unstable" equilibria: strategies that appear optimal under a shared-utility assumption but fail in practice because individual players have incentives to deviate. This paper argues that accounting for heterogeneous utility functions is essential for robust coordination in adversarial settings.
The Co-opetition Equilibrium
To address the instability caused by ignoring utility differences, this research introduces the Co-opetition Equilibrium (CoE). This solution concept captures the dual nature of team-based competition: team members cooperate internally while competing externally.
A strategy profile is a CoE if it satisfies two conditions:
- External Stability: The joint team strategy and the adversary's strategy form a Nash Equilibrium. Neither the team as a whole nor the adversary can improve their payoff by unilaterally changing their strategy.
- Internal Stability: Given the adversary's strategy, the team's joint strategy forms a Correlated Equilibrium. This ensures that no individual team member has an incentive to deviate from the "recommended" action provided by a coordination mechanism.
Building on this, the paper defines the Team-Maximizing CoE (TMCoE), which is the specific CoE that maximizes the total utility for the team. This provides a clear target for optimization in practical applications.
Case Study: The Game of Chicken
The authors demonstrate the impact of utility differences using modified versions of the "Game of Chicken," denoted as $G_a$ and $G_b$.
In $G_a$, the team players have distinct payoffs, whereas $G_b$ represents a simplified model where these differences are ignored. As shown in the results table below, ignoring these differences (using $G_b$ to compute strategies for $G_a$) often leads to unstable outcomes where the team's actual utility collapses.
The table highlights that while standard concepts like Nash Equilibrium (NE) or Team-Maxmin Equilibrium (TME) might fail or be unstable in $G_a$, the CoE and TMCoE consistently provide stable, high-utility solutions. For example, in the extended Game of Chicken, ignoring utility differences resulted in a team utility of 0, whereas TMCoE achieved a utility of 10.5.
Theoretical and Computational Insights
The paper provides a rigorous analysis of the computational complexity of these new equilibria:
- General Hardness: Finding a CoE is PPAD-complete, and finding a TMCoE is NP-hard for general-sum adversarial team games.
- Tractable Subclasses: The authors identify a special class of games with "consistent constraints"—where individual utilities are proportional to the team utility. For these games, TMCoEs can be computed in polynomial time using linear programming.
- Efficiency Breakthrough: For games with consistent constraints, the author provides a polynomial-time algorithm, making these complex real-world scenarios computationally tractable.
Conclusion and Future Directions
This work shifts the focus of adversarial team game research toward more realistic, heterogeneous team structures. By introducing CoE and TMCoE, it provides a framework for stable coordination among diverse actors.
Future research directions include developing Multi-Agent Reinforcement Learning (MARL) algorithms that converge specifically to a CoE and extending these concepts to extensive-form games that unfold over time. By moving beyond the "shared utility" simplification, AI can better model and support real-world collaboration in high-stakes adversarial environments.
Summary updated