Learning in Multi-Stage Decentralized Matching Markets
Authors: Xiaowu Dai
Michael Jordan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-stage matching
Decentralized markets
Uncertain preference
Fairness
College admissions
Reproducing kernel Hilbert spaces

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.


Learning in Multi-Stage Decentralized Matching Markets
Xiaowu Dai UC Berkeley xwdai@berkelee edu
Michael I. Jordan UC Berkeley jordan0cs Jordan@cs. berkeley.k.
edu
Abstract
Matching markets are often organized multi-stage and decentralized manner. Moreover, participants in real-world matching markets often have uncertain prefer- ences. This article develops a framework for learning optimal strategies such settings, based on 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- ceffare-versus-fiee fairness trade-off that is charac- terized by the uncertainty level of acceptance. Participants will strategically act in favor of 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 experiment using real data from college admissions.
Introduction
Two-sided matching markets have played an important role in microeconomics for several decades [34]. Matching markets used allocate indivisible "goods" multiple decision-making agents based on mutual compatibility as assessed via sets of preferences. Such a market does not clear through prices. For example, 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 multe 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 reject all offers within short period during each stage of early, regular, and waiting-list admissions [5]. This admission process provides little opportunity for colleges 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 challenge for colleges their attempt 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 side of the market (e.g., students), how can agents (e.g., colleges) learn optimal strategy that maximizes expected payoff' 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 new algorithm for maximizing agents' expected payoffs that based on learning
35th Conference on Neural Information Processing Systems (NcurIPS 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 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 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 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 faimess 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 '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 stage decentralized matching markets.
Related work This paper is related to three strands of literature. The first line is 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 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 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 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 the relative popularity of colleges over time. We develop a statistical model for learning the optimal strategies using historical data.

---

2 Problem Formulation
Multi-stage decentralized matching markets Let P (Pi, Pm. be a set of m agents. A = A2,,,,..... ) the a set of arms. Here P and AA are the sets of participants on the two sides of the matching market. Each agent P. has quota gi 2 1. We assume that q +..... S n. There are total of K 2 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 [rx] = {I,...,,u ni,, and [K] = {I....,K] Decentralized matching markets
[m] = {I...., 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 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 '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:
U,(A,) 0 + esj. Vi E [m].j E [n],
where by E 10 is arm Aÿ's systematic score considered by all agents, and Gj E [0, is an agent-specific idiosyncratic fir considered only by agent P., i E [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 agent's perspective, arms accept offers with probabilities dependent on opponents' strategies and arms' preferences. Let the parameter $1,k E [0. 1] be the state of the world [36] for agent P., such that the probability that an arm A, accepts P. at stage l is (T,,( Uz), Vi E [m].j E k E [K]. Since agents compete for arms with higher score, the acceptance probability (T,e(St,k,, Uy)) models the agents' competition through the dependence on the score Uj. Moreover, T 15)) incorporates the arm's uncertain preference into the state ki,k- It is known that there exists valid probability mass function T 22)) [15]. We assume that T (s 12)) is strictly increasing and continuous in 8,,-- Thus, a larger value of the state Si,A corresponds the case that agent P. more popular. In practice, the true state is unknown a priori to P. and needs to be estimated from data. For instance, the yield in college admissions defined
the rate at which a college's '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 (-, :) by assuming it belongs to a reproducing kernel Hilbert space (RKHS) [3, 39]. Later, in Section 3.2, we propose an algorithm for calibrating &,,s and efficiently estimating (t.)) using historical data. Given the latent utility (A,) and the acceptance probability TiA (Si.k U2), agent P s expected utility of pulling arm A₁ at stage le is (vy + C1y ) (88.kk U2).
Timeline of the matching First, Nature draws a state such that arms' preferences are realized. Denote by &i the true state for agent P. 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 & E [K), agents simultancously 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 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 's expected payoff An agent's ss goal is to maximize the expected payoff, which consists of two parts: the expected utilities and the penalty for exceeding the quota. Let Ag be the set of arms that are available in the market at stage k e [K]. Suppose that agent P. pulls arms from the set
3

---

BiA S [AR B,, at stage k, where A \. B denotes that set A minus set B. Let C. S B be the set of arms that accept P, stage k. Then C is unknown until stage & + where & I K - and Ci.K is unknown until the end of the matching process. Then P/'s expected payoff at stage E [K] is lower bounded by
Σ eey) JEBIN
uy) (B. qi. 0}.
(2)
Fi,h (5 U2)) + card(Uige--C.i). and &h is the true state for agent P; at stage k. We assume that the marginal penalty "r satisfies %/ > maxje. (vi + eig J. which implies that the penalty is greater than arm's latent utility. Since 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].
Here (Br,))
3 Statistical Learning of the Optimal Strategy
We consider variational formulation of the optimal strategy in Section 3.1 and propose two-step algorithm using a statistical machine learning method in Section 3.2.
3.1 Variational formulation
The problem of finding the optimal set of arms, and the corresponding optimal value U7 can be described as follows:
U BLACIA Night B., AEIK]
Σ (B.. KE[K]
where the expected payoff Ug is defined in (2). Finding and checking an optimal solution to (3) is difficult. Suppose that an arm set [ is given and that it is claimed to be the optimal
solution to (3). It is clear that the problem of verifying that U B,, is optimal is computationally intractable; because we need to individually check a significant fraction of the combinations of (ard(Uke[x]_An) arms to determine which combination might give a larger expected payoff than the given arm set URe K B. 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 depends on the unknown true state " which creates yet another layer of difficulty for finding and checking an optimal solution.
2 maxx.,, Ki,A (Si,k, v) min1 Ti,a (si,k v)], which measures the uncertainty of the acceptance probability with respect to the unknown state. Using this notation, we show that variational formulation gives a practical methodology for finding the optimal strategy.
Variational problem We introduce the following notation: (v) =
Theorem 1. There exist parameters 1j, O, for l. S. K 1, and n,, O such that with high probability, the minimizer of the following variational loss, Vk E [K].
[l, = Σ (u, + eiy) [T. TT 1z)1 + max x qs 0}: (4)
jEB
gives maximizer of the total expected payoff Ek=ı Ue Here the expected payoff U4 (B.,) is given in (2), and B C (Ax Uick-1 for any & E [K)
We make four remarks regarding this theorem. First, the parameter RR 2 0 in (4) induced by the hierarchical structure in the sense that the arms available at subsequent stages are worse than the current ones; see Appendix B. Hence, each agent prefers arms with a stable acceptance probability, and for which 17.k controls the penalty on the uncertainty. Second, 7i.k serves as regularization parameter in the optimization (4) for the uncertainty measure dτ,x- In practice, we may choose large value of 7/s.k if the agents' competition is tense, 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 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 multi- stage matching market involves multiple agents competing for arms. An arm exits the market once 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 fundamental difference between the multi-stage matching when K > and the single-stage matching when K = 1. In particular, when K > I, the optimization (4) has a regularization term 1j,,&i, (v;)) 0 on the uncertainty of the acceptance probability.
contrast, this term vanishes when = 1 as "i.k 0. As result, the optimal strategy in mtlti-stage matching in Section 3.2 and its economic consequences in Section 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 & E [K]. the finding and checking of an optimal solution is still computationally intractable. This is because we need to individually check significant fraction of the combinations of (AAd \ (USA-1B..)) arms at each stage k E [K] to determine the optimal solution for (4). The number of combinations grows exponentially with (ar Ulg for k E [K].
We propose greedy algorithm that gives an approximate solution to the optimization problem in (4). Suppose the true state fixed at 8 8i,.- We refer to (vj + eiy) (T))).te By) 77, (v;) as arm Aj 's variational expected utility. For each A₁ E (AA Uick- BB,),, the greedy algorithm computes the variational expected utility per unit of acceptance probability, that is.
r(4,) = (u, + (TL)) vy)) -
Then the algorithm ranks arms according its associated value of so that r(1) r(2)).. 2
Accard(AA (Uiga-1B,.)) Starting with the first arm corresponding to T(a) 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 value are better than or equal to the cutoff are selected for agent P; to pull at stage k E [K]. We present the formalized cutoff = T, in Appendix B.2. Then using the greedy algorithm, agent P. pulls arms from the following set,
(s,,)) = (ú Aj E (A \ AIgk- )B satisfying r(A,) 2 r..
(5)
Theorem 2. Suppose the true state is fixed at s7 Si,k- The arm set B. in (5) is near-optimal as its loss satisfies
min B. (AR Wiek- BB..} (B S C.(B,, S min
(A [l(B,,]] + +UE,
where the loss function C) is defined in (4). The quantity UEt 2 0 and it equals 0 if there is continuum of arms and (1.,(((5))) ) is continuous v.
3.2 A two-step learning algorithm
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 P.. We propose 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 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 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 I: Lower uncertainty bound Let A' = A4, "e....,,A,, AC, {1...., T}. Let sf be the state of agent P. at stage l and time t. The state s is unknown until the next stage or the next time point, and the state si varies over time. For instance, the yield rate of college may change over the years. For any arm A3 A', there are an associated pair of the
be the arm set at L E [T] =
5

---

score and fit values (v), (t1)) obtained from (1), where i E [m].j E [nd]]. Let (uj, eig) denote the attributes of arm A5. Define the set B 1.k {j P. pulls arm Aj at time t and step k 1 S j S n' j. where card
ni, S n'. For any j E B the outcome that P. observes is whether arm AG accepted P. that is, viy = 1 [[4] accepts P.). We want to estimate Ts based on the historical data, D = =((s oj,, ciy, v(y)) : [m];j E -
E [T]]-
wide range of machine learning methods, e-g.. reproducing kernel methods, random forests, or neural networks, can be applied here to learn Ti (cf. [23]). For concreteness, we consider a penalized estimator in RKHS. Let the log odds ratio fi, (8i,k,) v) = a w)/[1>ma/a (8i,R w]]}. which is assumed to reside in an RKHS HK..a with the kernel K. Then we solve for fi.e E Hx.,, that minimizes the objective function:
T Σn
-iigfee(shh + log (1 + exp (x, + A 1=1 K jE
E
where Aid 2 0 is tuning parameter. Consider the tensor product structure of Hx,, where Ki,, v), (5 v'), ( (s,, ,e), r') with some kernel functions K and KN,N,, [40]. It is known that fa, is minimax rate-optimal and satisfies B[(fr. - f(,))²] s c, (log T) -1--/=rr/ for any i E [m]] (ef. [15). Here, cy 0 is constant independent of T, and r 2 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 {AI..... A, be the new arm set at time T + 1, where A, has attributes obtained from (1). Then the probability that Aj accepts P. at stage k is estimated by (Sik, 0z) (1 expl-ffi. wg)]]=+ The expected utility of A, is 7 ( U5)(13 + eig) for any j E [n]] Finally, we construct a lower uncertainty bound for T (8i,k, U5) as,
( 15)) - m..33.
# (8)A)
if ef E [minfff I -. maxfu 1 ji 1 o.W.,
(6)
1.
where (1,
[maxx:. Hi.k (8i,k, 0y)- -mmn R (si,R 0j)]. The parameter V)i,k 2 0 defined in (4). Note that (6) assigns probability one to arms with scores that agent P; has never pulled. Hence it encourages the exploration of previously untried arms. A lower uncertainty bound for the expected utility is then given by #|, (st.k, (1) + eny) for any E [m].
The prediction of match compatibility is also possible in another direction that an arm A, can also learn how much an agent P; may like itself by predicting the probability that Aj can be puiled by P.. The arms would make the decisions based on the prediction that if they have a realistic potential of being pulled by 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 8i is unknown in practice, a natural question is how to calibrate the state parameter 8i,8 in (5). Consider the average-case loss, Eeg, (er, ( B [si,)]], where the loss ff, is defined in (4). Define the marginal set as (Bt,))) = lims, , (BL, -8a) B (81,))) Hence (B..)))))) represents the change of (x,,() with a perturbation of si,k-
Theorem 3. The average-case loss Ess, (Bi is minimized if si.k E (0, 1) is chosen as the solution
P( # s(,k)
Σ
(v, + eij Esr, [Te(())))))) Th m., sh + s.,k]
= 7v Faz Faz (88,6))
Esg, (TT 8in < 07, S 1},
where Fsr,, is the cumulative distribution function S E [0,

---

also perform the calibration under Algorithm The two-step algorithm for multi-stage decentralized matching
1: Inputs: Historical data for agent P:: {(
...,,...... T); New arm set AA*+1 at time + 1, where the arms have attributes {(V), (1)) = E [n]]; Penalty 7 for exceeding the quota. Regularization parameter 7/i,k 2 O.
e of, eiy, viy) ; Bl 1.,,...,
2: for stage k = 1, 2.....
do
3: Construct the lower uncertainty bound (st,s, 0ÿ) by (6)
4: Estimate the distribution Fet, (-) by the kernel density method [38]
5: Calibrate the state Si,k according Theorem
6: Determine the arm set R (st,)) in (8)
7: Calculate the remaining quota: qi
and the available arms
8: end for
9: Outputs: The arm set (8L,)) for agent P; 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 s4 chosen the largest one. If the distribution Frt, has discrete support, the objective in Theorem 3 needs to be changed as follows: choosing the minimal s,,k [0, 1] such that the left side of (7) is not less than the right side of (7), where the search of 81,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, the worst-case loss, which is discussed in Appendix B.3.
Summary of the two-step algorithm Using (6) and (7), obtain the cutoff estimate f, and calibrated state k, which suggests agent P. to pull arms from the following set at stage
(st,s) ti Aj E {4 Uigh-1Bi1) satisfying r(A,) 2 F.).
(8)
Here AT+1 is the set of arms that are available at stage h of time T +1 1. Due to the minimax optimality of fi we have the consistency result that A (81,x) + B,,,(St,.)) as T - oc, where the set (s..( is defined in (5). We summarize the above two-step algorithm in Algorithm We also remark that although the negligible application costs is assumed in Section 2, Algorithm 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).
4 Strategic Behavior and Economic Implications
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 implies that agents prefer arms with stable acceptance probability. This preference lead strategic behavior the part of the agents follows. Define the uncertainty level as the uncertainty measure ,r,x (t) in Section 3.1 relative to the acceptance probability (s,,, v). That is,
uncertainty level = 6,, (s1,e: v).
We show in Appendix B.2 that the cutoff r, in (5) is strictly increasing in the uncertainty level for any V E [o, 1] and k K K-1, which implies that an agent favors arms with a low uncertainty level. Hence, an agent's ss 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 faimess studied here is defined in terms of no justified envy [1, 8]. Specifi- cally, an arm Ay has justified envy if, stage e [K], A, prefers an agent Py. another agent P. that pulls Ay, even though P. pulls an arm Ay which ranks below A, according to the true preference of Pv. We define multi-stage matching procedure be fair if there no arm having justified envy at any stage.
Proposition The probability that an arm has justified envy is strictly increasing the arm's uncertainty level defined in (9).
7

---

The fairess issue has been noted in practical sulli-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 an agent has increased expected payoff under 7 > than under Th = for all stages I 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 mi. 2 O.
This proposition implies a trade-off between welfare and fairness since both the level of justified envy and welfare increase when changing Ti, 0 Ti > O. 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 and 2, agents in the first stage would strategically pull arms with low uncertainty levels by taking 1k, > 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 7),2 = 0. Theorem I shows that agents' strategic behavior 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 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, 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 decentrulized matching.
We provide an empirical example 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 im- plemented by employing the celebrated deferred acceptance (DA) algorithm [21]: see examples in [1, 32]. In the ammproposing version of DA (e.g., prudent-gooposig in college admissions), agents and arms report their ordinal preferences to clearinghouse, which simulates the following multi-stage procedure. Every arm shows its interest to the most preferred agent that has not yet rejected 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 otherwise remains unmatched. The multi-stage decentralized matching is different from DA in practice, mainly due 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 numerical example of Appendix A.3 that some agents are better off in decentralized markets than centralized markets. This finding gives partial explanation of the prevalence of decentralized college admissions many countries.
5 Numerical Studies
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 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.
8

---

Simulated graduate school admissions Consider 50 graduate schools from three tiers of col- leges: five top colleges ,PI....,PP Ps). ten good colleges {P...... .Is): and 35 other colleges (Pie..., P50 Each has the same quota 5 and penalty = 2.5. The simulation generates students' preferences with ten different states (6.....,,110] C [0, 1]. For any state, students' pref- erences 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 by chosen uniformly and ii.d. from [0.9. 1] and 100 students having score 2 i..d. uniformly chosen from [0.7, 0.9). The rest of the students have score V/ randomly chosen from [0, 0.7). The fits Eij for all college-student pairs are drawn uniformly and i.d. from [0. 1|.
[a] College P1
(b) College P6
(c) College P16
College's i payott
4
LUB-CCM
95% UCB
95% LCB
Simple Cutol Stralegy
95% UCB
LCB
01
01
260
270
280
290
300
260
270
280
290
300
250
260
270
280
290
300
Number students
Number students
Number of students
Figure 1: Performance of the proposed Algorithm (i.e., LUB-CUU and the Simple Cutoff Strategies with varying numbers of students. The results are averaged over 500 data replications. (a): College P1 from tier 1. (b): College Ps. from tier 2. (c): College Pie from tier 3.
We compare the college's 's expected payoff' achieved by the proposed Algorithm 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 random state from {8i..... ........................ fo0e which gives the corresponding arms' preferences. Then we apply Algorithm I with 7/.1 = 0.1, '/,2 of three colleges P1, Pb. and Pie over 500 data replications. Here colleges P1, Ps. and Pis belong to the three different tiers, respectively. In Figure 1, all colleges except P1 use Algorithm while Pi uses one of the two methods: Algorithm I and the simple cutoff strategy. It is seen that Algorithm I gives the largest average payoff's for all of Pt. Ps and Pie. In particular, Algorithm performs significantly better for Pg and Pıe compared to the simple cutoff strategy.
and 75 = 2.5. Figure reports the averaged payoffs
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, college's 's yield is proxy for the state 8i,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 (1)) m (St,ee, v) defined in (9) and study colleges' strategic responses. While conclusive evidence the individual students' acceptance probability is difficult to obtain, we estimate the college-wise uncertainty the yield: /Var(ss,u) for admitted students differs across years, the yield's uncertainty underestimates the uncertainty facing a college. Figure? 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
Since the choice set

---

Liberal arts col Other program University
0.15
Uncertainty
0.05
0.00
10000
15000
20000
Number admitted students in 2015
Ranking of colleges
Figure 2: Regression of uncertainty level on the size of admitted class and the ranking, respectively. Two dashed curves are fitted using smoothing splines with the tuning parameter chosen by GCV.
outlier is the University of Chicago 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 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 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.
Conclusion
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 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 'ss i welfare but leads 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, some applicants are indistinguishable a firm. We leave these questions for future work.
The problem of machine learning in economics has become increasingly important in many applica- deepen the understanding of decentralized matching markets
tion domains. In this work, we from a learning perspective and propose an efficient and scalable algorithm to solve optimal strategies. We do foresee any negative impact to society from our work.
Acknowledgments and Disclosure of F 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 part by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941.
10

---

References
[1] ABDULKADIROČLU, A., AND SÓNMEZ, T. School choice: A mechanism design approach.
American Economic Review 93, 3 (2003), 729-747.
[2] ADACHI, H. search model of two-sided matching under nontransferable utility. Journal of Economic Theory I13, 2 (2003), 182-198.
[3] ARONSZAIN, N. Theory of reproducing kernels. Transactions of the American Mathematical Society 68, 3 (1950), 337-404.
[4] ASIILGI,, I., BRAVERMAN, M., KANORIA, Y., AND SIII, Clearing matching markets efficiently: Informative signals and match recommendations. Management Science 66, (2020), 2163-2193
[5] AVERY, C., FAIRBANKS, A., AND ZBCKHAUSER, J. The Early Admissions Game: Joining the Elite. Harvard University Press, Cambridge, MA, 2003.
[6] AVERY, C., AND LEVIN, J. Early admissions at selective colleges. American Economic Review 100. (2010), 2125-56.
[7] AZEVEDO, E. M., AND LESHNO, matching markets. Journal of Political Economy 124, 5 (2016), 1235-1268.
supply and demand framework for two-sided
[8] BALINSKI, M., AND SÖNMEZ, T. A tale of two mechanisms: Student placement. Journal of Economic Theory 84, (1999), 73 73-94.
[9] BENIAMINI, Y., AND HOCHBERG, Y. Controlling the false discovery rate: practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodological) 57, (1995), 289-300.
[10] BUBECK, S., CESA-BIANCHI N. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning 5, 1 (2012), 1-122.
[11] CHADE, H., LEWIS, G., AND SMITH, L. Student portfolios and the college admissions problem. Review of Economic Studies 81, 3 (2014), 971-1002.
[12] CHADE, H., AND SMITH, L. Simultaneous search. Econometrica 74, (2006), 1293-1307.
[13] CHE, Y.-K., AND KOH, Y. Decentralized college admissions. Journal of Political Economy 124, 5 (2016), 1338-
[14] COLES, P., CAWLEY, J., LEVINE, P. B., NIEDERLE, M., ROTH, A. E., AND SIEGFRIED, J. J. The job market for new economists: market design perspective. Journal of Economic Perspectives 24, 4 (2010), 187-206.
[15] DAI, X., AND JORDAN, M. I. Learning strategies in decentralized matching markets under uncertain preferences. Journal of Machine Learning Research 22, 260 (2021), 1-50.
[16] DAS, S., AND KAMENICA, E. Two-sided bandits and the dating market. Proceedings of the 19th International Joint Conference on Artificial Intelligence (New York, 2005), vol. 5, AAAT Press, p. 19.
[17] DIAMANTOUDI, E., MIYAGAWA, E., AND XUE, L. Decentralized matching: The role of commitment, Games and Economic Behavior 92 (2015), 1-17.
[18] EPPLE, D., ROMANO, R., AND SIEG, H. Admission, tuition, and financial aid policies in the market for higher education. Econometrica 74, (2006), 885-928.
[19] FREEMAN, R., SHAH, N., AND VAISH, Best of both worlds: Ex-ante and ex ex-post fairness in resource allocation. In Proceedings of the / ACM Conference on Economics and Computation (2020), pp. 21-22.
[20] FU, C. Equilibrium tuition, applications, admissions, and enrollment the college market. Journal of Political Economy 122, 2 (2014), 225-281.

---

[21] GALE, D., AND SHAPLEY, L. S. College admissions and the stability of marriage. The American Mathematical Monthly 69. (1962), 9-15.
[22] HAFALIR, I. E., HAKIMOV, R., KÜBLER, D., AND KURINO, M. College admissions with entrance exams: Centralized versus decentralized. Journal of Economic Theory 176 (2018),
[23] HASTIE, T., TIBSHIRANI, R., AND FRIEDMAN, J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, New York, 2009.
[24] IMMORLICA, N., LESHNO, J., Lo, I,, AND LUCIER, B. Information acquisition in matching markets: The role of price discovery. Available at SSRN (2020).
[25] LIU, L. T., MANIA, H., AND JORDAN, M. I. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics (2020), PMLR, pp. 1618-1628.
[26] LIU, L. T., RUAN, F., MANIA, H., AND JORDAN, M. I. Bandit learning decentralized matching markets. arXiv preprint arXiv:2012.07338 (2020).
[27] MEHTA, A. Online matching and ad allocation. Foundations and Trends in Theoretical
Computer Science 8, 4 (2013), 365-368.
[28] MONTGOMERY, J. D. Equilibrium wage dispersion and interindustry wage differentials. The Quarterly Journal of Economics 106, 1 (1991), 163-179.
[29] NACAC. 2019 state of college admission. wttpriiiiosssstttttooooolleeeeee
http://www.nncccerr.nnnneeessssp (2019).
[30] NIEDERLE, M., AND YARIV, L. Decentralized matching with aligned preferences. Tech. rep., National Bureau of Economic Research, 2009.
[31] PETERS, M. Ex ante price offers in matching games non-steady states. Econometrica 5 (1991), 1454-
[32] ROTH, The evolution of the labor market for medical interns and residents: case study in game theory. Journal of Political Economy 92, 6 (1984), 991-1016.
[33] ROTH, A. E. Deferred acceptance algorithms: History, theory, practice, and open questions. International Journal of Game Theory 36, 3-4 (2008), 537-569.
[34] ROTH, A. E., AND SOTOMAYOR, M. Two-Sided Matching: Study Game-Theorene Modeling and Analysis, vol. 18. Econometric Society Monographs, Cambridge University Press, Cambridge, 1990.
[35] ROTH, A. E., AND XING, X. Tumnaruun time and bottlenecks in market clearing: Decentral- ized matching in the market for clinical psychologists. Journal of Political Economy 105, (1997), 284-329.
[36] SAVAGE, L. J. The Foundations of Statistics. Dover Publications, Inc., New York, 1972.
[37] SHAPLEY, L. S., AND SHUBIK, M. The assignment game i: The core. International Journal of Game Theory (1971), 111-130.
[38] SILVERMAN, B. W. Density Estimation for Statistics and Data Analysis, vol. 26. Chapman and Hall, London, 1986.
[39] WAHBA, G. Spline Models for Observational Data. SIAM, Philadelphia, PA, 1990.
[40] WAHBA, G., WANG, Y., GU, C., KLEIN, R., AND KLEIN, B. Smoothing spline anova for exponential families, with application to the wisconsin epidemiological study of diabetic retinopathy. Annals of Statistics 23, 6 (1995), 1865-1895.
12


Reviews:
[{"review_id": "pXsKAGlrRp", "reviewer": "Reviewer_auj5", "summary": "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$.\n\nAt 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.\n\nThe authors provide a variety of results: \n1. Three algorithms (one of which is their main result) on the side of learning the optimal strategy from the perspective of agent $i$.\n2. Fairness and Welfare trade-offs.\n3. Experiments. \n\nIn 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:\n1. Use an off the shelf estimator for the $\\pi_{i,k}(s_{i,k}, v_j)$.\n2. Modify them by subtracting a weighted variational term (as in the first algorithm), or set to 1 if the arm has not been used.\n3. Balance exploration and exploitation of the arms used.\n\nThe 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.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written at a very high mathematician standard and a lot of effort has been put into fitting it within the constraints of the format: nevertheless, it is choked by the page limit and I still required multiple passes to make sure I understood the notation and finer points of the setting. The related work is very clearly exposed and addressed whenever necessary: there’s no doubt that the authors understand the field very well. My only comment on the presentation is, if possible, to add a short explanation on the choice of $\\eta_{i, k}$: it is a crucial parameter that affects nearly every result, but I couldn’t find much more than “it exists” in the main text, without resorting to the Appendix for further details.\n\nThe model makes sense and the abstractions taken to make it workable mathematically are not too detached from reality: my main concern (perhaps as a game theorist) is if there was a way to more explicitly expose the competition aspect between agents. This is encoded through the $\\pi_$’s and $s_{i, k}$: I am wonder how different a model where each arm has a randomly produced weak ordering of arms would be.\n\nThe fairness results are interesting, but I might have chosen a different definition of envy for this setting: restricting the envy to be ‘per turn’ simplified the analysis but begs the question: if an arm is passed over by its favourite agent and then pulled by less desirable one over two rounds, should it not have envy? Moreover, the arms might not know exactly what the strategy of the agents is. Perhaps it would be more natural to define envy ex-post, for the case where we have pairs (arm1, agent1) and (arm2, agent2), even though arm1 prefers agent2 over agent1 and agent2 prefers arm1 over arm2.\n\nOverall, I enjoyed reading the paper, which studies a realistic model and produces impactful, punchy results which reassure our initial understanding and provide finer details as well.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SwqyMH0uYDT", "reviewer": "Reviewer_GLYK", "summary": "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).\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contributes to the growing literature in the intersection of learning and matching markets. The main novelty of the question (compared to the existing literature) is the assumption of multiple stages. Due to the similarity of the question with previous works, the technical/ algorithmic contribution is not particularly interesting. However, matching happening in multiple stages is a real concern in practice and the authors provide several insights about the implications of their findings. \n\nMain comments:\n- A common problem in college admissions is the lack of fully rational (but still strategic) behavior and access to full information on the student’s side, which makes the modeling on students’ side less realistic. How does the model address these concerns?\nThe related literature is incomplete. Several recent papers study very related questions, e.g.,\n Liu et al. (2020),    \"Bandit Learning in Decentralized Matching Markets,\"\n Liu et  al. (2020),   \"Competing Bandits in Matching Markets,\"\n  Immorlica et al. (2020), \"Information Acquisition in Matching Markets: The Role of Price Discovery.\"\n\t\nFurthermore, the paper is very closely related to [13]. How do the two papers compare from a modeling and technical perspective? What is the novelty of the current paper? The comparison to this work and the papers above should be made clear.\n\n- Does assuming just 2 stages ($K=2$) -- which would be realistic for college admissions -- help get more specific insights about the model?\n- How would the results change if arms behaved similarly to agents? E.g., instead of assuming some acceptance probability function, their decisions had more structure (like the agents’ decisions).\n- Lines 124-126: Assuming negligible application costs is not realistic. In fact, it would be interesting to study how relaxing this assumption would affect the results.\n- I didn’t find the result about the hierarchical structure in Theorem 1 particularly surprising but it was nice to see this intuition formalized.\n- The paper uses very heavy notation. For the sake of readability, I believe that some technical details and definitions could be omitted (for example, in Section 3.2).\n- I enjoyed the results in Section 4. It’s worth exploring the economic implications of the model further.\n- Although the notion of no justified envy is pretty standard, I think it’s quite misleading as a measure of fairness. It would be better to explicitly use the term “no justified envy” instead of “fairness”.\n- In Proposition 3: Is there any characterization of the gap possible? It would be nice to study this question (at least empirically).\n- The presentation in Section 5 needs improvement. It is unclear what information the data contained and how the authors used it in the simulations. \n- The insight that universities are better off by employing strategic admissions (see lines 350-351) seems to be true for less selective colleges. Top colleges tend to admit the best (but potentially earlier than others) so I am not sure how this finding reflects reality.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should discuss the technical limitations of their model, discuss/motivate their assumptions and empirical analysis. This discussion is currently not included in the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "Pqt_i9_p-n", "reviewer": "Reviewer_zGHc", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-I think the paper addresses an important and interesting topic and I do not think there has been much work in decentralized matching.  \n\n-In lines (155,181) NP-completeness is claimed. I do not see how the presented arguments are a valid justification. Isn't NP-completeness proved through a reduction not loosely by saying there are many possibilities to check. I think either a proof should be given or the claim should be that the proposed method would be computationally intractable.  \n\n-There is a large literature on stochastic matching and online matching which does not seem to be referred to at all. Further, it is possible that the techniques/results from stochastic/online matching could be useful here. See e.g., Mehta, \"Online matching and ad allocation.\" (2013).\n\n-Perhaps, the essential parts where the paper departs from most of the work in matching is decentralization and learning. With regards to the learning part, the inclusion of probabilities similar to \\pi in the model have been considered before in online matching where an agent would be matched with an arm and the match succeeds with some probability. In these online matching settings, it is assumed that these probabilities are learned from previous records similar to this work. But the learning step is abstracted away. Why can't we abstract the learning step here as well? Can't we assume that we have the probabilities or noisy estimates of them. Further, algorithm 1 solves for the values B_{i,k} before the matching process begins, so this isn't an interactive learning setting, is it? \n\n\n-Some parts of the paper do not seem new and have been used before in reference [13], e.g. the utility model and theorem 3. \n\n-Although it would complicate things, it seems that the model would be more accurate if it were to allow the arms to change their minds in the next round and possibly drop the agent to which they were matched in favor of a better agent. Excluding this setting, does the algorithm have stability guarantees, i.e. is the final matching a stable matching?  \n\n-Why doesn't \\pi_{i,k} also have a dependence on the fit e_{i,j}. Further, shouldn't \\pi_{i,k} also have an index for j? \n\n-Lines161,233: shouldn't the min and max arguments be over (i,k) instead of s_{i,k} \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations And Societal Impact are adequately addressed.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ExllLQeXmjQ", "reviewer": "Reviewer_wCZe", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work uses a novel variational formulation and framework to obtain the optimal strategy in a multi-stage decentralized matching market. The claims are well supported by theoretical proofs and some experimental results on synthetic and college admission data. The writing was clear and concise, although more explanation and background on the theoretical parts would be nice. The results shed some light on fairness in the college admission process, which is an interesting result on its own. They built upon the concepts of lower uncertainty bound to compute each arm's expected utility and uncertainty and calibrated decentralized matching to calibrate each agent's quota and each arm's parameter on each stage depending on historical data. Their framework is flexible in allowing the use of various machine learning methods to estimate arms' expected utility and uncertainty bounds. They also provide convincing experimental results to show the effectiveness of their algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were supportive of the present submission, appreciating its approach to a general problem faced in modern two-sided markets.  Reviewers supported the model at a high level, and appreciated the cleanliness of the results proved about that model.  Still, there were concerns raised by some reviewers about the definition of and exposition surrounding fairness (auj5, GLYK) and its application to particular settings (e.g., can preferences of the arms change, and so on; see reviews).  Some responses to the reviewers' questions were not satisfactory, for example, when asked about the complexity of their results, the authors responded with:

-- "We adopted the use of NP-completeness by following the literature; see, e.g., Section 2 of Milgrom (2017, Discovering prices. Columbia University Press). However, for clarity, we will change the writing in lines (155, 181) from NP-completeness to computational intractable."

That citation is a 200+ page general book, and referring to Section 2 of it does not answer the reviewer's question.  Other examples abound.  Still, the rebuttal did address many of the reviewers' concerns.  Should this paper be accepted, this AC would very much appreciate the authors spending substantial time with the reviewers' comments (especially auj5, zGHc, and GLYK) before finalizing their work.
Decision: Accept (Poster)