α-Rank: Multi-Agent Evaluation by Evolution

Area of Science:

• Game Theory
• Evolutionary Dynamics
• Multi-Agent Systems

Background:

• Existing models for evaluating agents in multi-agent interactions are limited in scalability and may not converge to desired game-theoretic solutions like Nash equilibrium.
• Current methods struggle with large numbers of agents, complex interaction types (beyond dyadic), and diverse empirical game structures (symmetric/asymmetric).

Purpose of the Study:

• To introduce α-Rank, a principled evolutionary dynamics methodology for evaluating and ranking agents in large-scale multi-agent interactions.
• To provide a scalable and tractable solution grounded in a novel dynamical game-theoretic concept, Markov-Conley chains (MCCs).

Main Methods:

• Leveraging continuous-time and discrete-time evolutionary dynamical systems applied to empirical games.
• Utilizing Markov-Conley chains, a dynamical solution concept based on Markov chains and Conley's Theorem, for agent evaluation.
• Establishing a correspondence between evolutionary dynamics and MCCs for large ranking-intensity parameter α.

Main Results:

• α-Rank scales tractably with the number of agents, interaction types, and game types.
• The method provides automatic rankings and insights into agent strengths, weaknesses, and long-term dynamics (basins of attraction, sink components).
• α-Rank runs in polynomial time, contrasting with the intractability of computing Nash equilibria for general-sum games.

Conclusions:

• α-Rank offers a unifying perspective on evolutionary evaluation models and provides formal underpinnings for agent ranking.
• The methodology is empirically validated in canonical games and complex domains like AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.
• This approach provides a robust and efficient alternative for analyzing agent behavior in complex, large-scale interactive environments.