Convergence of best-response dynamics in extensive-form games

• 成果类型: Article
• 署名作者: Xu, Zibo
• 署名单位: Singapore University of Technology & Design
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2015.12.001
• 发表日期: 2016
• 页码: 21-54
• 关键词: convergence; Extensive form; perfect information; Backward-induction strategy profile; best-response dynamics; self-confirming equilibrium

摘要

This paper presents a collection of convergence results on best-response dynamics in extensive-form games. We prove that in all finite generic extensive-form games of perfect information, every solution trajectory to the continuous-time best-response dynamic converges to a Nash equilibrium component. We show the robustness of-this convergence in the sense that along any interior approximate best-response trajectory, the evolving state is close to the set of Nash equilibria most of the time. We also prove that in any perfect-information game in which every play contains at most one decision node of each player, any interior approximate best-response trajectory converges to the backward-induction strategy profile. Our final result concerns self-confirming equilibria in perfect-information games. If each player always best responds to her conjecture of the current strategy profile, and she updates her conjecture based only on observed moves, then the dynamic will converge to the set of self-confirming equilibria. (C) 2015 Elsevier Inc. All rights reserved.