Advanced Search
MyIDEAS: Login

Analysis of Stochastic Matching Markets

Contents:

Author Info

  • Peter Biro

    ()
    (Institute of Economics - Hungarian Academy of Sciences)

  • Gethin Norman

    ()
    (School of Computing Science - University of Glasgow)

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.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://econ.core.hu/file/download/mtdp/MTDP1132.pdf
Download Restriction: no

Bibliographic Info

Paper provided by Institute of Economics, Centre for Economic and Regional Studies, Hungarian Academy of Sciences in its series IEHAS Discussion Papers with number 1132.

as in new window
Length: 22 pages
Date of creation: Jul 2011
Date of revision:
Handle: RePEc:has:discpr:1132

Contact details of provider:
Postal: 1112 Budapest, Budaorsi ut 45.
Phone: (+36-1) 309-2652
Fax: (36-1) 319-3136
Web page: http://econ.core.hu
More information through EDIRC

Related research

Keywords: roommates problem; marriage problem; stochastic processes; core convergence; probabilistic model checking;

Find related papers by JEL classification:

This paper has been announced in the following NEP Reports:

References

No references listed on IDEAS
You can help add them by filling out this form.

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Newton, Jonathan & Sawa, Ryoji, 2013. "A one-shot deviation principle for stability in matching problems," Working Papers 2013-09, University of Sydney, School of Economics, revised Mar 2014.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:has:discpr:1132. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Adrienn Foldi).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.