Sampled fictitious play is Hannan consistent

• 成果类型: Article
• 署名作者: Li, Zifan; Tewari, Ambuj
• 署名单位: University of Michigan System; University of Michigan; Yale University; University of Michigan System; University of Michigan
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.01.005
• 发表日期: 2018
• 页码: 401-412
• 关键词: Adaptive heuristics; learning; repeated games; Hannan consistency; Fictitious play

摘要

Fictitious play is a simple and widely studied adaptive heuristic for playing repeated games. It is well known that fictitious play fails to be Hannan consistent. Several variants of fictitious play including regret matching, generalized regret matching and smooth fictitious play, are known to be Hannan consistent. In this note, we consider sampled fictitious play: at each round, the player samples past times and plays the best response to previous moves of other players at the sampled time points. We show that sampled fictitious play, using Bernoulli sampling, is Hannan consistent. Unlike several existing Hannan consistency proofs that rely on concentration of measure results, ours instead uses anti-concentration results from Littlewood-Offord theory. (C) 2018 Elsevier Inc. All rights reserved.