Stable Matching with Interviews

We present an adaptive algorithm that finds an interim stable matching while requiring that each applicant and position engage in at most $O({\log }^{2}n)$ interviews. The algorithm is applicable to a general setting, where the publicly known values assigned to applicants and positions can vary arbitrarily, and the subjective interests are independent and identically distributed.

The proposed algorithm expands upon deferred acceptance [14] by dividing the process into distinct interview and proposal stages. Specifically, in the applicant-optimal version, each applicant submits a proposal to the position offering the highest observed utility. The position will accept the “highest” proposal or assign an interview if the proposing applicant has the potential to create a blocking pair, taking into account potential changes in the observed value following the interview.

The main technical ingredient of the analysis is to show the probability that an applicant gets rejected by more than $O({\log }^{2}n)$ consecutive positions is very small. More precisely, with probability at least $1-n^{-3}$, each applicant $a_i$ is matched to position $p_j$ for $j\le i+O({\log }^{2}n)$.

In the adaptive model, the algorithm is allowed to determine the sequence of interviews based on the results of previous ones. However, in practice, many markets favor a non-adaptive approach in which the interview lists are predetermined beforehand to allow the parties to streamline scheduling and the rest of the logistics.

We present a non-adaptive algorithm for interim stable matching with a poly-logarithmic number of interviews per agent. The algorithm works in tiered markets in which applicants and positions are partitioned into multiple tiers. Two applicants $a_i$ and $a_{i^{\prime }}$ in the same tier have the same publicly known value, i.e., $u_i=u_{i^{\prime }}$. On the other hand, if an applicant $a_i$ is in a higher tier than $a_{i^{\prime }}$, then it is always preferred independent of the interview outcomes, i.e., for all position $p_j$, $\mathrm{Pr}[u_i+{\epsilon }_{ji}^P>u_{i^{\prime }}+{\epsilon }_{j{i}^{\prime }}^P]=1$.

The design of the non-adaptive algorithm incorporates two key technical components. First, we observe that in markets where all applicants and positions are in a single tier, requiring each applicant to interview a set of $O({\log }^{2}n)$ positions chosen uniformly at random combined with an applicant-optimal Gale-Shapley algorithm results in an interim stable matching.

On the other hand, when all positions are in the same tier while applicants are in individual tiers, random interviews prove to be ineffective. This is primarily due to positions exhibiting a preference for applicants in the corresponding higher tiers. Consequently, these higher-tier applicants are given higher priority in the matching process. The challenge arises for the lowest-tier applicant who, despite undergoing a poly-logarithmic number of random interviews, struggles to find the sole available position among the interviewed positions. To address this, a different approach is taken. By fixing the order of positions, interviews are assigned to each applicant with consecutive positions whose indices closely match the tier number of the applicant. This strategy ensures that applicants with similar tier numbers have a substantial overlap of interviews. Consequently, positions that are interviewed by higher-tier applicants will be matched to them and will not be available options for lower-tier applicants.

The non-adaptive algorithm combines the above two technical ingredients with a few other ideas. Specifically, it creates a sequence of bipartite graphs $G_i(A_i,P_i,E_i)$, where each $G_i$ may be a random graph like the first special case we considered, a sequential graph like the second special case, or a small complete bipartite graph when we have two small tiers. We refer the reader to Section 3.3 for the details of the algorithm and its analysis.

Further, in Section 3.4, we demonstrate that if applicants and positions have individual preferences within the tiers prior to the interviews, the exact same ideas and proofs presented in Section 3.3 carry over, with some mild assumptions about the distribution of individual preferences before the interviews and subjective interest arising from the interview.

The extensive literature on two-sided matching has led to a rich theory and successful designs in practice. However, most of the existing work focuses on models in which agents know their own preferences. Little is known about the interaction period in which agents learn about their preferences by interacting with each other. This paper attempts to address this gap by looking at this problem with an algorithmic lens, focusing on extending Gale-Shapley’s deferred acceptance to this setting.

If ${\epsilon }_{ij}^A\ge 0$ and ${\epsilon }_{ji}^P\ge 0$, the interview does not change $\beta (a_i)$ and applicant $a_i$ remains the most preferable applicant proposing to $p_j$. Hence, the algorithm matches applicant $a_i$ to position $p_j$ in the next iteration.

Now, observe that, based on Algorithm 1 of Algorithm 1, $p_j$ is going to interview an applicant $a_{i^{\prime }}$ if either $i^{\prime }\le j$ or if $u_{i^{\prime }}>u_i+{\epsilon }_{ji}^P>u_i$, which implies . $\mathrm{⊲}$

Before proposing to $p_j$, $a_i$ proposes to all positions $p_{j^{\prime }}$ with . Also, based on Algorithm 1 of the algorithm, when $i\le j^{\prime }$, $p_{j^{\prime }}$ does not reject $a_i$ without an interview. $◀$

The next lemma establishes that positions do not interview any applicant with a significantly higher index. Moreover, we show that with the possible exception of $8\log n$ positions with the highest index (and lowest expected utility for the applicants), the positions get matched sequentially in the increasing order of their index.

The first part of the lemma holds trivially when $j\ge n-8\log n$. So suppose and let $S$ be the set of agents $a_i$ with . At most $j-1$ agents from $S$ can be matched to position $p_{j^{\prime }}$ for at any time. Further, applicants propose to positions in the increasing order of their index. Hence, in order for $p_j$ to get matched to an applicant $a_{i^{\prime }}$ with $i^{\prime }>j+8\log n$, it should reject at least $8\log n$ applicants from set $S$. We will show that such an event is extremely unlikely.

Let $ℐ$ be the set of the indices of the first $8\log n$ applicants interviewed by $p_j$. By the above argument, $ℐ\subseteq S$. By 2, if $p_j$ interviews some applicant $a_i$ and observes that both ${\epsilon }_{ij}^A$ and ${\epsilon }_{ji}^P$ are non-negative, then $p_j$ and $a_i$ get matched. Since ${\epsilon }_{ij}^A$ and ${\epsilon }_{ji}^P$ are drawn independently at random from a symmetric distribution with mean zero, $\mathrm{Pr}[{\epsilon }_{ij}^A\ge 0\text{ and }{\epsilon }_{ji}^P\ge 0]\ge 1/4$. Therefore,

A union bound over the above events implies the probability that there exists an $i$ such that $a_i$ and $p_j$ interview each other and $i>j+8\log n$ is at most $n^{-2}$.

The second part of the lemma follows by observing that as long as each position $p_j$ with gets matched to one of its first $8\log n$ proposals, $p_{j+1}$ does not receive any proposals before $p_j$ is matched. $◀$

For the rest of the section, we condition on the high probability events stated in Lemma 4. For $k\in [n]$, let $A_k=\{a_k,a_{k+1},\mathrm{\dots },a_n\}$ and $P_k=\{p_k,p_{k+1},\mathrm{\dots },p_n\}$. Also, let $\overline{A_k}=A\setminus A_k$ and $\overline{P_k}=P\setminus P_k$.

Since we condition on Lemma 4, Therefore,

$\mathrm{⊲}$

We need to prove the statement for . By Lemma 4, when the algorithm is considering pair $(a_{i^{\ast }},p_{j^{\ast }})$, we have $\mu (p_{j^{\prime }})\ne \mathrm{\varnothing }$ for . By 5,

which implies,

On the other hand,

$\mathrm{⊲}$

Let $\delta =8\log n$ and $\gamma =1999{\log }^{2}n$. The statement holds for $i\ge n-\gamma -\delta$ since . Suppose for some , applicant $a_i$ and position $p_{i+\gamma +1}$ interview each other at some point during the algorithm. At that time, by Lemma 4, all positions with index smaller than $i+\gamma +1$ are matched to an applicant. Also, by 3, all positions in $\{p_i,p_{i+1},\mathrm{\dots },p_{i+\gamma }\}$ have already interviewed $a_i$, but none of them is matched to $a_i$. We will show that the probability of such an event is at most $n^{-4}$.

Consider all positions $p_l$ for $i\le l\le i+\gamma$ and define

By 6, there are at most $\delta$ positions in the set of which are matched to an applicant with an index smaller than $i$. The rest are matched to an applicant in $\{a_i,a_{i+1},\mathrm{\dots },a_{l+\delta }\}$. Therefore, $|S_l|\le 2\delta$.

Define $Y_l$ to be indicating whether $p_l$’s utility for matching to $a_i$ is higher than being matched to all elements in $S_l$ and $X_l$ to be $Y_l=1$, ${\epsilon }_{li}^P\ge 0$, and ${\epsilon }_{li}^A\ge 0$. By 2, $X_l=1$ implies that $p_l$ can not be matched to an applicant with an index more than $i$. Further, by 6 at most $\delta$ positions in $\{p_i,p_{i+1},\mathrm{\dots },p_{i+\gamma }\}$ may be matched to an applicant with index less than $i$, so it is sufficient to bound the probability that $X={\sum }_{j=i}^{i+\gamma }{X}_j\le \delta$.

Observe that $\mathrm{Pr}[Y_l=1]\ge 1/(2\delta )$ for all $l$. Also, note that because of the independence of the subjective component of utilities, $Y_l$’s are independent. Further, $E[X_l]=1/4E[Y_l]\ge 1/(8\delta )$. Using Chernoff bound,

The first inequality is due to $\text{E}[X]-\frac{\gamma }{16\delta }\ge \frac{\gamma +1}{8\delta }-\frac{\gamma }{16\delta }>\frac{\gamma }{16\delta }\ge \delta ,$ assuming $n$ is sufficiently large. Applying union bound over all applicants completes the proof. $◀$

The statements of Lemma 4 and Lemma 7 hold with high probability, for all applicants $a_i$. Therefore, every $a_i$ is interviewed only by positions $p_j$ where $j\in [\max (1,i-8\log n),i+\min (n,2000{\log }^{2}n)]$. Similarly, for every position $p_j$ in Algorithm 1, the position only interviews $a_i$’s for which $i\in [\max (1,j-2000{\log }^{2}n),\min (n,j+8\log n)]$. Therefore, the number of interviews done by each applicant or position is at most $O({\log }^{2}n)$.

The proof of stability is fairly similar to the analysis of deferred acceptance. Suppose there exists a blocking pair $(a_i,p_j)$. This implies that $a_i{\succ }_{p_j}\mu (p_j)$ and $p_j{\succ }_{a_i}\mu (a_i)$. Therefore, $a_i$ must have been rejected by $p_j$ during one of the iterations of Algorithm 1. This implies that position $p_j$ is matched with an applicant who has a higher observed utility, and the current match of $p_j$ should not be worse than $a_i$, i.e., $\mu (p_j){\succ }_{p_j}{a}_i$. That is a contradiction, as we initially assumed that $(a_i,p_j)$ is a blocking pair. $◀$

We prove this by induction on the number of iterations. Initially, $|X|=e(X)$. Now assume that before the $i$th iteration. If $X$ is the short side in iteration $i$, then all vertices of $X$ will be removed after this iteration, and thus $|X|=e(X)=0$. Also, if $X$ is the long side and the algorithm is in case 3, then $|X|=e(X)$ by Algorithm 2 of Algorithm 2.

In all other cases, $e(X)$ decreases after the iteration. Further, by Algorithm 2, if $|X|-e(X)\ge \theta$, we remove vertices of $X$ for which . $◀$

Also, it is not hard to see that all applications and positions will be removed by the end of Algorithm 2.

Let $X_1,\mathrm{\dots },X_{{\tau }_M}$ be all tiers of positions and $Y_1,\mathrm{\dots },Y_{{\tau }_N}$ be all tiers of applicants. Note that ${\sum }_{i=1}^{{\tau }_M}e(X_i)={\sum }_{i=1}^{{\tau }_N}e(Y_i)$ at all times during the execution of Algorithm 2 since in all three cases, the effective cardinality of the short side tier is subtracted from both ${\sum }_{i=1}^{{\tau }_M}e(X_i)$ and ${\sum }_{i=1}^{{\tau }_N}e(Y_i)$. Since the algorithm does not terminate until either or both ${\sum }_{i=1}^{{\tau }_M}e(X_i)=0$ or ${\sum }_{i=1}^{{\tau }_N}e(Y_i)=0$, then all vertices are removed when the algorithm terminates. $◀$

We let $A_i$ be the set of applicants that are endpoints of $E_i$. We define $P_i$ similarly. Moreover, let $A_i^{\prime }\subseteq A_i$ and $P_i^{\prime }\subseteq P_i$ be the set of applicants and positions that are endpoints of $E_i$, and are unmatched when we run Gale-Shapley in Algorithm 3 between $A_i$ and $P_i$. Therefore, if $A_i$ and $P_i$ belongs to tiers $X$ and $Y$, then $|A_i^{\prime }|=e(X)$ and $|P_i^{\prime }|=e(Y)$ at the time of iteration $i$. As we mentioned before, a vertex may appear in multiple $A_i$s or $P_i$s. We will show that such sets are consecutive. To do so, we first give a helpful property of the algorithm.

The algorithm always chooses vertices with the lowest index from the long side to interview. Consider the interview with $Y_j$, those are the vertices with a relative index of $S(X)-|X^{j-1}|+1$ to $(S(X)-|X^{j-1}|)+(\delta +|X^{j-1}|-e(X^{j-1}))=S(Z)+\delta -e(X^{j-1})$. And by definition of Algorithm 2, $e(X^j)=e(X^{j-1})-e(Y_j)$. $\mathrm{⊲}$

Let $Z$ be the tier containing $v$ and $S(Z)$ be the initial size of tier $Z$ at the start of Algorithm 2. Also, let $L$ be the first iteration considering $v$ and $e(Z)$ be the effective size of tier $Z$ at that point. It is not hard to see that if $Z$ is the short side in this iteration, or if the short side $Z^{\prime }$ has size $e(Z^{\prime })>\delta$, all the vertices of $Z$ that have an interview in this iteration will be removed, and we are done. When $Z$ is the long side and $e(Z)\le \delta$, every vertex in $Z$ will be interviewed.

The only remaining case to consider is where $Z$ is on the long side, $e(Z)>\delta$, and the tiers considered alongside $v$ are $Y_1,Y_2,\mathrm{\dots }{Y}_r$, where $e(Y_i)\le \delta$ for all $i$. From 12 and the fact that $e(Z)$ decreases monotonically, as long as $v$ is not removed from the graph, it will be selected for interview, which means it will be the endpoint of at least one edge in $E_i$. That implies $v$ is in $A_i$ or $P_i$ by definition. $\mathrm{⊲}$

Let $X$ and $Y$ be two tiers that vertices of $A_i$ and $P_i$ belong to, respectively. Also, by the definition of $A_i^{\prime }$, we have $|A_i^{\prime }|=e(X)$ at the time of $i$th iteration. If $e(X)\le \delta$, since $|P_i^{\prime }|\ge \delta$, we choose a subset $S$ of $Y$ with size $\delta +|Y|-e(Y)$ and interview all edges. This set contains $\delta$ vertices that are not matched at $i$th iteration. By Lemma 10, if we choose $t=10{\log }^{2}n/{\log }^{2}e(Y)$, then $c_t>2\log n/\log e(Y)$ and with probability

$a_r$ will match to a position $p_j\in P_i^{\prime }$ such that ${\epsilon }_{rj}^A>0$.

Similarly, if $e(X)>\delta$, we choose a subset $S$ of $Y$ that contains $e(X)$ unmatched vertices. For each vertex of $A_i^{\prime }$ we interview $\delta$ random positions in $P_j^{\prime }$. Hence, if we choose $t=10{\log }^{2}n/{\log }^{2}e(X)$ in Lemma 10, then $c_t>2\log n/\log e(X)$, and with probability

$a_r$ will match to a position $p_j\in P_i^{\prime }$ such that ${\epsilon }_{rj}^A>0$. $◀$

Without loss of generality, assume that the removed vertex in iteration $i$ is applicant $a_r$ in tier $X$. Let $Y$ be the tier of the other side that the algorithm considers in iteration $i$. First, assume that $X$ is the short side, $e(X)\le \delta$, and $e(Y)\le \delta$ at iteration $i$. According to Case 1 of Algorithm 2, all vertices of $X$ interview all vertices of $Y$, hence, the statement hold with probability 1. Now suppose that $X$ is the short side and $e(Y)>\delta$ at iteration $i$. Hence, by definition, we have $|A_i^{\prime }|\le |P_i^{\prime }|$ and $|P_i^{\prime }|>\delta$. Therefore, by Lemma 14, $a_r$ is matched to a position $p_j$ such that ${\epsilon }_{ij}^A>0$ with probability $1-O(1/n^2)$, which implies that $(a_r,p_j)\in E_i$. Furthermore, if $e(X)>\delta$, $e(Y)>\delta$, and $X$ is the long side, $|A_i^{\prime }|=|P_i^{\prime }|$. Since for this case we run a position-proposing Gale-Shapley in Algorithm 3, by Lemma 14, all positions in $P_i^{\prime }$ get matched to applicants in $A_i^{\prime }$ with edges $E_i$. Thus, all vertices of $A_i^{\prime }$ are matched to positions in $P_i^{\prime }$ using edges $E_i$ since we have $|A_i^{\prime }|=|P_i^{\prime }|$.

The only case that remains to be investigated is when $X$ is the long side in several iterations until $a_r$ is removed at iteration $i$, i.e. $a_r\in A_j$, $|A_j^{\prime }|\ge |P_j^{\prime }|$ for $j\in [l,i]$ and $|P_j^{\prime }|\le \delta$. Also, let $Y_l,Y_{l+1},\mathrm{\dots },Y_i$ be the tiers of the other side in each iteration. Let $C_r={\sum }_{l\le j\le i}e(Y_j)$. First, we prove that $C_r\ge \theta$.

Let $X^{j-1}$ be tier $X$ before the $j$th iteration of Algorithm 2 for $j\in [l,i+1]$. Also, let $\psi$ be the relative position of $a_r$ in tier $X$ before any iteration. During iteration $j\in [l,i]$, since $|e(Y_j)|\le \delta$, 12 shows that (1) every vertex in $X^j$ with index at most $S(X)+\delta -e(X^{j-1})$ is in $A_j$; (2) $e(X^j)=e(X^{j-1})-e(Y_j)$. For $X^{l-1}$, the first case is that $e(X^{l-1})=|X^{l-1}|$ and $S(X)-e(X^{l-1})+1\le \psi$ when there is no iteration on $X$ before or when $|Y_{l-1}|>\delta$, and the second case is that $\psi >S(X)+\delta -e(X^{l-2})\ge S(X)+e(Y_{l-1})-e(X^{l-2})\ge S(X)-e(X^{l-1})$ when $|Y_{l-1}|\le \delta$. In both cases, we have $\psi \ge S(X)-e(X^{l-1})+1$. Since $a_r$ is removed in iteration $i$, we have $S(X)-(e(X^i)+\theta )+1\ge \psi$, thus $C_r={\sum }_{l\le j\le i}e(Y_j)=e(X^{l-1})-e(X^i)\ge \theta .$