Monoculture in Matching Markets
Authors: Kenny Peng
Nikhil Garg
Venue: NeurIPS 2024 poster (2024)
Keywords: algorithmic monoculture
matching markets
hiring
Primary area: algorithmic_game_theory
TL;DR: We study algorithmic monoculture in a matching markets framework

Abstract: Algorithmic monoculture arises when many decision-makers rely on the same algorithm to evaluate applicants. An emerging body of work investigates possible harms of this kind of homogeneity, but has been limited by the challenge of incorporating market effects in which the preferences and behavior of many applicants and decision-makers jointly interact to determine outcomes.

Addressing this challenge, we introduce a tractable theoretical model of algorithmic monoculture in a two-sided matching market with many participants. We use the model to analyze outcomes under monoculture (when decision-makers all evaluate applicants using a common algorithm) and under polyculture (when decision-makers evaluate applicants independently). All else equal, monoculture (1) selects less-preferred applicants when noise is well-behaved, (2) matches more applicants to their top choice, though individual applicants may be worse off depending on their value to decision-makers and risk tolerance, and (3) is more robust to disparities in the number of applications submitted.

Monoculture in Matching Markets
Kenny Peng
Nikhil Garg Cornell Tech
Cornell Tech
cornell.edi etn
ngargScornell.edd edu
Abstract
A Algorithmic monoculture arises when many Decision-makers rely on the same algorithm evaluate applicants. An emerging body of work investigates possible harms of such homogeneity, but has been limited by the challenge of incorporating market effects which the preferences of many applicants and decision-maie makers jointly interact to determine outcomes. Addressing this challenge, introduce a tractable theoretical model algorithmic monoculture in a two-sided matching market with many participants. We use the model to analyze outcomes under mono- culture (when decision-maker -makers all evaluate applicants using a common algorithm) and under polyculture (when decision-makers evaluate applicants independently). All else equal, monoculture (1) selects less- ress-preferred applicants when noise is well-behaved, (2) matches
applicants to their top choice, though individual applicants may be worse off and have higher variance outcomes depending on their value decision-makers and (3) more robust to disparities in the number of applications submitted. Overall, our approach strengthens, challenges, and broadens the scope of the existing monoculture literature.
Introduction
What happens when many decision-makers- in consequential domains like employment and college admissions-all evaluate applicants using the same algorithm? This possibility has been termed "algorithmic monoculture"- name that references the problems arising in agriculture when single crop is farmed extensively, amplifying the risk of correlated widespread failures. A recent line of work considers how lack of variety in algorithms may warrant similar concerns; this concern may be especially important if many decision-maken use the same large language models.
Initial inquiries into the consequences of algorithmic monoculture have identified potential harms to both decision-makers and applicants. seminal work initiating the formal study of algorithmic monoculture, Kleinberg and Raghavan [35] demonstrated that firms relying on common algorithm may hire weaker applicants than when using idiosyncratic (but less individually accurate) hiring processes. On the applicant side, emerging set of work highlights the concern of systemic exclusion, which occurs when an applicant denied from all opportunities [16, 11, 43, 31].
This emerging literature has been limited by the challenge of incorporating market effects. Domains where monoculture may be especially impactful-se -suhhsuchhaa employment and college admissions share some common properties. First, participants on both sides of the market compete: workers compete over limited number of job openings, and firms compete over workers who can each accept only one offer. Second, outcomes are determined by the preferences of participants on both sides: roughly speaking, a match is formed only if both a worker and firm prefer each other over their other options. Analyzing these interactions across many participants can be theoretically challenging; indeed, the existing monoculture literature in the ML community considers neither markets with many participants nor two-sided interactions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The technical contribution of our paper is matching markets model that can be used to study algorithmic monoculture. We analyze equilibrium outcomes (i.e., stable matchings) that emerge under monoculture (when firms each use the same method to evaluate applicants) and polyculture (when firms use idiosyncratic methods). The model builds on the popular continuum model formalized by Azevedo and Leshno [10], where stable matchings are characterized by a cutoff structure in which applicants are matched to their favorite firm among those where their score exceeds the firm's cutoff. In the model we introduce, an applicant's score is equal to an estimated value that is a noisy realization of their true value. Under monoculture, all firms use a single shared estimate of an applicant's 's value; under polyculture, firms obtain separate, independently drawn estimates of the applicant's value. Our theoretical results are shown in a setting with a symmetric setup with a large number of homogeneous firms. This allows for tractability, well clear intuition. We demonstrate empirically that our theoretical results hold in markets with heterogeneous firms, as well as when firms use MI models to rank applicants.
We show how modeling market effects with many participants advances the present understanding of monoculture in several ways, with Figure illustrating our first two theoretical results:
(Theorem 1) First, as long as noise is well-behaved (i.e., with teeeerrthan-eexooenntall tail), essentially only the most preferred applicants are hired under polyculture when there are many firms. This shows that the existing (relatively modest) effect found by Kleinberg and Raghavan [35] with two firms can be fully strengthened when considering many firms. Our result gives "wisdom of the crowds" like result, where even when individual firms are noisy, the market outcome can behave as if firms each had perfect information about applicants- even despite firms not explicitly sharing any information. Polyculture can thus significantly outperform monoculture in terms of firm welfare, even when the idiosyncratic evaluation processes of firms are much noisier than the shared algorithm used under monoculture.
(Theorem 2) Second, we challenge- and add nuance to exiittinn work suggesting that monoculture harms applicants. In fact, we show that on average, applicants are better off under monoculture than polyculture, in the sense that on average, applicants are matched firms that they more prefer. On the other hand, the individual preference of an applicant for monoculture or polycuiture depends on their true value. Some applicants are strictly more likely to be matched to their top choice under monoculture, but strictly less likely to match at all-and so have higher variance of outcomes conditional on true value; for these applicants, their preference could depend on other factors such as risk aversion. This finding can also be interpreted as showing that monoculture presents a greater risk of systemic exclusion [16, 11] to more qualified applicants who might be overlooked by a single algorithm. However, it does not pose greater risk of systemic exclusion overall.
(Theorem 3) Third, we expand the scope of existing analysis by extending our model to incorporate differential application access: when applicants submit a varying number of applications. This addresses an equity concern especially salient in college admissions, where the cost of application can be high.' It also reveals how different application systems incentivize applicants to submit more applications. We find that applicants who submit many applications benefit much more under polyculture than under monoculture. Consequently, differences in the number of applications submitted harms college and firm welfare more under polyculture than monoculture. Overall, monoculture is more robust than polyculture with respect to differential application access.
Our approach strengthens, challenges, and broadens the scope of the monoculture literature. The effects we study emerge in large markets with two-sided preferences, a standard setting for algorithmic monoculture (e.g., prior works often motivate monoculture through the lens of hiring). Moreover, the cutoff structure inherent in Azevedo and Leshno [10] results in clean intuition for each of our results-an as well as precise characterizations at the level of individual applicants. In this way, we bridge the literature monoculture and matching markets, and anticipate that the matching literature can provide further insight into the emerging study of monoculture.
The paper proceeds as follows. In Section 2, we consider related work in the algorithmic monoculture and matching markets literature (we give an extended discussion of related work in Appendix B). In
Application fees to U.S. colleges were as high as 100 dollars in 2022-2023 cycle [44], Moreover, the Common Application reported that the number of applications submitted by students varied significantly in the 2021 2022 cycle: for example. high-volung applicants who submitted 15 or more applications were 2.5x as likely to have attended a private high school [34].
2

---

Individual Outcomes for 1000 Applicants
in a market with 25 firms and 500 total openings
unmatched
25
rank of match
matched
10
0.0
0.2
0.4
0.6
0.8
polyculture
unmatched
rank of match
1.5
matched
1.0
0.8
applicant's percentile true value
Figure 1: Under monoculture, the set of matched applicants is more noisy. However, applicants are more likely to match to their top choices. Roughly speaking, the use of single algorithm means that applicants who match tend to "do well" across all firms; however, high-value applicants may not match due single poor evaluation.
Section 3, we introduce our model and establish some preliminary results. In Section 4, we introduce Theorem 1 and Theorem 2 (we give an extended model and establish Theorem 3 in Appendix A). In Section 5, we provide an overview of our computational experiments; in particular, we test our theoretical predictions in an experiment where firms use ML models (trained on the ACSIncome dataset [19]) evaluate applicants. Proofs of all theoretical results are given in Appendix E.
Related Work
Algorithmic Monoculture in ML Our model extends Kleinberg and Raghavan [35]; they analyze the case where two decision-maker makers each hire one applicant, while we consider many decision-makers who can each hire many applicants. Theorem 1 in the present work shows that the effect found in Kleinherg and Raghavan [35], where polyculture can result in higher total accuracy than monoculture, fully strengthened when considering many decision-makers.
Our two-sided matching markets model also makes it easy to simultaneously study applicant welfare, which has recently been of concern. Creel and Hellman [16] argue that systemic exclusion, in which applicants are systematically denied all opportunities, can pose significant harm. Bommasani et al. [11] and Toups et al. [43] analyze this effect empirically by examining the level of homogeneity in decision-making across algorithms. One limitation this existing work that it does not consider market-level effects, which are present in domains such hiring and college admissions. For example, the total number of available positions is fixed and if firms intend to fill all of these positions, then the total rate of systemic exclusion does not change (the number of people that do not end up receiving a position is fixed). We show which applicants are at a greater risk of systemic exclusion under monoculture, Our model gives tractable way theoretically analyze market outcomes. In Section 5, we further show how empirical approaches can be adapted accordingly under our model.
Matching Markets and School Choice By analyzing algorithmic monoculture through a matching markets framework, our results reveal connections between algorithmic monoculture and questions that have been considered in the matching markets (and school choice) literature. For example, Castera et al. [13] analyzes statistical discrimination in stable matching. In their model, the values of applicants from two groups are estimated by two decision-makke (monoculture). Like us, they leverage continuum model of applicants [10]. Their findings focus on aggregate measures of applicant-side welfare across groups. They show, for example, that the group of applicants evaluated with less correlation is matched with higher probability. More directly related to our work, they show that decreased correlation (even one group), reduces the number of applicants who receive their top choice; this parallels our finding in Theorem 2(ii), which implies that
potentially with correlation
3

---

fewer applicants are matched to their top choice under polyculture. This finding reflects a general result developed in the school choice literature: that increasing correlation in how decision-makers evaluate applicants also increases the total number of applicants matched to their top choice. It is well- established that in school matching, the use of a single lottery number (rather than an independent lottery per school) results in more students being matched to their top choices and is more robust to differences in the number of listed schools [2. 18, 9, 7, 5J. A key distinguishing feature of the model studied here and by [35] is using approximate values to determine which applicants are matched, but to analyze the matching using a different set of true (latent) values.
Interestingly, the matching markets and school choice literature generally shows the benefits of increased correlation in how applicant evaluation, while the algorithmic monoculture literature describes primarily harms. Our work helps reconcile these competing intuitions. In comparison to the matching markets literature, we assume that each applicant has some ground truth value, and that decision-maker noisily rank students based on this value. Consequently, we can analyze outcomes for individual applicants, whereas the markets literature primarily considers homogeneous applicants. This reveals the relevant trade-off's between monoculture and polyculture. For example, we show (Theorem 2) that increased correlation (monoculture) increases the probability that an applicant is matched to their top choice, but can also increase the probability that high-value applicant does not match at all. Our analysis with many firms and applicants also reveals market emergens phenomena not apparent in smaller markets. In follow-up work, we show that Theorem 1 extends to a setting with arbitrary student preferences and college capacities [40]. There, it is shown that when noise is long-tail long-tailed, the opposite effect can occur, where students match uniformly random under polyculture. See Appendix B for an extended discussion of related work.
3 Model and Preliminaries
Our model builds on Azevedo and Leshno [10], with continuum of applicants and finite number of firms (or colleges). An applicant is identified by their true value, which is distributed on TE according to probability measure 17. Let F = {1, ,.,,,,,,,,, be the set of all firms. Firms have total capacity S < 1 (there fewer positions than applicants) and each firm has the same capacity S In our setup, firms have only estimates of applicant true values, instead of direct access to the true values. An applicant with value is associated with an independent random variable 0(v), characterizing their preferences over firms and firms' estimated values for that applicant. The realization of (vv) is their type, which lies in the set of applicant types θ R. x RT, where R. is the set of preference orderings over the firms. If ((v) = 0 = (>+ (ee), then > 9 is the preference ordering of u over firms and ey is the estimated value of the applicant at firm f. (In this way, any measurable subset of student values induces measure over O.) Firms all prefer applicants with higher true values, but in practice, rank applicants based on the estimated values given by 0(v).
matching is a function μ : θ + FU {0} that satisfies the capacity constraints
S
Pr(u(((u)) = dn(()) = m'
VfEF,
as well as two additional technical assumptions: that μ (f) is measurable and that the set (0 ((0) -0 f} is open. Then ((((r)) is random variable indicating where an applicant with value is matched, with (((())) = 9 indicating that the applicant is not matched. When it is clear what @ is, we will abuse notation to write μ(v) instead of (()(v)) denote the random variable representing where an applicant with value v is matched. A matching is stable if there does not exist a pair 0 E O, e F such that f >~ uu0), and e, > o' for some 0' E p (f). In other words, there is no applicant- firm pair that would jointly prefer to defect from the current matching to be matched with each other.
A Cutoff Characterization of Stable Matching A benefit of the continuum model is that stable matchings are characterized by a tractable cutoff structure [10]. Given a vector of cutoffs P = (PI,... Pm)), applicant with type can afford firm f if E, 2 Py. The applicant's 's demand at P is D²(P) the applicant's most preferred firm (according to r among those they can afford. If they cannot afford any firm, (P) 0. The aggregate demand of firm f at P is
D (P) = [ Pr(DD(t)(P) = d]((()),
(2)
4

---

the measure of applicants who demand it. A vector of cutoffs P is market clearing if and only
if D' (P) f for all f E m. Notably, stable matchings are one-to-one correspondence with m
market-clearing cutoffs:
Lemma 1 (Supply and Demand Lemma [10D. A matching μ is stable if and only if there exists vector of market-clearing cutoff's P such that (() D2(P).
The characterization of stable matchings given by the continuum model is summarized as follows. Applicants each have an estimated value at each firm. Firms each have cutoffs. An applicant is then matched their most preferred firm among those at which applicant's estimated value is above the cutoff. Next, we show how we can instantiate monoculture and polyculture within the model.
Instantiating Monoculture and Polyculture We instantiate our model by specifying ((v) for monoculture and polyculture. In what follows, we consider a fixed noise distribution 'D.
In monoculture, we take the random variable
0 mono (v) == (-
where is drawn uniformly random from R and X D. In other words, applicants have preferences distributed uniformly at random, and each applicant has a single estimated value v + X that is shared across firms. This noisy estimated value equals the applicant's value perturbed by noise drawn from D.
In polyculture, we take the random variable
(4) where > is drawn uniformly at random from R and X1, X2, ... Xm D are ii.d.. Again, applicants have preferences distributed uniformly at random, but now each applicant has a distinct, independently drawn estimated value at each firm.
Pplly(1) (v) == (>, (v X1, u x2, .. + Xm));
Preliminary Analysis We establish some basic results. First, we show that under both monoculture and polyculture, stable matchings characterized by identical cutoffs at each firm.3
Lemma 2 (Equal Cutoffs Lemma). If mmmooo Puly ) then there is unique vector of market- clearing cutoffs P, and P1 = P2
Pm.
We denote these unique shared cutoffs by Pmono and Polyy. respectively, with corresponding stable matchings Mmono and Mpoly. Under our abuse of notation, (m) == Mmono Pm
(mmono (v)) and (ppol (v) := (p (0poly are random variables representing where matches. This cutoff structure allows for clean analysis of stable matchings. The next proposition follows directly from Supply and Demand Lemma (Lemma 1) and the Equal Cutoffs Lemma (Lemma 2).
Proposition For all R.
(i) the probability applicant with value is matched under monoculture is Pr(pamono (v) Pr(c + X >> Pinono);
(5)
where X DD and (ii) the probability an applicant with value is matched under polyculture is
Pr[mpoly (v) F] Pr[e
+ max
X > Ppolyl,
(6)
feF
where X1.
X,m Ri D.
We make basic technical assumption on the probability measure and the probability distribution D. Let be the probability measure associated with 2); we assume that both y and have connected support, where we mean that the smallest closed set of measure is interval. Let these respective intervals be [V_, V4, and [X [X], This assumption ensures a unique stable matching.
'The result intuitively follows from the existence of unique market-clearinn cutoffs under reasonable conditions (Theorem I in [10]. A complete proof is provided in the appendix.
5

---

Proposition 3 contrasts the structure of stable matchings in the monoculture and polyculture economies. monoculture, applicants match depending on a single noisy estimated value. In polycultre,, applicants match depending on the maximum of noisy estimated values.
Proposition also reveals that the shared cutoff is lower under monoculture than polyculture. This ex- plains the puzzle of why it is not the case that fewer applicants are matched overall under monoculture when estimated values firms become more correlated, the acceptance cutoff decreases:
Corollary 4 (Lower Cutoff Under Monoculture). When m 2 2, the shared cutoff in economy is lower under monoculture than under polyculture: ie., Pmono < polyy
Intuitively, the result holds because under polyculure,, applicants have multiple chances at getting an estimated value that higher than the shared cutoff; so order for the same number of applicants to be matched under monoculture and polyculture, the cutoff under monoculture must be lower.
We now introduce basic definitions that will be useful for reasoning about the noise distribution D. In particular, we define a particular class of noise distributions that we will focus our later analysis on. The maximum order statistic of n draws from distribution D is defined the random variable X(*) := max(X X2, Xn3 where
Definition: Maximuum-Concentaatinn Noise
XI, Xn iid D. The maximum order statistic plays an important role in analysis, since the probability an applicant with value v matched under polyculture (6) can be rewritten as
Pr[Mpoly (v) E F] = Pr(e + (m) > Ppotyl.
A distribution D is maximum concentrating if for all 0,
lim Pr n=+00
x - E [[
= 0.
(8)
In other words. a distribution is maximum concentrating if its maximum order statistic satisfies a "weak law of large numbers." " These include the uniform and Gaussian distributions, as well as (roughly speaking) distributions with an upper tail that "lighter than exponential." '4
4
Main Results: Firm and Applicant Welfare
4.1
Firm welfare
In this section, we focus on the perspective of firms, who would like admit the most-preferred applicants (i.e., those with the highest true values). To do this, we analyze the probability that an applicant with given value matched. As turns out, strong behavior emerges under polyculture as the number of firms m in the economy grows large. In particular, when the noise distribution D is maximum-comee concentratin., only the highest-value applicants are matched; as a function of an applicant's 's value, the probability that applicant is matched approaches step function when m approaches oo. This, in turn, implies that the matching under polyculture approaches optimal.
Define vg to be the unique value such that 7(Us; x)) = S, i.e., the threshold at which the mass of students with value above vs equals the total firm capacity. Note that in the firm-optimal matching. only applicants with value greater than Us are matched. We may now state our first main result.
Theorem (Wisdom the Crowds Polyculture not Monoculture). Suppose is maximum concentrating. Then:
(i) Under polyculture, the probability an applicant is matched approaches 0 or as m -> 00:
lim Pi[mpoly (v) E FI 10
V < US
m-+20
V > Ug
and firm welfare approaches optimal.
(ii) Under monoculture, the probability applicant is matched, Pr[Moooo (v) F). is constant in m, and firm welfare is constant and suboptimal.
'In general, it is possible to determine if distribution is maximum concentrating using the Fisher-Tipper Gnedenko theorem, comeestone of Extreme Value Theory (see [24] for detailed exposition).

---

Wiedom Crowds:
No Wiadom of Crowds:
Matching Probability Under Polyculture
Matching Probebility Under Monoculture
1.0
probability of matching
probability of matching
0.8-
0.0-
0.4-
number
0.4
number of firms
0.2
01
0.2
m
10
m- 10
0.0
0.5
0.2 0.4 0.6
0.5
1.0
0.0
0.2 0.4 0.6
6.8
1.0
applicant's percentile true value
applicant's percentile true value
Figure 2: As the number of firms m increases, Priuppll(V) (v) E F] approaches a step function, meaning that only the highest-valus applicants match. Mcanwhile, Pr(Mmmnn(V) E F] remains the same regardless of m, in particular, high-value applicants have positive probability of not matching. There and firms have total capacity 500. Applicants have values drawn uniformly from [0, 1] and uniformly uniformly-random preferences. Noise is drawn uniformly from [-0.5, 0.5]. Plot displays average over 1000 simulations.
1000 total applicants
Despite individual firms making noisy decisions, under polyculture, they collectively admit only the highest-value applicants as m grows large (as illustrated in Figure 2). This gives a "wisdom of the crowds" result. Notably, firms do not directly share information with one another; rather, the market at large (specifically, the structure of stable matchings) facilitates the pooling of information."
Intuition for Theorem At a high level, the maximum estimated value-which is what determines an applicant is matched- can effectively "distinguish" between applicants of higher and lower values. Consider applicants Alice and Bob. Alice's value dΛ is higher than Bob's value UB. We show that if is maximum-concentralee vanishes as the number of firms grows large. If Bob is matched but Alice is not, then Bob's maximum estimated value must be higher than Alice's s. The probability this occurs is given by Pr[uA+X(( (m) < UB +x ("")), where ((m) and X x are independent variables distributed according to (()). Since D is maximum concentrating, the probability that two independent draws from X (m)) differ by more than the constant EΛ en vanishes as m grows large. Thus, Alice's maximum estimated value will almost always be higher than Bob's.
the probability that Bob is matched but Alice is unmatched
4.2 Applicant welfare
We now consider matching from the applicant's perspective. Our main result (Theorem 2) shows few things. All applicants more likely to be matched to their top choice firm under monoculture than under polyculture (part (i)) moreover, under monoculture, all applicants who are matched to some firm matched to their top firm (part (ii)). This implies that total applicant welfare- measured by the average rank of where applicants are matched-is optimal under monoculture (and better than under polyculture). Meanwhile, in part (iii), measure that is simultaneously more likely to match to their top choice under monoculture while less likely match overall, which implies that the applicant's variance is higher under monoculture, For these applicants, neither monocultrr or polyculture stochastically dominates the other.
show that there exists set of applicants of positive
Define Ranke (f) := Kf f =d(o f}1 to be the rank of an applicant's s match, with Ranko (0) O. (u(()( is a random variable giving the rank of the firm an applicant of value is matched to under μ.. Let (X) be the support of noise distribution D. Theorem 2 (Likelihood of Matching to Top Choice or At All). The following hold:
(i) For all v, the probability an applicant matches to their top choice is at least as high under monoculture under polyculture: i.e., Pr[Rank, (ateankk,mmonn. (pmono (v)) 1] Pr|Ranko (P (v)) 1]. The inequality is strict for all (Pmono Xx, Pmono X-), a set of positive memasrre
'This holds even despite an apparent "winner's curse" [12, 42, 15]: tirms who extend an offer to an applicant tend to have upward biased estimate of the applicant's value.
7

---

Polyculture Hurts Applicants Submit Few Applications
0.55
probability matching
0.50
0.45
0.40
0.25
monoculture
0.20
polycuiture
10
25
number of applications submitted
Figure 3: We plot the probability of matching conditional on k, the number of applications submitted. There are 1000 applicants and 25 firms have total capacity 500. Applicants have values drawn uniformly from [o, 1] and uniformly-randee preferences, Noise is drawn uniformly from [-0.5, 0.5]. Each applicant can apply to colleges, drawn uniformly from {1,2, -. 255). Probabilities are averages over 10,000 simulations.
(ii) For all v, if (m) E F, then Rank, ((mono(()) 1, meaning that all applicants who match under monoculture are matched to their top choice, and that the matching altains optimal applicant welfare.
(iii When D is maximum concentrating, for all (Us: Pmono - X_),, which is set of positive n-measure, and for all m sufficiently large, an applicant with value is less likely to match under monoculture than under polyculture: i.e., ProMmmool (v) E F] Pr[Mpoly (v) Fl.
The high-level reasoning behind these results is fairly straightforward. First, in part (i), the probability an applicant is matched to their top choice is exactly the probability that their estimated value at that firm exceeds the shared cutoff: P Pmono under monoculture and Ppoty under polyculture. We know that Pmono < Pplly (from Corollary 4), so this probability is at least as large under monoculture in comparison under polyculture (and in many cases, strictly larger). To show part (ii), observe that if an applicant's 's common estimated value under monoculture exceeds the shared cutoff P Pmono- that applicant can afford any firm; thus, they are matched their top choice. Finally, part (iii) is a consequence of Theorem 1, where we showed that for applicants with value above a certain threshold vs, their likelihood of being matched approaches 1 as oc, while their likelihood of being matched remains constant (and less than 1) under monoculture when < P Pmono X_
An Extension: Differential Application Access.
We extend our primary setup include differential application access access-when different applicants submit a differing number of total applications. In practice, the number of applications submitted in college admissions varies significantly, and can be correlated with socioeconomic status: for example, in the 2021 1021-2022 cycle, applicants who submitted 15 or more applications on the Common App were 2.5x as likely to have attended private high school [34]. Our main result here (Theorem 3) shows that applicants who submit more applications do not benefit under monoculture, but do benefit under polyculture. Intuitively, this is because an applicant's estimated value is the same across firms under monoculture, so submitting applications does not increase the likelihood that an applicant will have a higher estimated value. Meanwhile, under polyculture, submitting more applications increases the likelihood that an applicant will receive a higher estimated value, since estimated values are drawn independently. This shown in Figure 3. The full extended model and results are given in Appendix A.

---

Monoculture Polyculture: ML--Based Evaluations (ACSincome Texas)
monoculture
polyculture
0.64
Accursy
0.50
10
12
21
23
24
Average Benk maach
22-
2.-
2.5
10
24 25
27 20 29
Subsuts of Modills
Figure 4: Each column corresponds to random subset of ML models. Red dots correspond to markets where all firms use the same (1 of the 5) MI. models to rank applicants (monoculture). Blue dots correspond to markets where all firms use different MI. model to rank applicants (polyculture). The top figure illustrates the accuracy of each market (the percentage of matehed applicants with positive label); here, polyculture outperforms monoculture, as predicted by Theorem 1. The bottom figure illustrates the average rank choice of applicant matches; here, monoculture outperforms polyculture, as predicted by Theorem 2. See Section 5 for details.
5 Computational Experiments
We provide an overview of our computational experiments, with full details in Appendices C and D. Code reproduce our experiments (and all other figures) is available at publicly-availale repository.' The code can also be adapted to test further variations in market settings.
ML Simulations: ACSIncome We test our theoretical predictions in a setting where preference approximation is done via ML models. Applicants have 0-1 true values, and firms rank applicants based on a prediction outputted by an ML model (following [II]. We consider models using different sets of features, and compare markets where firms use different models to evaluate applicants (polyculture) and markets where firms use the same model (monoculture). We use the ACSIncome dataset- specificclliii.............. individuals from Texas in 2018 [19]. (We also perform experiments using data from California; see Appendix C.) The ACSIncome dataset has 10 features that are used to predict a binary 0-1 outcome. For each of the (19) = 45 pairs of features, we train a logistic regression model using 90 percent train split. We then evaluate markets where each applicant corresponds to point in the test split. This yields markets with 13,593 total applicants, of which 5,055 have value I and 8,538 have value O. We assume that there are 5 firms, each with capacity 1000, and that applicants have uniformly random preferences over these firms. Each the 45 models yields a monoculture market in which all 5 firms that same model to rank applicants. We let the accuracy of a single model be the average value matched applicants in the corresponding monoculture market (i.e., the percentage of matched applicants with value 1). We then focus our analysis on the 20 highest-accuracy models (roughly speaking, the models that firms may consider using).
From these 20 models, we randomly select 50 subsets of 5 models that differ by at most 0.05 in accuracy, producing subsets "candidate models." (If the range of accuracies is too large, then this means that one model may be clearly superior than the others.) For each subset, we consider the 5 corresponding monoculture markets (where each firm uses the same model to evaluate applicants), and 1 corresponding polyculture market (where each firm uses different model). For each market, we plot (1) the average value of matched applicants (i.c., accuracy), ), and (2) the average firm rank among matched applicants (testing Theorems and 2 respectively). These plots are given in Figure 4, where each column corresponds to one subset 5 models. As Theorems and 2 predict, polyculture outperform monoculture in terms of accuracy, but monoculture outperforms polyculture in terms of
battps://githin com/ com/kennylpeng/neee wwapnn///oooclttto ture person's 's income above threshold.
In particular, the task is to predict whether

---

Correlated Applicant Preferences Our theoretical results are in setting where applicants have uniformly random preferences over firms-i.e, no firm on average more desirable than any other. While this assumption is common in the matching literature (e.g., much of the work single versus multiple tic- tic-breaking) for thcoretical tractability, one concern is that our insights do not extend beyond rank of applicant matches. Indeed, for 47 out of 50 subsets of models, the polyculture market is more accurate than all monoculture markets (this effect present but less strong for California") ): for 50 out of 50 subsets of models, the monoculure market produces better average applicant outcomes (indeed, matched applicants almost always match to their top choice). We also test theoretical predictions of Theorem 3 under this setup, detailed in Appendix C. Further experiments in which we varied applicant preferences and firm capacities yielded similar qualitative results.
this assumption. Here, we test the predictions of our main results in broader settings,
We consider computational experiments in which applicants have correlated preferences over firms. To introduce correlation, we follow Ashlagi et al. [8] in using random utility model adopted from Hitsch al. [26], where each applicant additional has a "location" parameter drawn uniform at random, and each firm has a "vertical quality" and a "location" parameter. Setup details and experimental results are given Appendix D. Simulations show that the results extend to the full range of component weights considered. In particular, Figures 7 to 10 demonstrate that the (directional) results of Theorems 1, and 3 are robust to correlation in applicant preferences. Experiments in which we further varied firm capacities revealed similar qualitative results.
6 Conclusion
In this paper, we studied the effects of algorithmic monoculture by employing a matching markets model. This allowed us capture a key feature of domains that may be affected by monoeulture: competition between and the limited capacity of decision-maken (firms, colleges). By incorporating these features, and by considering large markets with many participants, we strengthened, challenged, and expanded upon the existing understanding of monoculture. We presented three main theoretical findings, which we verified in computational experiments. All else equal, monoculture (1) selects less- eessfrreer applicants, (2) yields higher overall applicant welfare, though effects for individual applicants depend on their value decision-makers makers and risk tolerance, and (3) is more robust to differences in the number of applications submitted by different applicants.
Limitations The theoretical results we presented are derived in a setting with strong assumptions. The first assumption is of homogeneous firms -that students have uniformly random preferences over firms and that firms have equal capacities. The intuition behind the theoretical results suggest robustness to this assumption- a claim supported by computational experiments, which consider varying structures of correlation in student preferences (as well as estimated values derived from MI. models rather than i.i.d. noise). A second assumption is of maximum--oncentraate comparison to the homogeneous firms assumption, it should be emphasized that Theorem does not necessarily generalize beyond this assumption, as suggested by some of our empirical results (see Appendix C for ML experiments for the California subset of the data). In fact, our follow-up work demonstrates that long-tailed noise results in the opposite finding in Theorem 1 [40]. More broadly, the model we present does not consider other relevant aspects of matching markets such as biases in evaluations, heterogeneity across different groups of applicants, and search frictions. Studying monoculture in these broader settings is an interesting question for future work.
noise. In
Broader Impacts Our work analyzes the emerging concern of algorithmic monoculture, in which many decision-maken. rely on the same algorithm to evaluate individuals. Our work aims to build a stronger understanding of the potential risks of algorithmic monoculture, with the goal of creating positive societal impact by informing potential regulatory decisions. Our work is not comprehensive; in particular, our analysis focuses on quantitative measures of welfare, and does not consider rights- or claims based approaches (see [32]) that may be especially relevant in high-stakes settings.
*In California, for 19 out of 50 subsets of models, the polyculture market is more accurate than all monoculture markets and for 44 out of 50 subsets of models, the polyculture market outperforms the average of the 5 monoculture markets. This suggests that a "weak" version of Theorem holds broadly. Importantly, this may due a lack of strict adherence to the assumption that noise is moxcennnen..,aing, which Theorem requires.
10

---

Acknowledgments
We especially thank S. Nageeb Ali, Nick Arnosti, Rishi Bommasani, Kathleen Creel, Sophie Green- wood, Shomik Jain, Jon Kleinberg, Rajiv Movva, Manish Raghavan, Ran Shorrer, and Ashia Wilson for helpful feedback and discussion. NG also thanks Itai Ashlagi for explaining school matching tiebreaking to him many years ago. We also thank participants of the Digital Life Initiative seminar, the Marketplace Innovation Workshop, and the ESIF Economics and AL+ML Meeting for thoughtful questions and feedback. KP is supported by the Digital Life Initiative fellowship. NG is supported by NSF CAREER I1S-2339427, and Cornell Tech Urban Tech Hub, Meta, and Amazon research awards.
References
[1] A. Abdulkadiroglu and T. Sönmez. School choice: A mechanism design approach. American Economic Review, 93(3)-229-1) 747, 2003.
[2] A. Abdulkadiroğlu, P. A. Pathak, and A. E. Roth. Strategy versus efficiency in matching with indifferences: Redesigning the nyc high school match. American Economic Review, 9955):155411778 2009.
[3] A. Abdulkadiroğlu, Y.K.. Che, and Y. Yasuda. Expanding "choice" in school choice. American Economic Journal: Microeconomics, 7(1):1-42, 2015.
S. N. Ali and R. I. Shorrer. The college portfolio problem. Technical report, Working paper, Penn Statc.[566), 2021.
M. Allman, I. Ashlagi, and A. Nikzad. On rank dominance of tie-hreaking rules. Theoretical Economics, 182))77777748, 2023.
[6] N. Aroosti. continuum model of stable matching with finite capacities, arXiv preprint arXiv:2205.1288. 2022.
[7] N. Arnosti. Lottery design for school choice. Management Science, 69(1):244- 2023.
[8] I. Ashlagi, Y. Kanoria, and J. D. Leshno. Unbalanced random matching markets: The stark effect of competition, Journal of Political Economy, 129(19) 2017.
I. Ashlagi, A. Nikzad, and A. Romm. Assigning more students their top choices: comparison of tic- breaking rules. Games and Economic Behavior, 1 11::167-187, 2019.
[10] E. M. Azevedo and J. Leshno. A supply and demand framework for two-sided matching markets. Journal of Political Economy, 12355):1235-D1 1268, 2016.
[11] R. Bommasani, K. A. Creel, A. Kumar, D. Jurafsky, and Liang. Picking on same person: Does algorithmic monoculture lead to outcome homogenization? Advances in Neural Information Processing Systems, 14:3663-36788 2022.
[12] F. C. Capen, R. V. Clapp, and W. M. Camphell. Competitive bidding in high-risk situations. Journal of petroleum technology, 2306):641-655 1971.
[13] R. Castera, P. Loiseau, and B. S. Pradelski. Statistical discrimination in stable matchings. In Proceedings of the 23rd ACM Conference Economics and Computation, pages 373 3744, 2022.
[14] H. Chade and L. Smith. Simultaneous search. Econometrica, (945):1293-13000 2006.
[15] J. C. Cox and R. M. Isaac. In search of the winner's curse. Economic Inquiry, 22(4):579-592, 1984.
[16] K. Creel and D. Hellman. The algorithmic leviathan: Arbitrariness, fairness, and opportunity algorithmic dccision-matee making systems. Canadian Journal of Philosophy, 52(1))26-43, 2022.
[17] X. Dai and M. Jordan. Learning strategies in decentralized matching markets under uncertain preferences. The Journal of Machine Learning Research, 1286):11806111 11855, 2021.
[18] M. De Haan, P. A. Gautier, H. Oosterbeck, and B. Van der Klaauw. The performance of school assignment mechanisms in practice. Journal of Political Economy, 131(2)3388445 2023.
[19] F. Ding, M. Hardt. J. Miller, and L. Schmidt, Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.

---

[20] V. Emelianov, N. Gast, K. P. Gummadi, and P. Loiseau. On fair selection in the presence of implicit and differential variance. Artificial Intelligence, 302:103609, 2022.
[21] H. Fang and A. Moro. Theories of statistical discrimination and affirmative action: A survey, Handbook of social economics, 1:133-200, 2011.
[22] J. Fishkin. Bottlenecks: new theory of equal opportunity. Oxford University Press, USA, 2014.
[23] N. Garg, H. Li, and F. Monachou. Standardized tests and affirmative action:
The role of bias and variance. In Proceedings of the 2021 ACM Conference on Fairnes,, Accountabiliry, and Transparency, FAceT '21, page 261, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383097. doi:
021144/344218834455555
URL https://doi. org/10. 14445/442288834456888 3445889.
[24] L. Haan and A. Ferreira. Extreme value theory: introduction, volume 3. Springer, 2006.
[25] G. Haeringer and F. Klijn. Constrained school choice. Journal of Economic theory, 144(5):121--194) 2009.
[26] G. J. Hitsch, A. Hortaçsu, and D. Aricly. Matching and sorting in online dating. American Economic Review, 100(1):100-16,, 2010.
[27] N. Immorlica and M. Mahdian. Marriage, honesty, and stability. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003.
[28] N. Immorlica, J. Leshno, Lo, and B. Lucier. Information acquisition in matching markets: The role of price discovery. Available at SSRN 3705049, 2020.
[29] S, lonescu, Y. Du, K. Joseph, and A. Hannák. Incentives in two-sided matching markets with prediction- enhanced preference-formation arXiv preprint wexXix:2009.78.:0 2021.
[30] M. Jagadeesan, M. I. Jordan, J. Steinhardt, and N. Haghtalab. Improved bayes risk can yield reduced social welfare under competition. arXiv preprint arXiv:2306. 140.:00036.1670, 2023.
[31] S. Jain, V. Suriyakumar, and A. Wilson. Algorithmic pluralism: A structural approach towards equal opportunity. arXiv preprint Xiv:22005.0817 2023.
[32] S. Jain, K. Creel, and A. Wilson. Scarce resource allocations that rely on machine learning should be randomized. arXiv preprint arXiv:2404.08592 2024.
[33] M. Y. Jeloudar, I. Lo, T. Pollner, and A. Saberi. Decentralized matching in probabilistic environment. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 635-653, 2021.
[34] B. Kim, M. Freeman, Kajikawa, H. Karimi, and P. Magouirk. First-year applications per ap- plicant. Common App. 2022. https://s3. http::///33uu-uest--22 amazonaws hann/ca.. row.ca.researrch......mm..om.mc. Research, BeicchBBries_eeeeeeeee
publish/ habbisshh.publish/ 12_099_11______01000022222001 Apwp__pppp______ Bttplppsseee_ppp_eeee haw.eerr..ppllccttteeeeererrrrre .df.
ResearchBrief.
[35] J. Kleinberg and M. Raghavan. Algorithmic monoculture and social welfare. Proceedings of the National Academy of Sciences, (0022))e221134011110 18, 2021.
[36] L. T. Liu, H. Mania, and M. Jordan. Competing bandits in matching markets. In International Conference Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[37] I.. T. Liu, F. Ruan, H. Mania, and M. I, Jordan. Bandit learning in decentralized matching markets. The Journal of Machine Learning Research, 22(1):9612-966 9645, 2021.
[38] Z. Liu and N. Garg. Test-optional policies: Overcoming strategic behavior and informational gaps. In Pro- ceedings of the 1st ACM Conference on Equity and Access in Algorithums, Mechanisms, and Optimization, EAAMO '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385534, doi: 10.1 145/3465416.3483299
URL https:///oi. org 10. 1145/3465416 3483293.
[39] M. Niu, S. Kannan, A. Roth, and R. Vohra. Best all: Equity and accuracy of standardized test score reporting. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Trans- parency, FAceT '22, page 574-586, New York, NY, USA, 2022. Association for Computing Machinery. URL https: //doi. http:://oooo..oo....///././////. 11g/110.114//353145
ISBN 9781450393522. doi: 05.1145/3531146.5522 3533121.
[40] K. Peng and N. Garg. Wisdom and foolishness of noisy matching markets. arXiv preprint arX1v:4402.16771, 2024.
12

---

[41] B. Pitel. The average number of stable matchings. SIAM Journal on Discrete Muthematicc, 2(4):530-549,
1989.
[42] R. H. Thaler. Anomalies: The winner's is curse. Journal of economic perspectives, 2(1):191-202, 1988.
[43] C. Toups, R. Bommasani, K. A. Creel, S. H. Bana, D. Jurafsky, and P. Liang. Ecosystem-level analysis of deployed machine learning reveals homogeneous outcomes, arXiv preprint arXiv:2307.05882, 2023.
[44] S. Wood.
Colleges with the highest application fees. U.S. News & World Report,
2022. URI. https://: http://wwwwwuuwws.e.eu// usnews. caneewss.cmmeeeeeee ceathcaatioobbestccolggeggee taaeeesttte-shrt--eeeee short-list- cirtt-iitcoolleee
articles/colleges with- tee-theeeheeeeeee highest- applicationnfees.
13

---

A An Extension: Differential Application Access
We now consider when different applicants can apply to different numbers of firms (analogously, colleges)-whitee which refer differential application access. In particular, we assume some discrete probability distribution A over 21,2,-. ......., m that determines the number of firms an applicant can apply In particular, an applicant with value can apply to k(v) firms, where k(v) is drawn independently from K. All other aspects of our model remain the same.
Under both monoculture and polyculture there is natural Nash equilibrium in which applicants all apply to their top firms. this equilibrium, we find that applicants who can apply to more firms benefit under polyculture, producing inequitable outcomes. This is not true under monoculture. Consequently, while firm welfare not harmed when applicants can apply to a different number of firms under monoculture, it is harmed under polyculture. Together, these results suggest that monoculture is more robust than polyculture with respect to differential application access.
A.1 Model setup
We begin by instantiating differential application access within our model. An applicant v who can apply k firms must choose application strategy (i.e., which & firms apply to). A strategy profile is given by vector of maps S (S1, S2, Sm). where S₁ R x R + {S E 2 |S| = k}. Therefore, an applicant who who has value and preference ordering > and who can apply firms applies to the firms in (v, Therefore, strategy profile uniquely determines where an applicant with given value, preference list, and level of application access applies.
We will focus on the strategy profile S such that Se(u,>> >> to Therefore, strategies do not depend all We will later show that this intuitive set of strategies forms a Nash equilibrium. Fixing this strategy profile S, we can now define ((v) for monoculture and polyculture in the presence of differential application access.
gives the most preferred firms according
Monoculture with differential application access. Define
i mo (v) = (>,
(10)
where
X f SuCo)( S
E. = -o
(11)
for > drawn uniformly at random from R., k(v) drawn from and X drawn from D. As before, an applicant with value v is given a random preference ordering over firms. However, now the applicant's estimated values across firms depends also on random draw from K, which determines how many firms they can apply to. Recall that e gives the vector of estimated values of an applicant across firms. Therefore, under monoculture, this estimated value is shared across the firms the applicant applies to (which are the applicant's 's top-k(v) most preferred firms), but is -o at other firms (meaning that the applicant will never be matched firms they do not apply to).
Polyculture with differential application access. Define
ppoly xe (v)) = (x.e)
(12)
where
U 1 X, =
f E (v.> 000 f& (u,))(,))
(13)
for drawn uniformly at random from R, k(v) drawn from K, and X., Xmm applicant gets an independently drawn estimated value at each firm they apply to.
iid
D. Here, an
We now give the Equal Cutoffs Lemma in this setting, which again, is consequence of symmetry in applicants' preferences over firms.
Lemma 5 (Equal Cutoffs Lemma for Differential Application Access). If0 E (Omono, xp then there is unique vector of market-clearing cutoffs P, and P1 Pa P
14

---

We denote these unique stable matchings by Mmono... and Mpoly.x: with corresponding shared cutoffs P Pmnno,x and P poly,x- Recall that under our abuse of notation, Mmono,,: (v) := Mmono, (f (ono,, x (v) and /ppoly.dd (v) Mpoly. (0 poly.,x (r)) are the random variables representing where is matched under monoculture and polyculture.
The strategy profile we consider here forms an ex-ante Nash equilibrium, meaning that no applicants- prior to knowing their estimated values at each firm-would apply to set of firms different from their top k.
Proposition (Nash Equilibrium), For any K, and under both monoculture and polyculture, no applicant benefits ex-ante by deviating from S.
This is an immediate consequence of Lemma 5. Since cutoffs at all firms are the same, an applicant strictly harmed by applying to a set of firms other than their top k. since doing does not increase their chances of being matched to any given firm (or set of firms).
A.2 Analysis
We now show that while monoculture is robust to differential application access, polyculture is not. Our main result in this section is that under monoculture, applicants who apply to more firms do not gain advantage, while under polyculture, applicants who apply more firms are more likely to be matched. Again recall that (X_,X,) is the interval on which D is supported.
Theorem (Differential Application Access in Monoculture and Polyculture). The following hold:
(i) In monoculture, applicants who apply to more firms do not gain advantage: For all v,
Pr|pmoonox< E F
F ((())) = k] = Pri[Pmono (v) E F]
(14)
is constant in k.
(ii) In polyculture, applicants who apply to more firms gain an advantage: For all v,
Prijupoly (w)) F(b(e) = k]
(15)
is increasing in k and strictly increasing in l. for U (Ppoly.x X Ppoyy, X-).
This result is illustrated in Figure 3, which shows that while the probability of matching does not depend significantly k under monoculture, is increasing in & under polyculture. A consequence of the result is that students with higher values can go unmatched while students with lower values but who submit more applications may be matched. From the firm (or college) perspective, this means that the ability to distinguish higher- and lower-value applicants is diminished. We demonstrate this in our computational experiments (see, e.g., Figure 10). This further suggests that the strong result of Theorem is not robust to differential application access, and as a consequence, firms and colleges under polyculture are incentivized to "level the playing field" ensure that applicants each submit similar number of total applications.
Notice that, as in Theorem 1, the results here hold independently of the relationship between the noise distributions in monoculture and polyculture.
B Extended Related Work
Here, we further detail our relationship the algorithmic monoculture and matching markets literature. We conclude with discussion of how our work bridges these two lines of work, and reconciles some competing intuitions.
Algorithmic monoculture. Closest to our work is that of Kleinberg and Raghavan [35], who introduce a model of algorithmic monoculture in which there are two deecssin-maaeen who each hire one applicant. As in our model, instantiated as a ranked list. However, each decision-maker only has access to noisy version of this ranked list: they each can either use an idiosyncratic noisy list or a common (but more accurate) noisy list. One decision-man maker then selects the top applicant on their list. The second decision-mmker chooses the top applicant on their list that has not yet been chosen. Welfare is measured by the
makers have shared true preferences over a set of applicants,
15

---

rank of the chosen applicants according to the true preference list. Kleinberg and Raghavan [35] makers can be better off if they both use their idiosyncratic (more noisy)
show that the lists in comparison to using the shared list. In our work, we show that this effect becomes more pronounced when considering a large market with many decision-maken and applicants. By building on the model of Azevedo and Leshno [10], we overcome issues of tractability, while also gaining a cleaner interpretation for why the effect found in Kleinberg and Raghavan [35] holds, in terms of distributional order statistics and their effect on admission thresholds for each decision-maker. Moreover, we are able to model two-sided effects, where applicants also have preferences over eerision-makers. Absent in our work is the sthneethe analysis of Kleinberg and Raghavan [35], who show that there are cases where both decision-make makers use the shared list in the Nash equilibrium, even when both would be better off using idiosyncratic lists.
While Kleinberg and Raghavan [35] focus on the welfare of decision- makers, Bommasani et al. [11] consider the effect of algorithmic monoculture on applicants. In their setup, applicants are subject to binary decisions from several decision-maken They define the rate of systemic failure to be the probability that randomly drawn applicant receives negative decision from all computational experiments, they provide evidence that when decision-maker train machine learning models using the same data, the rate of systemic failure tends to increase. Toups et al. [43] document homogeneous outcomes in several commercial APIs, which they suggest could be a consequence of algorithmic monoculture arising from shared data or model usage. These empirical studies do not consider market effects such as fixed capacity constraints of secision-makers in the setup we consider, since decision decision-makers have fixed capacity, the number of applicants who experience systemic failure remains constant (assuming that applicants too only "accept" one offer).
In
Indeed, decision makerr capacity constraints play an important part in our results. Jagadeesan et al. [30] consider a different structure, in which several "model-providers" compete over users. In their setting, user (noisily) prefers model-providers that produce more accurate prediction for the user. A key difference between this model and ours is that the analog to the decision- provider) does not have limited capacity; rather, single model-provider can serve an unlimited number of users. Moreover, the model provider does not seek to evaluate users, but rather to make predictions in their service. Jagadeesan et al. [30] shows that as the ability of model-provide produce more accurate predictions increases overall, the social welfare of users can decrease as a consequence of growing homogeneity in predictions. (Users benefit from diversity since it means that there is likely at least one model provider that is accurate for them.) We also note that in Jagadeesan et al. [30]'s 'ss model, monoculture arises endogenously, while monoculture is specified exogenously in our model.
(the model
to
An emerging line of work also considers normative aspects of monoculture. Creel and Hellman [16] argue that arbilrariness in algorithmic decision-making is not generally of moral concern- however, they argue, arbitrary decision-maiee -making scale is of concern, since it can result in systemic exclusion: "Exclusion from a broad swath of opportunity in an important sector of life is likely to be morally problematic." Our work challenges the implicit assumption that the widespread adoption of a common algorithm necessarily increases the number of individuals excluded from all opportunities. When the number of "opportunities" (positions at firm, seats college) is constant, the number of individuals that receive these opportunities (and who are denied from all opportunities) should remain constant. Of course, not all domains of algorithmic decision-making share this feature. In the domains that do, our work suggests systemic exclusion is not clearly the primary concern, but rather who faces systemic exclusion, as well the other measures of welfare (e.g., worker power). Jain et al. [31] argue that al algorithmic decision-making should be viewed through the lens of opportunity pluralism [22]. A key implication of their argument that the use of algorithmic decision-mabee multiple decision-maker should be analyzed with respect to its impact on how opportunities are restricted large. (One possible intervention is to randomize outcomes, as argued for by Jain et al. [32].) Our work contributes to this type of analysis, helping develop more precise understanding of the effects of algorithmic decision decision-making at a system level.
by one or
Matching markets. The model we introduce here builds on the broader analysis of matching markets. In particular, a substantial literature analyzes the outcomes of random matching markets. Theoretical results have established the expected number of stable matchings (i.e., the size of the core) as well as the distribution of outcomes for each participant (e.g., Pittel [41], Immorlica and Mahdian [27], Ashlagi et al. [8]).
16

---

We depart from this literature by modeling the process of preference approximation. Whereas existing analysis focuses on single set of stated preferences, we assume that participants (specifically, decision-makers) can only obtain or communicate an approximation of their own preferences. As result, stable matchings are computed with respect to these approximate preferences. We then analyze the matching outcome with respect to the true preferences of participants. Our model can thus be viewed as having two components:
First, preference approximation model, in which each participant acquires approximate knowledge of their true preferences over the other side." 9
Second, stable matching model, which takes input the approximate preferences of participants, and outputs a stable matching with respect to these preferences.
For the stable matching model, we adopt model with a continuum of students [3, 10). This allows for an especially tractable analysis. A limitation of this approach is that we do not capture the effects of stochasticity in small markets (particularly, where the capacity of decision-makers is small). In our framework, it is possible to substitute a stable matching model that is more amenable to such analysis, such as the standard finite model or that of Arnosti [6].
An emerging line of work similarly considers matching markets (both centralized and decentralized) in which participants are unsure of their true preferences or broader information about the market. Existing work primarily focuses on settings where participants gain information sequentially (e.g.. Liu et al. [36, 37], Dai and Jordan [17]. Ionescu et al. [29]. Jeloudar et al. [33], Immorlica et al. [28]). Our work focuses instead on one-shot setting, where we analyze the outcomes of matchings that arise given the current information of each participant.
Closest to our work is a model introduced by Castera et al. [13] to analyze statistical discrimination' 10 in stable matching. In their model, the values of applicants from two groups are estimated by two decision-maker Like us, they leverage a continuum model of applicants. Their findings focus on aggregate measures of applicant-side welfare across groups They show, for example, that the group of applicants evaluated with less correlation is matched with higher probability. More directly related to our work, they show that decreased correlation (even in one group), reduces the number of applicants who receive their top choice; this parallels our finding in Theorem 2(i),, which implies that fewer applicants are matched to their top choice under polyculture (i.e., when there is total correlation). This finding reflects general result developed in the school choice literature: that increasing correlation in how decision-makers evaluate applicants also increases the total number of applicants matched to their top choice. We discuss this line of literature next.
Tie-breaking rules in school choice. Our work has close connections to the matching markets literature studying tie-breaking rules in the context of school choice, where lottery numbers are often used to determine the school preferences inputted into stable matching mechanisms [1]. A significant line of empirical and theoretical work compares the use of single tie-breaking (STB) where each student is assigned single lottery number across all schools, and multiple tie-breaking (MTB) where each student is assigned a different random lottery number for each school.
A main finding across this literature is that STB results in more students being assigned to their top choice school (e.g., Abdulkadiroglu et al. [2], De Haan et al. [18], Ashlagi et al. [9], Arnosti [7], Allman et al. [5]). This finding is echoed in our Theorem 2. Indeed, one may directly compare monoculture to STB, since each applicant in our model has single estimated value used by all decision-makers From the perspective of population-leve statistics of overall student welfare, monoculture and STB are both equivalent to a model in which all firms (schools) have the same preferences over applicants. At high level, both sets of results rely on a similar intuition: in settings
"Noe that in our model, only the preferences of decision-makers "approximated," " while applicants assumed know their own true preferences. This preference approximation further relates recent literature modeling the role of standardized testing admissions, where tests (among other features) help schools estimate their value for each applicant Emelianov et al. [20], Garg et al. [23], Liu and Garg [38], Niu et al. [39]. However, studying more than two schools in this framework has proven theoretically challenging. Castera et al. [13] analyzes related model to understand the effect of statistical discrimination in matching; they too focus on a two school setting. broader insight our analysis grows large can be more tractable than the strictly finite setting.
the limiting regime in which the number of schools
See Fang and Moro [21] for survey of the statistical discrimination literature.
17

---

with two-sided preferences, applicants as a whole benefit if their preferences most influence matches; this happens when schools share preferences (as induced by either monoculture or STB, but not by polyculture or MTB).
Our setup departs from the tie-breaking literature by having each applicant's estimate depend on the applicant's 's true value. Thus, the "noise" in their estimate (the equivalent of tie-breaking score) is not just differentiating between equivalent applicants: it can move a lower-value applicant over higher-value one. As a result, our analysis further focuses on comparing monoculture and polyculture from the perspective of an individual applicant with a particular value. This also allows us to analyze welfare from the perspective of the fimm (who prefer to be matched with applicants of higher true value). Polyculture and MTB also share differences even at the population level; in polyculture, there remains some correlation between "lottery numbers" across schools (firms) depending on the applicant's true value.
In addition to showing that STB results in more students being matched to their top choice," !I Arnosti [7] shows that students who list many schools are more likely to be matched under MTB, while students who list few schools are more likely to be matched under STB. This accords with our finding in Theorem 3 that applicants who submit more applications gain an advantage under polyculture but not under monoculture. We show that this further implies that (1) students with lower true values but who submit more applications can be matched over students with higher true values but who submit fewer applications, and that (2) differences in the number of applications submitted by students reduces firm welfare under polycultrre. but not under monoculture.
We anticipate that the techniques developed in the study of tie-breaking rules may be useful for analyzing outcomes in algorithmic monoculture, especially the applicant side. The introduction of heterogeneity on the applicant side adds a dimension of analysis beyond what is considered by the existing tie-breaking literature, and which is ripe for further inquiry.
Bridging the literatures. Our work bridges two lines of work: algorithmic monoculture and matching markets. We briefly elaborate the nature of this connection. The initial inquiry into algorithmic monoculture has been limited by lack of market-level analysis. The choice of a firm to adopt a certain hiring algorithm not only affects outcomes at that firm, but also other firms. The nature of this effect is further dictated by the preferences of applicants. We have shown how machinery in the matching markets literature is well-equipped to handle these effects. Adopting this machinery enhances our understanding of algorithmic monoculture. While the algorithmic monoculture literature has largely pointed to negative effects of monoculture, both on the firm and applicant side, we showed that monoculture can have positive welfare effects for applicants- a competing intuition that can be found the matching markets literature on tie-breaking, which has found that correlation in school-side preferences can benefit students in a school choice setting. In this way, we anticipate that the matching markets literature can provide further insight into the emerging study of algorithmic monocultur.
At the same time, our work expands the scope of questions that can be analyzed using a matching markets framework. While existing work in matching markets largely takes preferences at face value, we further model a stage of preference approximation. in which participants form noisy approximations of their true preferences. In this work, we focused on correlation in this approximation process. but the question can be posed more generally. Our results suggest that the structure of the approximation process can have intriguing consequences on the quality of the resulting matching.
C Computational Experiments: ML-Based Evaluations
Details of Data and Experimental Setup We consider the ACSIncome dataset [19], which consists of predicting whether individual makes more than 50,000 dollars based on 10 features, including demographic features. Importantly, this is not a legitimate setup for making any assessment of an individual's employability, but rather intended as toy task in which to demonstrate how our theoretical setup can transfer to a ML-based setup. The data is available via the Python package folktables." The package is released under MIT license. The data may be restricted to
"In fact, Arnosti [7] shows more precise results, characterizing the probability that a student is matched to one of their top k choices.
Ptttps:/
/ / /gi thub. cwt///ooaaa.foomaaatoooooloooaa.
18

---

Monoculture Polyculture: ML-Based Evaluations (ACSincome California)
monoculture
polyculture
Acturacy
0.70
0.66
22
2.50
weonge hatt Waach
2.25
2.00
1.75
1.50
Subsers Modess
Figure 5: Each column corresponds to random subset of ML models. Red dots correspond to markets where all firms the same (1 of the 5) MI. models to rank applicants (monoculture). Blue dots correspond to markets where all firms use different MI. model to rank applicants (polyculture). The top figure illustrates the accuracy of each market (the percentage of matehed applicants with positive label); here, polyculture outperforms monoculture, as predicted by Theorem 1. The bottom figure illustrates the average rank choice of applicant matches; here, monoculture outperforms polyculture, as predicted by Theorem 2. See Appendix C for details.
particular states and years. We focus on two subsets of the data: Texas in 2018 and California in 2018, two subsets which are analyzed by [19] (among many other subsets).
The models we train use the default sklearn Logistic Regression hyperparameters. Additional optimization was not necessary for our purposes, since it was not important to improve upon the accuracy of individual models, but rather understand matching markets in which MI. models are used to form preferences. All experiments can be completed on typical laptop in at most a few hours.
Results for California In addition to the Texas 2018 data, we perform the same experiments on the California 2018 data. Again, for each of the (19) = 45 pairs of features, we train a logistic regression model using 90 percent train split. We then evaluate markets where each applicant corresponds to a point in the test split. This yields markets with 19,567 total applicants, of which 7,933 have value and 11.634 have value We assume that there are firms, each with capacity 1000, and that applicants have uniformly random preferences over these firms. Each of the 45 models yields monoculture market in which all firms use that same model to rank applicants. We let the accuracy of a single model be the average value of matched applicants in the corresponding monoculture market. This gives the percentage of matched applicants with value in a market where all firms used that model. We then focus our analysis on the 20 highest-accuraan models (roughly speaking, the models that firms may consider using).
From these 20 models, we randomly select 50 subsets of 5 models that differ by at most 0.05 in accuracy, producing subsets of "candidate models." (If the range of accuracies is large, then this means that one model may be clearly superior than the others.) For each subset, we consider the corresponding monoculture markets (where each firm uses the same model to evaluate applicants). and corresponding polyculture market (where each firm uses a different model). For each market, we plot (I) the average value of matched applicants, and (2) the average firm rank among matched applicants (testing Theorems 1 and 2 respectively). These plots are given in Figure 4, where each column corresponds to one subset of models. As Theorems and 2 predict, polyculture outperform monoculture in terms of accuracy. but monoculture outperforms polyculture in terms of rank of applicant matches. Indeed, for 19 out of 50 subsets of models, the polyculture market more accurate than all monoculture markets and for 44 out of 50 subsets of models, the polyculture market outperforms the average of the monoculture markets. This suggests that a "weak" version of Theorem I holds broadly. Again, for 50 out of 50 subsets of models, the monoculture market
19

---

Robusiness Under Differential Application Access: ML-Based Evaluations
monoculture
polyculture
Toxod
0.02
0.60
Caliomia
11
10
0.74
0.72
0.7
0.60
35
37
Subbnets Mudels
Figure 6: Each column corresponds to random subset of ML models. Red dots correspond to markets where all firms the same (1 of the 5) ML models to rank applicants (monoculture). Blue dots correspond markets where all firms use different ML model to rank applicants (polyculture). Both figures illustrate the accuracy of each market (the pereentage matched applicants with positive label). The top figure gives the Texas data, and the bottom figure gives the California data. Dots on the left side of cach column correspond to no differential application access, while the dots the right side of each column correspond to differential application access. One may observe that the blue dots change from the left the right side each column, indicating that polyculture less robust to differential application access.
produces better average applicant outcomes (indeed, matched applicants almost always match their top choice).
Testing Differential Application Access (Theorem 3) Using the same setup, we further test the prediction of Theorem 3, that monoculture more robust to differential application access than polyculture. Here, we allow each applicant apply le firms, where is drawn uniformly at random from {1, 2, 3, 4, 5.. Proposition 6 implies that (given the symmetric setup we consider here) the optimal strategy for an applicant who applies to & firms is to apply to their k most preferred firms. We then test the robustness of the accuracy of the markets considered above under this form of differential application access.
For the Texas data, the accuracy of polyculture markets has an average absolute change (between differential application access and differential application access) of 1.54%, while the average absolute change for monoculture markets is 0.056%. For California, these two figures are 0.58% and 0.061 % respectively. This is consistent with the prediction of Theorem 3 that monoculture is more robust under differential application access than polyculture.
D Computational Experiments: Correlated Preferences
In this section, we perform computational experiments test the accuracy of predictions from theoretical results in more general settings. We focus on our three broad theoretical findings: that all else equal, in comparison to polyculture, monoculture:
selects less-preferred applicants (Theorem 1),
matches more applicants their top choice, though effects for individual applicants vary depending on their value (Theorem 2),
is more robust to differential application access (Theorem 3).
All experiments below be completed typical laptop in at most few hours.
Correlated applicant preferences. We proved our theoretical results a setting where applicants have uniformly random preferences over firms. We consider computational experiments in which
20

---

Average Firm Welfare
Average Match Rank for Applicants
average match rank for applicants
average fim wellare
0.75
0.70
0.65
monoculture polyculture
monoculture polyculture
0.60
0.50
20
20
20
20
15
15 g
15
10
10
10
10 g
Figure The average percentile value matched applicants (left) and the average rank firms matched to applicants (right), as function of 3 and y. which control the level of global and local correlation between applicant preferences. (The case 9 = 0 corresponds to our theoretical setup.) For all choices of 3 and we consider here, average firm welfare is higher under polyculture while average applicant welfare is higher under monoculture (note that lower corresponds better outcome right plot).
applicants can have correlated preferences over firms. To introduce this correlation, we follow [8] in using a random utility model adopted from [26].
The model generates applicant preferences in the following way. Each applicant i has a characteristic x!P drawn independently from U(0, 1]. Each firm has characteristies, =f and z both drawn independently from UO, 1]. Then the utility applicant i for being matched to firm is
uu(f)= 3x7 7(x - +
(16)
where Eif drawn independently from the standard logistic distribution. Here, 2z is vertical measure of firm quality, shared by all applicants, / controls the level of correlation between preferences. xr and L are "locations" of the applicant and firm, and controls the preference for an applicant to be "close" to the firm. Eif accounts for other idiosyncratic factors.
When / y = 0, we recover the uniformly random preferences used in our theoretical analysis. When 3 grows large, preferences become fully correlated: applicants all have the same preferences. When increases, there is more correlation in preferences between "nearby" applicants.
Experiment details. We now consider a market which there are 1000 applicants and firms each with capacity 50. (So half of applicants are matched.) We let applicant values be distributed uniformly from 0 to (so 77 is the uniform measure on [0, 1]), and take the noise distribution D to be the Gaussian distribution (0, }). We vary 3 and between 0 and 20. The plots we show are all in this setting, and provide averages over 100 random instantiations of the market.
D.1 Firm welfare
We test our first prediction: that polyculture selects more-preferred applicants in comparison to monoculture. To do this, we compute the average percentile value applicants matched to firms, that higher average percentile corresponds to higher firm welfare. As shown in Figure 7 (left), average firm welfare is higher under polyculture across all 3 and y we consider. fact, experiments suggest that firm welfare in both monoculture and polyculture remains consistent regardless the correlation structure we choose.
D.2 Applicant welfare
We now test our second prediction: that monoculture yields higher total applicant welfare. Here, measure total applicant welfare as the average rank applicant matches-condithe on matching
In [8]. the model is used to generate preferences on both sides of the market: in our setting, we only use the model generate applicant-side side preferences, i.e., how applicants rank firms.
21

---

Probability of Matching to Top Choice
Probability of Matching
1.0
probability
0.6
monoculture
probabilitt
monoculture polyculture
0.6
0.4
polyculture
0.4
0.2
0.0
0.6 percentile value
1.0 0.8
0.4
02
0.0
0
10 B
15
0.0
1.0
percentile value
0.8
0.6
0.4
0.0
5
10
$
15
Figure 8: The probability an applicant matches to their top choice (right) and to any firm at all (right), as a function of the applicant's percentile true value and 5 the level of global correlation in applicant preferences.
with a firm, what is expected rank of an applicant's match according to their preference list? A lower average rank corresponds better applicant outcomes, since this means that applicants are on average matched to more- core--peferred options. As shown in Figure 7 (right), the average rank of applicant matches worse under polyculture than monoculture for all 3 and y we consider. Notice that for both monoculture and polyculture, the average rank of applicant matches increases as B increases. Intuitively, this is true because the increased correlation between applicant preferences means that it is harder for all applicants to receive their preferred options.
We further test more specific predictions from Theorem 2, that an applicant is more likely to be matched to their top choice under monoculture (Theorem 2())) and that some applicant's are more likely be matched overall under polyculture (Theorem 2(ii)), leading a non-strchastic--ominnnee result. Our experiments are plotted in Figure 8. We vary the level of global correlation 8 and consider the probability of matching conditional on an applicant's 's true value. Our experiments confirm the two predictions. Note that as / increases, the probability of an applicant matching to their top choice smaller both for monoculture and polyculture. Since many applicants share the same top choice, few applicants can be matched to their top choice.
D.3 Differential application access
We now test our third main theoretical prediction: that monoculture is more robust to polyculture with respect to variation in the number of applications submitted by different applicants. Recall that in order to study differential access, it is necessary to specify an application strategy for each applicant- for an applicant that can apply to k firms, which l: do they select? In our theoretical setup-where there was no correlation in applicant preferences-we benefited from the existence of a simple Nash equilibrium, where applicants all apply to their top k choices. Given arbitrary correlation structures, the characterization of Nash equilibria remains an open question, and an area of continued inquiry." 14
Therefore, we implement two heuristic strategies: applying one's k most-preferred firms, and applying to k randomly selected firms (in the order of the applicant's 's true preferences). The former, as we showed Proposition 6, is a Nash equilibrium when applicant preferences are fully uncorrelated (i.e.. when 3 = 0). Intuitively, this strategy performs poorly when preferences are correlated: applicants who have low value and who can only apply to one firm should not apply to their most preferred firm, which is likely to be highly competitive. In this case, the second heuristic strategy we propose, applying to randomly selected firms (in the true order of the applicant's preferences) likely to perform better. Roughly, applying randomly implements the commonly-used Seaach-math--sffeyy approach, which has also been theoretically justified by [4].
11114] and [4] consider the optimal choice firms to apply to when admissions probabilities are independent and correlated, respectively. Neither, however, consider interactions between the strategies of multiple applicants. [25] show the existence of Nash equilibria in the deferred acceptance algorithm (in addition to other mechanisms) when applicants only apply & firms. However, does not consider the stochasticity present in our model.
22

---

Applicants Who Submit More Applications Benefit More Under Polyculture
Applying to Top Choices
Applying Random Choices
advantage in prob. match
advanto 0 prob. match
0.6
0.40
0.5
0.35
0.30
0.4
monoculture
0.25
monoculture polyculture
0.3
polyculture
0.2
0.10
0.1
0.05
0.0
0.00
15
10
5
10
B
15
20
15
V
10
10
15 B
20
Figure Difference probability matching among applicants who can apply between and firms, and those who can apply to between I and firms. This difference is always higher in polyculture than in monoculture across the parameters we consider. This holds both when applicants apply to their top choices (lcft) and when they apply to random firms in their order of preferenee (right).
Change in Firm Welfare Under Differential Application Access
Applying to Top Choices
Applying Random Choices
change in firm welfare
change in firm welfare
0.01
0.00
0.00
-0.02
-0.01
-0.04
monoculture polyculture
-0.02
monoculture
-0.06
polyculture
-0.08
-.044
-0.00
-0.05
20
2015
10
15
20
10
15
20
The change college welfare moving from (1) market with no differential application access. to (2) a market with differential application access. Note that college welfare decreases more under polyculture. This holds both when applicants apply to their top choices (left) and when they apply to random firms in their order of preference (right).
Figure 10:
In our experiments, we consider x to the uniform distribution on {1, 21,2..... 10), so applicants are allowed apply to random number of firms between and 10. In Figure 9, we plot the difference the probability of matching between applicants who can apply to between and firms and applicants who can apply to between 1 and 5 firms. This is measure of the benefit accrued by an applicant who applies to more firms. larger difference is equivalent to less robustness to differential application access, since this implies that applicants who apply to more firms have larger chance of being matched. As shown in Figure 9, this difference is larger under polyculture than under monoculture for all choices of 3 and we consider. This holds both when applicants apply to their most preferref firms and random firms.
We further test our prediction that firm welfare is affected more by differential application access under polyculture than under monoculture. To do this, we consider the change in firm welfare when moving from "uniform application access" where all applicants apply to all firms to differential application access according k. As shown Figure 10, this change more significant under polyculture than under monoculture, for both application strategies. This supports prediction.
23

---

E
Preliminary Results and Proofs
E.1
Observations About Measures with Connected Support
To aid subsequent proofs, we recall our assumption on the probability measure v) (of student values) and the probability distribution D (the noise distribution); namely, that they have connected support. We then make two useful observations.
Let be the probability measure associated with D. Then we make the assumption that both r) and ı have connected support, where we mean that the smallest closed set of measure is an interval. Let these respective intervals be [V_, V+] and [X_,X4 X+J. (Note that V_, X_ may be equal -oo and V+, X+ may be equal to oo.) In what follows we let V and X be random variables distributed according to the probability measures and ग, and let Fy and Fx denote their cdfs.
Proposition The following hold:
(i) Fy is strictly increasing on the interval VV_V+), and (v(v) (0, when v (V_, V4).
(ii) Fx is strictly increasing on the interval (X=,X+), and Fx(x) E (0,1) when (X),
(iii) For all integers m 2 1, F& is strictly increasing on the interval xx)x and FX (x) E
(0, 1) when x E x+)-
Proof. We show the result for Fy; the result for Fx is (clearly) analogous.
First suppose that Fy were not strictly increasing on V-, V+, such that there exists v1, 02 such that V- < e1 < U2 < V4 and (v)) (v2) Then (7((1,)))) implies that n[VV,, V+] \ [01, v2]) = - 0 = 1, which contradicts the assumption that [V_, V4] is the smallest closed set of m7-maauuee 1.
Fv(22) - (v 0. This
To show that (v) E 1) when v E (V_,V+), it suffices to show that (v = 0 and (V+)+) 1. Assume otherwise, such that (v_V) or Fvv (V+) 1. This would imply that 7(V V+]) < 1, which gives contradiction.
Proposition Let I be an interval such that
In (V),
(17)
Then (!) > O.
Proof. There exists a, b such that V_ < a < b < V+ such that (a, C I V+). Therefore, m(T) > (((a, b)). We have that b)) = (b) - (a) > O, where we used that Fy strictly increasing on [V_, V-J, as shown in Proposition 7. This gives the result.
E.2 The Lattice Theorem for Stable Matchings
powerful result in the stable matching literature shows that stable matchings have a complete lattice structure. In this section, we state this result in our setup (Theorem A.1 in [10].. Consider the lattice operators and on cutoffs R,C where for set Z of cutoffs,
V VP) PEZ
P
sup Pj
(18)
PEZ
and
A = inf Ps- PEZ
(19)
PEZ
Proposition 9 (The Lattice Theorem). The set of market-clearing cutoffs forms a complete lattice with respect to V and as defined above.
For our purposes, this will useful to establish the two "Equal Cutoffs Lemmas" we prove (Lemma and Lemma 5), in which we show that our economies induce unique stable matchings, in which all cutoffs are equal. The high-level idea to show that the maximum and minimum cutoff vectors (1)
each comprised of identical cutoffs, and (2) coincide.
24

---

F Proofs for Section 4
We begin by proving the Equal Cutoff's Lemma for mono and ppoly.
Proof of Lemma 2. For now, consider generic & E { pplly). Let Z be the set of market-
clearing cutoffs. Then by symmetry, if P (P1. Pm)] E Z, then any permutation of P is also in Z. It follows that
sup P1
sup P3 =
sup Pm PEZ
(20)
PEZ
PeZ
and
inf P1 = inf P22 =.. inf Pm. PEZ
(21)
PEZ P+ and P_ respectively. These are the greatest and least elements of the com- plete lattice of market-clearing cutoffs. Therefore, suffices to show that P+ = P_. We show this separately for mono and 0poly.
PEZ
Call
these two common values
By Proposition 9,
(P+,..., ,P+); (P_....,, P-) E Z.
Case 1: Monoculture. Consider 0 m It suffices to show that P+ P_. Assume for sake of contradiction that P+ > P_. (By definition, P+ P-.) By the definition of market clearing, the total measure of students matched is equal to S under either (P....., P-) (P+.... PP).. Therefore.
/ Priu + X > P+]dn(v) = 5 / Pr(u+ + X P_)d((v)-
(22)
To give the desired contradiction, we show that
/ Pr|u + X P+] < / Pr(u + X P-)dn(v).
(23)
Clearly, Prfc + P+] S Pr(u + X > P-]. Therefore, it suffices to show that Pr(u + X >
P. Pr(u + X > P-] on set T of positive n-measure. We show this is the case for I
P_ X4, P_-)). X-). -XX..
We first show that the inequality is satisfied on I. Note that for E I, we have that P_ - v E (X X.). Therefore,
- P
u) 00
(24)
where the last inequality follows from observing that by P+ - P- by assumption and applying Proposition 7, which says that Fx is strictly increasing on (X_, X+).
It remains to show that the interval I has positive n-measure. We begin by showing that P_ V_ X_. This is true because for P S V_ + +X..
Pr(o x V x_ x-]dn(v) / dn(()) 1, (25)
Pr(u+ + X> P)dn(w)= 2 JR
J
contradicting the assumption that S < 1. Similarly, P_ < V4 + X4. It follows that P_ P_ P_ < V+ and P_ - -X_> V_. Therefore, the interval I = (P- - X+, P_ x-) intersects (V-, V+). So Proposition 8 implies that it has positive measure.
Case 2: Polyculture. The result holds analogously for Opolys where we replace with (m) (and thus Fx with F)))
suffices to show that P. = P_. Assume for sake of contradiction that P. P_. (By definition, P4 > P_.) By the definition of market clearing, the total measure of students matched is equal to S under either (P_.... .P) or (P+..... .P)). Therefore,
/ Pr|u + (m) > P_]dr(v).
Pr(u + (m) > P+)dn(v) = S =
(26)
To give the desired contradiction, we show that
Pr[v + (mm) > P+] P+]dn(v)= < Pr[u + ((m) > P-]
(27)
25

---

Clearly, Pr(u + X((m) > P+] I Pr(v + x(m) > P-]. Therefore, it suffices to show that Pr(v +
((m) > P+1 < Pr(u + X(m) > P-] on a set I of positive n-measure. We show this is the case for
T= X (P P-
We first show that the inequality is satisfied on Note that for E I, we have that P- - v E
(x), Therefore.
Pr(u + ((m) > P-1 - Pr[p + (mm) > = = -0)
0) Fx - v) > 0 (28)
where the last inequality follows from observing that by P+ - P by assumption and applying Proposition 7, which says that FX is strictly increasing on (X_,X-).
remains show that the interval has positive n-measure. We begin by showing that P- V_ + X_ This is true because for P S V- + X-,
Pr(c + x(m) > P] dn(v)) 2 Prfc+ + x(m) > V- + x-] x-]dd(()>> = dn(())) =1, (29) JR
contradicting the assumption that 1. Similarly, P_ V, + x. follows that P_-X, V+
and P_ X- > V_. Therefore, the interval I = (P- - X P_ -X-) intersects (V V+). So Proposition 8 implies that has positive measure.
As consequence of the above proof,
1y( (M(Pooon mono
X+,, Pmono X-])
(30)
and
(((Pol -x,, Ppoly - -x-)) > O,
(31)
which will be useful subsequent proofs.
Proof of Corollary 4. Noting that the total measure of students matched is the same under both monoculture and polyculture (equal to 5), we have, using (5) and (6) that
[ Pr[u + x Pmonol dn(u)= = S Pr(u + x > Ppoly] dn(v).
(32)
Assume for the sake of contradiction that Pmono 2 Ppoly. To give the desired contradiction, we will show that this implies
| Pr/u + X P Pmooo] du(()= < / Pr(u + x (m)) > Ppoly] dn(()).
(33)
Clearly,
Pr[c + X Pmoooo S Pr(v + ((m) Ppolyl
(34)
for all v. We now show that
Pr(o X > P Pmnono] < Pr(u + ((m)
Ppoty]
(35)
for (Ppoly- X4, Ppoly
X)), ), interval which will show has positive memauure We have
that
Pr(c X> P Pmoon]] Pr|u X
Ppoty]:
(36)
so it suffices show that
Pr(u X > Ppoly] < Pr/u + (m)
Pplly].
(37)
We have that
Pr(u+ + X Ppoly] = Fx poly 17)
(38)
Pr[u + (()) P Ppuly]
= 1 FX (Ppoly Poly
v))
(39)
Therefore, since m 2 2, (37) holds whenever Px(Ppaly v) E (0. 1), which, by Proposition 7, is true when Ppoly V E (X_, X+). Equivalently, v (Ppoly- X+, Ppoly positive measure (31).
X-). This interval has
26

---

F1
Proof of Theorem
We first prove part (i) and then part (ii).
F.1.1 Theorem 1(1)
The proof of Theorem 1(1) requires a few key observations, which we provide as separate (but closely related) parts in the following lemma.
Lemma 10. D is maximum concentrating, the following hold for all E, when m is sufficiently large:
(i) For all Polyy
[x(m]]]
3.
Pr|mpoly (v) E m] <.
(40)
(ii) For all > Poloy
EE [mm]]
+ g
Pr[ppoly (v) E Em] > 1 -
(41)
(iii)
( (Ppoly- - E [x((m)) Us
25
(42)
We provide some intuition for each part of the lemma, and how they come together to show Theorem 1. First consider the value Ppoly X [(()], which a natural "threshold" in the following sense:
The expected maximum score of student with value Ppoty - E [x (m²) is exactly the cutoff Ppoly- Part (i) of the lemma says that student with even a slightly lower score than Ppoly [x(m]] has very low chance of having their maximum score exceed the cutoff Pplly- Meanwhile, part (ii)
says that a student with even slightly higher score than Pplly - E [X is almost certain to have their maximum score exceed Ppoly. Part (iii) of the lemma says that this threshold Ppoly [x(m] (m) cannot differ much from Us. which we recall is defined such that exactly an S proportion of students have value higher than Uş. Parts (i) and (ii) essentially show that there is threshold which the probability student is matched jumps from nearly 0 to almost 1; part (iii) specifies the location of this threshold. In combination, these parts show Theorem
Proof of Theorem I using Lemma 10. We first show that for < us, for all O, Pr[mMpoly (v) F < E for all m sufficiently large. Consider any v < Us. Then there exists > 0 such that v < ui - 8. Using Lemma 10(ii)) and taking m sufficiently large, follows from us 8 that Ppoly [x(m]] In turn, again taking m sufficiently large, Lemma 10() implies that
Pr[mpooy (v) E FF] <e.
(43)
We next show that for o > US, for all > O, Prijppooy( (v) E F > - for all m sufficiently large. Consider any us. Then there exists 0 such that us 5. Taking sufficiently large, Lemma 10ii shows that > Ug ö implies that v > Ppoly E [x((m) + $, and Lemma 10(ii) implies that
Pr(mpoly(v) (F]
(44)
This completes the proof.
Proof of Lemma 10. We show the three parts in order.
27

---

We first show part (i). Suppose that < polyy - E [x(m]]] 3.
Then, using Proposition 3(i),
Pr [Polly (v)
F Pr
max x SEF
Poll
(45)
Pr
((m)
x
Ppoly
(46)
(mm) ((mm) 8
Pr
(47)
Pr
X(m) E
((m)
(48)
<,,
(49)
where the last line follows from the definition of D being maximum concentrating and by taking m sufficiently large.
Part (ii) can be shown analogously.
To show part (iii), we use parts (i) and (ii). For sufficiently large,
S
Pr Prijppty (v) FF
(50)
poly =[x
Pr[upaty (v) E FFdn(()) f
Pr|upoty E FI dn((v)
Ppoty Sp
(51)
Pooly -E(x(m0]
E <n(()) + f
dr((v)
(52)
-00
Ppols Ppoty- -[(x(m]]- Ppoto-((x(m)-
=1] =n((-s0 ((-se, Ppoly
E [ {
)
E ((Pror E [x(m]]
3 00 ))
(53)
where (52) follows from part (i) and by taking m sufficiently large.
Now define A : ((Ppoly - E x [m]]
3: oo)) Substituting this notation into (53), we have
S < (1 A) + A
(54)
S é < (1 - =)A
(55)
A> S- 1-E
(56)
Taking & sufficiently small, A is arbitrarily close to S, which implies-usine using that 1) has connected support-that Ppoly E [x(m] < ug + 5' for any 8' > 0 when m sufficiently large. Setting 8' =
we have that
(ppoly - E [ us <
28
(57)
3
when is sufficiently large.
We may analogously use (ii) to show that
Us 1s-(1 (Ppoly [x(m)]
28
(58)
Combining (57) and (58) shows the result.
F.1.2 Theorem 1(ii)
Proof of Theorem I(ii). We first show that P Pmono is fixed for all m. Indeed,
S =
Pr|pmona (v) E F] dn((v)
(59)
oc
Pr[u + X > Pmonol dn(v).
(60)
28

---

It follows from the proof of Lemma 2 that there is unique solution to (60). Therefore, Pmoo is the same for all m. It follows directly that Pr(u X
P monoo is constant in m.
remains to show that college welfare is suboptimal for Ymmno -i... that
e Pr(u + X> Pmonoo dn(e) < v dn(v).
(61)
Since 1- Pr(u + X > Pmoooo] dn(v) = - Sog dn(()) it suffices to show that Pr(u + X > P mmooo] E (0, 1) set I of positive 7--masure. The inequality clearly holds for / mooo X4, P mono -)),, where we use that has connected support [4], (Specifically,, Proposition gives that (x) strictly increasing and lies in (0, 1) for (x_,)+))) Finally, have from (30) that / has positive measure.
F.2 Proofs for Section 4.2
Proof of Theorem 2. We show the three parts separately:
Part (i). To show part (i), note that
Pr(Rank, (r[Rank,,((monoo()) 1] = Pr/u + X Pmono]-
(62)
This can be contrasted with the polyculture setting, in which
Pr RaaRa,, (Moplyy (v)) 1] = Pr/u X P Ppoly].
(63)
By Corollary 4, Pmono < Polly for all m, from which the non-strict inequality. To characterize when the inequality is strict, note that
Pr (H (v)) 1 = Pr[u + X > Pmoooo = 1 - Fx(Pmoono - u)
(64)
Pr Pr[Rank, (1cply (v)) 1| Pr(u X Ppoty] Fx(Ppoly v).
(65)
When (P (Pmono-
X+, P Pmooo
X-), we have that
Pmonn v E (4_,
(66)
Noting that Pplly Pmmono v, the result follows from Proposition 7, which shows that Fx strictly increasing on (X_,X4) X4). Also, we have already shown that this interval is of positive measure (30).
Part (ii). Part (ii) is direct consequence of the Equal Cutoff's Lemma (Lemma 2), since if, under monoculture, the student's 's score is above the cutoff for one college, then it is above the cutoff for all colleges. Therefore, any student who receives an offer from one college receives an offer from all colleges, and matches with their top choice
Part (iii). We first show that < P Pmmoo
X_ Indeed,
f
0o
1dn(v)
=
Pr(pmono(U)) E Fl dn(v)
(67)
Pmona X
Pimono X
< S
(68)
d)(()).
(69)
It is also clear that vs < V+. Therefore, (us: P Pmono X-) is non-empty interval that intersects (V_, V4), and so has positive measse from Proposition 8. It suffices show that PriJomono (v)
F < Pr(ppoly(1)) E F] on this interval.
When Pmmon X_,
=1 1==1-xxxPP Fx v) << 1. Pr[Pmonna (v) E =
(70)
Note here that Fx (mmono - 2) is constant m, so for all v E (Ug, P Pmono X-),
lim Pr(pmona (v) E F < C
(71)
29

---

Meanwhile, for any > Theorem gives that
lim Priupoly (v) E E C
(72)
follows that for all (ug, P mono
X-), for m sufficiently large,
Priupoly (v) E FF Pr(pmono (v) F].
(73)
G Proofs for Section A
Proof of Lemma 5. Let Z be the set of market-clearing cutoffs. Then by symmetry, if P
(Pi,... .Pm) E Z, then any permutation of P is also in Z. follows that
sup P1 = sup P2 = PEZ
sup Pm PEZ
(74)
PEZ
and
inf Pm- PEZ Call these two common values P+ and P_ respectively. By Proposition 9, (P....., .,)) (P....., ,P) Z. These are the greatest and least elements of the com- plete lattice of market-clearing cutoffs. Therefore, it suffices to show that P. P_.
inf P1 PEZ
inf P2 PEZ
(75)
We show the result for 0 polyy.s and the result follows similarly forf mono., It suffices to show that P+ = P_. Assume for sake of contradiction that P+ P_. (By definition, P+ 2 P-.) By the definition of market clearing, the total measure of students matched equal to S under either (P_,... P-) or (P+,... ..)). Therefore,
| Pr(u + x( > Pt) = 5 Pr|u + x(6) > P-]dn(()-
(76)
To give the desired contradiction, we show that
/ Pr|u+ (()) > P-]dn(t).
Pr[u + (x)) P+] dn]d)(0)= <
(77)
Clearly, Pr[u+XX x(++ (x) > P+] < Pr(e+X(()) (x) > P-]. Therefore, it suffices to show that Pr[u+ >
P.] < Pr(u + (x) > P-] on set of positive m-messure. We show this is the case for
X-).
We first show that the inequality is satisfied on Note that for E I, we have that P_ - v E (X_,X+. Therefore,
Pr/u + x(x) > P-] Pr|e ( > P+]= P
A -) -v)- v)) 0
1=1
(78)
where the last inequality follows from observing that by P. - -0> P_ by assumption and applying Proposition 7, which says that F% strictly increasing on (+_,
It remains to show that the interval / has positive m-measree. We begin by showing that P_ > V_ X_. This true because for P V_ X_.
Pr(u + xx() Pldn(u) 2 / Prfu + + V- + X =/ dd)(v)= =1 (79)
JR
contradicting the assumption that S < 1. Similarly, P_ < V, + X It follows that P_ P X4 < V+ and P_ x_ V_. Therefore, the interval T (P_ X4, P x_) intersects (V_14). So Proposition 8 implies that it has positive measure.
O
Proof of Theorem 3. To show part (i), note that P Pmoono P Pmono...
30

---

To show part (ii), note that
Pr Prilppoly.a (v) E (()(()) k] Pr/u x(k)
ppoly.k]
(80)
=1 (Pooyxx U). -0),
(81)
which is increasing in k. Moreover, when (Ppoly, X+; Ppoly.. X-): we have that Pplly,x - U E (X-, X+), so by Proposition 7, Fx (Ploly,e) E (0, in which case (81) strictly increasing in k.
31

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We clearly specify the claims of our paper: a model of algorithmic monoculture
in a matching markets context, and corresponding theoretical results.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We note that our results hold in a theoretical setup that leverages symmetry: accordingly, we provide computational experiments in more general settings. We also note in the Broader Impacts section that we focus on quantitative measures of welfare, and not rights- or claims-based approaches.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide complete statements of our results (and assumptions), and provide complete proofs in the appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, we describe our experimental results in detail and provide full code to reproduce the figures and results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide link to anonymized repository in the main text: (which we would re-
https://anonymou.. http:///oonnnoousooopeeeeeieteee wwt.e/eeeeeoooooouuuoo007---E-E
place with non-anonymized version in camera-ready version)
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify our (basic) training and test details, We use the default scikit logistic regression model.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We do make claims about statistical significance.
8. Experiments Compute Resources
32

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We note that all of our experiments can be performed using a standard laptop in most few hours (i.e., our experiments not compute intensive).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neurips. httprrrpp....ppp...c//iitieeaaaa
Answer: [Yes]
Justification: We have reviewed the Code of Ethics and verified that our research conforms.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification: Yes, we include a discussion broader impacts in the main text.
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We acknowledge the creators of the ACSIncome dataset and associated Python package, which is released under an MIT license.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide an anonymized repository of our code to reproduce experiments. We point which notebooks are used for which figures and experiments, and comment within.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
33


Reviews:
[{"review_id": "8mnh5EVpHd", "reviewer": "Reviewer_V2nV", "summary": "This paper examines the effects of algorithmic monoculture in a large two-sided matching market, in which participants on both sides compete with each other and outcomes are determined by preferences on both sides.\nIt proposes a matching markets model to study monoculture and produces both expected and surprising results.\nWhile under monoculture, all firms use a single shared estimate of an applicant's value, under polyculture, they obtain separate, independently drawn estimates.\n- One expected result is that polyculture benefits firm welfare.\n- More surprisingly, another result shows that applicants are better off under monoculture, yet risk-averse well-qualified applicants would rather prefer the security afforded by polyculture. In other words, and expectedly in this regard, monoculture presents a risk of systemic exclusion to certain more qualified applicants.\n- A third result is that polyculture benefits applicants who submit more applications, thus allows differences in the number of applications submitted to harm firm welfare.", "questions": "What happens when applicants have competitive preferences?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Connects literature on monoculture and matching markets.\nS2. Produce novel results.\nS3. Computational experiments training on real data.", "weaknesses": "W1. The results in Figure 5 seem to contradict the strong claims made about polyculture outperforming monoculture; the related claims need to be qualified.\nW2. The concept of \"positive label\", or binary 0-1 outcome, is not defined.\nW3. In the experiment, applicants have uniformly random preferences, which do not yield competition as suggested.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the helpful comments. We’re glad to see that you found the results interesting, and at times surprising. We address your comments, mostly about the ML experiments, below:\n\n“The results in Figure 5 seem to contradict the strong claims made about polyculture outperforming monoculture; the related claims need to be qualified.”\n- Thanks, we agree that the results in Figure 5 (California data) are less strong than those in Figure 3 (Texas data), and that we should qualify the claims more in the main text. The current paper briefly notes that results are weaker, but we will add exact description of results into the main text. Specifically, we will move line 709-714 in the appendix into the main text. We will also more carefully note that the weaker results could be due to less adherence to our “maximum-concentrating noise” assumption of Theorem 1, and that the accuracy of this assumption needs to be further studied in real-world settings.\n\n“The concept of ‘positive label’, or binary 0-1 outcome, is not defined.”\n- Thanks, we will add more description. First, we will note that the 0-1 label in the ACSIncome dataset is whether or not an applicant exceeds a certain income. We will also note that this itself is not a realistic task for make hiring decisions, but is a standard ML prediction task similar to those used in hiring. In particular, the ML experiments mimic the setup of Bommasani et al., except with many firms in a market framework. \n\n“In the experiment, applicants have uniformly random preferences, which do not yield competition as suggested.” “What happens when applicants have correlated preferences?”\n- We further tested the ML experiments in a setting where applicants have shared preferences over firms, regenerating Figures 3 and 5. These can be seen in our PDF. The results continue to hold, almost identically. We will make note of this robustness check in the paper.\n- More generally, we substantially vary the amount and type of variation in the numerical simulations (as noted in Section 5, and fully detailed in Appendix C). We find that each of our (directional) theoretical predictions continue to hold over all parameterizations.", "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": "", "extra_scores": {}}, {"review_id": "iMQo9CZMzC", "reviewer": "Reviewer_dgPg", "summary": "The paper considers a matching model with a continuum of students/applicants and m colleges/firms where the firms have a noisy estimate of the candidates' quality and compares the stable matching outcome in two situations: monoculture (where all firms have the same estimate) vs polyculture (where each firm has an iid estimate). It makes two major assumptions : all firms have the same capacity and candidates' preferences are uniform amongst the m firms. Then the unique stable matching is described by a single cutoff for all firms. The paper states two main results: \n- Thm 1: with polyculture, as m grows large, the stable matching approaches an optimal cutoffs mechanism on the true quality; whereas with monoculture it does not\n- Thm 2: the probability of first choice match is higher under monoculture\n- Thm 3: if candidates can submit variable length preference lists, the students submitting more benefit from polyculture but not from monoculture", "questions": "See weaknesses.", "limitations": "I very strongly encourage the authors to be much more upfront about the limitations of their model (discussed at length above). I have not seen them mentioned in abstract or introduction, whereas they are extremely important for the results to hold (in fact, some results do not hold without, see the counter-example at the end of [13] for more than 2 firms).", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "The topic of the paper is clearly important. From what I see, the paper is not original except in rewording things studied in previous works as monoculture vs polyculture instead of correlation vs independence. Perhaps this can contribute to increasing the volume of literature labeled as studying the effect of monoculture (which is an important concern), but other than that I don't see anything fondamental it brings. The paper is clear. The take-aways are interesting but besides their lack of novelty their significance is diminished a lot by the very strong assumptions made (see below).", "weaknesses": "There are two main weaknesses to the paper: (i) lack of novelty in the model, the questions and the flavor of the results and (ii) very strong assumptions that make the results mostly trivial so that I could not identify any strong technical result either. I elaborate on both in the remaining of this box. \n\n- The paper claims (l. 38) that the technical contribution is a matching market model that can be used to analyze monoculture. However, the model used is a particular case of that of [13] (because in [13] they can have multiple demographic groups). Even [13] with a single demographic group is more general because it can handle any level of correlation and not just 0-1 (mono-polyculture). The particular case of latent quality+noise is described in appendix A.4 of [13]. \n\nNote that in [13], some results apply only for 2 colleges, but the model applies to any number of colleges. \n\n- The paper makes two very strong assumptions: each firm has the same capacity and candidates' have uniform preferences. Under these, it shows (actually, it just states, because it is trivial) that at the stable matching each firm uses the same cutoff. This makes the rest of the paper technically straightforward, but this is very unrealistic in practice. So, even if one were to see the paper as an extension of some results of [13] for m firms, this would be only under *extremely* simplifying assumptions that make the extension straightforward and of much diminished significance. \n\nJust in contrast, most of the technical difficulty in [13] seems to be in handling the fact that the cutoffs may be different and hence if one increasing, it does not imply that the other does so too. The authors in fact show that the property of diminishing cutoffs is no longer always true for >2 firms. Of course, it holds with all equal cutoffs but as mentioned above, this is too simplifying (and trivial). \n\n- Thm 1 gives an interesting message but it is very straigthforward under the assumptions mentioned above. \n\n- Thm 2 is very similar to [13], the extension to m firms does not seem significant. See my discussion above.\n\n- Thm 3 is very connected to [7]. This is (really) discussed only in the appendix (l. 644-651), but it appears that the additional value of Thm 3 compared to [7] is minimal. \n\n- There are some numerical simulations. Unfortunately, as far as I could see, they do not relax the assumption of same capacity. \n\n\nOverall, even though the paper is well-written and interesting, I cannot identify any strong or novel result that would get close to the NeurIPS bar. Perhaps if the authors focus on the elements that are novel and try to remove the strong assumptions that make the results straightforward, this would improve the paper's contribution.\n\n\n[13] Castera et al. EC'22. I used for this review the latest available version from May 2024 https://hal.science/hal-03672270v6, but I checked and the previous version is extremely similar. \n[7] Arnosti. MS (2022)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful feedback, and we discuss your concerns below.\n\n**Assumptions:** We give detailed comments on our theoretical assumptions in the general response. We reemphasize here that we will incorporate your feedback in being clearer about assumptions in the introduction. We also believe that our results extend beyond the assumptions, and we hope you find the previous experiments (varying correlation of applicant preferences, considering ML experiments) as well as the new experiments (varying firm capacities, as you suggest) convincing of this point.\n\n**Novelty:** We respectfully disagree regarding novelty. We describe three main points of novelty below:\n\n**(1) Modeling true applicant values.** The statement “the model used is a particular case of that of [13]” is inaccurate. This can be seen by observing that our model extends that of Kleinberg and Raghavan, while Castera et al. does not. More specifically, our model departs from Castera et al. (and Arnosti) by following Kleinberg and Raghavan in modeling a ground-truth *true value* of each applicant, which firms estimate. This is essential for many of our results:\n- Theorem 1 reveals that under polyculture, exactly the applicants with the highest true values match.\n- Theorem 2 shows that applicants with high true value face a trade-off between likelihood of matching to top choice (monoculture) and likelihood of matching overall (polyculture).\n- Theorem 3 shows that, under polyculture, applicants with higher true values may fare worse than applicants with lower true values who can apply to more places. \n\nCastera et al. and our work share a common high-level finding with past work on tie-breaking in school choice (correlation improves applicant welfare); however, our respective novel contributions are fundamentally distinct. In particular, Castera et al. certainly identifies interesting and important results that our paper does not touch upon (we discuss these results in lines 110-122 in Section 2); we view our work as studying a complementary set of questions, in studying the effects of monoculture with heterogeneous true applicant values and emergent/strengthening effects as the number of firms grows large\n\n**(2) Bridging literatures.** We also believe that it is a novel contribution to bridge the algorithmic monoculture papers of [Kleinberg and Raghavan (theoretical, firm-side)] and [Bommasani et al. (empirical, applicant-side)] with a matching markets framework. **Prior to our work first being posted online, these literatures did not discuss each other** (the 2022 version of Castera et al. cites Kleinberg and Raghavan only in passing alongside many other algo fairness papers and does not discuss monoculture). As reviewers noted, our work extends and challenges these past ML results. Our ML-based simulations directly show how our framework can be adopted for empirical studies like in Bommasani et al., demonstrating how researchers in ML can utilize the framework.\n\n**(3) M > 2 firms/schools and emergent effects.** All the main results of prior relevant work (including K&R and Castera, who directly state their models in the 2 school setting) hold in a 2 school model. One technical insight of our work is showing how a Azevedo-Leshno continuum model admits a tractable way to study M > 2 schools (Castera also use AL model, but only to study 2 schools). **Crucially, this is not just a technical detail: one important conceptual insight of our work is that considering many firms/schools *fully strengthens* the underlying effect—large polyculture markets behave essentially like noiseless markets (i.e., sort according to true value).** This insight about emergent effects is novel in our work, compared to all the prior literature in both matching markets and machine learning. We also note that, from the proof techniques of Castera and other related work, it is not clear how to derive results for more than 2 schools—doing so seems algebraically intractable. One key insight of our work is to consider maximum-concentrating distributions (which generalizes common Gaussian assumptions), which become extremely tractable with a large number of firms/colleges.\n\nIn other words, studying emergent phenomena with many firms is a novel insight of our work, that is distinct from the dimension studied in Castera et al. and other work. To illustrate this, we modify our numerical simulations so that we vary both number of firms and the amount of correlation between firms (which Castera et al. varies). **Indeed, in the bottom figure in the PDF attached in the main response, effects of variation in correlation become stark only when the number of firms is large.**\n\nFinally, we also note that we did not intend to minimize the relationship with Castera et al. Lines 110-120 detail the relationship with Castera, and lines 123-133 summarize some of the above points about emergent phenomena with many firms and the novel aspect of assuming that students have heterogeneous true values. We also have a 3.5 page extended related work section in the Appendix that details the relationship with the burgeoning literature around this area, and our novel contributions. \n\nTo summarize, we highly respect the work of Castera et al. and others in this literature, and we believe that our work is complementary, both conceptually and technically, to this line of work. It is inaccurate to say that our model and assumptions nest within past work: while some assumptions (full correlation vs no correlation) are stricter than some past work, other aspects are more general / entirely distinct (especially, considering the true values of applicants and M>>2 firms). In particular, while our model extends Kleinberg and Raghavan, the model in Castera et al., Arnosti, and others do not. We are happy to modify the writing in the main text further to clarify this important point.", "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": "", "extra_scores": {}}, {"review_id": "n7F4qYJTGH", "reviewer": "Reviewer_FF9T", "summary": "This paper studies the monoculture problem in matching markets from a theoretical perspective. The authors found that on the firms' (colleges') side, monoculture may decrease the quantity of matched applicants; while on the applicants' side, monoculture may help matched applicants to match with higher-ranked firms (colleges). Additionally, monoculture may decrease the risk of unfairness if some applicants are born with more opportunities to apply to more firms (colleges).", "questions": "See above Weakness.", "limitations": "One concern is whether the paper is a good fit for NeurIPS acceptance. The paper focuses more on economics and matching markets than on machine learning and computer science, attempting to analyze the phenomenon of monoculture using economic models. This paper might be more suitable for conferences like EC and WINE.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies the monoculture problem with multiple (possibly infinite) homogeneous firms and heterogeneous applicants differed by real-numbered type, broadening the elements modeling within the monoculture literature.\n2. The paper provides positive theoretical and empirical results for monoculture, which are inspiring as the results are counter-intuitive and challenged the preexisting beliefs about monoculture.", "weaknesses": "**General Weakness:**\n\n1. The connection between this work and CS/ML conferences is vague, as this paper mainly addresses monoculture, which is intrinsically an economic problem. Additionally, the technical derivation seems quite straightforward.\n2. In the model, firms are assumed to be homogeneous, which might be an oversimplification and not realistic.\n\n**Corrections for Typos:**\n\n1. In line 203, it should state \"the cutoff under monoculture must be lower.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewers comments, and are glad to hear that it challenged preexisting beliefs about monoculture. We address your comments below:\n\n**Assumptions/Straightforwardness:** We note in our general response that we believe our computational experiments demonstrate that our conceptual insights extend beyond our theoretical assumptions. We also noted in the general response that we believe the technical straightforwardness is only possible due to key insights.\n\n**Fit for NeurIPS:** Regarding the fit for NeurIPS, we note that papers studying monoculture have appeared in several ML venues. For example, Bommasani et al. (NeurIPS 2022), Jagadeesan et al. (NeurIPS 2023), Toups et al. (NeurIPS 2023) Jain et al. (ICML 2024), and Jain et al. (Best Paper at FAccT 2024). Insofar as the ML community is interested in questions related to algorithmic hiring and monoculture, we believe that the market-level approach we present is essential for understanding effects. Indeed, while this prior work exclusively views monoculture as bad for applicants, our work (as you note) demonstrates that market-level effects may reverse (and add nuance to) this effect. \n\nIn fact, we directly seek to connect to this literature in our paper by adapting the setup of Bommasani et al. into our framework in our computational ML-based experiments. \n\nMore broadly, this paper fits into the “social and economic aspects of machine learning” and “theory” parts of the Neurips CFP, the latter of which further specifies Algorithmic Game Theory (which arguably is even more an “EC” topic than our paper). We also note that NeurIPS accepts matching papers that intersect with ML, e.g.: Learning equilibria in matching markets from bandit feedback. M Jagadeesan, A Wei, Y Wang, M Jordan, J Steinhardt (NeurIPS 2021).\n\n(Thanks also for pointing out the typo, which we will correct.)", "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": "", "extra_scores": {}}, {"review_id": "Ua4LJxbRev", "reviewer": "Reviewer_LFB2", "summary": "The authors are focused on matching markets in which different firms use a single algorithm / evaluation criterion (monoculture) vs. markets where different firms may each have different evaluation algorithms / criterion (polyculture). This can be seen as a substantial generalization of the wonderful work of Kleinberg and Raghavan [35] on monoculture in hiring with two firms. \n\nThe authors first introduce the continuum matching market model introduced by Azevedo and Leshno [10]. Here, there is a continuum of applicants, and a finite number of firms. The authors make the assumptions that (1) each firm has the same fixed capacity, and (2) not all applicants will eventually be matched with a firm. The authors first review critical results in the existing continuum model. These include the fact that a stable matching corresponds to a particular cutoff vector, and subject to this cutoff vector, applicants always choose their highest preferred firm for which their estimated quality is higher than the cutoff for that firm.\n\nNext, the authors introduce their notion of mono and polyculture into this model. Intuitively, monoculture is where each firm has an identical estimate of the value of an applicant of type $\\theta(v)$, given by $v + X$ for an $X$ drawn from some noise distribution $D$. This captures, for example, each firm using Chat GPT to evaluate the resumes of all applicants. In polyculture, each firm $i$ may have a different estimate $v + X_i$ for the value of applicants of type $\\theta(v)$.\n\nThe authors begin by proving that the cutoff characterization of stable matching is unique in the mono and polyculture settings (Lemma 2). This follows from the lattice structure of stable matchings. Then, in Proposition 3, they show that the probability of an applicant of type $\\theta(v)$ being matched under polyculture is related to the maximum of $X_i$ over all firms' noisy estimates $X_i$, whereas under monoculture this probability is related only to $X$ (since all firms have identical estimates).\n\nWe now move to the main results. In Theorem 1, the authors show that under polyculture, as the number of firms $m \\to \\infty$, the (firm-) optimal welfare can be achieved by the resulting matching. This does not hold for monoculture. In particular, under monoculture, the probability that an individual of type $\\theta(v)$ is matched at all is constant for varying $m$.\nIn Theorem 2, the authors examine applicant welfare. They show that applicants have a higher chance of being matched with their top choice under monoculture, but that for a subset of applicants of positive measure, the variance in whether they are matched or not is higher under monoculture than polyculture. This means that not all applicants are incentivized to prefer monoculture unconditionally.\n\nFinally, some extensions under a differential application access setting are provided. Intuitively, the authors show that more applications do not help applicants under monoculture but does under polyculture. Experiments complement most of the theoretical results, and also demonstrate that the uniform preference assumption is not essential to practical relevance of the results.", "questions": "Q1: How does Lemma 2 (Equal Cutoffs Lemma) relate to Theorem 1 part 1 from Azevedo and Leshno [10], which says that if $\\eta$ has full support, then there is a unique stable matching?\n\nQ2: Do we expect the maximum concentrating distribution assumption to hold in, e.g., the included experiments?", "limitations": "I do not believe that the authors have a dedicated limitations section of their paper, which I recommend. Some limitations are sprinkled throughout the paper (e.g. Line 350-353), but perhaps more could be mentioned. In particular, how strong/important the technical assumptions are in practice are could be explicitly discussed in a formal limitation section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is generally extremely well written, motivated, and clear. I also think that the work is already very important in the modern context in which universities and hiring managers may already be using one of only a handful of services to conduct automated applicant filtering. The work examines what this would potentially lead to in terms of macroeconomic market dynamics.\n\nThe theoretical results are presented clearly, and I understood most even though I have not personally worked in the continuum matching model (have only worked in the discrete matching model). I appreciate that the authors also empirically investigate the (strong) assumption that all applicants' preferences over firms are drawn uniformly at random. The empirical results confirm that this is perhaps not a fundamental assumption, even though the (current) proofs critically hinge on it.\n\nThis work certainly challenged my preconceived notion (“monoculture=bad”) in a fundamental way and may open a more general line of inquiry into monoculture more broadly. This paper was a pleasure to read, and I look forward to additional work from the authors.", "weaknesses": "Note that I did not carefully check the proofs.\n\n(W1) I think the introduction of the continuum model could be made a bit more clear, in particular the definition of applicant types. For example, there seems to be a small typo in lines 141-142:: “The realization of θ(v) is their type, which lies in $\\Theta \\coloneqq \\mathcal{R} \\times \\mathbb{R}^m$ is the set of applicant types,”. \n\nFurther, I am not sure if this is a typo as well (in line 143): “$\\succ^\\theta$ is the preference ordering of v over firms…”. Do all applicants of value $v$ have the same type $\\theta(v)$? That is, do all have the same preferences over firms? Or, do we draw different preferences uniformly at random for each individual of value $v$? These were not clear from just this introduction on the continuum model.\n\n(W2) The model considers identical noise across all applicant “types”. This is certainly a reasonable form of polyculture to analyze, however, in practice we may be more concerned with bias based on different “types” of individuals. I.e., historically underrepresented minorities having a skewed or higher variance noise distribution. “Types” in this sense is (I believe) not captured by solely preference and firm quality estimates. This is certainly less of a weakness and more of a direction of future work, but I think it is perhaps important to mention. The authors have some discussion in lines 350-352, but more could certainly be added earlier in the paper.\n\n(W3) I think that the assumptions made throughout the work are sprinkled throughout the paper. Having a collection of all assumptions, perhaps in the appendix, may help the reader better understand the limitations of the work.\n\nMinor: Most non-theorems from the main paper are referred to incorrectly in the appendix, e.g. Lemma 2 is mistakenly referred to as proposition 2 in the appendix, and similarly proposition 10 / lemma 10, and corollary 4 / proposition 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the thoughtful feedback, and are glad you enjoyed the paper. We answer your questions below:\n\n**Q1: How does Lemma 2 (Equal Cutoffs Lemma) relate to Theorem 1 part 1 from Azevedo and Leshno [10], which says that if has full support, then there is a unique stable matching?**\n\nIt is essentially implied (since the existence of unequal cutoffs would then imply multiple stable matchings). We can make note of this. We include a standalone proof, partly because it gives some intuition on how to analyze the noisy model we have, and partly because our proof provides some additional facts (equations 30 and 31) that are important for later results. \n\n**Q2: Do we expect the maximum concentrating distribution assumption to hold in, e.g., the included experiments?**\n\nWe think that in many cases, we might intuitively expect the maximum order statistic to at least partially concentrate (i.e., have diminishing variance); this is the case when the “maximum evaluation” of an applicant is less noisy than a single evaluation, which seems generally plausible. If we think noise is Gaussian, as is often assumed (though perhaps primarily for tractability), then it would fully concentrate. Theoretically, max-concentration does not hold for noise distributions where tails are “heavier than exponential”, such as the Laplace distribution. \n\nOur ML experiments, in which we did not hard-code any notion of noise (in fact, noise is not even i.i.d.), seem to suggest maximum-concentrating behavior holds in that setup, since the market as a whole tends to select higher-value applicants than individual ML models. It would be interesting to better understand what noise looks like in practice. \n\n\n**Other comments.** Thank you for pointing out potential areas of confusion in our model, which we will address. Applicants of the same true value do not have the same estimated value. What we care about is the distribution of outcomes for a student with true value v. We will make this more clear in the text.\n\nThank you also for the suggestion about a limitations section. We will add in a limitations section that discusses the following:\n- The technical assumptions (e.g., homogeneous firms, max-concentrating noise), and when they are more/less likely to hold.\n- A summary of what our computational experiments address (varying correlation structure in applicant preferences, estimates derived from ML models).\n- Broader limitations (e.g., heterogeneous noise/bias across applicants, notions of welfare beyond utilitarian frameworks, potential degradation of effects due to search frictions).", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for the thoughtful comments.

We’re glad to see that reviewers found the paper to be clear and well-written (R2, R3, R4), and the results to be surprising, countering past literature and expectations about algorithmic monoculture (R1, R3, R4). All reviewers noted how the model bridges the ML literature with the matching markets literature.

The most common concerns were about the strength of theoretical assumptions (particularly noted by R2, and by others to varying degrees); R2 relatedly noted that this led to simple and straightforward proofs. 

In this general response, we discuss these concerns about theoretical assumptions (and corresponding simple proofs). We defer more reviewer-specific questions and concerns to individual responses, including concerns about novelty (R2) and fit-to-venue (R3).

**Discussion on theoretical assumptions:** We agree that our theoretical model makes a strong assumption of homogeneous firms (equal capacities, and that students have uniformly random preferences). At a high level, we believe that our experiments convincingly demonstrate that the conceptual insights extend beyond these assumptions.

Both R2 and R4 note that we should make this assumption clearer earlier in the text. We fully agree, and will add the following after line 46 in the introduction: “Our theoretical results are shown in a setting with a symmetric setup with a large number of homogeneous firms. This allows for tractability, as well as clear intuition. We demonstrate empirically that our theoretical results hold in markets with heterogeneous firms, as well as when firms use ML models to rank applicants.”

To address limitations in our theoretical model, we test our theoretical predictions in computational experiments. In our paper, we included both (1) simulations of markets with correlated student preferences, following a simulation setup of Ashlagi et al., and (2) simulations of markets with ML models, bringing the setup in Bommasani et al. to a market context. Each of these experiments verify the predictions of our model.

R2 noted that our theoretical results on polyculture only consider fully independent noise. Our ML experiments represent a case in which firms using different algorithms have some but not perfect correlation (since the ML models share data and overlap in features).

There were still some settings that our experiments did not cover, and which reviewers noted. To alleviate these concerns, we include a PDF of additional experiments addressing these specific concerns:
- R1 noted that our ML experiments only assumed uniformly random preferences (unlike our pure simulation setting). We include the corresponding figures when applicants have heavily-correlated preferences (beta=10 in our simulation setup), showing that the same results hold. 
- R2 noted that our numerical experiments did not vary capacity. We rerun each numerical experiment when firms have random differing capacities (still also varying correlation in applicant preferences), showing that our results continue to hold. In the paper, we will remark that these further experiments align with our theoretical results. We note that varying capacity has similar effects as non-uniform preferences (which our simulation setting already includes), as they induce heterogeneous cutoffs.

**Straightforwardness.** While this theoretical setup makes our proofs relatively straightforward (as R2 notes), we believe this to be a feature, and that our work makes a significant technical contribution in two ways. In particular, our model *generalizes* aspects of models in past work that make the model *more tractable:* we consider many firms rather than two firms (as considered by Kleinberg and Raghavan, and Castera et al.). We also consider an interpretable-but-general class of noise distributions (that includes bounded and Gaussian distributions common in other work). The key technical insight is that by considering many firms, we can leverage the well-behaved tail of max-concentrating distributions to tractably (and cleanly) analyze the resulting stable matching. The simple-seeming nature of our proofs is a consequence of these technical insights, contra the (substantial) algebra often needed in prior work.

We also want to note the attached pdf, in which we run new computational experiments to supplement our responses, including around assumptions and to make clearer the relationship with prior work.

Meta-review: There were three positive reviews (5, 6, 7) and one quite negative review (3) on this paper. The paper is exceptionally well-written and nicely presented, and although the model is very simplistic, leading to straightforward proofs (not necessarily a bad thing, as simple proofs more clearly show the intuition behind them), the theoretical results are somewhat surprising. Furthermore, the authors take great pains to do extensive simulations to show that their results extend past their simple theoretical model. 

The negative review (dgPg) focuses on lack of novelty in the model---in particular, they claim that it is a specific case of [Castera et al., EC 2022]---and the simplicity of the theoretical results. For the simplicity concern, as stated above, I agree with LFB2 that simple proofs are sometimes desirable. As to the lack of novelty, the authors effectively rebutted dgPg's concerns that their model is a straightforward extension of previous work (it is not), and the results they were able to prove are significantly different from those of [Castera et al., 2022]. 

Overall, I feel like this paper's strengths (extremely well-written, empirical results that go beyond their theoretical model) outweigh its weaknesses (simple model, straightforward results), especially once the authors clarified its novelty compared to previous work.
Decision: Accept (poster)