Matching mechanisms in theory and practice

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

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.