Job applicants can now easily submit many job applications, and so interviewing applicants, which is time consuming, has become a major source of congestion in many labor markets. But even in labor markets that use a clearinghouse to process offers and acceptances (like the market for medical residents in the U.S., the NRMP match) interviews are often organized in a decentralized manner. Here's a paper that tackles the question of how to organize an interview match, under some assumptions about what kind of information is obtained in interviews. Two approaches are considered: an 'adaptive' algorithm that takes into account the results of previous interviews in assigning subsequent interviews, and a 'non-adaptive' algorithm that matches candidates to interviews before any interview results are known.
Stable Matching with Interviews, by Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi (all at Stanford)
Abstract
"In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon GaleShapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log^2 n).
"In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log^3 n) interviews to each applicant or position. "
Posts
