Turning Defense into Offense in $O(\log 1/\epsilon)$ Steps: Efficient Constructive Proof of the Minimax Theorem

Gabriele Farina

---

Abstract

Von Neumann’s minimax theorem asserts that the ability to defend against any opponent strategy implies the existence of an offensive strategy that guarantees the same value. This note revisits that symmetry from a constructive, oracle-based point of view. Given access to a defense oraclethat, for any opponent strategy x, returns a response y guaranteeing payoff at least v, we ask how efficiently one can compute an offense strategy y⋆ that guarantees value at least v − ε against all x. A classical construction via no-regret learning yields such a y⋆ after O((1/ε)2) calls to the defense oracle. In this note, I describe a different construction that uses only O(log(1/ε)) calls to the oracle (up to polynomial factors in the dimension and encoding size). I then illustrate this primitive through three applications: computing Φ-equilibria in convex and extensive-form games beyond polynomial type, computing expected solutions to variational inequalities, and computing expected fixed points of possibly discontinuous maps.