Proof. We prove interim stability by adapting the classic Gale-Shapley argument, interpreting preferences as interim preferences. Suppose, toward a contradiction, that \((a_i,p_j)\) is a blocking pair. Since \(a_i\) interim-prefers \(p_j\) to her final match, she must have proposed to \(p_j\) at some iteration. At some iteration, \(p_j\) rejected \(a_i\) (with or without an interview) in favor of an applicant it interim preferred to \(a_i\). Moreover, every subsequent tentative match of \(p_j\), including its final match, is to an applicant that \(p_j\) interim prefers to its previous tentative match, and hence, by transitivity, is interim preferred to \(a_i\). Because a position’s interim value of an applicant never changes after rejecting them or after becoming matched to them, the preference comparisons made between \(p_j\)’s tentative matches and \(a_i\) remain valid throughout the process up to the final match. Thus, \((a_i,p_j)\) cannot be a blocking pair, a contradiction. ◻

Proof. Since \(p_{j^*}\) and its match \(\mu(p_{j^*})\) interim like each other, it holds that \(\mu(p_{j^*})\succ_{p_{j^*}}^{Z^t}a_{i^*}\), and according to the algorithm, position \(p_{j^*}\) rejects applicant \(a_{i^*}\) without an interview. ◻

Proof. Since \(p_j\) agreed to interview in iteration \(t\), we must have that \(a_i\succ^{t-1}_{p_j}\mu(p_j)\), which implies \(a_i\succ^{t}_{p_j}\mu(p_j)\) (since \(p_j\) interim likes \(a_i\)). Therefore, \(p_j\) will agree to be matched to \(a_i\) in iteration \(t+1\) if it receives a proposal. If a position \(p_j\) and an applicant \(a_i\) interview in iteration \(t\), then it must hold that \(a_i\) weakly prefers \(p_j\) over any other position that had not yet rejected \(a_i\). Moreover, if \(a_i\) interim likes \(p_j\) then \(v_{i,j}^{Z^{t}}> V_{i,j}= v_{i,j}^{Z^{t-1}}\), so \(a_i\) still prefers \(p_j\) in iteration \(t+1\). Since 1 selects the same applicant until she is matched, in iteration \(t+1\) applicant \(a_i\) proposes to \(p_j\). Since \(p_j\) accepts, they are tentatively matched. ◻

Proof. From 1, this claim holds as long as \(p_j\) and \(a_i\) remain matched. Assume that in some iteration \(t\), position \(p_j\) receives a proposal from an applicant \(a_{i^*}\) whom it prefers over \(a_i\), i.e. \(a_{i^*}\succ_{p_{j}}^{Z^t}a_i\). Since \(u_{j,i}^{Z^{t}}>U_{j,i} = U\), it must hold that \(u_{j,i^*}^{Z^{t}}> U\). Assume, towards contradiction, that in a later iteration \(t'>t\) some applicant \(a_{i'}\) such that \((a_{i'},p_j)\notin Z^{t'}\) is chosen by the algorithm, and \(a_{i'}\) and \(p_j\) meet for an interview. For this to happen, it must hold that \(U=U_{j,i'}=u^{Z^{t'}}_{j,i'}>u^{Z^{t'}}_{j,i^*}=u^{Z^{t}}_{j,i^*}>U\) which is a contradiction. ◻

Proof. Let \(X_j\) be a random variable counting the number of interviews performed by position \(p_j\). Clearly, the expected number of interviews in 1 is \(\sum_{j=1}^m \mathbb{E}[X_j].\) By [lem:position-stops-interview-after4343], each position continues interviewing applicants until it finds one such that they interim like each other. (A position may stop interviewing earlier, but once this condition is met, it stops permanently.) Since each interview is a Bernoulli trial with success probability at least \(\left(\frac{1}{2}\right) ^ 2 = \frac{1}{4}\) (since other outcomes may also be considered successful), the expected number of trials until success is at most \(4\). Therefore, \(\sum_{j=1}^m \mathbb{E}[X_j] \leq 4m.\) ◻

Proof. According to 1 if a position \(p_j\) and an applicant \(a_i\) have met for an interview in iteration \(t\), then it must hold that \(a_i\) weakly prefers \(p_j\) over any other position \(p_{j'}\) that had not yet rejected \(a_i\), so for any such \(j'\neq j\) it holds that \[\label{eq:prefer-j} v_{i,j}^{Z^{t-1}}\ge v_{i,j'}^{Z^{t-1}}.\tag{1}\] Assume that \(a_i\) interim likes \(p_j\). From the definition of interim like, it follows that \(v_{i,j}^{Z^{t}}>V_{i,j}=v_{i,j}^{Z^{t-1}}\). Then, using 1 , we have that for every other position \(p_{j'}\) that had not yet rejected \(a_i\): \(v_{i,j}^{Z^{t}}>V_{i,j}=v_{i,j}^{Z^{t-1}}\ge v_{i,j'}^{Z^{t-1}}=v_{i,j'}^{Z^{t}}\). Hence, \(p_j\) will be the position picked by the algorithm at line 4 as \(p_{j^*}\in \mathcal{P}^*\) in iteration \(t+1\). If \(p_j\) is unmatched (\(\mu(p_j)=p_j\)), then \(p_j\) will agree to be matched to \(a_i\), as any match is better than being unmatched (any realization is non-negative). ◻

Proof. Once a position becomes tentatively matched with an applicant they interim like each other, it stops conducting further interviews ([lem:position-stops-interview-after4343]). Consequently, any proposal that \(p_{j^*}\) may receive can only come from an applicant whom \(p_{j^*}\) interviewed before this tentative match was formed. By 4, if an applicant interim likes a position, it proposes to that position in the immediate next iteration. Therefore, if \(p_{j^*}\) interviewed \(a_{i^*}\) before forming its current tentative match, and \(a_{i^*}\) proposes to \(p_{j^*}\) only now, then \(a_{i^*}\) did not propose immediately after that interview, which implies that \(a_{i^*}\) does not interim like \(p_{j^*}\). ◻

Proof. According to the algorithm, if an applicant is selected by the algorithm and she has to meet for an interview with a position, she will first interview with an unmatched position. Since \(k\)-eventual-happiness holds, each applicant that the algorithm chooses, if she meets for an interview with up to \(k\) unmatched positions, she will eventually meet a position in some iteration which she interim likes. By 4, after such a meeting occurs, the applicant and the position will be tentatively matched. Since there are always \(k\) unmatched positions before iteration \(t_0\), any applicant selected by the algorithm that has to meet for an interview with a position will initially interview only with unmatched positions. As proposals occur only after interviews, she will never propose to a matched position. ◻

Proof. From 6 and 4. ◻

Proof. Suppose toward contradiction that at some iteration before \(t_0\), an unmatched applicant \(a_{i^*}\) proposes to a position she does not interim like. This implies that \(a_{i^*}\) has already been rejected by every position that \(a_{i^*}\) did not interview with. However, an unmatched position never rejects an applicant without an interview. Since there are at least \(k\) unmatched positions available before \(t_0\), applicant \(a_{i^*}\) must have interviewed with at least \(k\) positions. Given the \(k\)-eventual-happiness for applicants assumption, \(a_{i^*}\) must have found at least one position she interim likes among those \(k\) interviews. By 4, \(a_{i^*}\) would have been matched to such a position. For \(a_{i^*}\) to be currently proposing to a position she does not interim like, she must have been subsequently unmatched from that position. This directly contradicts 1, which establishes that before \(t_0\), once an applicant is matched to a position they interim like, they remain matched. ◻

Proof. According to the algorithm, the same applicant is chosen in each iteration until she is tentatively matched. By 1, no matched applicant becomes unmatched before iteration \(t_0\). Therefore, by iteration \(t_0\), all applicants \(a_1,...,a_{m-(k-1)}\) have been matched and the remaining applicants \(a_{m-k+2},...,a_n\) have not yet been selected by the algorithm. ◻

Proof. According to the algorithm, if an applicant interviews in some iteration, it must have been interviewed by a position that is unmatched at that iteration. This is because if the interview is with an unmatched position, this is trivially true. Otherwise, if she interviews with a matched position, she must have been previously interviewed by all unmatched positions in earlier rounds. This follows from the tie-breaking rule of 1: in the bilaterally ex-ante setting, the algorithm resolves ties between non-interviewed positions by prioritizing interviews with unmatched positions. Furthermore, since a matched position remains matched until the end of the algorithm, every interview conducted after \(t_0\) involves an applicant who has interviewed at some point with a position that was unmatched at iteration \(t_0\). For the transition point \(t_0\), consider the \(k-1\) positions that are unmatched at that iteration. Consider the interviews conducted by these positions. Assume in contradiction that \(r> k \cdot (k-1)\). By the pigeonhole principle, it implies that there exists at least one position out of the \(k-1\) positions that has conducted more than \(k\) interviews. However, since the \(k\)-eventual-mutual-happiness condition holds, any position that has interviewed at least \(k\) applicants must have interviewed an applicant such that they interim like each other. By [lem:position-stops-interview-after4343], once such an interview occurs the position stops interviewing. This contradicts the assumption that there is a position that conducts more than \(k\) interviews, completing the proof. ◻

Proof. We prove the lemma using induction on \(t\).
Induction base (\(t=t_0\)): By definition, iteration \(t_0\) is an iteration in which an interview occurs. Consequently, both claims hold trivially as there is no proposal made in iteration \(t=t_0\).

Induction step: Fix any iteration \(t\geq t_0\) for which \(Q(t)\leq k\cdot(k-1)\). Assume the following statements hold for every iteration \(t'<t\):

1. Any unmatched applicant chosen by the algorithm in iteration \(t'\) does not propose to a position she does not interim like.

2. If a proposal occurs in iteration \(t'\), then the number of positions (matched and unmatched) that do not interim like their current match is at least \(k^3-Q(t')\) (which is at least \(k\)).

We note that since \(Q(t)\leq k\cdot(k-1)\), for any \(t'<t\) it holds that \(Q(t')\leq k\cdot(k-1)\), as \(Q\) is non-decreasing.

Assuming that the induction hypothesis holds for every iteration \(t'<t\), we now prove that it holds for iteration \(t\). If no proposal occurs in iteration \(t\), both claims are trivially true. Thus, assume a proposal occurs at \(t\), so in that case \(Q(t)=Q(t-1)\). Let \(a_{i^*}\) be the applicant selected by the algorithm in iteration \(t\). Denote by \(\tilde{t}\) the most recent iteration after \(t_0\) but prior to \(t\), in which a proposal occurred (or \(t_0\) if no such iteration exists).

We observe that in the case that \(\tilde{t}=t_0\), as the realization is not a “\(k\)-bad realization,” the number of positions (matched and unmatched) that do not interim like their current match in \(t_0\) is at least \(k^3\), which is at least \(k^3-Q(t_0)\) as \(Q(t_0)\geq 0\). If \(\tilde{t}>t_0\), then this number is at least \(k^3-Q(\tilde{t})\) by the induction hypothesis. So for every \(\tilde{t}\) (whether it is \(t_0\), or the most recent iteration after \(t_0\) but prior to \(t\) in which a proposal occurred), this number is at least \(k^3-Q(\tilde{t})\).

Between \(\tilde{t}\) and \(t\), at most one interview could have resulted in the agents interim liking each other. That is because, by 2, such an outcome immediately triggers a proposal in the subsequent iteration. Since \(t\) is the first proposal after \(\tilde{t}\), no more than one such outcome can occur in this interval. Moreover, if \(a_{i^*}\) proposes to a position that does not interim like \(a_{i^*}\), then clearly \(Q(t)=Q(\tilde{t})\). We first observe that \(a_{i^*}\) was never previously matched to a position where they interim like each other. Once such a match is formed, the applicant can only become unmatched if another applicant who does not interim like that position proposes to it (5). However, no such proposals could have ever occurred. This is true after time \(t_0\) by the inductive assumption. Additionally, it holds up to time \(t_0\) by 7. Consequently, one of two cases must hold for \(a_{i^*}\):

• In iteration \(t-1\), applicant \(a_{i^*}\) has interviewed with a position, and they interim like each other. In this case, \(Q(t) = Q(t-1) = Q(\tilde{t}) + 1\). By 2, and noting that the match of any position never changes without a proposal, the number of positions that do not interim like their current match is at least \(k^3 - Q(\tilde{t}) - 1 = k^3 - Q(t)\). Thus, the second statement holds for iteration \(t\). The first statement trivially holds for iteration \(t\), because \(a_{i^*}\) is proposing to the position she just interviewed and liked.

• In iteration \(t-1\), applicant \(a_{i^*}\) did not interview with a position such that they interim like each other. In this case, we claim that \(a_{i^*}\) has never interviewed with a position such that they interim like each other. This holds because, as claimed above, \(a_{i^*}\) was never matched with such a position in any previous iteration. Any such interview would have triggered an immediate tentative match of that kind in the following iteration (2). Therefore, the absence of such a match necessarily means that if \(a_{i^*}\) had not interviewed with such a position prior to the current iteration, she could not have encountered one. Since the \(k\)-eventual-mutual-happiness condition holds, \(a_{i^*}\) must have participated in fewer than \(k\) interviews up to this point. As shown above, there are at least \(k^3 - Q(\tilde{t}) \ge k\) positions that do not interim like their current match. Since \(a_{i^*}\) has conducted fewer than \(k\) interviews, there must exist a position \(p_j\) such that

  • Position \(p_j\) does not interim like their currently matched applicant, position \(p_j\) has not interviewed \(a_{i^*}\), and therefore has not rejected \(a_{i^*}\). Therefore it willing to interview \(a_{i^*}\).

  • Therefore, \(a_{i^*}\) prefers position \(p_j\) to all the positions that she has interviewed with and does not interim like.

  This ensures that if applicant \(a_{i^*}\) proposes at iteration \(t\), she must interim like that position, satisfying the first statement. Finally, if the position \(a_{i^*}\) proposes to does not interim like \(a_{i^*}\), the count of positions that do not interim like their current tentative match remains unchanged (position only improve their tentative match), which is by the inductive hypothesis still \(k^3 - Q(t)\), since \(Q(t) = Q(\tilde{t})\) in this case.

 ◻

Proof. By 5, such an event implies that the applicant proposing to \(p_j\) does not interim like \(p_j\). Yet, 9 ensures no such proposal occurs while \(Q(t) \le k\cdot(k-1)\). ◻

Proof. Assume toward contradiction that some applicant proposes (and thus must be unmatched) at some \(t \ge t_0\), yet her only interviews occurred before \(t_0\). If \(t = t_0\), then by 2, there is no proposal. Thus, for any \(t > t_0\), if all her interviews occurred before \(t_0\), the interview with the position to which she now proposes did not occur in the previous iteration. By 4, this implies that the applicant does not interim like the position she is proposing to now, which contradicts 9. ◻

Proof. By 2 if an applicant \(a_i\) and a position \(p_j\) meet for an interview at iteration \(t\in [T]\) and interim like each other, they become tentatively matched at iteration \(t+1\). By 1, any such pair that interviewed before \(t_0\), will stay matched till \(t_0\). We are left to show that no pair that interim like each other will be broken after iteration \(t_0\). Let \(Q(t)\) be the number of interviews conducted from \(t_0\) (including) through \(t\) (including) in which the agents interim like each other. Assume, towards contradiction, that there exists an applicant \(a_i\) and a position \(p_j\) who interim like each other after an interview and become tentatively matched (including before \(t_0\)), but their match is later broken. For any \(t\) where \(Q(t) \le k\cdot(k-1)\), this contradicts 3. If at \(T\), it holds that \(Q(T)\le k\cdot(k-1)\), the claim holds for every \(t\in[T]\). To complete the proof we prove that it indeed holds that \(Q(T)\le k\cdot(k-1)\).

Denote the last iteration in which \(Q(t)=k\cdot(k-1)\) as \(t^*\). We claim that at the conclusion of \(t^*\), no unmatched applicants remain, implying \(T = t^*\). We observe that by 4, no unmatched applicant proposes between \(t_0\) and \(t^*\) without an interview occurring in those iterations (implying that an applicant is unmatched between \(t_0\) and \(t^*\) if and only if it interviews between \(t_0\) and \(t^*\)). In that interval, every applicant matched to a position they interim like each other remains matched to it (3). Since \(Q(t^*) = k\cdot(k-1)\), exactly \(k\cdot(k-1)\) such interviews occurred in that interval each resulting in a match. Consequently, there are \(k\cdot(k-1)\) applicants who interviewed at some point after \(t_0\) and are now matched at \(t^*\). By 8, as the realization is not a “\(k\)-bad realization”, at most \(r = k\cdot(k-1)\) applicants interview after \(t_0\). Since we have shown that the \(k\cdot(k-1)\) applicants interviewed between \(t_0\) and \(t^*\) (inclusive) (who are exactly those who were unmatched sometime in that interval) and became matched by iteration \(t^*\) (and stayed matched), it follows that all applicants who were unmatched in the interval are matched in \(t^*\). Thus, no unmatched applicants remain at \(t^*\), which implies \(t^* = T\) and completes the proof.  ◻

Proof. Assume towards contradiction that there exists an applicant \(a_i\) who participated in more than \(k\) interviews. By the \(k\)-eventual-mutual-happiness condition, after \(k\) interviews, \(a_i\) must have interviewed with a position \(p_j\) such that \(a_i\) and \(p_j\) interim like each other.

Then, by 10, applicant \(a_i\) would have been tentatively matched to \(p_j\) and remained matched until the end of the algorithm. This contradicts the assumption that she continued to interview after her \(k\)-th interview. Hence, no applicant can have more than \(k\) interviews. ◻

Proof. By 8, there are at most \(r\) applicants who interview starting from \(t_0\) and by 11, each such applicant participates in at most \(k\) interviews. It follows that the total number of interviews after \(t_0\) is bounded by \(k \cdot r\). ◻

Proof. Assume that before the execution of the algorithm, a table of quantiles is sampled. Each entry in the table contains a pair \((w_{i,q},z_{i,q})\), where both values are drawn independently from the uniform distribution on \([0,1]\). The table has one row for each applicant and \(m\) columns. When an applicant \(a_i\) interviews with a position \(p_j\), instead of sampling the values from the distributions during runtime, we can use the pre-sampled quantiles and convert them into realized values via the inverse CDFs of their true distributions. Specifically, if it is the \(q\)-th interview for applicant \(a_i\), then the interview value for \(a_i\) is set to be \(F_{i,j}^{-1}(w_{i,q})\) and the interview value for \(p_j\) is set to be \(G_{j,i}^{-1}(z_{i,q})\).

Note that this method is statistically equivalent to sampling values from the distributions \(F_{i,j}\) and \(G_{j,i}\) during runtime. Therefore, the probability that an execution of 1 satisfies that every applicant who has participated in \(k\) interviews, the applicant and at least one of her interviewing positions interim like each other is equal to the probability that, for each applicant, among the first \(k\) columns there exists at least one quantile pair \((w_{i,q},z_{i,q})\) such that \(w_{i,q} > 0.5\) and \(z_{i,q} > 0.5\).

Let \(A_{i_l}\) for \(l\in[k]\) be the event that in the \(l\)-th interview of applicant \(a_i\), \(a_i\) and the position interim like each other. Let \(A_i=\bigcup_{l=1}^kA_{i_l}\) be the event that one of the \(k\) interviews that applicant \(a_i\) performs, ends with the position and the applicant interim like each other. Let \(B_1=\cap_{i=1}^nA_i\) be the event that every applicant \(a_i\) that participates in \(k\) interviews with \(k\) positions, there exists a position such that the applicant \(a_i\) and the position interim like each other. As the results of the interviews are sampled independently for each applicant and each interview: \[\begin{align} \Pr(B_1)&=\prod _{i=1}^n\Pr(A_i)=\prod_{i=1}^n\left(1-\Pi_{l=1}^k\Pr(\overline{A_{i_l}})\right) \\&=\left(1-\left(\frac{3}{4}\right)^k\right)^n=\left(1-\left(\frac{3}{4}\right)^{\lceil10 \log n\rceil}\right)^n\ge\left(1-\left(\frac{3}{4}\right)^{10 \log n}\right)^n \\&=\left(1-n^{10\log\left(\frac{3}{4}\right)}\right)^n\ge\left(1-n^{-4}\right)^n \end{align}\] ◻

Proof. The proof follows a symmetric argument to the one used in the proof of 12. As in 12, we assume that, prior to the execution of the algorithm, a table of quantiles is sampled and later converted into realized values during runtime. Each entry in the table consists of a pair of quantiles \((w'_{j,q},z'_{j,q})\), where both values are drawn independently from the uniform distribution on \([0,1]\). However, in this case, the table has one row for each position and \(n\) columns. Similarly, let \(B_2\) be the event that for every position \(p_j\) that conducts \(k\) interviews with \(k\) applicants, there exists at least one applicant such that the applicant and \(p_j\) interim like each other. Then \[\Pr(B_2)\ge\left(1-n^{-4}\right)^m >\left(1-n^{-4}\right)^{n+k-1}\] ◻

Proof. Let \(D\) be the event that \(k\)-eventual-happiness for applicants holds. Similarly to the proof of 12, assume that before the execution of the algorithm, a table of quantiles is sampled. Each entry in the table contains a value that is sampled independently of the uniform distribution on \([0,1]\). The table has one row for each applicant and \(m\) columns. When an applicant \(a_i\) interviews with a position \(p_j\), instead of sampling the value from distribution \(F_{i,j}\) during runtime, we can use the pre-sampled quantiles and convert them into realized values.

The probability that an execution of 1 satisfies \(k\)-eventual-happiness for applicants equals the probability that, for each applicant, among the first \(k\) columns there exists at least one quantile that is bigger than \(\frac{1}{2}\). Let \(E_{i_l}\) for \(l\in[k]\) be the event that the value sampled in the \(l\)-th column of applicant \(a_i\) is such that \(a_i\) interim likes the position. Let \(D_i=\bigcup_{l=1}^kE_{i_l}\) be the event that one of the \(k\) interviews that applicant \(a_i\) performs, ends with the applicant interim liking the position. Let \(D=\bigcap_{i=1}^nD_i\) be the event that for every applicant \(a_i\) that participates in \(k\) interviews with \(k\) positions, there exists at least one position that \(a_i\) interim likes. Since the interview values are sampled independently for each applicant and each interview, and for each \(i\), \(\Pr(D_i)=1-\Pi_{l=1}^k\Pr(\overline{E_{i_l}})=1-\left(\frac{1}{2}\right)^k\): \[\Pr(D)=\Pi_{i=1}^n\Pr(D_i)=\Pi_{i=1}^n\left(1-\Pi_{l=1}^k\Pr(\overline{D_{i_l}})\right) =\left(1-\left(\frac{1}{2}\right)^k\right)^n\] ◻

Proof. By 14, using Bernoulli’s inequality: \[1-p_D=1-\left(1-\frac{1}{2^k}\right)^n\le 1-\left(1-\frac{n}{2^k}\right)=\frac{n}{2^k}\] ◻

Proof. By 14 and Bernoulli’s inequality, \[p_D\ge\left(1-\frac{1}{2^k}\right)^n\ge\left(1-\frac{1}{n^{10}}\right)^n\ge1-\frac{1}{n^{9}}.\] ◻

Proof. By 14, and since \(k = \lceil10 \log n\rceil\): \[\begin{align} p_D&=\left(1-\left(\frac{1}{2}\right)^k\right)^n=\left(1-\left(\frac{1}{2}\right)^{ \lceil10 \log n\rceil}\right)^n \\&\ge\left(1-\left(\frac{1}{2}\right)^{10 \log n}\right)^n=\left(1-n^{10\log\left(\frac{1}{2}\right)}\right)^n=\left(1-n^{-10}\right)^n \end{align}\] ◻

Proof. To lower bound the probability \(\Pr(X> s)\), we apply Chernoff bound. For any \(0\le\lambda\le1\): \[\Pr\left(X\le (1-\lambda)M\right)\le\exp\left(\frac{-\lambda^2M}{2}\right)\] \[\Pr\left(X> (1-\lambda)M\right)\ge1-\exp\left(\frac{-\lambda^2M}{2}\right)\] Set \(\lambda = \frac{M - s}{M}\) and note that \(\lambda\in [0,1]\) as \(0\leq s\leq M\), and observe that \((1-\lambda)M = s\). We obtain \[\begin{align} \Pr\left(X> s\right)&\ge1-\exp\left(\frac{-(M-s)^2}{2M}\right) \ge1-\exp\left(\frac{-(M-s)^2}{2M}\right)\\&=1-\exp\left(\frac{-M^2+2sM-s^2}{2M}\right) \ge1-\exp\left(\frac{-M^2+2sM}{2M}\right)\\&=1-\exp\left(\frac{-M+2s}{2}\right) \end{align}\] ◻

Proof. W.L.O.G, assume that in \(t_0\) the tentatively matched positions are \(p_1,\dots,p_{m-k+1}\). Let \(X_{1},\dots,X_{m-k+1}\) be indicator random variables, where \(X_j=1\) if the tentatively matched position \(p_{j}\) does not interim like its matched applicant in iteration \(t_0\), and \(X_j=0\) otherwise. Let \(D\) be the event that \(k\)-eventual-happiness for applicants holds. Assuming that event \(D\) holds, these variables are independent and identically distributed, each being a Bernoulli random variable with success probability \(\frac{1}{2}\). That is, since up to iteration \(t_0\) each position is tentatively matched to the first applicant that interim likes it (by 1, regardless of the position’s value for that applicant). Let \(X=\sum_{j=1}^{m-k+1} X_j\) be a random variable that counts the number of tentatively matched positions that do not interim like their matched applicant in iteration \(t_0\). Then, \(M\triangleq\mathbb{E}\left[X \mid D\right]=\frac{m-k+1}{2}\). Let \(C\) be the event that an execution of 1 results in \(d\)-positions unhappy. We bound \(\Pr(C)\) using \(\{X\ge d\}\subset C\) and the formula of total probability: \[\label{equation4} \Pr(C)\ge\Pr(X\ge d)\ge\Pr(X\ge d \mid D)\Pr(D)\tag{2}\]

To lower bound the probability \(\Pr(C \mid D)\), we apply this to bound the probability that an execution of 1 results in \(d\)-positions unhappy, given that \(k\)-eventual-happiness for applicants holds, by using 16, and since \(M\ge d\) for large enough \(m\) \[\begin{align} \Pr\left(X\ge d \mid D\right)&\ge\Pr\left(X> d \mid D\right)\ge1-\exp\left(\frac{-M+2d}{2}\right) \\&=1-\exp\left(\frac{\frac{-m+k-1}{2}+2k^3}{2}\right)=1-\exp\left(\frac{-m+k-1+4k^3}{4}\right) \\&\ge1-\exp\left(\frac{-n+k+4k^3}{4}\right)\ge1-\exp\left(-\frac{n}{5}\right) \end{align}\] where the last inequality holds for any \(n\) that is large enough, as \(k = \lceil10 \log n\rceil\). We conclude: \[\label{equation5} \Pr\left(X\ge d \mid D\right)\ge1-\exp\left(-\frac{n}{5}\right)\tag{3}\] Note that by 15\[p_D\ge \left(1-n^{-10}\right)^n=\exp\left(n\cdot\ln\left(1-n^{-10}\right)\right)\] using the Taylor series of \(\ln(1-x)=-\sum_{i=1}^\infty\frac{x^i}{i}\ge -2x\) for sufficiently small positive \(x\ge0\): \[p_D \ge\exp\left(n\cdot\left(-\frac{2}{n^{10}}\right)\right)=\exp\left(-\frac{2}{n^{9}}\right)\] Combining with 2 and 3 : \[\begin{align} \Pr(C)&\ge \left( 1-\exp\left(-\frac{n}{5}\right)\right)\cdot\exp\left(-\frac{2}{n^{9}}\right) \\&\ge\exp\left(-\frac{2}{n^{9}}\right)-\exp\left(-\frac{n}{5}-\frac{2}{n^{9}}\right) \\& \geq \exp\left(-\frac{2}{n^{9}}\right)-\exp\left(-\frac{n}{5}\right) \end{align}\] Using the fact that \(e^x\ge1+x\) for every \(x\): \[\Pr(C)\ge 1-\frac{2}{n^{9}}-\exp\left(-\frac{n}{5}\right)\ge1-\frac{3}{n^{9}}\] Where the last inequality holds for any \(n\) that is large enough. ◻

Proof. For a realization to be considered a “\(k\)-bad realization”, at least one of the following events must hold:

1. \(k\)-eventual-mutual-happiness fails. By 12 and 13 and the union bound, it occurs with probability at most \(2-\left(1-\frac{1}{n^4}\right)^n-\left(1 - \frac{1}{n^4} \right)^{n+k-1}\).

2. \(d\)-positions unhappy fails, which, for large enough \(n\), occurs with probability at most \(\frac{3}{n^{9}}\), by 17.

Applying the union bound to these two events, the total probability that at least one fails is at most: \[p_{bad}\le2-\left(1-\frac{1}{n^4}\right)^n-\left(1 - \frac{1}{n^4} \right)^{n+k-1}+\frac{3}{n^{9}}\] Using Bernoulli’s inequality (as \(-\frac{1}{n^4}\ge -{1}\) for every \(n\in\mathbb{N}\)), we get the inequalities \(\left(1 - \frac{1}{n^4}\right)^n \ge 1 - \frac{n}{n^4}\) and \(\left(1 - \frac{1}{n^4}\right)^{n+k-1} \ge 1 - \frac{n+k-1}{n^4}\). For large enough \(n\), \[p_{bad}\le\frac{1}{n^3}+\frac{n+\lceil10\log n\rceil-1}{n^4} +\frac{3}{n^{9}}\le\frac{3}{n^3}\] ◻

Proof. For \(q\leq k\), let \(Z_{i,q}\) be the indicator that in the \(q\)-th interview of applicant \(a_i\) she interim likes the position with which she interviewed. Let \(D_i\) be the event that if applicant \(a_i\) has participated in \(k\) interviews, she interim likes at least one of her interviewing positions. Let \(D=\bigcap_{i=1}^n D_i\) be the event that \(k\)-eventual-happiness for applicants holds. We want to compute \(\Pr(Z_{i,q} \mid D)\). Since the value for interviews are independent across applicants, \(\Pr(Z_{i,q} \mid D)=\Pr(Z_{i,q} \mid D_i)\). By Bayes’ theorem, \[\Pr(Z_{i,q}=1\mid D_i)=\frac{\Pr(D_i\mid Z_{i,q}=1)\cdot \Pr(Z_{i,q}=1)}{Pr(D_i)}\] Note that for \(q\leq k\) it holds that \(\Pr(D_i \mid Z_{i,q} = 1) = 1\), since if one of the interviews is successful, \(D_i\) occurs. Moreover, by 14 we have that for every \(i\), \(\Pr(D_i)=1-\left(\frac{1}{2}\right)^k.\) So, \[\Pr(Z_{i,q}=1\mid D_i)=\frac{\Pr(Z_{i,q}=1)}{Pr(D_i)}=\frac{\frac{1}{2}}{\left(1-\left(\frac{1}{2}\right)^k\right)}\ge\frac{1}{2}\] for every \(k\in\mathbb{N}\). Since the \(k\)-eventual-happiness for applicants condition holds, by 1 and 2 all the interviews up to iteration \(t_0\) are conducted by applicants \(a_1,...,a_{m-k+1}\), if \(n+k-1>m\), or by all applicants otherwise. Each of these applicants interviews until they find a position they interim like, which takes at most \(k\) steps. Since each interview is a Bernoulli trial with success probability at least \(\frac{1}{2}\), the expected number of trials until success is at most \(2\). Therefore, the expected number of interviews across \(\min(m-k+1,n)\) applicants is at most \(2n\). ◻

Proof. For a given \(n\), let \(k=\lceil10\log n\rceil\). Let \(p_{bad}\) be the probability that a realization is a “\(k\)-bad realization” and let \(p_D\) be the probability that \(k\)-eventual-happiness for applicants holds. Let \(Y\) be a random variable counting the number of interviews conducted by 1. By the law of total expectation: \[\label{equation3} \begin{align} \mathbb{E}\left[Y\right]&=\mathbb{E}\left[Y \mid D\right]\Pr(D)+\mathbb{E}\left[Y \mid\overline{D}\right]\Pr(\overline{D}) {\le\mathbb{E}\left[Y \mid D\right]+\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D})} \end{align}\tag{4}\] Let \(Y_1\) count the number of interviews conducted up to iteration \(t_0\) and let \(Y_2\) count the number from iteration \(t_0\), so that, \(Y=Y_1+Y_2\). Then: \[\label{equation2} \mathbb{E}\left[Y \mid D\right]=\mathbb{E}\left[Y_1 \mid D\right]+\mathbb{E}\left[Y_2 \mid D\right]\tag{5}\]

Let \(B_1\) be the event that for every applicant that has participated in \(k\) interviews, the applicant and at least one of her interviewing positions interim like each other. Let \(B_2\) be the event that for every position that has participated in \(k\) interviews, the position and at least one of its interviewing applicants interim like each other. Finally, let \(C\) be the event that \(d\)-positions unhappy for \(d=k^3\) holds. Let event \(E_G=B_1\cap B_2\cap C\) be the event that a realization is not a “\(k\)-bad realization” (G stands for Good). Then \(\Pr(E_G)=1-p_{bad}\).

\[\begin{align} \mathbb{E}\left[Y_2 \mid D\right] &=\mathbb{E}\left[Y_2 \mid D\cap E_G\right]\cdot\Pr(E_G \mid D)+\mathbb{E}\left[Y_2 \mid D\cap \overline{E_G}\right]\cdot\Pr(\overline{E_G} \mid D) \\&=\frac{1}{\Pr(D)}\left(\mathbb{E}\left[Y_2 \mid D\cap E_G\right]\cdot\Pr(D\cap E_G)+\mathbb{E}\left[Y_2 \mid D\cap \overline{E_G}\right]\cdot\Pr(D\cap \overline{E_G})\right) \end{align}\] Since \(k\)-eventual-mutual-happiness implies \(k\)-eventual-happiness for applicants, we have that \(E_G\subseteq B_1 \subseteq D\) and therefore: \[\begin{align} \mathbb{E}\left[Y_2 \mid D\right] &=\frac{1}{\Pr(D)}\left(\mathbb{E}\left[Y_2 \mid E_G\right]\Pr(E_G)+\mathbb{E}\left[Y_2 \mid D\cap \overline{E_G}\right]\cdot (\Pr(D)-\Pr(E_G))\right) \\&\le\frac{1}{\Pr(D)}\left({\mathbb{E}\left[Y_2 \mid E_G\right]+\mathbb{E}\left[Y_2 \mid D\cap \overline{E_G}\right]\cdot (\Pr(D)-\Pr(E_G))}\right) \end{align}\]

By [lem:interviews-after-t0] and since the number of interviews is always at most \(n\cdot m\), we can bound the remaining terms: \[\label{equation1} \mathbb{E}\left[Y_2 \mid D\right] \le \frac{1}{p_D}\left(k^3+n\cdot m\cdot (p_D-1+p_{bad})\right)\tag{6}\]

As the number of interviews is always at most \(n\cdot m\) we have \(\mathbb{E}\left[Y \mid \overline{D}\right]\leq n\cdot m\). Thus, by [lem:number-of-interviews-before-t0], 5 , 6 and 4 : \[\begin{align} \mathbb{E}\left[Y\right] &\leq\mathbb{E}\left[Y_1 \mid D\right]+\mathbb{E}\left[Y_2 \mid D\right] +\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D}) \\&\leq 2n+\frac{1}{p_D}\left(k^3+n\cdot m\cdot (p_D-1+p_{bad})\right)+n\cdot m\cdot(1-p_D) \\&\leq 2n+\frac{1}{p_D}\left(k^3+n\cdot m\cdot (p_D-1+p_{bad})+n\cdot m\cdot(1-p_D)\right) \\&\leq 2n+\frac{1}{p_D}\left(k^3+n\cdot m\cdot p_{bad}\right) \end{align}\]

By [lem:prob-k-bad], for large enough \(n\) it holds that \(p_{bad}\le{\frac{3}{n^3}}\). Thus: \[\begin{align} \mathbb{E}\left[Y\right]&\leq 2n+\frac{1}{p_D}\left(k^3+ n\cdot m\cdot{\frac{3}{n^3}}\right) \le2n+\frac{1}{p_D}\left(k^3+ n^3\cdot{\frac{3}{n^3}}\right) \end{align}\] where the last inequality holds for any \(n\) that is large enough, as \(k = \lceil10 \log n\rceil\) and \(m\le n + k - 1\). By 15, \(p_D\ge\left(1 - \frac{1}{n^{10}} \right)^n\ge \frac{n^9-1}{n^{9}}\). Thus, \[\begin{align} \mathbb{E}\left[Y\right]&\le2n+2\cdot\left(k^3+3\right)=2n+O(\log^3n). \end{align}\] ◻

Proof. For a given \(n\) and \(m\ge n+\lceil10\log n\rceil-1\), let \(k=m-n+1\). Let \(D\) be the event that \(k\)-eventual-happiness for applicants holds and let \(p_D\) be the probability for that event. Let \(Y\) be a random variable counting the number of interviews conducted by 1. By the law of total expectation: \[\label{eq:condition-on-k-happ} \begin{align} \mathbb{E}\left[Y\right]&=\mathbb{E}\left[Y \mid D\right]\Pr(D)+\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D}) {\le\mathbb{E}\left[Y \mid D\right]+\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D})} \end{align}\tag{7}\]

As the number of interviews is always at most \(n\cdot m\) we have \(\mathbb{E}\left[Y \mid \overline{D}\right]\leq n\cdot m\). Since \(m\ge n+ k -1\) the algorithm stops before \(t_0\), by [lem:number-of-interviews-before-t0], 7 : \[\label{eq:after-numbers} \begin{align} \mathbb{E}\left[Y\right] &\leq\mathbb{E}\left[Y \mid D\right] +\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D}) \\&\leq 2n+m\cdot n \cdot \Pr(\overline{D}) \end{align}\tag{8}\]

By 5, it holds that \(\Pr(\overline{D})=1-p_D\le\frac{n}{2^k}\). Thus, by 8 : \[\begin{align} \mathbb{E}\left[Y\right]&\le2n+\frac{n^2\cdot m}{2^k} \end{align}\] when \(m\le n^7\), since \(k\ge\lceil10\log n\rceil\). Then, \[\begin{align} \mathbb{E}\left[Y\right]&\le2n+\frac{n^2\cdot m}{2^k}\le2n+\frac{n^2\cdot m}{2^{\lceil10\log n\rceil}} \\&\le2n+\frac{n^2\cdot m}{2^{10\log n}}=2n+\frac{n^2\cdot m}{n^{10}}\\& \le2n+\frac{n^9}{n^{10}} =2n+\frac{1}{n} =2 n+O(\log^3n) \end{align}\] Otherwise, when \(m>n^7\), then \(k> m -\sqrt[7]{m}+1\ge \sqrt{m}\): \[\begin{align} \mathbb{E}\left[Y\right]&\le2n+\frac{n^2\cdot m}{2^k}\le2n+\frac{m^3}{2^{ \sqrt{m}}} =2 n+O(\log^3n) \end{align}\] ◻

Proof. We prove this by induction on the applicant index \(i \ge 1\). Recall that by 1, an applicant is selected by the algorithm until she is matched, and she interviews unmatched positions in increasing order of their indices (tie-breaking towards smaller indices).

For the base case \(i=1\), applicant \(a_1\) interviews positions in strictly increasing order starting from \(p_1\). Under the \(k\)-eventual happiness assumption and when \(m\ge n +k - 1\), she stops interviewing once she finds a position she interim likes, which occurs within her first \(k\) interviews. Therefore, the maximum index of a position she interviews is \(k\), meaning she will not interview any position \(p_j\) with \(j \ge k+1\).

Assume the claim holds for all applicants \(a_{i'}\) where \(i' < i\). This inductive hypothesis implies that all \(i-1\) previously matched applicants found their matches at positions with indices strictly less than \(k+i-1\). When applicant \(a_i\) begins interviewing, she considers the remaining unmatched positions in increasing order of index. Because the preceding \(i-1\) applicants occupy \(i-1\) positions, the first \(k\) unmatched positions are guaranteed to fall within \([1,k+i-1]\). Under the \(k\)-eventual happiness assumption and when \(m\ge n+k-1\), \(a_i\) will find a match within her first \(k\) available positions. Thus, she will not interview any position beyond index \(k + i - 1\).

Since the final applicant is \(a_n\), no applicant will ever interview a position with an index greater than \(k + n - 1\). Therefore, under the \(k\)-eventual happiness assumption, every position \(p_j\) such that \(j \ge n + k\) never interviews. ◻

Proof. Assume that \(n + \lceil10\log n\rceil - 1> m\), and let \(k=\lceil10\log n\rceil\) and assume that the realization that is not \(k\)-bad. In 1, by [lem:position-stops-interview-after4343], a position stops interviewing once it meets an applicant such that they interim like each other. Under the assumption the realization is not \(k\)-bad, this occurs after at most \(k\) interviews. Moreover, when the realization is not \(k\)-bad, 11 applies. Consequently, every applicant will participate in at most \(k\) interviews. Therefore, when the realization is not \(k\)-bad, which holds a probability of at least \(1-\frac{3}{n^3}\) for large enough \(n\) (by [lem:prob-k-bad]), every agent conducts at most \(k\) interviews, which is \(O(\log n)\).

Now, consider the case that \(m\ge n + \lceil10\log n\rceil - 1\). Assume that \(k\)-eventual happiness for applicants holds for \(k=\lceil10\log n\rceil\), and denote this event by \(D\). When \(m\ge n +k - 1\), by 1, an applicant stops interviewing after the first position she interim likes (which can take at most \(k\) interviews). Therefore, under event \(D\)-which occurs with a probability of at least \(1-\frac{1}{n^9} \ge 1-\frac{1}{n^3}\) by 6-every applicant conducts at most \(k = O(\log n)\) interviews.

By 20, no position \(p_j\) with index \(j \ge n + k\) is ever interviewed. Therefore, we only need to analyze the interview counts for the first \(n + k - 1\) positions. By [lem:position-stops-interview-after4343], a position stops interviewing once it meets an applicant such that they interim like each other. Let \(E_P\) be the event that every position stops interviewing after at most \(k\) interviews. Conditioned on \(D\), we established that only the first \(n+k-1\) positions may be interviewed. Therefore, by 13, we have \[\Pr(E_P \mid D) \ge \left(1-n^{-4}\right)^{n+k-1}\ge 1 - \frac{n+k-1}{n^4}\] From 6, we know that \(\Pr(D) \ge 1-\frac{1}{n^9}\). By the law of total probability \[\Pr( E_P) \ge \Pr(E_P \mid D)\Pr(D) \ge \left( 1 - \frac{n+k-1}{n^4}\right) \cdot \left(1-\frac{1}{n^9}\right)\ge 1-\frac{3}{n^3}\] for large enough \(n\). Therefore, with probability \(1 - O(n^{-3})\), every position conducts at most \(k = O(\log n)\) interviews. ◻

Proof. If the algorithm reaches Phase 3 of 2 (i.e., the fallback stage in line 13), then all values have been realized, and 5 execute the standard DA algorithm over fully realized random preferences, which is known to produce a stable matching. Otherwise, if the algorithm proceeds only through Phase 1 and Phase 2 (i.e., does not reach the fallback stage in line 13), the proof is exactly as in [lemma:serial-stable]. ◻

Proof. We prove all three statements by induction on the iteration \(t\) (i.e., a single execution of the while-loop of the hybrid 2).

Base case (\(t=1\)).

1. In iteration \(t=1\), under Subroutine 3 when the instance is in the bilateral ex-ante equivalent setting, each applicant \(a_i\) has \(\mathcal{P}_i^{*} = \mathcal{P}\). Since \(m\ge n\), the algorithm assigns each applicant an interview with some unmatched position.

2. All positions are initially unmatched, so no unmatched applicant in \(\mathcal{A}'\) can propose to a matched position.

3. Let \(p_j\) be the position that applicant \(a_i\) interviews in iteration \(t=1\). If \(a_i\) interim likes \(p_j\), then by definition after the interview \[v_{i,j}^{Z^{1}} > V_{i,j} = V = V_{i,j'} = v_{i,j'}^{Z^{1}} \qquad\text{for every } j' \neq j,\] Thus \(p_j\) is \(a_i\)’s top interviewed position, and she will propose to \(p_j\) in DA. For any other applicant \(a_{i'} \ne a_i\), since \(p_j \notin \succ^{trunc}_{a_{i'}}\), the only proposal that \(p_j\) receives is from \(a_i\). Because \(p_j\) is unmatched, it accepts the proposal. Hence every applicant who interim likes the first position she interviewed with becomes tentatively matched to it.

Induction step. Assume that for every iteration \(t'<t\):

1. Every unmatched applicant in \(\mathcal{A}'\) in iteration \(t'\) interviews with an unmatched position in iteration \(t'\).

2. No unmatched applicant in \(\mathcal{A}'\) proposes to a matched position.

3. Any applicant who interim liked the position she interviewed in iteration \(t'\) became tentatively matched to that position in \(t'\) and remained matched until iteration \(t-1\).

We prove the statements for iteration \(t\).

• Since \(m \ge n\), at the beginning of iteration \(t\) there are at least \(|\mathcal{A}''| + (k-1)\) unmatched positions. By the induction hypothesis, the applicants in \(\mathcal{A}''\) in iteration \(t\) are precisely those who were in \(\mathcal{A}'\) at \(t=1\) and have not interim liked any position so far. Since \(k\)-eventual-happiness for applicants holds, each applicant meets a position that she interim likes within her first \(k\) interviews. Thus, at iteration \(t\), every applicant in \(\mathcal{A}''\) has interviewed fewer than \(k\) positions.

  Therefore each applicant in \(\mathcal{A}''\) still has at least \(|\mathcal{A}''|\) unmatched positions that she has not yet interviewed. Therefore, for any subset \(S \subseteq \mathcal{A}''\), the set of neighbors has size at least \(|\mathcal{A}''|\), and Hall’s condition holds for the bipartite graph whose one side is \(\mathcal{A}''\) and the other side consists of unmatched positions. Hence Subroutine 3 assigns interviews to all applicants in \(\mathcal{A}'\) using only unmatched positions.

• Fix some \(a_i \in \mathcal{A}''\) and let \(p_j\) be the unique unmatched position with which she interviews in iteration \(t\).

  • If \(a_i\) interim likes \(p_j\), then \[v_{i,j}^{Z^{t}} > V_{i,j} = V = V_{i,j'}= v_{i,j'}^{Z^{t}} \quad\text{for every } j' \neq j \text{ with } p_{j'} \in \mathcal{P}_i^*,\] so \(a_i\) will want to propose to \(p_j\).

  • Otherwise, \(v_{i,j}^{Z^{t}} < V_{i,j} = V = V_{i,j'} = v_{i,j'}^{Z^{t}}\) for all \(j' \neq j\) with \(p_{j'} \in \mathcal{P}_i^*\). Since she has interviewed fewer than \(k\) positions so far, there exists a position \(p_{j^*} \in \mathcal{P}_i^{*}\) that she prefers and that has not rejected her, so she will not propose to \(p_j\).

  Therefore, an applicant \(a_i \in \mathcal{A}''\) proposes in iteration \(t\) only if she interim likes the position she interviews in that iteration, and in that case she proposes to that position and to no other. Since each applicant interviews exactly one position, each position receives at most one proposal in this iteration. Because all these positions are unmatched, every proposal is accepted.

  In particular:

  • no unmatched applicant proposes to a matched position. Consequently, no existing tentative match is broken, and every applicant who was matched prior to iteration \(t\) remains matched afterward. and

  • every applicant who interim liked the position she interviewed in iteration \(t\), became tentatively matched to it in that iteration.

This completes the induction and the proof. ◻

Proof. By [lemma:parallel-matched-stays-matched], an applicant stops interviewing at Phase 1 once she is interviewed with a position that she interim likes. Until then, in each iteration, every unmatched applicant conducts an interview. Since \(k\)-eventual-happiness for applicants holds, there can be at most \(k\) interview rounds. ◻

Proof. For any realization that is not \(k\)-bad, the property of \(k\)-eventual-happiness for applicants holds by definition. Therefore, by [lemma:parallel-log-iterations], Phase 1 terminates after at most \(k\) iterations. ◻

Proof. By [lemma:parallel-matched-stays-matched], as long as an applicant in \(\mathcal{A}'\) remains unmatched, she receives an interview in every iteration. Consequently, Subroutine 3 never outputs a set of interviews that is smaller than \(\mathcal{A}''\), and thus 2 continues executing the DA phase (Subroutine 4) until all applicants in \(\mathcal{A}'\) become matched. ◻

Proof. For any realization that is not \(k\)-bad, the property of \(k\)-eventual-happiness for applicants holds by definition. Therefore, by 8, 2 does not reach Phase 3. ◻

Proof. In Phase 1, the claim holds trivially, since applicants only interview with unmatched positions. ◻

Proof. In Phase 1, since not being a \(k\)-bad realization implies that \(k\)-eventual-happiness for applicants holds, the claim follows from [lemma:parallel-matched-stays-matched]. ◻

Proof. In Phase 1, since not being a \(k\)-bad realization implies that \(k\)-eventual-happiness for applicants holds, the claim follows from [lemma:parallel-matched-stays-matched]. ◻

Proof. In Phase 1, since not being a \(k\)-bad realization implies that \(k\)-eventual-happiness for applicants holds, the claim follows trivially from [lemma:parallel-matched-stays-matched], since applicants don’t propose to matched positions. ◻

Proof. In Phase 1, the claim holds from [lemma:parallel-matched-stays-matched], and since only unmatched positions interview. ◻

Proof. In Phase 1, the claim holds from [lemma:parallel-matched-stays-matched]. ◻

Proof. Since the realization is not \(k\)-bad, by 9, 2 never reaches Phase 3. By 10 12 13 15 11 14, all general lemmas established for the sequential 1 apply in this setting as well. Furthermore, by 2, every claim stated in the lemmas that applies before the transition point in the sequential algorithm also holds during Phase 1 of 2. Since Phase 2 of 2 is exactly the execution of the sequential 1 after \(t_0\), all lemmas that apply after the transition point in the sequential algorithm apply during Phase 2 as well.

In 2, each interview in Phase 2 is interpreted as a single parallel interview round. Therefore, by [lem:interviews-after-t0], the number of interview rounds in Phase 2 is at most \(k^2\cdot(k-1)\). ◻

Proof. For a given \(n\), let \(k=\lceil 10\log n\rceil\). Let \(E_G\) denote the event that a realization is not a \(k\)-bad realization, and let \(\overline{E_G}\) denote the complementary event. Let \(Y\) be the random variable counting the number of interview rounds conducted by 2. By the law of total expectation, \[\label{eq:1} \begin{align} \mathbb{E}[Y] &= \mathbb{E}[Y \mid E_G]\Pr(E_G) + \mathbb{E}[Y \mid \overline{E_G}]\Pr(\overline{E_G}) \\ &\le \mathbb{E}[Y \mid E_G] + \mathbb{E}[Y \mid \overline{E_G}]\Pr(\overline{E_G}). \end{align}\tag{9}\]

Let \(Y_1\) be the number of interview rounds before the transition point \(t_0\) (Phase 1), and let \(Y_2\) be the number of rounds after \(t_0\) (Phase 2). Since when a realization is not a \(k\)-bad realization, \(Y = Y_1 + Y_2\) (9), we have from 22 and 7: \[\label{eq:2} \mathbb{E}[Y \mid E_G] = \mathbb{E}[Y_1 \mid E_G] + \mathbb{E}[Y_2 \mid E_G] \le k + k^3.\tag{10}\]

Since the number of interview rounds is always at most \(n\cdot m\), it follows that \(\mathbb{E}[Y \mid \overline{E_G}] \le n \cdot m\).

Moreover, by [lem:prob-k-bad], \(\Pr(\overline{E_G}) \le \frac{3}{n^3}\). Using 9 10 , we obtain: \[\begin{align} \mathbb{E}[Y] &\le (k + k^3) + n\cdot m \cdot \frac{3}{n^3}= k + k^3 + \frac{3m}{n^2} \\ &< k + k^3 + \frac{3(n + \lceil 10 \log n \rceil -1)}{n^2} \\ &= O(\log^3 n). \end{align}\] ◻

Proof. By [lemma:parallel-matched-stays-matched], 2 terminates once every applicant has interviewed a position they interim like. Let \(D\) denote the event that the \(k\)-eventual happiness condition holds for all applicants. Let \(T_q\) denote the number of applicants interviewing in round \(q\). For Phase 1 to continue to round \(q\), there must be applicants who have not yet found a position they interim like. We initialize \(T_1 = n\) (since \(m \ge n+k-1\), all applicants participate initially). For \(q\leq k\), let \(X_{i,q}\) be the indicator variable that applicant \(a_i\) does not interim like the position interviewed in round \(q\). From the proof of [lem:number-of-interviews-before-t0], we know that \(\Pr(Z_{i,q} \mid D) \ge \frac{1}{2}\), where \(Z_{i,q} = 1 - X_{i,q}\) is the indicator that the applicant does interim like the position. Consequently, \(\Pr(X_{i,q} \mid D) < \frac{1}{2}\). Note that if some applicant \(i\) interviewed in iteration \(q\), then \(X_{i,q-1} =1.\) Therefore, the expected number of applicants interviewing in round \(q\) is: \[\mathbb{E}[T_q\mid D] = \sum_{i } \Pr(X_{i,q-1} \mid D) < \frac{1}{2} \mathbb{E}[T_{q-1}\mid D]\] Since \(T_1 = n\), \(\mathbb{E}[T_q\mid D] < \frac{n}{2^{q-1}}\) or every \(q>1\). Let \(R\) be the random variable representing the total number of rounds in Phase 1. The phase continues to round \(q\) only if there is at least one applicant interviewing in that round. Thus, the event \(R \ge q\) implies \(T_q \ge 1\). By the monotonicity of probability and Markov’s inequality, we have:\[\Pr(R \ge q \mid D) \le \Pr(T_q \ge 1 \mid D) \le \frac{\mathbb{E}[T_q \mid D]}{1} = \mathbb{E}[T_q \mid D]\]Using the tail sum formula for expectation, we split the summation at the index \(1+\lfloor \log n \rfloor\). For the first part of the sum, we bound the probability by \(1\): \[\begin{align} \mathbb{E}[R \mid D] &= \sum_{q=1}^\infty \Pr(R \ge q \mid D) \\ &= \sum_{q=1}^{1+\lfloor\log n\rfloor} \Pr(R \ge q \mid D) + \sum_{q=2+\lfloor\log n\rfloor}^\infty \Pr(R \ge q \mid D) \\ &\le \sum_{q=1}^{1+\lfloor\log n\rfloor} 1 + \sum_{q=2+\lfloor\log n\rfloor}^\infty \mathbb{E}[T_q \mid D] \end{align}\]

Substituting the bound \(\mathbb{E}[T_q \mid D] < \frac{n}{2^{q-1}}\), the first term sums to \(1+\lfloor\log n\rfloor\), and the second term becomes a geometric series:\[\begin{align} \mathbb{E}[R \mid D] &\le (1+\lfloor\log n\rfloor) + \sum_{q=2+\lfloor\log n\rfloor}^\infty \frac{n}{2^{q-1}} = (1+\lfloor\log n\rfloor) + n \cdot \sum_{j=1+\lfloor\log n\rfloor}^\infty \frac{1}{2^j} \\&\le 1+\log n + \frac{n}{2^{\lfloor\log n\rfloor}} \le 1+\log n +2 = 3+ \log n \end{align}\] ◻

Proof. For a given \(n\) and \(m\ge n+\lceil10\log n\rceil-1\), let \(k=m-n+1\). Let \(D\) be the probability that \(k\)-eventual-happiness for applicants holds and let \(p_D\) be the probability for that event. Let \(Y\) be a random variable counting the number of interview rounds conducted by 2. By the law of total expectation: \[\label{eq:condition-on-k-happ-rounds} \begin{align} \mathbb{E}\left[Y\right]&=\mathbb{E}\left[Y \mid D\right]\Pr(D)+\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D}) {\le\mathbb{E}\left[Y \mid D\right]+\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D})} \end{align}\tag{11}\] Since \(m\ge n+ k -1\), the algorithm stops before reaching Phase 2. Consequently, by 24, we have \(\mathbb{E}\left[Y \mid D\right]\le 3+\log n\). Furthermore, if \(k\)-eventual-happiness does not hold, the number of interview rounds is at most \(n\cdot m\). Therefore, by 11 : \[\label{eq:after-numbers-rounds} \begin{align} \mathbb{E}\left[Y\right] &\leq\mathbb{E}\left[Y \mid D\right] +\mathbb{E}\left[Y \mid \overline{D}\right]\Pr(\overline{D}) \\&\leq 3+\log n+n\cdot m \cdot \Pr(\overline{D}) \end{align}\tag{12}\] By 5, it holds that \(\Pr(\overline{D})=1-p_D\le\frac{n}{2^k}\). Thus, by 12 , \[\label{eq:before-two-cases} \mathbb{E}\left[Y\right]\le 3+\log n+\frac{n\cdot n\cdot m}{2^k}.\tag{13}\] When \(m\le n^7\), since \(k\ge\lceil10\log n\rceil\), \[\begin{align} \mathbb{E}\left[Y\right]&\le 3+\log n+\frac{ n^9}{2^{\lceil 10\log n\rceil}}\le 3+\log n+\frac{n^9}{2^{ 10\log n}} \\ &= 3+\log n+\frac{n^9}{n^{10}}= 3+\log n+\frac{1}{n} \\ &\le 4+\log n \end{align}\] Else, since \(n\ge2\) and \(m>n^7\), it holds that \(m>2^7\) and that \(k=m-n+1> m-m^{\left(\frac{1}{7}\right)}\). Therefore, \(m^3\le 2^{m-m^{1/7}}\) and \(\frac{n^2\cdot m}{2^k}<{\frac{ m^3}{2^{m-m^{1/7}}}<1}\). In total, by 13 , \(\mathbb{E}\left[Y\right] \leq 4 + \log n\). ◻

Proof. The proof follows immediately from [lem:number-of-interviews-before-t0], as the sequential lemmas correspond to lemmas of Phase 1. ◻

Proof. The proof follows immediately from [lem:number-of-interviews-before-t0], as the sequential lemmas correspond to lemmas of Phase 1. ◻

Proof. The proof follows immediately from 19, as the sequential lemmas correspond to lemmas of Phase 1. ◻

Proof. When \(m=n\) the algorithm sets \(k=\lceil10\log n\rceil\). Assume that the realization is not \(k\)-bad. In 2, by 14, a position stops interviewing once it meets an applicant they interim like each other. Under the not \(k\)-bad assumption, this occurs after at most \(k\) interviews. Moreover, by 10 12 13 15 11 14 , when the realization is not \(k\)-bad, 11 applies for 2. Consequently, every applicant will participate in at most \(k\) interviews. Therefore, when the realization is not \(k\)-bad, which holds a probability of at least \(1-\frac{3}{n^3}\) for large enough \(n\) (by [lem:prob-k-bad]), every agent conducts at most \(k\) interviews, which is \(O(\log n)\). ◻

Proof. Let \(c=\min\{m,n\}\), and let \(\varepsilon=\frac{2}{c}>\frac{1}{c}\), and note that as \(\varepsilon\cdot c=2\), the algorithm performs no more than \((2-\varepsilon)\cdot c\) interviews. A sufficient condition for the matching to be non-interim stable is the existence of an applicant-position pair \((a_i, p_j)\) such that:

1. \(a_i\) and \(p_j\) have not interviewed each other;

2. \(a_i\) has interviewed only once and did not interim like the position she interviewed with; and

3. \(p_j\) has interviewed only once and did not interim like the applicant it interviewed.

If these conditions hold, both agents strictly interim prefer each other to their final match (that is, \(a_i \succ_{p_j}^Z \mu(p_j)\) and \(p_j \succ_{a_i}^Z \mu(a_i)\)). Consequently, \((a_i, p_j)\) forms a blocking pair. Let \(B\) denote the event that the matching is not interim stable, and let \(C\) be the event that the sufficient condition described above occurs. Thus, \(C \subseteq B\). We assume that every matched agent participates in at least one interview (otherwise the matching is trivially interim unstable). We focus our analysis on the set of interviews performed by the \(c\) matched agents on each side. Let \(J\) be the random variable counting the number of applicants who, after their first interview, do not interim like the interviewed position. We observe that \(\mathbb{E}[J] \geq \frac{c}{2}\). Consider the event where \(J > (1-\varepsilon)\cdot c\). We claim that if this occurs, at least one of these applicants must have interviewed only once. To see this, suppose for the sake of contradiction that all the \(J\) applicants interviewed at least twice, while the remaining \(c-J\) applicants interviewed at least once. The total number of interviews would be at least \(2J + (c-J) = c + J > c + (1-\varepsilon)\cdot c = (2-\varepsilon)\cdot c .\) This contradicts the lemma’s assumption that the total number of interviews is at most \((2-\varepsilon)\cdot c\). Therefore, if \(J > (1-\varepsilon)\cdot c\), there exists at least one applicant \(a_i\) that interviewed only once and who does not interim like the position she interviewed with.

By symmetry, let \(L\) be the random variable counting the number of positions who, after their first interview, do not interim like the interviewed applicant. Following the same logic, if \(L > (1-\varepsilon)\cdot c+1\), there exists at least two positions that interviewed only once and who do not interim like the applicant they interviewed. Thus, at least one of them, denoted as \(p_j\), did not interview with \(a_i\), and together they form a blocking pair. If both \(\{J > (1-\varepsilon)\cdot c\}\) and \(\{L > (1-\varepsilon)\cdot c + 1\}\) occur, we can guarantee a blocking pair. Notice that \(J > (1-\varepsilon)\cdot c + 1\) implies \(J > (1-\varepsilon)\cdot c\). Moreover, since \(\varepsilon>\frac{1}{c}\), it holds that \(c>(1-\varepsilon)\cdot c+1\), and \(J=c\) implies \(J > (1-\varepsilon)\cdot c + 1\) and \(L=c\) implies \(L > (1-\varepsilon)\cdot c + 1\). Thus

\[\{L =c\} \cap \{J =c\} \subseteq C \subseteq B\]

Thus, the probability that the matching fails (is not interim stable) is at least the probability of the event \(\{L =c\} \cap \{J =c\}\). The events \(\{L =c\}\) and \(\{J =c\}\) are independent, since every matched agent necessarily had a first interview, and the result of that first interview is independent of the result of other agents’ first interviews (as depending on any past history, every agent interim like the interviewed agent with probability of \(\frac{1}{2}\)). and thus: \[\begin{align} \Pr(B) &\geq \Pr(C) \\&\geq {\Pr\left(\{L =c\} \cap \{J =c\}\right)}\\&\ge\frac{1}{2^c}\cdot \frac{1}{2^c}=\frac{1}{2^{2c}}>0. \end{align}\] ◻

Proof. Let \(\mu^{\mathcal{A}}\) denote the output of the applicant-proposing DA. A matching is defined as interim stable if (1) there are no blocking pairs with respect to the final interim utility, and (2) every matched pair has met for an interview. The first condition is satisfied since the DA algorithm guarantees stability with respect to the input preferences. We prove the second condition: for every \(a_i\), the pair \((a_i, \mu^{\mathcal{A}}(a_i))\) has interviewed. First, observe that since \(\mu\) is interim stable, it is stable with respect to the final interim utilities. Consequently, because \(\mu^{\mathcal{A}}\) is the applicant-optimal stable matching, every applicant \(a_i\) weakly prefers \(\mu^{\mathcal{A}}(a_i)\) to \(\mu(a_i)\). Now, suppose, towards a contradiction, that there exists an applicant \(a_i\) such that the pair \((a_i,\mu^{\mathcal{A}}(a_i))\) did not interview. By assumption, \(a_i\) strictly interim-prefers her match in \(\mu\) to any position she did not interview, implying \(\mu(a_i) \succ_{a_i}^Z \mu^{\mathcal{A}}(a_i)\), which contradicts the optimality of \(\mu^{\mathcal{A}}(a_i)\). Therefore, \(\mu^{\mathcal{A}}\) must consist only of interviewed pairs and is interim stable. Moreover, by transitivity, every applicant strictly prefers \(\mu^{\mathcal{A}}(a_i)\) to any position she did not interview. Since the applicant-proposing DA proceeds in decreasing order of preference and terminates at \(\mu^{\mathcal{A}}\), no applicant ever reaches the point of proposing to an uninterviewed position. Therefore, it suffices to execute the algorithm using preference lists restricted only to interviewed positions. ◻

Proof. By the definition of interim liking when applicants view positions as ex-ante equivalent, every applicant \(a_i\) interim strictly prefers \(\mu(a_i)\) to any position she did not interview. The claim therefore follows directly from [prop:opt]. ◻

Proof. Assume that \(n + \lceil10\log n\rceil - 1> m\), and let \(k=\lceil10\log n\rceil\) and assume that the realization is not \(k\)-bad. First, in 1, by 1, before time \(t_0\) an applicant never proposes to a position she does not interim like. Moreover, when the realization is not \(k\)-bad, 9 applies. Consequently, after \(t_0\) no applicant proposes to a position she does not interim like.

We next consider 2. When the realization is not \(k\)-bad, 9 implies that the algorithm consists only of Phase 1 and Phase 2. By [lemma:parallel-matched-stays-matched], during Phase 1 no applicant is matched to a position she does not interim like. Since all the claims stated in the lemmas about the sequential algorithm also hold for the hybrid algorithm under a non-\(k\)-bad realization, the same conclusion applies to Phase 2 as well: no applicant is matched to a position she does not interim like.

Therefore, when the realization is not \(k\)-bad (which holds a probability of at least \(1-\frac{3}{n^3}\) for large enough \(n\) by [lem:prob-k-bad]) an applicant never proposes to, and hence is never matched with, a position she does not interim like.

Finally, consider the case \(m\ge n + \lceil10\log n\rceil - 1\). Assume that \(k\)-eventual happiness for applicants holds for \(k=m-n+1\ge\lceil10\log n\rceil\). By 6 this event occurs with a probability of at least \(1-\frac{1}{n^{9}}>1-\frac{3}{n^3}\). Conditioned on this event, neither algorithm proceeds beyond time \(t_0\) (In 1 it follows from 1, and in 2 since \(\mathcal{A}'=\mathcal{A}\), it follows from 8). By 1 [lemma:parallel-matched-stays-matched], it follows that no applicant is matched to a position she does not interim like in this case either.

Overall, with a probability of at least \(1-\frac{3}{n^3}\), both 1 2 terminate with a matching in which every applicant interim likes her assigned position. Together with [cor:opt-interviews], this completes the proof. ◻