Turning Defense into Offense in O (log 1/ε) Steps: Efficient Constructive Proof of The Minimax Theorem
ACM SIGecom Exchanges · 01.01.2026 · 23 (2) · 76-84
DOI: 10.1145/3817099.3817105 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGecom Exchanges, online erschienen am 01.07.2026. Verfasst von Gabriele Farina. Die Arbeit nennt 13 Literaturangaben.
Abstract (Originalsprache)
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 oracle that, 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.
Zitieren
APA
Farina, G. (2026). Turning Defense into Offense in O (log 1/ε) Steps: Efficient Constructive Proof of The Minimax Theorem. ACM SIGecom Exchanges, 23(2), 76-84. https://doi.org/10.1145/3817099.3817105
Vancouver
Farina G. Turning Defense into Offense in O (log 1/ε) Steps: Efficient Constructive Proof of The Minimax Theorem. ACM SIGecom Exchanges. 2026;23(2):76-84. doi:10.1145/3817099.3817105
BibTeX
@article{Farina2026,
author = {Farina, Gabriele},
title = {Turning Defense into Offense in O (log 1/ε) Steps: Efficient Constructive Proof of The Minimax Theorem},
journal = {ACM SIGecom Exchanges},
year = {2026},
volume = {23},
number = {2},
pages = {76--84},
doi = {10.1145/3817099.3817105}
}
EUVIMED