# Learning Equilibria of Games via Payoff Queries

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2013.

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

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)
- [Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games](https://mlsanity.com/paper/2304.12768/) (2023)
- [An active learning method for solving competitive multi-agent decision-making and control problems](https://mlsanity.com/paper/2212.12561/) (2022)
- [Protocols for Verifying Smooth Strategies in Bandits and Games](https://mlsanity.com/paper/2507.10567/) (2025)

## Abstract (arXiv)

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for bimatrix and graphical games. Our focus is on symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.