Monoculture in Matching Markets

We appreciate the thoughtful feedback, and are glad you enjoyed the paper. We answer your questions below:

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?

It 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.

Q2: Do we expect the maximum concentrating distribution assumption to hold in, e.g., the included experiments?

We 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.

Our 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.

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.

Thank you also for the suggestion about a limitations section. We will add in a limitations section that discusses the following:

• The technical assumptions (e.g., homogeneous firms, max-concentrating noise), and when they are more/less likely to hold.
• A summary of what our computational experiments address (varying correlation structure in applicant preferences, estimates derived from ML models).
• Broader limitations (e.g., heterogeneous noise/bias across applicants, notions of welfare beyond utilitarian frameworks, potential degradation of effects due to search frictions).

We appreciate the reviewers comments, and are glad to hear that it challenged preexisting beliefs about monoculture. We address your comments below:

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.

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.

In 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.

More 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).

(Thanks also for pointing out the typo, which we will correct.)

We thank the reviewer for the careful feedback, and we discuss your concerns below.

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.

Novelty: We respectfully disagree regarding novelty. We describe three main points of novelty below:

(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:

• Theorem 1 reveals that under polyculture, exactly the applicants with the highest true values match.
• 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).
• 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.

Castera 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

(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.

(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.

In 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.

Finally, 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.

To 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.

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:

“The results in Figure 5 seem to contradict the strong claims made about polyculture outperforming monoculture; the related claims need to be qualified.”

• 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.

“The concept of ‘positive label’, or binary 0-1 outcome, is not defined.”

• 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.

“In the experiment, applicants have uniformly random preferences, which do not yield competition as suggested.” “What happens when applicants have correlated preferences?”

• 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.
• 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.