Evolutionary Dynamics and Fast Convergence in the Assignment Game

We study decentralized learning dynamics for the classic assignment game with transferable utility.  At random points in time firms and workers match, break up, and re-match in the sesarch for better opportunities.  We propose a simple learning process in which players have no knowledge about other players' payoffs or actions and they update their behavior in a myopic fashion.  Behavior fluctuates according to a random variable that reflects current market conditions: sometimes the firms exhibit greater price stickiness than the workers, and at other times the reverse holds.  We show that this stochastic learning process converges in polynomial time to the core.  While convergence to the core is known for some types of decentralized dynamics this paper is the first to prove fast convergence, a crucial feature from a practical standpoint.  The proof relies on novel results for random walks on graphs, and more generally suggests a fruitful connection between the theory of random walks and matching theory.