Global Nash convergence of Foster and Young's regret testing

• 成果类型: Article
• 署名作者: Germano, Fabrizio; Lugosi, Gabor
• 署名单位: Pompeu Fabra University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2006.06.001
• 发表日期: 2007
• 页码: 135-154
• 关键词: regret-based learning; Stochastic dynamics; Random search; uncoupled dynamics; unknown games; global convergence to Nash equilibrium

摘要

We construct an Uncoupled randomized strategy of repeated play such that, if every player plays according to it, mixed action profiles converge almost surely to a Nash equilibrium of the stage game. The strategy requires very little in terms of information about the game, as players' actions are based only on their own past payoffs. Moreover, in a variant of the procedure, players need not know that there are other players in the game and that payoffs are determined through other players' actions. The procedure works for finite generic N-player games and is based on appropriate modifications of a simple stochastic learning rule introduced by Foster and Young [Foster, D.P., Young, H.P., 2006. Regret testing: Learning to play Nash equilibrium without knowing you have an opponent. Theoretical Economics 1, 341-367]. (c) 2006 Elsevier Inc. All rights reserved.