Analysis of ground state in random bipartite matching
- Shi, Gui-Yuan Physics Department, University of Fribourg, Switzerland
- Kong, Yi-Xiu Physics Department, University of Fribourg, Switzerland
- Liao, Hao Guangdong Province Key Laboratory of Popular High Performance Computers, College of Computer Science and Software Engineering, Shenzhen University, China
- Zhang, Yi-Cheng Physics Department, University of Fribourg, Switzerland
-
15.02.2016
Published in:
- Physica A: Statistical Mechanics and its Applications. - 2016, vol. 444, p. 397–402
English
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.
- Faculty
- Faculté des sciences et de médecine
- Department
- Département de Physique
- Language
-
- English
- Classification
- Physics
- License
- License undefined
- Identifiers
-
- RERO DOC 259000
- DOI 10.1016/j.physa.2015.10.005
- Persistent URL
- https://folia.unifr.ch/unifr/documents/304913
Statistics
Document views: 54
File downloads:
- zha_ags.pdf: 107