Game theory, on-line prediction and boosting

Yoav Freund, Robert E. Schapire

Research output: Contribution to conferencePaperpeer-review

365 Scopus citations


We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann's famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this game-playing algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the `dual' of this game.

Original languageEnglish (US)
Number of pages8
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 9th Annual Conference on Computational Learning Theory - Desenzano del Garda, Italy
Duration: Jun 28 1996Jul 1 1996


OtherProceedings of the 1996 9th Annual Conference on Computational Learning Theory
CityDesenzano del Garda, Italy

All Science Journal Classification (ASJC) codes

  • Computational Mathematics


Dive into the research topics of 'Game theory, on-line prediction and boosting'. Together they form a unique fingerprint.

Cite this