Pareto stable matchings : an empirical study

• Main Author: Le, Truc Viet
• Other Authors: School of Physical and Mathematical Sciences
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
• Online Access: http://hdl.handle.net/10356/52238
• Institution: Nanyang Technological University

One of the important functions of many markets and social processes is to match one kind of agent with another. Well-known examples include students and colleges, workers and firms, marriageable men and women, and so on. When the set of agents can be partitioned into two disjoint subsets, each desires to be matched with another, we have a two-sided matching market. Thus, a matching is the outcome of the interactions between agents on both sides of the market and the process that produces such a matching is called a matching mechanism. Due to its versatile ability to model many essential social and economic activities, two-sided matching markets have been well studied in the economics and game theory literature. In this thesis, we study the two-sided matching market that arises from the allocation of courses to undergraduate students in NTU. Hence, the set of students and the set of courses form two sides of the market. We take an empirical approach by collecting data on one semester's allocation and examining the efficiency issues of the provided data. We further take the role of the market operator by designing centralized matching mechanisms via algorithms. Because the naive matching algorithm employed by NTU exhibits inherent drawbacks in terms of efficiency, we strive to improve the current system by introducing several other matching algorithms and applying those to the provided data. The primary social welfare objectives used to determine the efficiencies of the algorithms are stability and Pareto optimality -- thus the name Pareto stable matchings. Some novel aspects of this study include the use of secondary social welfare metrics (for comparing efficiencies across algorithms) and the implementation of matching algorithms developed in recent years. We conclude the thesis with two equally viable algorithms to the problem studied.