Analysis of ground state in random bipartite matching
Analysis of ground state in random bipartite matching
复制标题
随机二分匹配中的基态分析
DOI：
10.1016/j.physa.2015.10.005
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Yi-Cheng Zhang
中科院分区：
文献类型：
--
作者：
Gui-Yuan Shi;Yi-Xiu Kong;Hao Liao;Yi-Cheng Zhang
二部匹配问题存在于许多人类社会现象中。本文研究了最流行的二部匹配模型--Gale-Shapley模型的基态。我们应用Kuhn-Munkres算法来计算模型的数值基态。首次得到了衡量系统不稳定性的阻塞对个数。我们还证明了每个人形成的阻塞对的数目服从几何分布。此外，我们还研究了两部分匹配问题中的连接性对基态不稳定性的影响。
Bipartite matching problems emerge in many human social phenomena. In this paper, we study the ground state of the Gale–Shapley model, which is the most popular bipartite matching model. We apply the Kuhn–Munkres algorithm to compute the numerical ground state of the model. For the first time, we obtain the number of blocking pairs which is a measure of the system instability. We also show that the number of blocking pairs formed by each person follows a geometric distribution. Furthermore, we study how the connectivity in the bipartite matching problems influences the instability of the ground state.
登录
查看更多内容
克服多样性的挑战：大数据抽象，AAL 通信系统数据管理的下一代发展
影响因子：
11.2
作者：
Mao Rui;Xu Honglong;Wu Wenbo;Li Jianqiang;Li Yan;Lu Minhua
通讯作者：
Lu Minhua
DOI：
--
发表时间：
1957
期刊：
--
影响因子：
--
作者：
J. Munkres
通讯作者：
J. Munkres
DOI：
10.1016/s0378-4371(97)00623-7
发表时间：
1997-10
影响因子：
3.3
作者：
T. Nieuwenhuizen
通讯作者：
T. Nieuwenhuizen
DOI：
10.1051/jphys:019870048090145100
发表时间：
1987-09
期刊：
Journal De Physique
影响因子：
--
作者：
M. Mézard;G. Parisi
通讯作者：
M. Mézard;G. Parisi
DOI：
10.1016/s0378-4371(00)00344-7
发表时间：
2000-07
影响因子：
3.3
作者：
M. Dzierzawa;Marie-José Oméro
通讯作者：
M. Dzierzawa;Marie-José Oméro