EUVIMEDEUVIMED entdecken
Crossref

Turning Defense into Offense in O (log 1/ε) Steps: Efficient Constructive Proof of The Minimax Theorem

Gabriele Farina

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →