Journal article

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
Show more…
    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
Persistent URL
https://folia.unifr.ch/unifr/documents/304913
Statistics

Document views: 12 File downloads:
  • zha_ags.pdf: 2