Research Repository

Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games

Ferraioli, Diodato and Ventre, Carmine (2019) 'Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games.' ACM Transactions on Algorithms, 15 (2). ISSN 1549-6325

[img]
Preview
Text
MetaStab4PotGames-TALGEdit2.pdf - Accepted Version

Download (523kB) | Preview

Abstract

Convergence rate and stability of a solution concept are classically measured in terms of “even- tually” and “forever”, respectively. In the wake of recent computational criticisms to this approach, we study whether these time frames can be updated to have states computed “quickly” and stable for “long enough”. Logit dynamics allows irrationality in players’ behavior, and may take time exponential in the number of players n to converge to a stable state (i.e., a certain distribution over pure strategy pro- files). We prove that every potential game, for which the behavior of the logit dynamics is not chaotic as n increases, admits distributions stable for a super-polynomial number of steps in n no matter the players’ irrationality, and the starting profile of the dynamics. The convergence rate to these metastable distributions is polynomial in n when the players are not too rational. Our proofs build upon the new concept of partitioned Markov chains, that might be of indepen- dent interest, and a number of involved technical contributions.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 30 Nov 2018 15:27
Last Modified: 13 Mar 2019 13:15
URI: http://repository.essex.ac.uk/id/eprint/23526

Actions (login required)

View Item View Item