Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7379146 | Physica A: Statistical Mechanics and its Applications | 2016 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematical Physics
Authors
Gui-Yuan Shi, Yi-Xiu Kong, Hao Liao, Yi-Cheng Zhang,