MULTIPERIOD MATCHING

• Author: Maciej H. Kotowski,Sangram V. Kadam
• Published date: 01 November 2018
• Date: 01 November 2018
• DOI: http://doi.org/10.1111/iere.12324

INTERNATIONAL ECONOMIC REVIEW

Vol. 59, No. 4, November 2018 DOI: 10.1111/iere.12324

MULTIPERIOD MATCHING∗

BYSANGRAM V. KADAM AND MACIEJ H. KOTOWSKI1

Charles River Associates, U.S.A.; Harvard University, U.S.A.

We examine a dynamic, two-sided, one-to-one matching market where agents on both sides interact over a

period of time. We define and identify sufficient conditions for the existence of a dynamically stable matching,

which may require revisions to initial assignments. A generalization of the deferred acceptance algorithm can

identify dynamically stable outcomes in a large class of economies, including cases with intertemporal preference

complementarities. We relate our analysis to market unraveling and to common market design applications,

including the medical residency match.

1. INTRODUCTION

Gale and Shapley’s (1962) concept of “stability” is the leading theoretical organizing principle

for two-sided matching markets. The term’s connotation, however, suggests an immutability in

a market’s outcome. But this is not what we often observe. Consider a few consequences of

seemingly, or aspirationally, stable pairings in two-sided markets:

(1) After freshman year, a student transfers to another college.

(2) A married couple divorces. Each then finds a new spouse.

(3) A business graduate initially works in management consulting. After a year, she quits to

start her own business.

In the preceding cases, commitment is limited and intended long-term (or permanent) pairings

often see revisions after a few periods. Gale and Shapley’s (1962) model of ephemeral one-time

assignments cannot capture these changes, which unfold with time.

In this article, we examine an extension of Gale and Shapley’s model to a multiperiod setting,

where agents match and possibly change their assignments over time. As part of our analysis, we

propose a new stability definition—dynamic stability—that extends Gale and Shapley’s solution

in an intuitive and tractable way. Drawing on familiar intuitions, a matching is dynamically

stable if, at each moment in time, it is individually rational and no pair of agents can arrange

a mutually preferable relationship plan conjecturing that the wider market evolves in an unfa-

vorable manner. We consider dynamic stability to be the simplest and most natural multiperiod

generalization of Gale and Shapley’s original idea. We identify sufficient conditions for the

existence of a dynamically stable matching, and we propose a new generalization of Gale and

∗Manuscript received January 2017; revised August 2017.

1We thank seminar audiences at Harvard/MIT, Santa Clara University, Stanford, the University of Melbourne,

the University of Western Ontario, and Yale and conference participants at the 2014 Meeting of the Society for

Social Choice and Welfare (Boston), the 2014 International Conference on Game Theory (Stony Brook), and the

2014 International Workshop on Game Theory and Economic Applications honoring Marilda Sotomayor (Sao Paulo)

for helpful suggestions that greatly improved this study. We thank Fanqi Shi, Neil Thakral, Norov Tumennasan, and,

especially, Chris Avery for their comments on earlier versions of this article. We are grateful to Mei Liang and Dr. Laurie

Curtin of the National Resident Matching Program for comments on a draft of this article. Sangram V. Kadam gratefully

acknowledges the support of the Danielian Travel & Research Grant. Portions of this study were completed when Maciej

H. Kotowski was visiting the Stanford University Economics Department. He thanks Al Roth and the department

for their generous hospitality. Please address correspondence to: Maciej H. Kotowski, John F. Kennedy School of

Government, Harvard University, 79 JFK Street, Cambridge, MA 02138. E-mail: maciej_kotowski@hks.harvard.edu

1927

C

(2018) by the Economics Department of the University of Pennsylvania and the Osaka University Institute of Social

and Economic Research Association

1928 KADAM AND KOTOWSKI

Shapley’s (1962) deferred acceptance algorithm to find such assignments. Our model captures

the periodic rematching observed in many two-sided markets.

Though we adopt Gale and Shapley’s terminology of a matching between men and women,

our model’s applications extend beyond the study of interpersonal relations. Labor markets offer

a germane application. According to the U.S. Bureau of Labor Statistics (2012), “individuals

born from 1957 to 1964 held an average of 11.3 jobs from ages 18 to 46.” Our model and

solution accommodate such dynamics.2For simplicity, we suppress the role of financial transfers

in our main exposition, but they can be incorporated into our model, as we show in the online

Appendix.

Our analysis is primarily a positive description of a multiperiod economy, and we make no

presumption concerning the existence of a centralized authority determining agents’ assign-

ments. Nevertheless, the existence of algorithms that can identify stable outcomes has spurred

the establishment of specialized clearinghouses to coordinate participants’ interaction in some

markets (Roth, 2002). Our results can inform these applications as well since they often in-

volve a multiperiod component. As an example, consider the National Resident Matching

Program (NRMPR) medical residency match (Roth and Peranson, 1999).3The NRMP is a

clearinghouse that matches graduating medical students to hospital residency programs in the

United States using an algorithm. Although the initial match of a trainee-doctor to a residency

program draws the most attention, a deeper look at this market reveals a rich multiperiod

structure. Some residency programs, for example, only provide introductory instruction, and

students must also match with an advanced specialty. Other programs bundle all years of train-

ing together. Attrition (McAlister et al., 2008; Yaghoubian et al., 2012) and transfers between

residency programs occur as well.4These features suggest that an assessment of the algorithm’s

success and of participants’ welfare requires a longer term perspective, going beyond the ini-

tial “Match Day” headlines. Multiperiod models, like ours, provide a framework for such an

analysis.

This article is organized as follows: Section 2 briefly reviews the related literature. Section 3

introduces our model and defines our main solution concept, dynamic stability. For simplicity,

we focus on a two-period setting, but our model generalizes.5Section 4 identifies sufficient

conditions for the existence of a dynamically stable matching and presents a new multiperiod

generalization of Gale and Shapley’s (1962) deferred acceptance algorithm. Sections 5 and 6

explore two applications of our model. First, Section 5 examines several multiperiod matching

mechanisms, including the aforementioned NRMP algorithm, in greater detail. We contrast

their operation with the algorithms that we propose. And second, Section 6 considers the role

of learning in a multiperiod matching market. We apply our definition of dynamic stability to

offer a new explanation for market unraveling in situations where agents interact over multiple

periods. Section 7 concludes by summarizing our contributions and by outlining extensions

of our analysis, which we investigate in the online Appendix. All omitted proofs are in the

Appendix.

2. LITERATURE

We study an economy where agents interact over multiple periods, forming and revising

their assignments with time. Similar two-sided, one-to-one matching markets are studied by

Damiano and Lam (2005), Kurino (2009), and Kotowski (2015).6These studies propose

2Labor market dynamics are a central focus of the search-and-matching literature (Rogerson et al., 2005). Our model

offers a complementary perspective on this phenomenon building more directly on Gale and Shapley’s (1962) model.

3“National Resident Matching Program” and “NRMP” are registered trademarks of the National Resident Matching

Program.

4Losada (2015) describes the process of switching programs and specialities, including anecdotal accounts of students’

experiences.

5We offer a T-period version of our model in the online Appendix. See also Kadam and Kotowski (2018).

6Abdulkadi̇ro˘

glu and Loertscher (2007), Bloch and Cantala (2013), and Kurino (2014), among others, study dynamic

one-sided markets. We do not study this case, though our analysis is complementary.