Best-response dynamics in two-person random games with correlated payoffs

• 成果类型: Article
• 署名作者: Mimun, Hlafo Alfie; Quattropani, Matteo; Scarsini, Marco
• 署名单位: Luiss Guido Carli University; Sapienza University Rome
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.03.011
• 发表日期: 2024
• 页码: 239-262
• 关键词: Pure Nash equilibrium; Random games; potential games; best response dynamics

摘要

We consider finite two -player normal form games with random payoffs. Player A's payoffs are i.i.d. from a uniform distribution. Given p is an element of [0 , 1], for any action profile, player B's payoff coincides with player A's payoff with probability p and is i.i.d. from the same uniform distribution with probability 1 - p . This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive p , asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability.