The stochastic stability of decentralized matching on a graph

• 成果类型: Article
• 署名作者: Boncinelli, Leonardo; Pin, Paolo
• 署名单位: University of Florence; Bocconi University; Bocconi University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2017.06.005
• 发表日期: 2018
• 页码: 239-244
• 关键词: Matching; graph; stochastic stability; Maximal matching; Maximum matching

摘要

We provide a perturbed evolutionary model of matching on a graph. First, we obtain that maximal matchings are the singleton recurrent classes of the model without perturbations. Then, we apply stochastic stability analysis considering two different error models: the link-error model, where mistakes directly hit links, and the agent-error model, where mistakes hit agents' decisions, and indirectly links. We find that stochastic stability is ineffective for refinement purposes in the link-error model - where all maximal matchings are stochastically stable - while it proves effective in the agent-error model - where all and only maximum matchings are stochastically stable. (C) 2017 Elsevier Inc. All rights reserved.