Learning and aciclicity in the market game

Abstract

We show that strategic market games, the non-cooperative implementation of a matching with transfers or an assignment game, are weakly acyclic. This property ensures that many common learning algorithms will converge to Nash equilibria in these games, and that the allocation mechanism can therefore be decentralized. Convergence hinges on the appropriate price clearing rule and has different properties for better- and best-response dynamics. We tightly characterize the robustness of this convergence in terms of so-called schedulers for both types of dynamics.