Scaling properties of Two-sided Matching with Compromise

In this paper, we propose a new algorithm for two-sided matching problems with some compromise. We dis-cuss the self-interested hypothesis vs. human sociality hypothesis. It is an important issue such as how far agents seek their own interest in a competitive environment? There are overwhelming evidences that support peoples are also motivated by concerns for fairness and reciprocity. We showed that compromise, an indi-vidually irrational behavior, improves the welfare of others. We also obtain large-scale properties of some two-sided matching algorithms. We show some compromises of individuals increase global welfare. The op-timal compromise level is designed so that the social utility is maximized.