REAL

Analysis of stochastic matching markets

Biró, Péter and Norman, Gethin (2013) Analysis of stochastic matching markets. INTERNATIONAL JOURNAL OF GAME THEORY, 42 (4). pp. 1021-1040. ISSN 0020-7276

[img]
Preview
Text
BN13ijgt_last.pdf

Download (749kB) | Preview
[img] Text
art%3A10.1007%2Fs00182-012-0352-8.pdf
Restricted to Repository staff only

Download (345kB) | Request a copy

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 imply that the corresponding stochastic processes are absorbing Markov chains. 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. © 2012 Springer-Verlag Berlin Heidelberg.

Item Type: Article
Uncontrolled Keywords: STABLE MATCHINGS; Path to stability; Model checking; Markov chain
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 05 Dec 2013 10:04
Last Modified: 02 Mar 2016 07:05
URI: http://real.mtak.hu/id/eprint/7775

Actions (login required)

Edit Item Edit Item