The goal of the stable marriage problem is to match by pair two sets composed by the same number of elements. Due to its widespread applications in the real world, especially the unique importance to the centralized matchmaker, a very large number of questions have been extensively studied in this field. This article considers a generalized form of the stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single men or women is inevitable. Theoretical analysis and numerical simulations confirm that even a small deviation on the number of men and women from the equality condition can have a large impact on the matching solution of the Gale‐Shapley algorithm. These results provide insights to many of the real‐world applications when matching two sides with an unequal number.
Bipartite matching problem is to study two disjoint groups of agents who need to be matched pairwise. It can be applied to many real‐world scenarios and explain many social phenomena. In this article, we study the effect of competition on bipartite matching problem by introducing conformity into the preference structure. The results show that a certain amount of competition can improve the overall utility of society and also eliminate the giant shift of social utility when matching unequal numbers of men and women.
Cities serve as the main platform for human socio-economic activities, where large crowds, products, and information converge, forming complex societal interactions and the space for human to interact with each other. Like traditional geographical space, in cities, cyberspace and societal space also offer diverse channels for human interactions. While urban mobility in geographical space has been extensively studied across disciplines such as geography, economics, transportation and human behavior, mobility within societal space in cities has rarely been examined in depth. This paper focuses on the self-organized consolidation of mobility within urban societal spaces. Based on the rational person hypothesis and Dunbar's number, we construct a simple model to explain why urban societal classes spontaneously emerge in the evolution of societal space. We also find that the mobility within urban societal space decreases spontaneously over time, and eventually outstanding individuals potentially can be trapped in lower classes, resulting in an inefficient matching of urban resources.
The Stable Marriage Problem is to find a one-to-one matching for two equally sized sets of agents. Due to its widespread applications in the real world, especially the unique importance to the centralized match maker, a very large number of questions have been extensively studied in this field. This article considers a generalized form of stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single is inevitable. Theoretical analysis and numerical simulations confirm that even small deviations from equal number of two sides can have a large impact on matching solution of Gale-Shapley Algorithm. These results provide insights to many of the real-world applications when matching two sides with unequal number.
$k$-core decomposition is widely used to identify the center of a large network, it is a pruning process in which the nodes with degrees less than $k$ are recursively removed. Although the simplicity and effectiveness of this method facilitate its implementation on broad applications across many scientific fields, it produces few analytical results. We here simplify the existing theoretical framework to a simple iterative relationship and obtain the exact analytical solutions of the $k$-core pruning process on large uncorrelated networks. From these solutions we obtain such statistical properties as the degree distribution and the size of the remaining subgraph in each of the pruning steps. Our theoretical results resolve the long-lasting puzzle of the $k$-core pruning dynamics and provide an intuitive description of the dynamic process.