Collective efficiency in two-sided matching

Gale and Shapley originally proposed the two-sided matching algorithm, Deferred Acceptance Algorithm (DA). This is very brilliant method, but it has a demerit which produces. That is if men propose, it produces stable matching which is the best for men and the worst for women, and vise versa. In this paper, we propose a new algorithm with compromise that produce the bal-anced matching which are almost optimal for both sides. It is an important issue how far agents seek their own interests in a competitive environment. There are overwhelming evidences that support peoples are also motivated by concerns for fairness and reciprocity. We will show that compromise which is individually irra-tional improves the welfare of the whole groups. The reasonable compromise level is obtained as the function of the size of the group so that the social utility should be maximized. We also obtain large-scale properties of the proposed algorithm. 1