Approachability with bounded memory

Ehud Lehrer and Eilon Solan ()

Games and Economic Behavior, 2009, vol. 66, issue 2, 995-1004

Abstract: We study Blackwell's approachability in repeated games with vector payoffs when the approaching player is restricted to use strategies with bounded memory: either strategies with bounded recall, or strategies that can be implemented by finite automata. Our main finding is that the following three statements are equivalent for closed sets. (i) The set is approachable with bounded recall strategies. (ii) The set is approachable with strategies that can be implemented with finite automata. (iii) The set contains a convex approachable set. Using our results we show that (i) there are almost-regret-free strategies with bounded memory, (ii) there is a strategy with bounded memory to choose the best among several experts, and (iii) Hart and Mas-Colell's adaptive learning procedure can be achieved using strategies with bounded memory.

Keywords: Approachability; Repeated; games; Vector; payoffs; Bounded; memory; Bounded; recall; Automata; No-regret; Adaptive; learning (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00181-4
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:66:y:2009:i:2:p:995-1004

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().