2016/09/14 by Stéphane Le Roux, Arno Pauly
Computer Science · #cs.GT #cs.MA
paper · pdf · doi:10.4204/eptcs.226.17
published as EPTCS 226, 2016, pp. 242-256 · In Proceedings GandALF 2016, arXiv:1609.03648
arxiv created 2016/09/14 · arxiv updated 2016/09/15
We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite sequential games we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are Delta02 sets.