– 61 – Two-sided matching with compromise

We consider the problem of matching one kind of agent with another, e.g. marriageable men and women, students and colleges, workers and firms. These problems are defined as two-sided matchings if there are two groups of agents, and if an agent from one side of the group can be matched with an agent from the other side. Gale and Shapley originally proposed the two-sided matching problem. Much of the two-sided matching theory is concerned with determining the conditions under which stable matchings exist, and with what algorithms stable matching can be achieved effectively. In this paper, we propose a new algorithm for two-sided matching with some compromise at individual levels. We also obtain large-scale properties of the proposed algorithm. An important issue is how far agents seek their own interests in a competitive environment. There is overwhelming evidence to support that people are also motivated by concerns for fairness and reciprocity. We will show that compromise which is individually irrational improves the welfare of the whole group. The reasonable compromise level is obtained as the function of the size of the group so that the social utility should be maximized