# D3C: Reducing the Price of Anarchy in Multi-Agent Learning

arXiv: https://arxiv.org/abs/2010.00575 · HTML: https://mlsanity.com/paper/2010.00575/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2020.

## Built on by (most cited first, 16 of 16)

- [A Review of Cooperation in Multi-agent Learning](https://mlsanity.com/paper/2312.05162/) (2023)
- [A social path to human-like artificial intelligence](https://mlsanity.com/paper/2405.15815/) (2024)
- [Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.06760/) (2022)
- [Multi-Agent, Human-Agent and Beyond: A Survey on Cooperation in Social Dilemmas](https://mlsanity.com/paper/2402.17270/) (2024)
- [Warmth and competence in human-agent cooperation](https://mlsanity.com/paper/2201.13448/) (2022)
- [The Importance of Credo in Multiagent Learning](https://mlsanity.com/paper/2204.07471/) (2022)
- [Aligning Individual and Collective Objectives in Multi-Agent Cooperation](https://mlsanity.com/paper/2402.12416/) (2024)
- [Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment](https://mlsanity.com/paper/2106.14993/) (2021)
- [Learning to Balance Altruism and Self-interest Based on Empathy in Mixed-Motive Games](https://mlsanity.com/paper/2410.07863/) (2024)
- [Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments](https://mlsanity.com/paper/2209.10958/) (2022)
- [Learning Roles with Emergent Social Value Orientations](https://mlsanity.com/paper/2301.13812/) (2023)
- [Towards a Better Understanding of Learning with Multiagent Teams](https://mlsanity.com/paper/2306.16205/) (2023)
- [Multi-Head Attention Is a Multi-Player Game](https://mlsanity.com/paper/2602.00861/) (2026)
- [Learning to Learn Group Alignment: A Self-Tuning Credo Framework with Multiagent Teams](https://mlsanity.com/paper/2304.07337/) (2023)
- [Preference-based opponent shaping in differentiable games](https://mlsanity.com/paper/2412.03072/) (2024)
- [Adaptive Punishment for Cooperation in Mixed-Motive Games](https://mlsanity.com/paper/2605.24516/) (2026)

## Abstract (arXiv)

In multiagent systems, the complex interaction of fixed incentives can lead agents to outcomes that are poor (inefficient) not only for the group, but also for each individual. Price of anarchy is a technical, game-theoretic definition that quantifies the inefficiency arising in these scenarios -- it compares the welfare that can be achieved through perfect coordination against that achieved by self-interested agents at a Nash equilibrium. We derive a differentiable, upper bound on a price of anarchy that agents can cheaply estimate during learning. Equipped with this estimator, agents can adjust their incentives in a way that improves the efficiency incurred at a Nash equilibrium. Agents do so by learning to mix their reward (equiv. negative loss) with that of other agents by following the gradient of our derived upper bound. We refer to this approach as D3C. In the case where agent incentives are differentiable, D3C resembles the celebrated Win-Stay, Lose-Shift strategy from behavioral game theory, thereby establishing a connection between the global goal of maximum welfare and an established agent-centric learning rule. In the non-differentiable setting, as is common in multiagent reinforcement learning, we show the upper bound can be reduced via evolutionary strategies, until a compromise is reached in a distributed fashion. We demonstrate that D3C improves outcomes for each agent and the group as a whole on several social dilemmas including a traffic network exhibiting Braess's paradox, a prisoner's dilemma, and several multiagent domains.