Dynamics in tree formation games

• 成果类型: Article
• 署名作者: Arcaute, E.; Dyagilev, K.; Johari, R.; Mannor, S.
• 署名单位: Technion Israel Institute of Technology; Stanford University; Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.01.002
• 发表日期: 2013
• 页码: 1-29
• 关键词: Network formation games; Network dynamics; strong stability; Tree formation games

摘要

Network formation games capture two conflicting objectives of selfish nodes in a network: such nodes wish to form a well-connected network and, at the same time, to minimize their cost of participation. We consider three families of such models where nodes avoid forming edges beyond those necessary for connectivity, thus forming tree networks. We focus on two local two-stage best-response dynamics in these models, where nodes can only form links with others in a restricted neighborhood. Despite this locality, both our dynamics converge to efficient outcomes in two of the considered families of models. In the third family of models, both our dynamics guarantee at most constant efficiency loss. This is in contrast with the standard best-response dynamics whose efficiency loss is unbounded in all three families of models. Thus we present a globally constrained network formation game where local dynamics naturally select desirable outcomes. (c) 2013 Elsevier Inc. All rights reserved.