Affordable Access

Adaptive Game Playing Using Multiplicative Weights

Authors
Journal
Games and Economic Behavior
0899-8256
Publisher
Elsevier
Publication Date
Volume
29
Identifiers
DOI: 10.1006/game.1999.0738
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract We present a simple algorithm for playing a repeated game. We show that a player using this algorithm suffers average loss that is guaranteed to come close to the minimum loss achievable by any fixed strategy. Our bounds are nonasymptotic and hold for any opponent. The algorithm, which uses the multiplicative-weight methods of Littlestone and Warmuth, is analyzed using the Kullback–Liebler divergence. This analysis yields a new, simple proof of the min–max theorem, as well as a provable method of approximately solving a game. A variant of our game-playing algorithm is proved to be optimal in a very strong sense. Journal of Economic Literature Classification Numbers: C44, C70, D83.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Game playing.

on Wiley interdisciplinary review... March 2014

Playing with evidence: Using video games in the co...

on Entertainment Computing Jan 01, 2011

Playing Games

Jan 01, 2013
More articles like this..