Analysis of Stochastic Matching Markets

Péter Biró and Gethin Norman ()
Additional contact information
Gethin Norman: School of Computing Science - University of Glasgow

No 1132, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: Suppose that the agents of a matching market contact each other randomly and form new pairs if is in their interest. Does such a process always converge to a stable matching if one exists? If so, how quickly? Are some stable matchings more likely to be obtained by this process than others? In this paper we are going to provide answers to these and similar questions, posed by economists and computer scientists. In the first part of the paper we give an alternative proof for the theorems by Diamantoudi et al. and Inarra et al. which implies that the corresponding stochastic processes are absorbing Markov chains. Our proof is not only shorter, but also provides upper bounds for the number of steps needed to stabilise the system. The second part of the paper proposes new techniques to analyse the behaviour of matching markets. We introduce the Stable Marriage and Stable Roommates Automaton and show how the probabilistic model checking tool PRISM may be used to predict the outcomes of stochastic interactions between myopic agents. In particular, we demonstrate how one can calculate the probabilities of reaching different matchings in a decentralised market and determine the expected convergence time of the stochastic process concerned. We illustrate the usage of this technique by studying some well-known marriage and roommates instances and randomly generated instances.

Keywords: roommates problem; marriage problem; stochastic processes; core convergence; probabilistic model checking (search for similar items in EconPapers)
JEL-codes: C62 C63 C71 C78 (search for similar items in EconPapers)
Pages: 22 pages
Date: 2011-07
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1132.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to econ.core.hu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
Journal Article: Analysis of stochastic matching markets (2013)
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:has:discpr:1132

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).