The stochastic stability of decentralized matching on a graph

Abstract

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.