Matching is the part of economics that deals with the question of who gets what, e.g. who gets which jobs, who goes to which university, who receives which organ or who marries whom. During the second part of the last century, many markets have been discovered to have failed in providing the necessary conditions for efficient matches. These market failures have partly evolved on ethical or institutional grounds, but are more generally attributed to congestion or coordination problems caused by the inability of the market to make it safe for participants to act on their private information. For this reason, a variety of allocation mechanisms have been developed and subsequently tested in field and laboratory experiments for possible implementation in real-world applications.
This work attempts at giving a condensed review of different matching mechanisms and the performance of algorithms that have been implemented for solving the problems in their respective environments. The theoretical properties of these mechanisms as described in the increasingly vast literature on matching design will be used as a benchmark to compare their relative performance in terms of overall efficiency. The results yield some basic insights in the varying success of the competing algorithms in practice, indicating that both the quality of theoretical predictions and the actual performance of the algorithms decrease with the complexity of market environments. In particular, they show that imperfections of markets such as information asymmetry and incentive problems can have far-reaching consequences with respect to the effective working of matching procedures.
Table of Contents
1. INTRODUCTION
2. PRACTICAL PROBLEMS
2.1 Coordination and market failures
2.1.1 The labor market for medical interns
2.1.2 School choice
2.1.2.1 The New York City (NYC) High School Match
2.1.2.2 The Boston Public School Match (BPS)
2.2 Double coincidence of wants: kidney exchange
3. THEORETICAL FRAMEWORK
3.1 The marriage problem
3.1.1 A hypothetical model of the marriage market
3.1.2 Important matching properties
3.2 Gale-Shapley (GS) deferred-acceptance algorithm
3.2.1 A formal description of the assignment mechanism
3.2.2 Weak optimality of the GS stable matching algorithm
3.3 Alternative matching mechanisms
3.3.1 Top trading cycles mechanism
3.3.2 Priority mechanisms
3.3.3 Linear programming mechanism
4. INCENTIVES AND STRATEGIC BEHAVIOUR
4.1 Dominant strategies
4.1.1 Definitions and terminology
4.1.2 Stability and incentives
4.1.3 Strategy choice under incomplete information
4.2 Practical implications of stability and strategy-proofness
4.2.1 Relative performance of matching algorithms in laboratory experiments
4.2.2 Strategy-proofness of the Gale-Shapley algorithm: a fictitious example
5. CONCLUSIONS
Objectives and Topics
This thesis investigates the performance of various matching mechanisms in both theoretical and practical contexts, addressing market failures such as congestion, unraveling, and uncertainty. The central research question examines how different allocation algorithms—specifically the Gale-Shapley deferred-acceptance algorithm, Top Trading Cycles, and priority mechanisms—perform in environments where price signals are absent or prohibited.
- Theoretical properties of stable matching in two-sided markets.
- Practical implementation challenges in labor markets and public school choice systems.
- Incentives for strategic behavior and preference manipulation by market participants.
- Efficiency comparisons between mechanisms through field observations and laboratory experiments.
Excerpts from the Book
2.1.2.2 The Boston Public School Match (BPS)
Unlike with NYC schools, the student priorities of public schools in Boston are set by a central administration. As a consequence, students are allocated to over-demanded school seats by a system of priorities with the goal of giving as many students as possible their first choice school (Abdulkadiroglu et al., 2005b). First in priority are students who have older siblings already attending a specific school, and second priority is given to students who live in the walking distance of the school. Further priorities are assigned via a lottery generating random numbers once for each student. Since most popular schools would be filled in the first round of the assignment process, students who fail to get their first choice are likely to be crowded out of their secondary choices. This induces many parents to “game” the system by lying about their first choice because ranking a less desirable school first will increase the chances of getting a slot there (Cook, 2003). The old Boston mechanism belongs to the class of most common matching techniques called priority mechanisms which are traditionally applied in school choice.
Summary of Chapters
1. INTRODUCTION: Provides an overview of market matching functions, defines categories of market failure, and outlines the thesis structure.
2. PRACTICAL PROBLEMS: Analyzes real-world matching issues in medical labor markets, public school choice, and kidney transplantation, highlighting the necessity of centralized clearinghouses.
3. THEORETICAL FRAMEWORK: Examines the marriage problem model and evaluates matching mechanisms including Gale-Shapley, Top Trading Cycles, and linear programming based on stability and efficiency criteria.
4. INCENTIVES AND STRATEGIC BEHAVIOUR: Investigates the impact of strategic misrepresentation on matching outcomes and compares the performance of algorithms under different information scenarios.
5. CONCLUSIONS: Summarizes the performance of matching mechanisms, reaffirming the efficiency of the stable Gale-Shapley algorithm in two-sided markets despite challenges posed by incomplete information and human behavior.
Keywords
Matching mechanisms, market design, Gale-Shapley algorithm, school choice, kidney exchange, stability, strategy-proofness, Pareto-efficiency, market failure, incentive compatibility, labor markets, deferred-acceptance, priority mechanisms, Top Trading Cycles, preference revelation.
Frequently Asked Questions
What is the core focus of this thesis?
The work examines how matching mechanisms allocate indivisible goods or individuals in markets where price-based clearing is not feasible or permitted.
What are the primary fields of application discussed?
The thesis focuses on the assignment of medical interns to hospitals, the allocation of students to public schools, and the matching of organ donors with recipients.
What is the main objective of the research?
The goal is to compare different matching algorithms based on their theoretical advantages and their actual performance in real-world environments.
Which scientific methods are employed?
The author uses a game-theoretic framework to analyze matching models and reviews empirical evidence from both field studies and laboratory experiments.
What topics are covered in the main body?
The main body covers market failure definitions, the stability of matching algorithms, strategic behavior under incomplete information, and the practical implementation of clearinghouses.
How is this research characterized?
The work is characterized by the study of market design, stability hypothesis, and the trade-off between Pareto-efficiency and strategy-proofness.
Why was the "Boston Mechanism" considered problematic in school choice?
It was found to be unstable and provided incentives for parents to "game" the system, leading to inefficient outcomes and preference manipulation.
What role does the Gale-Shapley algorithm play in kidney exchange?
Modified versions of the Gale-Shapley algorithm and the Top Trading Cycles mechanism help organize exchange networks to maximize the number of life-saving transplants.
How does preference manipulation affect algorithm efficiency?
Misrepresentation by participants to secure better outcomes frequently leads to systemic inefficiency, as seen in laboratory tests and real-world application data.
What potential application does the author suggest for the University of Zurich?
The author proposes that the deferred-acceptance algorithm could be utilized to allocate students to scarce seminar slots to reduce congestion and uncertainty.
- Citar trabajo
- Andreas Zweifel (Autor), 2009, Matching mechanisms in theory and practice, Múnich, GRIN Verlag, https://www.grin.com/document/147246
