nucleation

LIT-1508: Re-evaluating Evaluation

2 min read

Properties4
StatusActive — read in full 2026-10-24 (NOTE-1155) from arXiv v2 (30 October 2018, the authors' "NIPS 2018, final version"); worth reading as the source of the Hodge and Schur reading of evaluation data and of Nash averaging. Elo is the row mean of the log-odds matrix, exact only when the log-odds have no cyclic part, and copies of an agent move it. Nash averaging scores each agent against the maximum-entropy Nash team of the meta-game. Its invariance to copies is proved only for the Nash set (Lemma 1): when the meta-game has more than one equilibrium, copying an agent moves the maximum-entropy selection and the Nash averages with it, which the reading checked by script. The Atari re-evaluation used an LP solution, not the maximum-entropy one.
Tagsgame-theory, mathematics, anthology-candidate
Cited as “paper” byNOTE-1155 — Balduzzi et al. — Re-evaluating evaluation
Cited as “source” byTHEORY-924 — When Elo ratings generate a win-probability matrix they are the row means of its log-odds; some set of Elo ratings reproduces a win-probability matrix exactly when its log-odds have no cyclic component, batch Elo otherwise matches only the row sums, and adding a copy of one agent shifts the batch Elo ratings of the others, THEORY-946 — In the zero-sum meta-game on an antisymmetric evaluation matrix the maximum-entropy Nash equilibrium is unique; when the meta-game has only one Nash equilibrium, adding exact copies of an agent splits that agent's mass evenly and leaves every Nash average unchanged; the equilibrium is uniform exactly when every agent's mean log-odds is zero, and uniform on the top-rated agents when the matrix is a pure gradient

Graph View

Balduzzi, Tuyls, Pérolat & Graepel (2018), Advances in Neural Information Processing Systems 31 (NeurIPS 2018) — arXiv:1806.02643

Key takeaways

From the reading, NOTE-1155. Page numbers are arXiv v2’s.

  • Elo is a mean. “Elo is, essentially, a uniform average in logit space” (p. 4). Elo ratings reproduce the win probabilities exactly when the log-odds matrix has no curl (Proposition 3), and a copy of an agent shifts everyone’s rating (appendix A; THEORY-924).
  • Nash averaging. Treat the evaluation matrix as a symmetric zero-sum meta-game, take its unique maximum-entropy Nash equilibrium, and score each agent by its expected log-odds against that team. Uniform when every agent’s mean is zero, concentrated on the top-rated agents when the matrix is a pure gradient (Theorem 1, P3; THEORY-946).
  • Invariance holds less widely than stated. Lemma 1 proves that the Nash set of the padded matrix is the set of splits of the original one. That fixes the maximum-entropy selection only when the original game’s equilibrium is unique. With a segment of equilibria, a copied agent pulls the selection toward itself. In the reading’s example, an outside agent’s Nash average moves from −0.5 to −0.2 when one agent is copied (NOTE-1155).
  • Weak continuity, harsh adversary. The Nash payoff is continuous, but the equilibrium itself “can jump discontinuously when A is modified slightly” (p. 7). The authors call Nash “a harsh master” that “removes control from the user” (p. 8).
  • Atari. Under Nash averaging over environments, human ties with the best agents (p. 7), but the equilibrium used was an LP solution, not the maximum-entropy one the invariance is about.

Why this is here

Filed 2026-10-24 for the record’s governance line, as a scoring rule designed so that padding the evaluated population cannot buy a ranking. It bears on CASE-124’s μ route and CASE-155’s share-dependent score c, and its Hodge reading bears on TERM-077 and THEORY-894 (NOTE-1155). It carries anthology-candidate because it is a method for evaluating ML agents. It is filed for understanding, not as an instruction for practice.

Backlinks