Evolutionary Dynamics and Fast Convergence in the Assignment Game

Bary S.R. Pradelski

No 700, Economics Series Working Papers from University of Oxford, Department of Economics

Abstract: 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.

Keywords: assignment games; core; evolutionary game theory; matching markets; convergence time; random walks (search for similar items in EconPapers)
JEL-codes: C71 C73 C78 D83 (search for similar items in EconPapers)
Date: 2014-03-03
New Economics Papers: this item is included in nep-evo, nep-ger, nep-gth and nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://ora.ox.ac.uk/objects/uuid:f5acf754-310c-4b9f-8526-5f71e68cd4d1 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:oxf:wpaper:700

Access Statistics for this paper

More papers in Economics Series Working Papers from University of Oxford, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Anne Pouliquen ( this e-mail address is bad, please contact ).