The New Nash Proof
Nash's 1950 proof relied on Kakutani's fixed-point theorem; his 1951 revision used Brouwer's. Carpentiere and Watson (2023) show there is another way—one that needs no fixed-point machinery at all.
Root Function Approach
A root function r: Σ → S maps any mixed strategy profile to a pure strategy profile. The key property: for each player i, the chosen pure strategy ri(σ) must already have positive probability in their current mix, and it must yield zero incentive to deviate.
Pre-equilibria
A pre-equilibrium is a subset R ⊂ Σ that a root function maps onto the entire set of pure strategy profiles. The proof shows arbitrarily small pre-equilibria always exist via a geometric volume argument.
Preserving the Equilibrium. Because the root-function structure constrains how strategies can evolve, cooperative updates to agents' behavior do not destabilize the game. The equilibrium remains robust even as the profile shifts.
Moving Beyond Naive Learning
When AI agents optimize only their own objectives, they often collapse into the worst Nash equilibria. Duque et al. (ICLR 2025) introduce a family of algorithms that shape opponents by aligning advantages.
The Problem: Naive Learning
Standard RL agents are naive learners: they treat opponents as part of the stationary environment and optimize only their own return. In social dilemmas, this reliably leads to mutually destructive outcomes such as Always Defect.
The AdAlign Solution
Advantage Alignment increases the log-probability of an action proportionally to how well an agent's cumulative past success aligns with the opponent's current potential. When historic interaction is positive, cooperative action becomes more probable.
Key Properties. AdAlign preserves Nash equilibria, requires no imagined parameter updates (unlike LOLA/SOS), needs no DiCE-style gradient estimation (unlike POLA/COLA), and extends naturally to continuous action domains via Proximal Advantage Alignment (PAA).
Mechanisms for Bounded Agents
Even incentive-compatible mechanisms fail if agents cannot understand them. Pycia and Troyan (Econometrica, 2023) formalize simplicity through planning horizons.
k-step OSP
An agent's planning horizon is the number of future decisions (k) they can plan for. Obviously Strategy-Proof (OSP) mechanisms require only that the current action is unambiguously good, regardless of what happens beyond the horizon.
- Short horizon → simpler mechanisms
- Long horizon → more complex mechanisms allowed
- Simplicity is a spectrum of robustness
Planning Horizon
The longer the horizon, the more social choice rules a designer can implement in a simply dominant way. Yet any implementable rule can be implemented via a perfect-information extensive-form game.
Reverse Greedy
Agents "clinch" outcomes by deferring commitment. At each step they can verify their action is safe without forecasting the entire future. This deferred-acceptance logic is markedly more robust to imperfect human or AI rationality.
Forward Greedy
Agents commit immediately to the best current option. Under bounded rationality, this often leads to suboptimal outcomes because agents cannot foresee how early commitments constrain later possibilities.
From Grid Worlds to Common Resources
Three benchmark domains demonstrate how aligning advantages converts conflict into cooperation.
The Coin Game
Agents move on a grid collecting colored coins. Each scores only for coins matching its own color. Naive agents greedily grab any coin; AdAlign agents learn specialization—each collects only their own color, maximizing the collective score.
The Negotiation Game
Agents split items with different private utilities. Where greed takes everything, AdAlign learns reciprocal fairness: splits reflect individual utility profiles, converging to cooperative reciprocity similar to Tit-for-Tat.
Commons Harvest
A multi-agent tragedy of the commons: agents harvest apples from trees that regenerate slowly. Naive over-harvesting destroys the orchard. AdAlign agents learn sustainable restraint, preventing resource extinction.