Existence of Pairwise Stability in Two-sided Matching Markets

Abstract

In this thesis, we study two types of two-sided matching markets. The prime objective in these markets is to show that there always exists a pairwise stable matching. In these markets, each participant has a preference list. This preference list contains participants of the opposite side listed in an order. In these two-sided matching markets participants of one side can exchange money with participants of the opposite side. The preferences of the participants depend upon the money which they exchange. In fact, the preferences are given in terms of increasing functions of money. First, we consider a one-to-many matching market. For this market we as- sume that the preferences are continuous, strictly increasing linear functions of money. We develop an algorithm to show the existence of pairwise stability in this matching model. This matching model is more general than that of marriage model by Gale and Shapley, assignment game by Shapley and Shubik and hybrid models by Eriksson and Karlander, Sotomayor and Farooq. We also consider a market in which money appears as a discrete variable. For this market, we consider the preferences as strictly increasing functions of money. We use algorithmic approach to show the existence of pairwise stable outcome for the one-to-one matching market. This market generalizes the marriage model by Gale and Shapley.