The Nash Equilibrium With Inertia in Population Games

• 成果类型: Article
• 署名作者: Gentile, Basilio; Paccagnan, Dario; Ogunsula, Bolutife; Lygeros, John
• 署名单位: Imperial College London; Bloomberg L.P.; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3044007
• 发表日期: 2021
• 页码: 5742-5755
• 关键词: Distributed algorithms; games; multiagent systems; Nash equilibrium; Vehicle Routing

摘要

In the traditional game-theoretic set up, where agents select actions and experience corresponding utilities, a Nash equilibrium is a configuration where no agent can improve their utility by unilaterally switching to a different action. In this article, we introduce the novel notion of inertial Nash equilibrium to account for the fact that in many practical situations switching action does not come for free. Specifically, we consider a population game and introduce the coefficients c(ij) describing the cost an agent incurs by switching from action i to action j. We define an inertial Nash equilibrium as a distribution over the action space where no agent benefits in switching to a different action, while taking into account the cost of such switch. First, we show that the set of inertial Nash equilibria contains all the Nash equilibria, is in general nonconvex, and can be characterized as a solution to a variational inequality. We then argue that classical algorithms for computing Nash equilibria cannot be used in the presence of switching costs. Finally, we propose a better-response dynamics algorithm and prove its convergence to an inertial Nash equilibrium. We apply our results to study the taxi drivers' distribution in Hong Kong.