Game theory, on-line prediction and boosting

Yoav Freund; Robert E. Schapire

doi:10.1145/238061.238163

Game theory, on-line prediction and boosting

Yoav Freund
, Robert E. Schapire

Research output: Contribution to conference › Paper › peer-review

402 Scopus citations

Abstract

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 language	English (US)
Pages	325-332
Number of pages	8
DOIs	https://doi.org/10.1145/238061.238163
State	Published - 1996
Externally published	Yes
Event	Proceedings of the 1996 9th Annual Conference on Computational Learning Theory - Desenzano del Garda, Italy Duration: Jun 28 1996 → Jul 1 1996

Other

Other	Proceedings of the 1996 9th Annual Conference on Computational Learning Theory
City	Desenzano del Garda, Italy
Period	6/28/96 → 7/1/96

All Science Journal Classification (ASJC) codes

Computational Mathematics

Access to Document

10.1145/238061.238163

Cite this

@conference{25cb8d8c792b41f388445a50031a8264,

title = "Game theory, on-line prediction and boosting",

abstract = "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.",

author = "Yoav Freund and Schapire, \{Robert E.\}",

year = "1996",

doi = "10.1145/238061.238163",

language = "English (US)",

pages = "325--332",

}

TY - CONF

T1 - Game theory, on-line prediction and boosting

AU - Freund, Yoav

AU - Schapire, Robert E.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0030419058

UR - https://www.scopus.com/pages/publications/0030419058#tab=citedBy

U2 - 10.1145/238061.238163

DO - 10.1145/238061.238163

M3 - Paper

AN - SCOPUS:0030419058

SP - 325

EP - 332

T2 - Proceedings of the 1996 9th Annual Conference on Computational Learning Theory

Y2 - 28 June 1996 through 1 July 1996

ER -

Game theory, on-line prediction and boosting

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this