Abstract
This paper investigates whether decentralized deep reinforcement learning (RL) agents can learn to negotiate complex team-formation and reward-sharing tasks without prior game-theoretic knowledge. By framing the problem through Weighted Voting Games in both non-spatial and spatial environments, the researchers demonstrate that self-interested agents converge on "fair" reward distributions that closely approximate the Shapley value—a classic solution concept from cooperative game theory. The study highlights how physical environment constraints, such as distance, act as leverage in negotiations and how emergent fairness serves as a stable equilibrium in multi-agent systems, even when theoretical solutions like the Nash Equilibrium are computationally infeasible.
Introduction
In multi-agent systems, cooperation is rarely a given. When self-interested agents inhabit the same space, they often need to form teams to accomplish tasks that are impossible alone, such as search-and-rescue missions or complex manufacturing lines. This presents two major hurdles: Coalition Selection (deciding who to team up with) and Reward Division (determining how to split the "spoils" to maintain the agreement).
Traditional cooperative game theory provides mathematical "fair" solutions like the Shapley value, but these are often computationally intractable (NP-hard) and assume perfect, abstract negotiation protocols. Real-world negotiation is messy, temporally extended, and often influenced by physical factors like location. This research asks: Can decentralized RL agents learn to navigate these complexities and reach stable, fair agreements on their own?
Bridging Cooperative and Non-Cooperative Game Theory
The core of this research lies in establishing a correspondence between abstract cooperative game theory and the practical application of non-cooperative reinforcement learning. The researchers map the "Underlying Game" (a cooperative characteristic function) onto a "Markov Game" through a specific negotiation protocol.
As illustrated in the framework above, while the Shapley value serves as the theoretical solution concept for the underlying game, finding a Nash Equilibrium in the resulting Markov game is often computationally infeasible. Instead, the authors utilize Independent Reinforcement Learning to see if agents can empirically discover solutions that align with cooperative theory.
Experimental Methodology
The authors frame the problem using Weighted Voting Games, where each agent has a "weight," and a team only wins if the sum of its members' weights meets a certain quota. They test their agents in two distinct environments:
- Propose-Accept (Non-Spatial): A turn-based game where a random proposer suggests a team and a reward split. The "proposees" must all accept for the deal to go through. If they decline, they risk the game ending with zero reward for everyone.
- Team-Patches (Spatial): A 15x15 grid-world where agents must physically move to colored "patches" to form a team. Agents set a "demanded share" of the reward. A deal is struck only if the agents on a patch meet the weight quota and their total demands do not exceed the available reward.
For the non-spatial task, the researchers used SARSA($\lambda$) with a multi-layer perceptron. For the spatial task, they employed an Advantage Actor-Critic (A2C) architecture with V-trace corrections, using a Convolutional Neural Network (CNN) to process the visual grid.
Key Insights and Results
Emergent Fairness and the "Leveling" Effect
The most striking finding is that RL agents, driven purely by maximizing their own reward, converge on distributions that correlate strongly with the Shapley value. This suggests that "fairness" in these games isn't just a moral preference; it's a stable equilibrium for self-interested negotiators. However, the agents exhibit a "leveling" effect: in cases of extreme power inequality, RL agents tend to be more egalitarian than the Shapley value predicts. "Strong" players receive slightly less than their theoretical share, while "weak" players receive slightly more.
Geography as Leverage
In the spatial environment, physical location acts as a hidden "weight." If a powerful agent starts further away from the negotiation patches, their bargaining power drops significantly. In the Team-Patches environment, increasing the distance of the strongest agent from the patches by just 10 steps caused their share of the reward to plummet from ~35% to ~10%. This highlights how environment design can mitigate "monopolistic" power.
Capacity vs. Dynamics
By training a separate supervised model, the authors proved that even a tiny neural network can calculate Shapley values accurately. This implies that the deviations seen in the RL agents are not due to a lack of model capacity, but rather the complex, non-stationary dynamics of learning while peers are simultaneously changing their strategies.
Conclusion and Future Work
The research demonstrates that deep RL agents can consistently outperform hand-crafted rule-based bots by roughly 10% in total reward share while aligning with theoretical fairness concepts. While Multi-Agent Reinforcement Learning (MARL) remains computationally expensive and potentially unstable due to non-stationarity, this work opens doors for exploring emergent language in negotiations, scaling to hundreds of agents, and investigating the enforcement of dynamic contracts in complex societies.
Summary updated