Analysis of stochastic matching markets
Analysis of stochastic matching markets
复制标题
随机匹配市场分析
DOI：
10.1007/s00182-012-0352-8
复制
发表时间：
2012
影响因子：
0.6
通讯作者：
Biró P
中科院分区：
文献类型：
--
作者：
Biró P
假设一个匹配市场的代理人随机地相互联系，如果对他们有利，就组成新的对。这样的过程是否总是收敛到一个稳定的匹配，如果存在的话？如果是，有多快？是否有些稳定匹配比其他匹配更有可能通过这个过程获得？在本文中，我们将为经济学家和计算机科学家提出的这些问题和类似问题提供答案。在本文的第一部分中，我们给出了Diamantoudi等人的定理的另一种证明。和Inarra等人，这意味着相应的随机过程是吸收马尔可夫链。本文的第二部分提出了分析匹配市场行为的新技术。我们介绍了稳定的婚姻和稳定的室友自动机，并展示了如何概率模型检测工具PRISM可用于预测近视代理之间的随机相互作用的结果。特别是，我们演示了如何计算在分散的市场中达到不同匹配的概率，并确定有关随机过程的预期收敛时间。我们通过研究一些著名的婚姻和室友的实例和随机生成的实例来说明这种技术的用法。
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.
登录
查看更多内容
基于IPS模型的各种系统变革及其结构背景
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
M. Csanádi
通讯作者：
M. Csanádi
Árukapcsolás és csomagban történő értékesítés: Jogesetek és közgazdasági elmélet
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
P. Valentiny
通讯作者：
P. Valentiny
Maple 计算机代数系统
DOI：
--
发表时间：
1993
期刊：
Comput. Sci. J. Moldova
影响因子：
--
作者：
M. Monagan
通讯作者：
M. Monagan
影响因子：
1.1
作者：
Jimmy J. M. Tan;Y. Hsueh
通讯作者：
Y. Hsueh
关于访问联盟结构核心所需的区块数量
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
S. Béal;É. Rémila;P. Solal
通讯作者：
P. Solal