Please use this identifier to cite or link to this item:
Title: Pareto stable matchings : an empirical study
Authors: Le, Truc Viet
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
Issue Date: 2012
Abstract: 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.
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Tspms G1003096C.pdf
  Restricted Access
720.5 kBAdobe PDFView/Open

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.