Learning in Multi-Stage Decentralized Matching Markets
Year: 2021

Abstract:
Matching markets are often organized in a multi-stage and decentralized manner. Moreover, participants in real-world matching markets often have uncertain preferences. This article develops a framework for learning optimal strategies in such settings, based on a nonparametric statistical approach and variational analysis. We propose an efficient algorithm, built upon concepts of “lower uncertainty bound” and “calibrated decentralized matching,” for maximizing the participants’ expected payoff. We show that there exists a welfare-versus-fairness trade-off that is characterized by the uncertainty level of acceptance. Participants will strategically act in favor of a low uncertainty level to reduce competition and increase expected payoff. We prove that participants can be better off with multi-stage matching compared to single-stage matching. We demonstrate aspects of the theoretical predictions through simulations and an experiment using real data from college admissions.

heading: 1 Introduction
text: Two-sided matching markets have played an important role in microeconomics for several decades [34]. Matching markets are used to allocate indivisible “goods” to multiple decision-making agents based on mutual compatibility as assessed via sets of preferences. Such a market does not clear through prices. For example, a student applicant cannot simply demand the college she prefers but must also be chosen by the college. Matching markets are often organized in a decentralized way. Each agent makes their decision independently of others’ decisions, and each agent can have multiple stages of interactions with the other side of the market. College admissions with waiting lists and academic job markets are notable examples. We refer to such markets as multi-stage decentralized matching markets.
Uncertain preference is ubiquitous in multi-stage decentralized matching markets. For instance, colleges competing for students lack information on students’ preferences. An admitted student may receive offers from other colleges. She needs to accept one or reject all offers within a short period during each stage of early, regular, and waiting-list admissions [5]. This admission process provides little opportunity for colleges to learn students’ preferences, which are uncertain due to competition among colleges and variability in the relative popularity of colleges over time. Such uncertain preferences pose a challenge for colleges in their attempt to formulate an optimal admission strategy. Consequently, colleges may end up enrolling too many or too few students relative to their capacity or having enrolled students overly far from the attainable optimum in quality.
This paper addresses the following two research questions: (i) Given the uncertain preferences on one side of the market (e.g., students), how can agents (e.g., colleges) learn an optimal strategy that maximizes expected payoffs based on historical data? (ii) What are the fundamental implications of multi-stage decentralized matching on the welfare and fairness for both sides of the market? We study these two questions using nonparametric statistical methodology and variational analysis. We propose a new algorithm for maximizing agents’ expected payoffs that is based on learning
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
stage-wise optimal strategies and calibrating state parameters based on historical data. In particular, our algorithm balances the opportunity cost and the penalty for exceeding the quota for calibration. Based on the calibrated state, the algorithm efficiently learns an optimal strategy using statistical machine learning methods. The statistical model not only provides a foundation for the algorithm but it also provides an analytical framework for understanding the implications of the approach for welfare and fairness. We show that agents will favor arms with realistic and stable opportunities for matching instead of only targeting the top-ranked arms. Moreover, we show that agents are better off with multi-stage decentralized matching as compared to single-stage decentralized matching.
Adopting literature from the bandit literature, our model has a set of agents, each with limited capacity, and a set of arms. Each agent values two attributes of an arm: a “score" that is common to all agents and a “fit" that is agent-specific and independent across agents. Agents rank arms according to their scores and fits. An agent’s strategy consists of how many and which arms to pull at each stage. On the other hand, there is no restriction on the preferences of arms. The model allows uncertainty in the preferences, which is incorporated into the arms’ stage-wise acceptance probabilities. The acceptance probability depends on the unknown state of the world and the competition of agents at each stage. We consider a simple timeline for multi-stage markets. At each stage, agents simultaneously pull sets of arms. Each arm accepts at most one of the agents that pulled it. The arms have to make irreversible decisions at each stage without knowing which other agents might select them in later stages.
Our contributions There are two main contributions in this paper, which correspond to the two questions above. Our first contribution is to propose a new algorithm that maximizes the agent’s expected payoff in multi-stage decentralized matching markets. The algorithm sequentially learns the optimal strategy at each stage and is built upon notions of lower uncertainty bound (LUB) and calibrated decentralized matching (CDM). The key idea is to calibrate the state parameter in a data-driven approach and take the opportunity cost and penalty for exceeding the quota into account. The calibration can be performed under both average-case and worst-case metrics, depending on whether we are maximizing the averaged or minimal expected payoff with respect to the uncertain state. Given the calibrated state, the algorithm efficiently learns the optimal strategy using historical data via statistical machine learning methods.
The second contribution is providing an analytical framework for understanding the welfare and fairness implications. We show that agents favor arms with low uncertainty in levels of acceptance, suggesting that agents prefer arms with a realistic and stable chance for matching instead of only targeting the top-ranked arms. Such strategic behavior improves the agent’s expected payoff since otherwise, by the time that arms have rejected that agent, the next-best arms that the agent has in mind may already have accepted other agents. However, the strategic behavior leads to unfair outcomes for arms because some arms are not pulled by their favorite agents even though these agents pull arms ranked below them. We prove that agents are better off in multi-stage decentralized matching markets compared to single-stage decentralized matching markets.
Related work This paper is related to three strands of literature. The first line is on matching markets. Most theoretical work on matching markets traces back to [21] that formulated a model of two-sided matching without side payments, and [37] that formulated a model of two-sided matching with side payments. The model in [37] is also related to the maximum weighted bipartite matching and its to stochastic and online generalizations [27]. Our goal is to design algorithms for maximizing the agent’s welfare under the model of [21], given the uncertain preferences of arms. This is different from the goal of finding a matching with the largest size in maximum matching literature [37, 27]. The second strand of literature is on the decentralized interactions in matching markets [15–17, 30, 35] and search literature [28, 31]. Our paper contributes to this strand of literature via its analysis of multi-stage markets that allow uncertain preferences. We also study the economic implications for strategic behaviors in multi-stage decentralized markets. The third related body of literature is on algorithmic studies of college admissions. The celebrated work in [21] introduced the deferred acceptance algorithm implemented under central clearinghouses. Recent works have been focused on equilibrium admissions, students’ efforts, and students’ information acquisition costs in forming preferences; see, [7, 11–13, 18, 20, 22, 24]. In contrast, we emphasize students’ multidimensional abilities and multiple colleges competing for students. The students’ preferences are uncertain due to the competition among colleges and variability in the relative popularity of colleges over time. We develop a statistical model for learning the optimal strategies using historical data.

heading: 2 Problem Formulation
text: Multi-stage decentralized matching markets Let P = {P1, P2, . . . , Pm} be a set of m agents. Let A = {A1, A2, . . . , An} the a set of n arms. Here P and A are the sets of participants on the two sides of the matching market. Each agent Pi has a quota qi 1. We assume that q1+q2+· · ·+qm  n. There are total of K 1 stages of the matching process. At each stage, an agent who has not used up its quota can pull available arms in the market. When multiple agents select the same arm, only one agent can successfully pull the arm according to the arm’s preference. We denote [m] ⌘ {1, . . . ,m}, [n] ⌘ {1, . . . , n}, and [K] ⌘ {1, . . . ,K}. Decentralized matching markets require participants to make their decisions independently of others’ decisions [33, 35]. Notable examples of such markets include college admissions in the United States, Korea, and Japan, where P and A represent the sets of colleges and students, respectively [5, 6]. Our goal is to learn the agent’s optimal strategy for maximizing the expected payoff. A strategy consists of deciding how many and which arms to pull at each stage. Agent’s decision-making in decentralized markets faces incomplete information about other agents’ decisions and arms’ preferences.
Participants’ preferences The agents’ preferences are based on the arms’ latent utilities. Consider the following latent utility model:
Ui(Aj) = vj + eij , 8i 2 [m], j 2 [n], (1)
where vj 2 [0, 1] is arm Aj’s systematic score considered by all agents, and eij 2 [0, 1] is an agent-specific idiosyncratic fit considered only by agent Pi, i 2 [m]. A utility model with a similar separable structure has been widely used in the matching market literature [4, 13, 15].
The arms’ preferences have no restrictions and can involve uncertainty. From an agent’s perspective, arms accept offers with probabilities dependent on opponents’ strategies and arms’ preferences. Let the parameter si,k 2 [0, 1] be the state of the world [36] for agent Pi, such that the probability that an arm Aj accepts Pi at stage k is ⇡i,k(si,k, vj), 8i 2 [m], j 2 [n], k 2 [K]. Since agents compete for arms with a higher score, the acceptance probability ⇡i,k(si,k, vj) models the agents’ competition through the dependence on the score vj . Moreover, ⇡i,k(si,k, vj) incorporates the arm’s uncertain preference into the state si,k. It is known that there exists a valid probability mass function ⇡i,k(si,k, vj) [15]. We assume that ⇡i,k(si,k, vj) is strictly increasing and continuous in si,k. Thus, a larger value of the state si,k corresponds to the case that agent Pi is more popular. In practice, the true state is unknown a priori to Pi and needs to be estimated from data. For instance, the yield in college admissions is defined as the rate at which a college’s admitted students accept the offers. However, the yield is unknown a priori to the college in the current year [13]. Colleges can only estimate the distribution of the yield from historical data. In this paper, we study a nonparametric model of ⇡i,k(·, ·) by assuming it belongs to a reproducing kernel Hilbert space (RKHS) [3, 39]. Later, in Section 3.2, we propose an algorithm for calibrating si,k and efficiently estimating ⇡i,k(·, ·) using historical data. Given the latent utility Ui(Aj) and the acceptance probability ⇡i,k(si,k, vj), agent Pi’s expected utility of pulling arm Aj at stage k is (vj + eij)⇡i,k(si,k, vj).
Timeline of the matching First, Nature draws a state such that arms’ preferences are realized. Denote by s⇤i,k the true state for agent Pi at stage k. Next, arms display their interests to all agents. For example, students apply to colleges in a given period. Under the assumption that students incur negligible application costs, submitting applications to all colleges is the dominant strategy as students lack information on how colleges evaluate their academic ability or personal essays [6, 13]. Next, at each stage k 2 [K], agents simultaneously pull available arms that have not previously rejected them. Each arm either accepts one of the agents that pulled it (if any) or rejects all. An arm exits the market once it accepts an agent, and agents are allowed to exit the market at any time. The arms act simultaneously at each stage. They cannot “hold" offers for accepting or rejecting at a later stage. Hence, agents make “exploding" offers, and arms have to make irreversible decisions without knowing what other offers are coming in later stages. Finally, this multi-stage matching process ends when all agents have exited or when a pre-specified number of stages has been reached. If there remain arms in the market when the matching has terminated, these arms are unmatched.
Agent’s expected payoff An agent’s goal is to maximize the expected payoff, which consists of two parts: the expected utilities and the penalty for exceeding the quota. Let Ak be the set of arms that are available in the market at stage k 2 [K]. Suppose that agent Pi pulls arms from the set
Bi,k ✓ {Ak \ [lk 1Bi,l} at stage k, where A \ B denotes that set A minus set B. Let Ci,k ✓ Bi,k be the set of arms that accept Pi at stage k. Then Ci,k is unknown until stage k+1, where k  K 1, and Ci,K is unknown until the end of the matching process. Then Pi’s expected payoff at stage k 2 [K] is lower bounded by
Ui,k[Bi,k] ⌘ X
j2Bi,k
(vj + eij)⇡i,k(s ⇤ i,k, vj) i max{Ni,k(Bi,k) qi, 0}. (2)
Here Ni,k(Bi,k) ⌘ P
j2Bi,k ⇡i,k(s⇤i,k, vj) + card([lk 1Ci,l), and s ⇤ i,k is the true state for agent Pi at stage k. We assume that the marginal penalty i satisfies i > maxj2A{vj + eij}, which implies that the penalty is greater than arm’s latent utility. Since our model involves unknown strategies of the opponents and uncertain arms’ preferences, we consider the optimal expected payoff in (2) instead of the optimal realized payoff. Similar expected payoff have been studied in [13, 15].

heading: 3 Statistical Learning of the Optimal Strategy
text: We consider a variational formulation of the optimal strategy in Section 3.1 and propose a two-step algorithm using a statistical machine learning method in Section 3.2.

heading: 3.1 Variational formulation
text: The problem of finding the optimal set of arms, and the corresponding optimal value Ūi, can be described as follows:
Ūi = max Bi,k✓{Ak\[lk 1Bi,l},k2[K]
X
k2[K]
Ui,k[Bi,k], (3)
where the expected payoff Ui,k is defined in (2). Finding and checking an optimal solution to (3) is difficult. Suppose that an arm set [k2[K]B̄i,k is given and that it is claimed to be the optimal solution to (3). It is clear that the problem of verifying that [k2[K]B̄i,k is optimal is computationally intractable; because we need to individually check a significant fraction of the combinations of card([k2[K]Ak) arms to determine which combination might give a larger expected payoff than the given arm set [k2[K]B̄i,k. Since the number of combinations grows exponentially with the number of arms, the complexity of any systematic algorithm becomes impractically large. Moreover, the expected payoff Ui,k depends on the unknown true state s⇤i,k, which creates yet another layer of difficulty for finding and checking an optimal solution.
Variational problem We introduce the following notation: i,k(v) ⌘ 12 [maxsi,k ⇡i,k(si,k, v) minsi,k ⇡i,k(si,k, v)], which measures the uncertainty of the acceptance probability with respect to the unknown state. Using this notation, we show that a variational formulation gives a practical methodology for finding the optimal strategy. Theorem 1. There exist parameters ⌘i,k > 0, for k  K 1, and ⌘i,K = 0 such that with high probability, the minimizer of the following variational loss, 8k 2 [K],
L † i,k[Bi,k] = X
j2Bi,k
(vj + eij) [⌘i,k i,k(vj) ⇡i,k(s ⇤ i,k, vj)] + i max{Ni,k(Bi,k) qi, 0}, (4)
gives a maximizer of the total expected payoff PK
k=1 Ui,k[Bi,k]. Here the expected payoff Ui,k[Bi,k] is given in (2), and Bi,k ✓ {Ak \ [lk 1Bi,l} for any k 2 [K].
We make four remarks regarding this theorem. First, the parameter ⌘i,k 0 in (4) is induced by the hierarchical structure in the sense that the arms available at subsequent stages are worse than the current ones; see Appendix B.1. Hence, each agent prefers arms with a stable acceptance probability, and for which ⌘i,k controls the penalty on the uncertainty. Second, ⌘i,k serves as a regularization parameter in the optimization (4) for the uncertainty measure i,k. In practice, we may choose a large value of ⌘i,k if the agents’ competition is tense, as the arms available at subsequent stages are much worse than the current ones. Third, we note that the multi-stage decentralized matching problem is different from the multi-armed bandit problem [10, 25, 26]. A bandit problem is a sequential
allocation problem in which an environment repeatedly provides an agent with a fixed set of arms. Although similar in that it involves sequential decision making under limited information, the multistage matching market involves multiple agents competing for arms. An arm exits the market once it accepts an offer. The competition induces a hierarchical structure which makes the optimization in (4) different from the optimization in multi-armed bandits. Finally, there exists a fundamental difference between the multi-stage matching when K > 1 and the single-stage matching when K = 1. In particular, when K > 1, the optimization (4) has a regularization term ⌘i,k i,k(vj) > 0 on the uncertainty of the acceptance probability. In contrast, this term vanishes when K = 1 as ⌘i,K = 0. As a result, the optimal strategy in multi-stage matching in Section 3.2 and its economic consequences in Section 4 are distinct from those in single-stage matching [15].
Greedy strategy Although the variational problem in (4) requires only stage-wise optimization and can be solved sequentially for each k 2 [K], the finding and checking of an optimal solution is still computationally intractable. This is because we need to individually check a significant fraction of the combinations of card(Ak \ [lk 1Bi,l) arms at each stage k 2 [K] to determine the optimal solution for (4). The number of combinations grows exponentially with card(Ak \ [lk 1Bi,l) for k 2 [K].
We propose a greedy algorithm that gives an approximate solution to the optimization problem in (4). Suppose the true state is fixed at s⇤i,k = si,k. We refer to (vj + eij)[⇡i,k(si,k, vj) ⌘i,k i,k(vj)] as arm Aj’s variational expected utility. For each Aj 2 {Ak \ [lk 1Bi,l}, the greedy algorithm computes the variational expected utility per unit of acceptance probability, that is,
r(Aj) ⌘ (vj + eij)[⇡i,k(si,k, vj) ⌘i,k i,k(vj)]/⇡i,k(si,k, vj).
Then the algorithm ranks arms according to its associated value of r so that r(1) r(2) · · · r(card(Ak\[lk 1Bi,l)). Starting with the first arm corresponding to r(1) and continuing in order, the algorithm selects the arm if its variational expected utility is larger than the expected penalty of exceeding the quota. This algorithm terminates when it arrives at a cutoff value of r. Then only arms whose associated r value are better than or equal to the cutoff are selected for agent Pi to pull at stage k 2 [K]. We present the formalized cutoff r = r⇤ in Appendix B.2. Then using the greedy algorithm, agent Pi pulls arms from the following set,
bBi,k(si,k) = {j |Aj 2 {Ak \ [lk 1Bi,l} satisfying r(Aj) r⇤} . (5)
Theorem 2. Suppose the true state is fixed at s⇤i,k = si,k. The arm set bBi,k(si,k) in (5) is near-optimal as its loss satisfies
min Bi,k✓{Ak\[lk 1Bi,l}
L † i [Bi,k]  L † i [ bBi,k(si,k)]  min Bi,k✓{Ak\[lk 1Bi,l} L † i [Bi,k] + UE † ,
where the loss function L†i is defined in (4). The quantity UE † 0 and it equals 0 if there is a continuum of arms and ⇡i,k(·, v) is continuous in v.

heading: 3.2 A two-step learning algorithm
text: Since the true state and the acceptance probability are unknown a priori in practice, the greedy strategy in (5) is unknown a priori to the agent Pi. We propose a two-step algorithm to learning the greedy strategy by using historical data and statistical machine learning methods. The two-step algorithm is built upon the concepts of lower uncertainty bound (LUB) and calibrated decentralized matching (CDM) [15]. In the first step, we compute an estimated expected utility of each arm and its lower uncertainty bound. Many machine learning methods can be applied here for the modeling of historical data. In the second step, we calibrate the state parameter in a data-driven approach that takes the opportunity cost and penalty for exceeding the quota into account. Based on the calibrated state, an agent selects arms with the largest lower uncertainty bounds of the expected utility. The key idea is to select arms which have large expected utility or little uncertainty in the expected utility.
Step 1: Lower uncertainty bound Let At = {At1, At2, . . . , Atnt} be the arm set at t 2 [T ] ⌘ {1, . . . , T}. Let sti,k be the state of agent Pi at stage k and time t. The state s t i,k is unknown until the next stage or the next time point, and the state sti,k varies over time. For instance, the yield rate of a college may change over the years. For any arm Atj 2 At, there are an associated pair of the
score and fit values (vtj , etij) obtained from (1), where i 2 [m], j 2 [nt]. Let (vtj , etij) denote the attributes of arm Atj . Define the set Bti,k = {j | Pi pulls arm A t j at time t and step k, 1  j  nt}, where card(Bti,k) = n t i,k  n t. For any j 2 Bti,k, the outcome that Pi observes is whether an arm A t j accepted Pi, that is, ytij = 1{Atj accepts Pi}. We want to estimate ⇡i,k based on the historical data, D = {(sti,k, v t j , e t ij , y t ij) : i 2 [m]; j 2 [ K k=1B t i,k; t 2 [T ]}.
A wide range of machine learning methods, e.g., reproducing kernel methods, random forests, or neural networks, can be applied here to learn ⇡i,k (cf. [23]). For concreteness, we consider a penalized estimator in RKHS. Let the log odds ratio fi,k(si,k, v) = log{⇡i,k(si,k, v)/[1 ⇡i,k(si,k, v)]}, which is assumed to reside in an RKHS HKi,k with the kernel Ki,k. Then we solve for bfi,k 2 HKi,k that minimizes the objective function:
TX
t=1
1
nti,k
X
j2Bti,k
⇥ y
t ijfi,k(s t i,k, v t j) + log 1 + exp fi,k(s t i,k, v t j) ⇤
+ i,kkfi,kk 2 HKi,k ,
where i,k 0 is a tuning parameter. Consider the tensor product structure of HKi,k , where Ki,k((si, v), (s0i, v 0)) = Ksi,k(si, s 0 i)K v i,k(v, v 0) with some kernel functions Ksi,k and K v i,k [40]. It is known that bfi,k is minimax rate-optimal and satisfies E[( bfi,k fi,k)2]  cf [T (log T ) 1] 2r/(2r+1) for any i 2 [m] (cf. [15]). Here, cf > 0 is a constant independent of T , and r 1 denotes the order of smoothness. The value of learning from historical data is particularly significant when a new arm is introduced into the problem. Let AT+1 = {A1, . . . , An} be the new arm set at time T + 1, where Aj has attributes obtained from (1). Then the probability that Aj accepts Pi at stage k is estimated by b⇡i,k(si,k, vj) = {1 + exp[ bfi,k(si,k, vj)]} 1. The expected utility of Aj is b⇡i,k(si,k, vj)(vj + eij) for any j 2 [n]. Finally, we construct a lower uncertainty bound for ⇡i,k(si,k, vj) as,
b⇡Li,k(si,k, vj) =
8 ><
>:
b⇡i,k(si,k, vj) ⌘i,kb i,k(vj), if vj 2 [min{vtj | j 2 [Tt=1Bti},max{vtj | j 2 [Tt=1Bti}];
1, o.w., (6)
where b i,k(vj) = 12 [maxsi,k b⇡i,k(si,k, vj) minsi,k b⇡i,k(si,k, vj)]. The parameter ⌘i,k 0 is defined in (4). Note that (6) assigns probability one to arms with scores that agent Pi has never pulled. Hence it encourages the exploration of previously untried arms. A lower uncertainty bound for the expected utility is then given by b⇡Li,k(si,k, vj)(vj + eij) for any j 2 [n].
The prediction of match compatibility is also possible in another direction that an arm Aj can also learn how much an agent Pi may like itself by predicting the probability that Aj can be pulled by Pi. The arms would make the decisions based on the prediction that if they have a realistic potential of being pulled by a better agent. This feature also distinguishes the two-sided matching platform from a one-sided recommendation engine that only considers which arms an agent may like, but not which arms may also like the agent in return.
Step 2: Calibrated decentralized matching Since the true state s⇤i,k is unknown in practice, a natural question is how to calibrate the state parameter si,k in (5). Consider the average-case loss, Es⇤i,k{L † i,k[ bBi,k(si,k)]}, where the loss L†i,k is defined in (4). Define the marginal set as @ bBi,k(si,k) ⌘ lim s!0+{ bBi,k(si,k s) \ bBi,k(si,k)}. Hence @ bBi,k(si,k) represents the change of bBi,k(si,k) with a perturbation of si,k.
Theorem 3. The average-case loss Es⇤i,k{L † i,k[ bBi,k(si,k)]} is minimized if si,k 2 (0, 1) is chosen as the solution to
P(s⇤i,k 6= si,k) X
j2@ bBi,k(si,k)
(vj + eij)Es⇤i,k ⇥ ⇡i,k(s ⇤ i,k, vj) ⌘i,k i,k(vj) | s ⇤ i,k 6= si,k ⇤
= i[1 Fs⇤i,k(si,k)] X
j2@ bBi,k(si,k)
Es⇤i,k [⇡i,k(s ⇤ i,k, vj) | si,k < s ⇤ i,k  1], (7)
where Fs⇤i,k is the cumulative distribution function of s ⇤ i,k 2 [0, 1].
Algorithm 1 The two-step algorithm for multi-stage decentralized matching 1: Inputs: Historical data for an agent Pi: {(sti,k, vtj , etij , ytij) : j 2 Bti,k; t = 1, 2, . . . , T}; New
arm set AT+1 at time T + 1, where the arms have attributes {(vj , eij) : j 2 [n]}; Penalty i for exceeding the quota. Regularization parameter ⌘i,k 0.
2: for stage k = 1, 2, . . . ,K do 3: Construct the lower uncertainty bound b⇡Li,k(si,k, vj) by (6) 4: Estimate the distribution Fs⇤i,k(·) by the kernel density method [38] 5: Calibrate the state si,k according to Theorem 3 6: Determine the arm set bBLi,k(si,k) in (8) 7: Calculate the remaining quota: qi card([lk 1Ci,l) and the available arms 8: end for 9: Outputs: The arm set bBLi,k(si,k) for agent Pi at each stages.
The key idea of (7) is to balance the trade-off between opportunity cost and penalty for exceeding the quota. If (7) has more than one solution, then si,k is chosen as the largest one. If the distribution Fs⇤i,k
has discrete support, the objective in Theorem 3 needs to be changed as follows: choosing the minimal si,k 2 [0, 1] such that the left side of (7) is not less than the right side of (7), where the search of si,k starts from the maximum value in the support and decreases to the minimal value. Moreover, instead of the average-case loss in Theorem 3, we can also perform the calibration under the worst-case loss, which is discussed in Appendix B.3.
Summary of the two-step algorithm Using (6) and (7), we can obtain the cutoff estimate br⇤ and calibrated state si,k, which suggests agent Pi to pull arms from the following set at stage k:
bBLi,k(si,k) = {j |Aj 2 {AT+1k \ [lk 1Bi,l} satisfying r(Aj) br⇤ . (8)
Here AT+1k is the set of arms that are available at stage k of time T + 1. Due to the minimax optimality of bfi,k, we have the consistency result that bBLi,k(si,k) ! bBi,k(si,k) as T ! 1, where the set bBi,k(si,k) is defined in (5). We summarize the above two-step algorithm in Algorithm 1. We also remark that although the negligible application costs is assumed in Section 2, Algorithm 1 is applicable to non-negligible application costs, in which different agents (i.e., colleges) would have different sets of available arms (i.e., student applicants).

heading: 4 Strategic Behavior and Economic Implications
text: Agents in a multi-stage decentralized matching markets cannot observe other agents’ quotas or the choices of the arms that accept other agents. Each agent only observes the arms that are left in the market at each stage. Theorem 1 implies that agents prefer arms with stable acceptance probability. This preference lead to strategic behavior on the part of the agents as follows. Define the uncertainty level as the uncertainty measure i,k(v) in Section 3.1 relative to the acceptance probability ⇡i,k(si,k, v). That is,
uncertainty level ⌘ i,k(v)/⇡i,k(si,k, v). (9)
We show in Appendix B.2 that the cutoff r⇤ in (5) is strictly increasing in the uncertainty level for any v 2 [0, 1] and k  K 1, which implies that an agent favors arms with a low uncertainty level. Hence, an agent’s strategic behavior in this market is to strategically select arms with a low uncertainty level. We now study the implications of such strategic behavior on fairness and welfare.
No justified envy The fairness studied here is defined in terms of no justified envy [1, 8]. Specifically, an arm Aj has justified envy if, at a stage k 2 [K], Aj prefers an agent Pi0 to another agent Pi that pulls Aj , even though Pi0 pulls an arm Aj0 which ranks below Aj according to the true preference of Pi0 . We define a multi-stage matching procedure to be fair if there is no arm having justified envy at any stage. Proposition 1. The probability that an arm has justified envy is strictly increasing in the arm’s uncertainty level defined in (9).
The fairness issue has been noted in practical multi-stage matching markets. For example, candidates in job markets may “fall through the cracks"—an employer that values a candidate highly perceives that the candidate is unlikely to accept the job offer and hence declines to conduct an interview with the candidate; hence, candidates may have justified envy [14]. Besides our ex-ante definition of no justified envy, there are other choices of no justified envy, including ex-post definition, which could lead to a different set of technical results [19].
Fairness vs. welfare trade-off We note that by Theorem 1, an agent has increased expected payoff under ⌘i,k > 0 than under ⌘i,k = 0 for all stages k  K 1. Define the number of arms with justified envy to be the level of justified envy of the matching outcome. Then if the level of justified envy is zero, the matching outcome is fair for arms.
Proposition 2. The level of justified envy is strictly increasing in ⌘i,k 0.
This proposition implies a trade-off between welfare and fairness since both the level of justified envy and welfare increase when changing ⌘i,k = 0 to ⌘i,k > 0. We give an example of two-stage decentralized matching, that is, K = 2. Such two-stage matching is typical in college admissions, which may include regular admissions and waiting-list admissions. By Theorems 1 and 2, agents in the first stage would strategically pull arms with low uncertainty levels by taking ⌘i,1 > 0. In this way, agents would reduce head-on competition. Next, agents in the second stage would act according to their true preferences and pull available arms with top latent utilities by taking ⌘i,2 = 0. Theorem 1 shows that agents’ strategic behavior in the first stage increases the welfare compared to acting according to their true preferences, whereas in the second stage, agents acting according to their true preferences suffices. Proposition 2 shows that agents’ strategic behavior in the first stage results in increased welfare, but at the cost of arms’ fairness.
Comparison with single-stage matching markets Different from multi-stage matching markets, the optimal strategy in single-stage matching gives a fair outcome for arms [15]. However, we show that agents are better off in multi-stage markets compared to single-stage markets.
Proposition 3. Agents have improved welfare under multi-stage decentralized matching than under single-stage decentralized matching.
We provide an empirical example in Appendix A.4 to illustrate the gap between multi-stage welfare and single-stage welfare.
Comparison with centralized matching markets Many centralized matching markets are implemented by employing the celebrated deferred acceptance (DA) algorithm [21]; see examples in [1, 32]. In the arm-proposing version of DA (e.g., student-proposing in college admissions), agents and arms report their ordinal preferences to a clearinghouse, which simulates the following multi-stage procedure. Every arm shows its interest to the most preferred agent that has not yet rejected it at each stage. Every agent tentatively pulls the most preferred arms up to its quota limit and permanently rejects the remaining arms that have indicated their interest to the agent. Once the process terminates, each arm is assigned to the agent that has tentatively pulled it or otherwise remains unmatched. The multi-stage decentralized matching is different from DA in practice, mainly due to the acceptance is not tentative (i.e., non-deferrable) in decentralized matching. Moreover, there is usually a restriction on the number of stages in decentralized matching due to the time cost at each stage of multi-stage decentralized matching is not negligible. We show in a numerical example of Appendix A.3 that some agents are better off in decentralized markets than centralized markets. This finding gives a partial explanation of the prevalence of decentralized college admissions in many countries.

heading: 5 Numerical Studies
text: In this section we demonstrate aspects of the theoretical predictions through a simulation and a real data application in college admissions. We provide extensive numerical comparisons of Algorithm 1 with other methods in Appendix. We also give additional real data analysis in Appendix. The total computing hour is within one hour in personal laptop with Intel Core i5.
Simulated graduate school admissions Consider 50 graduate schools from three tiers of colleges: five top colleges {P1, . . . , P5}, ten good colleges {P6, . . . , P15}, and 35 other colleges {P16, . . . , P50}. Each has the same quota q = 5 and penalty = 2.5. The simulation generates students’ preferences with ten different states {s1, . . . , s10} ⇢ [0, 1]. For any state, students’ preferences for colleges from the same tier are random. However, students prefer top colleges to good colleges, and the other colleges are the least favorite. The random preferences depend on the state due to colleges’ uncertain reputation and popularity in the current year. We consider varying numbers of students {250, 260, 270, 280, 290, 300}. For each size of students, there are ten students having score vj chosen uniformly and i.i.d. from [0.9, 1] and 100 students having score vj i.i.d. uniformly chosen from [0.7, 0.9). The rest of the students have score vj randomly chosen from [0, 0.7). The fits eij for all college-student pairs are drawn uniformly and i.i.d. from [0, 1].
We compare the college’s expected payoff achieved by the proposed Algorithm 1 with the simple cutoff strategy, where the latter method has each college choosing the most preferred students up to the remaining quota at each stage. The training data are simulated from colleges’ random proposing by pulling a random number of arms according to the latent utilities. The training data consists of 20 times of random proposing under each of the arms’ preference structures with the two-stage admissions. This training data simulates the graduate school admissions over 20 years. The testing data draws a random state from {s1, . . . , s10} which gives the corresponding arms’ preferences. Then we apply Algorithm 1 with ⌘i,1 = 0.1, ⌘i,2 = 0 and i = 2.5. Figure 1 reports the averaged payoffs of three colleges P1, P6, and P16 over 500 data replications. Here colleges P1, P6, and P16 belong to the three different tiers, respectively. In Figure 1, all colleges except P1 use Algorithm 1 while P1 uses one of the two methods: Algorithm 1 and the simple cutoff strategy. It is seen that Algorithm 1 gives the largest average payoffs for all of P1, P6 and P16. In particular, Algorithm 1 performs significantly better for P6 and P16 compared to the simple cutoff strategy.
U.S. college admissions We study a public data on college admissions from the New York Times “The Choice" blog. In this dataset, 37 U.S. colleges reported their admission yields and waiting list offers for 2015–17 applicants without personally identifiable information. As we discussed in Section 2, a college’s yield is a proxy for the state si,k as it indicates the college’s popularity. The set of 37 colleges consists of liberal arts colleges, national universities, and other undergraduate programs.
We estimate the uncertainty level i,k(v)⇡ 1i,k (si,k, v) defined in (9) and study colleges’ strategic responses. While conclusive evidence on the individual students’ acceptance probability is difficult to obtain, we estimate the college-wise uncertainty on the yield: p Var(si,k)s 1i,k . Since the choice set for admitted students differs across years, the yield’s uncertainty underestimates the uncertainty facing a college. Figure 2 shows that colleges’ uncertainty levels are much smaller than one, which, together with Theorem 1, implies that students face limited unfairness. In particular, the yield uncertainty is robust to the size of admitted students; see the left plot of Figure 2. On the other hand, top-ranked national universities may have higher uncertainty levels; see the right plot of Figure 2, where the
outlier is the University of Chicago at the .19 uncertainty level. We verify the higher uncertainty level for top universities using the waiting list data. We perform Fisher’s exact test for the rank data on the difference of rates of accepted waiting list students to total enrolled students over 2015–16. This statistic reflects the uncertainty on both the regular admission yield and the wait-listed students’ quality. We reject the null hypothesis that the uncertainty of acceptance is the same for all national universities at the .05 significance level. The higher uncertainty for top-ranked national universities may arise due to the intense competition. Those universities are better off by employing strategic admission to reduce the enrollment uncertainty. This result implies that students are more likely to experience unfairness when applying for top national universities.

heading: 6 Conclusion
text: This paper develops a nonparametric statistical model to learn optimal strategies in multi-stage decentralized matching markets. The model provides insight into the interplay between learning and economic objectives in decentralized matching markets. In the model, arms have uncertain preferences that depend on the unknown state of the world and competition among the agents. We propose an algorithm, built upon the concepts of lower uncertainty bound and calibrated decentralized matching, for learning optimal strategies using historical data. We find that agents act strategically in favor of arms with low uncertainty levels of acceptance. The strategic targeting improves an agent’s welfare but leads to unfairness for arms. Our theory allows analytical comparisons between single-stage decentralized markets and centralized markets.
For future directions, it is of interest to study algorithmic strategies when agents’ preferences show complementarities or indifference. These settings have important applications, as firms may demand workers that complement one another in terms of their skills and roles, or some applicants are indistinguishable to a firm. We leave these questions for future work.
The problem of machine learning in economics has become increasingly important in many application domains. In this work, we aim to deepen the understanding of decentralized matching markets from a learning perspective and propose an efficient and scalable algorithm to solve optimal strategies. We do not foresee any negative impact to society from our work.
Acknowledgments and Disclosure of Funding
We would like to thank the area chair and four anonymous referees for constructive suggestions that improve the paper. We thank Robert M. Anderson and Joel Sobel for helpful discussions. This work was supported in part by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941.

Review summaries:
The paper studies learning in multi-stage decentralized markets. Motivated by applications such as college admissions and the academic job market, the paper studies the classic matching problem under the assumptions that agents do not know their preferences and matching decisions can take place in multiple stages. As in the classic matching problem, a constraint is that colleges and applicants have quotas (e.g., students cannot accept more than one offer).  The paper models this problem as a multi-armed bandit problem with K>1 stages and quota constraints. Colleges are the agents and students are the arms. The arms’ preferences have no restrictions and are modeled through a probability function. Each agent values both a common quality aspect (the “score”) and a “fit” which is agent-specific. In this model, the paper proposes an algorithm that is based on the notions of lower uncertainty bound and calibrated decentralized matching; this algorithm learns the optimal strategy at each stage. Further, the paper investigates the economic implications of the model. For example, they show that strategic behavior may lead to unfairness (measured in terms of no justified envy) and that agents are better off with multi-stage compared to single-stage matching. Finally, they include simulations using data from college admissions. 

The authors study a multi sided matching market under a statistical model, with the goal of finding the optimal strategies. The model uses agents and arms, but due to its applications the intuition is easier to capture assuming the agents are universities and the arms students. Specifically, there are $n$ agents and $m$ arms, which are pulled over $K$ rounds. Each agent has a quota $q_i \ge 1$ of arms they can use, and the sum of all quotas is at most $n$. The market is two-sided because the arms (students) have preferences over the agents (universities) (and these preferences can be fuzzy) and the agents (universities) have preferences over the arms (students): each arm $j$ has an intrinsic value $v_j$ and an extra value $e_{ij}$, specific to agent $i$.  At every step, each agent can pull any number of arms. However, each arm can only respond to at most one agent, or reject all of them. The arms don’t have such explicit preferences: their interaction with the agents is captures by the probability $\pi_{i,k}(s_{i,k}, v_j)$ that arm $i$ will accept agent $j$ at time $k$, where $s_{i,k}$ is the state at time $k$. This probability is generally not known but is inferred from data. Overall, agent $i$’s utility is the sum of $(v_j + e_{ij}) \cdot \pi_{i,k}(s_{i,k}, v_j) $ over every turn $k$ and all arms they tried using, minus a penalty if the quota $q_i$ is exceeded. Clearly, this induces a game between the agents, which have to decide how to use their quotas to select arms that are good enough, but not so good that they might be snatched by other agents.  The authors provide a variety of results:  1. Three algorithms (one of which is their main result) on the side of learning the optimal strategy from the perspective of agent $i$. 2. Fairness and Welfare trade-offs. 3. Experiments.   In particular, the first algorithm yields an optimal strategy for maximising the welfare of agent $i$ by minimising their *variational loss*, which is (roughly described) a modification of their utility with an added factor depending on $\max_{s_{i,k}} \pi_{i,k}(s_{i,k}, v_j)  - \min_{s_{i,k}} \pi_{i,k}(s_{i,k}, v_j)$ (the ‘variance’) and weighted by $\eta_{i, k}$, which reflects that subsequent rounds are typically less valuable than the first ones. Intuitively this makes sense: minimising the variance would maximise the way the quota is used. This strategy is NP-hard to solve for though, which leads to the development of a *greedy* approximation: rather than immediately solving for variance, the arms are chosen greedily based on their expected utility per unit of acceptance probability. The second algorithm (and arguably main result of the paper) uses historic data to estimate the $\pi_{i,k}(s_{i,k}, v_j)$’s. The actual algorithm has many details, but I hope is fairly represent an abstraction as follows: 1. Use an off the shelf estimator for the $\pi_{i,k}(s_{i,k}, v_j)$. 2. Modify them by subtracting a weighted variational term (as in the first algorithm), or set to 1 if the arm has not been used. 3. Balance exploration and exploitation of the arms used.  The fairness results revolve around *justified envy*: in a nutshell, an arm would have justified envy if it is pulled by agent $i’$, but agent $i$ (which the arm prefers) is trying a different arm on the same turn. This would reflect the real world situation where highly skilled individual might miss an offer because a potential employer might think they have a high chance of rejecting it. The authors show that higher uncertainly results in higher probability of an arm being envious. Moreover, the higher the $\eta_{i,k}$ terms are, the higher the number of envious arms. Finally, they compare with the single-stage matching markets (which do not produce envy in their optimal outcome) and show that multi-stage markets provide increased welfare, at the expense of fairness.  The authors also have experiments on synthetic data that support their learning procedure, comparing to a simpler strategy, where every agent selects their favourite arms within their remaining quota, at every step. As expected, both strategies perform well for popular agents, but have very different performance for less desirable ones. Again, this reflects that minimising variance (which is easier for popular agents: imagine a top university offering positions to students, knowing most would accept) is the key, which is further supported by extrapolating from real data sets of admissions and university rankings. 

The paper studies matching in decentralized markets. A collection of agents (schools) and a collection of arms (students) form the two sides of the market. The matching is done over stages where agents select a collection of arms, an arm would choose only one agent with some probability and once matched would exit the market. Further, the agents have quotas which they cannot exceed. An important point is that the market is decentralized and that the probabilities are not known in advance and hence they have to be estimated. The paper thus involves both a learning step and a maximization step. Some theoretical characterizations of the fairness and welfare are also obtained. 

This paper develops a nonparametric statistical framework to learn optimal strategies in multi-stage decentralized matching markets, where agents with limited capacity are matched with arms with uncertain preferences in several stages. They propose an algorithm relying on the concepts of lower uncertainty bound and calibrated decentralized matching to maximize agents’ expected payoff. The algorithm uses a data-driven approach to calibrate the arms’ uncertainty and penalize agents for exceeding capacity. They show several implications on welfare and fairness based on their model. First, they show that agents favor arms with low uncertainty in the levels of acceptance to maximize their welfare, leading to unfair outcomes for arms since they might not be picked by their favorite agents even though those rank below them are picked. Then, they show that agents do better in a multi-stage matching instead of a centralized one. They demonstrate the effectiveness of their algorithms through experiments on synthetic and college admissions data.