Multiagent Learning: dynamic games & applications

Daniel Hennes2013 · DOI

Abstract

Game theory studies strategic interactions where multiple players act rationally to maximize their expected payoffs. While its origins date back to the seminal work of von Neumann and Morgenstern (1944), it has since found applications in diverse fields including economics, social sciences, biology, and multi-robot systems. This work bridges the gap between Reinforcement Learning (RL) and Evolutionary Game Theory (EGT) by extending the formal framework of replicator dynamics to multi-state stochastic games. We introduce State-Coupled Replicator Dynamics (SCRD) to accurately predict agent learning in complex environments and apply these insights to bargaining, market foresight, and robot collision avoidance.

Introduction: The Strategic Landscape

To provide an intuitive understanding of game theory, consider the classic Prisoners' Dilemma. Two suspects are arrested and interrogated separately. They face a choice: "cooperate" with each other by remaining silent, or "defect" by betraying the other.

If one suspect testifies while the other remains silent, the defector is released while his loyal fellow is convicted to serve the full sentence. If both defect, both serve a long sentence. If both deny all accusations, they serve a short sentence for a minor charge. Rational analysis for a self-interested player suggests that defection is the dominant strategy, even though mutual cooperation yields a better collective outcome. This predicament serves as a foundational example for studying repeated interactions and evolution in multiagent systems.

The Problem: Learning in Non-Stationary Environments

Multiagent Learning (MAL) is notoriously difficult because agents face a "moving target" problem: as one agent adapts its behavior, the environment effectively changes for all other agents. This violates the stationary environment assumption required by most standard machine learning proofs.

While EGT provides elegant tools like Replicator Dynamics to model these interactions, they have traditionally been restricted to simple, single-state games. Conversely, Reinforcement Learning algorithms are often treated as "black boxes," making it hard to predict if they will converge to an equilibrium or cycle indefinitely. This research provides a mathematical bridge that allows evolutionary models to predict, analyze, and design better learning algorithms for dynamic, multi-state environments.

Methodological Contributions

State-Coupled Replicator Dynamics (SCRD)

Previous attempts to model multi-state games used "piecewise" models that partitioned the strategy space, often resulting in mathematical anomalies and discontinuities. SCRD addresses this by coupling states directly through an average reward game formulation. This allows for a smooth, continuous model of how policies evolve across different states, incorporating the frequency of state occurrences into the differential equations. SCRD has been shown to match the actual learning traces of Finite Action-set Learning Automata (FALA) far more accurately than previous models.

RESQ-learning

By "reverse-engineering" the SCRD model and injecting a Boltzmann-style mutation term for exploration, we derive RESQ-learning. Unlike standard Q-learning, which can cycle in certain games, RESQ-learning is designed to converge to both pure and mixed Nash equilibria in stochastic games.

Metastrategy Reduction

To handle the massive strategy spaces found in real-world bargaining, we use "metastrategies"—high-level heuristic strategies (e.g., "Proposer Focus" vs. "Responder Focus"). This reduces complex interactions to canonical 2x2 or 3x3 games that are easier to analyze using evolutionary tools.

Key Insights and Applications

A core finding is the proof that a large collective of independent learners follows symmetric continuous-time replicator dynamics if fitness-proportionate selection is used. This justifies using EGT to study massive systems of simple agents.

Market Dynamics and the J-Curve of Information

In market simulations involving Continuous Double Auctions, the value of information is non-monotonic. "Non-informed" (random) traders often perform at the market average because they are unpredictable. "Average-informed" traders actually perform the worst because they are predictable and easily exploited by "insiders." This J-curve suggests that a stable diversity of information levels emerges only if information has a non-zero cost; if information is free, insiders eventually drive all other traders out.

Bargaining and Inequity Aversion

Experiments using the Colored Trails (CT) test-bed showed that human-like "inequity aversion" (disliking unfair splits) significantly changes the "basins of attraction" in a game. Proposers are often forced to coordinate on more equitable outcomes to avoid total rejection by responders who prioritize fairness over absolute gain.

Robot Collision Avoidance

In robotics, reciprocal strategies—where both agents assume the other will help avoid a crash—are shown to be Evolutionarily Stable Strategies (ESS). However, this stability is sensitive to the "truncation" or look-ahead horizon of the agents, determining how far into the future they project potential collisions.

Conclusion and Future Directions

This research establishes a rigorous link between evolutionary models and reinforcement learning, providing a framework to predict learning behavior in complex, multi-state environments. While the current SCRD framework is based on the limiting average reward criterion, extending it to discounted rewards remains an open challenge. Furthermore, integrating these models with Differential Game Theory could handle continuous robot motion more naturally. As multiagent systems grow in complexity, developing techniques to visualize high-dimensional policy spaces will be essential for designing robust, predictable autonomous agents.

Summary updated

Abstract

Chapter 1. Introduction Games, Equilibria and EvolutionGame theory studies strategic interactions where multiple players act rationally in order to maximize their expected payoffs.The origin of modern game theory dates back to the seminal work by von Neumann and Morgenstern (1944).Game theory has since found applications in very diverse fields.Players can represent companies in the realm of economics, single individuals in the psychological or social science domain, animals, bacteria, or plants in the field of biology, as well as computer agents situated in a multiagent or multi-robot setting.To provide an intuitive understanding of the methodology of game theory we shall first consider a particular strategic encounter.The prisoners' dilemma (Axelrod, 1984) is a prevalent example to showcase game theoretical decision making and analysis.We first introduce the classical predicament, while gradually extending the problem to repeated interaction, and evolution.Example 1 (Prisoners' dilemma).The dilemma presents itself in the following situation.Two subjects are under arrest.The police has not collected enough evidence to provide the prosecution with grounds for a severe accusation.Thus the two prisoners are separated for interrogation and are both confronted with the same choice: either confess the crime and hence "defect" and betray the other suspect, or to deny any accusation and hence "cooperate" with the other suspect.If one suspect testifies while the other remains silent, the defector is released while his loyal fellow is convicted to serve the full sentence.If both defect, both have to serve a long sentence, only slightly reduced for cooperating with the police.If both deny all accusations, they serve a short sentence for a minor charge.How should the prisoners choose rationally in order to minimize penalty?Seemingly, the best option is to cooperate, both parties only serve a short sentence and are set free after a relatively short time.However, this intuition suggests a nonrational decision.Game theory provides the tools to reason about such a strategic situation and identify the rational choice.Let us consider the options of a suspect under the following set of assumptions.A suspect is self-interested and therefore only cares about his own well-being (or degree of punishment in our example) and thus does not profit from lowering the sentence of the other.Furthermore, any communication between suspects is inhibited and both are ensured that the other is provided with the same information and faces the same choice.Both have the same option to choose exactly one of the two strategies "defect" or "cooperate" and the outcome of the game is independent of the order or identity of the players.In other words, the game is symmetric.Since no communication is allowed we might as well assume that players act simultaneously.Suppose a player chooses to "cooperate".If the other one cooperates as well the player is convicted to serve a short sentence; if the other one betrays him he serves the
BibTeX
@misc{hennes2013multiagent,
  author = {Daniel Hennes},
  title = {{Multiagent Learning: dynamic games \& applications}},
  year = {2013},
  doi = {10.26481/dis.20130516dh},
}
Figure