New AI Learns the Rules of a Game Just by Watching Players

Luke Snow and Vikram Krishnamurthy study a sequence of independent one-shot non-cooperative games where agents play equilibria determined by a tunable mechanism. Observing only equilibrium decisions — with no parametric or distributional knowledge of utilities — they aim to steer equilibria toward social optimality, and to certify when that is impossible due to the game's structure. Their adaptive reinforcement learning framework derives a multi-agent revealed-preference test for Pareto optimality, giving necessary and sufficient conditions for utilities to exist under which the observed mixed-strategy Nash equilibria are socially optimal. Those conditions form a tractable linear program. The test feeds an inverse reinforcement learning step that computes the Pareto gap — the distance of observed strategies from Pareto optimality — coupled with a policy-gradient update, and they prove convergence to a mechanism that globally minimizes the Pareto gap. The result is a principled achievability test: if social optimality is attainable for the given game and observed equilibria, Algorithm 1 attains it; otherwise, the algorithm certifies unachievability while converging to the mechanism closest to social optimality. They also show a tight link between their loss and robust revealed-preference metrics, so algorithmic suboptimality can be read through established microeconomic notions. And when only finitely many i.i.d. samples of mixed strategies are available, they derive concentration bounds for convergence and design a distributionally robust RL procedure that attains the mechanism-design objective for fully specified strategies.