Matching Mechanism Design For Market With Weak Preferences

With the rapid development of economy and internet technology, the size of the market of resource allocation will be bigger. Hence, people pay much attention to design some fair and efficient mechanisms. The price mechanism can not apply in the matching market, because the object is indivisible and monetary transfers are not permitted in this market, such as, the market of school choice. To solve these trading problems in the real market, Shapley proposed the Top Trading Cycles mechanism and Deferred Acceptance mechanism for one-sided matching and two-sided matching, respectively. After that, Roth applied the theory of matching to market design for the clearing center of the hospital market, school choice and kidney exchange, etc. It brings significant influence for human welfare by using these mechanisms. As they improve the mechanism of the resources allocation and promote the market fairness, Shapley and Roth won the Nobel Prize in economics in 2012. It shows that the matching theory in the resources allocation has a important position. However, the matching mechanisms designed by them are under strict preferences. Since the information obtained by participants is limited and the size of the market is expanded, the participants may have not strict preferences over potential matching object. In this case, Top Trading Cycles and Deferred Acceptance mechanisms are not Pareto-efficient and fair. Consequently, studying on mechanism design and algorithmic research for one-sided and two-sided, static and dynamic matching market with weak preferences has theoretical and practical value.For the one-sided matching market with endowment and ties, appling the strongly connected of the TTC-graph to find the cores, this thesis presents a matching mechanism that satisfies Pareto efficient, strategy-proof and individual rational. The complexity of the corresponding algorithm is lower than the existing algorithms. When the objects are divided into collective and individual objects in the one-sided matching market, this thesis considers the priority of choice collective object for participants and presented a matching mechanism that satisfies Pareto efficiency, strategy-proofness and individual rationality, while it ensures that collective objects were allocated by the priority of participants. The complexity of the algorithm is also effective.For the many-to-many matching market with ties, the Gale-Shapley mechanism is not Pareto efficient, and the corresponding algorithm of the existing matching mechanisms that satisfy stable and Pareto efficient is not effective, this thesis presents a new PARETO-STABLE mechanism, and improved effectiveness of the algorithm. For the dynamic two-sided matching market, the individual rationality may conflict with the fairness in the matching process, this thesis has introduced a fair and efficient criterion, and proposed a matching algorithm to get matching that satisfies the new fairness criterion.We apply the above matching mechanisms to the public rental housing distribution market and the electronic brokers in this thesis. The designed matching mechanisms under the practical background, it greatly improves the social welfare of the public rental housing distribution market. Also, it achieves automatic matching of search target between buyers and sellers, and makes the matching satisfing the Pareto stable. At the same time, it ensures the success rate of trading between the buyers and sellers. Thus, it improves the efficiency of purchasing and matching. The results of this thesis can be used to college admission, organ transplantation, school choice, college student hunt jobs, distribution of university research funds and online auction of advertisement, because the monetary transfers are not permitted in these matching problems.