PaperlayerView exact revision on arXiv

Source-linked AI summary

Monoculture in Matching Markets

Kenny Peng, Nikhil Garg

arXiv:2312.09841v1cs.GTcs.CYecon.TH

TL;DR

Prior work on algorithmic monoculture had limited evidence on markets where many participants' preferences and behavior interact. This paper models those markets through stable matching under shared or independent noisy evaluations. It finds that monoculture selects less-preferred applicants, improves overall applicant welfare with individual tradeoffs, and is more robust to differences in application counts.

  • Problem

    Research on algorithmic monoculture has been limited in modeling markets with many participants and two-sided preferences, where competition and preferences on both sides shape outcomes.

    Source: §1 · pp. 1–2

  • Method

    The paper builds a tractable matching-market model with stable outcomes under a shared noisy applicant estimate for monoculture or independent firm estimates for polyculture.

    Source: §1 · p. 2

  • Results

    Monoculture selects less-preferred applicants, yields higher overall applicant welfare with individual tradeoffs, and is more robust to differences in application counts.

    Source: §7 · p. 28

  • Takeaways & Limitations

    A market-level evaluation reveals distinct consequences for firms, applicants, and application-access disparities rather than a single welfare ranking.

    Source: §7 · p. 28

    The model assumes shared preferences on one market side; effects with more heterogeneous preferences remain future work.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper develops a tractable matching-market model to study algorithmic monoculture amid competition and preferences on both sides. It finds that monoculture and polyculture produce different welfare and application-access outcomes.

1 Introduction

  • Prior work identified potential harms to firms and applicants but had not modeled many participants with two-sided preferences, a gap this paper addresses.Employment and college admissions feature competition on both sides of the market.Source: §1 · pp. 1–2

1.1 Overview of Model

  • The model builds on cutoff-based stable matching, using a shared noisy applicant estimate in monoculture and independent firm estimates in polyculture.Applicants accept their most-preferred offer; market-clearing cutoffs characterize stable outcomes.Source: §1 · p. 2, §1.1 · p. 5

Firm welfare.

  • With lighter-than-exponential noise tails, many firms under polyculture select nearly only the highest-value applicants, yielding higher firm welfare than monoculture.Independent noisy evaluations can collectively distinguish applicants by value as the number of firms grows.Source: §1 · p. 2, Firm welfare · p. 6

Applicant Welfare.

  • Monoculture raises average applicant welfare by matching applicants to more-preferred firms, but individual outcomes trade off top-choice likelihood against matching at all.Applicants may be more likely to reach their top choice but less likely to match; risk tolerance can affect which system they prefer.Source: §1 · p. 2, Applicant Welfare · p. 7

Overview of Computational Experiments

  • A market-level analysis shows that monoculture's welfare effects differ across firms and applicants, and that application-count disparities affect outcomes under both systems.The authors report that their theoretical predictions hold directionally across computational settings with varying preference structures and correlations.Source: §1 · p. 3, Overview of Computational Experiments · p. 8

1.2 Overview of Theoretical Results and Comparison to Past Work

  • The theoretical comparison covers firm welfare, applicant welfare, and unequal application access, with computational experiments testing predictions across simulated markets.The experiments vary the structure and correlation of applicant preferences.Source: §1.2 · p. 6, Overview of Computational Experiments · p. 8

An Extension: Differential Application Access.

  • With differential application access, submitting more applications benefits applicants under polyculture but not monoculture, making monoculture more robust to disparities in application counts.Under monoculture, an applicant's estimate is shared across firms, so applying to more firms does not raise the chance of a higher estimate.Source: §1 · p. 2, An Extension: Differential Application… · p. 8

2 Model and Preliminaries

The section sets up a continuum matching model and characterizes stable outcomes through cutoffs, then specifies monoculture and polyculture and introduces noise conditions used in the analysis.

2 Model and Preliminaries

  • The model has a continuum of applicants and finite firms; applicant types encode preferences and firms’ estimated values, which determine matching outcomes.Firm capacities and the distribution of applicant values also help determine the market, while stable matchings are analyzed through applicants’ estimated values rather than their true values directly.Source: §2 · pp. 8–9

2.1 A cutoff characterization of stable matchings

  • Stable matchings correspond to market-clearing cutoffs, and applicants match to their favorite firm where their estimated value clears its cutoff.This cutoff characterization makes stable outcomes tractable to analyze.Source: §2.1 · pp. 9–10

2.2 Instantiating monoculture and polyculture

  • Monoculture gives each applicant one noisy estimated value shared across firms, whereas polyculture assigns independently drawn values to each firm.The analysis uses the same noise distribution in both settings for exposition; this is not necessary for many results, though it permits ceteris paribus comparison in some cases.Source: §2.2 · p. 10

2.3 Preliminary Analysis

  • With at least two firms, the unique common cutoff is lower under monoculture than polyculture, whose applicants have multiple chances to exceed a cutoff.The model also establishes that all firms share the same cutoff within either setting.Source: §2.3 · pp. 11–12

2.4 Maximum-Concentrating Noise

  • Maximum-concentrating noise is defined by concentration of its maximum order statistic, a condition associated with upper tails lighter than exponential.The maximum order statistic matters because polyculture matching depends on the maximum of an applicant’s noisy estimated values.Source: §2.4 · pp. 12–13

3 Main Results: Firm and Applicant Welfare

With maximum-concentrating noise, polyculture increasingly matches only the highest-value applicants as the number of firms grows, while monoculture’s firm welfare remains constant and suboptimal. Monoculture gives applicants more top-choice matches on average, but some applicants can be less likely to match at all.

3.1 Firm welfare

  • With maximum-concentrating noise, polyculture’s match probability approaches a step function at the firm-capacity threshold, and firm welfare approaches optimal as the number of firms grows.The figure illustrates this contrast with simulated values and preferences.Source: §3.1 · p. 13, Figure 3 · p. 14
  • Under monoculture, the probability an applicant is matched and firm welfare remain constant as the number of firms grows, with firm welfare suboptimal.Unlike polyculture, monoculture’s matching error does not diminish with more firms.Source: §3.1 · pp. 13–14
  • Despite firms’ noisy preferences, polyculture collectively selects the highest-value applicants because stable-match structure pools information without firms directly sharing it.This result is a “wisdom of the crowds”-like effect.Source: §3.1 · pp. 13–14

3.2 Applicant welfare

  • Applicants are at least as likely to match to their top choice under monoculture, and anyone matched under monoculture receives their top choice, yielding optimal average applicant welfare.The paper illustrates the comparison in Figure 5.Source: §3.2 · pp. 15–17, Figure 5 · p. 16
  • For a positive-measure set of applicants, monoculture can raise the chance of a top-choice match while lowering the chance of matching at all, so neither system stochastically dominates.For sufficiently many firms, applicants in the stated value range are less likely to match under monoculture; applicants above the monoculture guarantee threshold do not gain this advantage from polyculture.Source: §3.2 · pp. 16–17
  • The top-choice comparison depends on using the same noise distribution under both systems; with different noise, top applicants may instead be more likely to receive their top choice under polyculture.The paper gives the example of noiseless polyculture and substantially noisy monoculture.Source: §3.2 · p. 17

4 An Extension: Differential Application Access

The extension allows applicants to submit different numbers of applications and finds that unequal access has different consequences under monoculture and polyculture: monoculture is more robust, while polyculture favors applicants who can apply to more firms.

4.1 Model setup

  • Each applicant’s application count is drawn from a distribution κ, and applicants apply to their top k firms; equal market-clearing cutoffs support this equilibrium.With equal cutoffs, applying to a different set does not increase an applicant’s chance of matching to any given firm or set of firms.Source: §4 · p. 17, §4.1 · p. 19

4 An Extension: Differential Application Access

  • Applicants with access to more firms benefit under polyculture, producing inequitable outcomes and harming firm welfare, whereas monoculture does not give them an advantage or harm firm welfare.The result holds when applicants apply to their top k firms, an ex-ante Nash equilibrium under both systems.Source: §4 · p. 18, §4.1 · p. 19

4.2 Analysis

  • Matching probability stays constant in k under monoculture but increases with k under polyculture, strictly over an intermediate range of applicant values.Figure 6 illustrates the contrast; under polyculture, higher-value applicants can go unmatched while lower-value applicants who submit more applications may match.Source: Figure 6 · p. 19, §4.2 · p. 20

5 Computational Experiments: Correlated Preferences

The computational experiments examine whether the paper’s predictions persist with correlated applicant preferences. Across the tested settings, polyculture selects higher-value applicants, while monoculture produces better average applicant matches and is more robust to unequal application access.

5 Computational Experiments: Correlated Preferences

  • The experiments test predictions about applicant selection, top-choice matching, and robustness to differences in application access using correlated applicant preferences.The experiments vary global and local preference correlation; β = γ = 0 recovers the theoretical model’s uniformly random preferences.Source: §5 · p. 20

5.1 Firm welfare

  • Average firm welfare is higher under polyculture across the tested preference correlations and remains consistent across the correlation structures considered.Firm welfare is measured by the average percentile value of matched applicants.Source: §5.1 · pp. 21–22, Figure 7 · p. 21

5.2 Applicant welfare

  • Average applicant match rank is better under monoculture for all tested correlations, though it worsens as global correlation β increases under both systems.Experiments also confirm that monoculture more often matches applicants to their top choice, while some applicants are more likely to match overall under polyculture.Source: Figure 7 · p. 21, §5.2 · p. 22, Figure 8 · p. 22

5.3 Differential application access

  • For correlated preferences, equilibrium application strategies remain uncharacterized, so the experiments compare applying to top-choice firms with applying to randomly selected firms.Applying to top choices is a Nash equilibrium when preferences are uncorrelated; the authors use the two strategies as heuristics for the correlated-preference experiments.Source: §5.3 · p. 23
  • The benefit in matching probability for applicants able to apply to 6–10 rather than 1–5 firms is larger under polyculture for both tested application strategies.The change in firm welfare from uniform to differential application access is also more significant under polyculture for both strategies.Source: §5.3 · p. 23

6 Extended Related Work

This section connects algorithmic monoculture to matching-market and school-choice research, using market-level interactions and preference approximation to refine existing intuitions. It also identifies boundaries of the model and reframes concerns about systemic exclusion.

Algorithmic monoculture

  • Kleinberg and Raghavan (2021) study two decision-makers choosing from noisy or shared rankings; this paper adds large markets, two-sided preferences, and a cleaner threshold-based account.The paper does not include their game-theoretic analysis of firms’ algorithm choices.Source: §6 · p. 25

Normative aspects of monoculture

  • With fixed opportunity capacity, the number excluded from all opportunities remains constant in the model; the concern shifts toward who is excluded and other welfare measures.The authors caution that this conclusion applies to domains with fixed opportunities and does not cover every domain of algorithmic decision-making.Source: §6 · pp. 25–26

Model scope

  • The continuum matching model omits stochastic effects in small markets, particularly when decision-maker capacity is small.The authors note that alternative stable-matching models could support analysis of those effects.Source: §6 · p. 26

Related matching-market models

  • Compared with Castera et al. (2022), this work studies how evaluation correlation affects top-choice matching; it instead analyzes one-shot outcomes given participants’ current information rather than sequential information acquisition.The related model by Castera et al. focuses on aggregate applicant welfare across groups.Source: §6 · pp. 26–27

Tie-breaking rules in school choice

  • Monoculture parallels single tie-breaking in school choice: shared school preferences can increase top-choice matches, but this model’s value-dependent noise can reorder applicants by true value.Unlike lottery tie-breaking, the estimates here depend on applicants’ true values, allowing a lower-value applicant to outrank a higher-value one.Source: §6 · p. 27

Bridging the literatures

  • Matching-market tools capture how firms’ choices and applicants’ preferences jointly shape outcomes, while preference approximation extends the questions matching models can address.The paper frames its contribution as a bridge between monoculture and matching markets, and proposes studying noisy approximations of true preferences before evaluating the resulting matching.Source: §6 · pp. 26, 28

7 Conclusion

The paper uses a matching-market model to study monoculture with competition and capacity constraints, and verifies its three theoretical findings in computational experiments. Monoculture selects less-preferred applicants, raises overall applicant welfare with individual effects depending on value and risk tolerance, and is more robust to application-number differences.

Conclusion

  • Monoculture selects less-preferred applicants, as predicted theoretically and verified in computational experiments.The framework captures competition and limited decision-maker capacity in large markets.Source: §7 · p. 28
  • Monoculture yields higher overall applicant welfare, although individual effects depend on applicants’ value to decision-makers and risk tolerance.Source: §7 · p. 28
  • Monoculture is more robust than polyculture to differences in the number of applications submitted by applicants.Source: §7 · p. 28
  • The framework inherits tractability from Azevedo and Leshno (2016) and can be adapted to other ways of modeling preference approximation and stable matching.It evaluates resulting stable matches against participants’ true preferences.Source: §7 · pp. 28–29

A Preliminary Results

Under the connected-support assumption for student values and noise, the appendix establishes properties of their distribution functions and of intervals within the value support. These properties support subsequent proofs.

A.1 Observations About Measures with Connected Support

  • The student-value measure η and noise measure π are assumed to have connected support, each represented by an interval that may have infinite endpoints.Source: §A.1 · p. 33
  • The CDFs F_V and F_X are strictly increasing within their respective support intervals and take values strictly between zero and one there.Source: §A.1 · p. 33
  • Any interval intersecting the interior of the value support contains positive η-measure.The proof uses strict increase of F_V on the support interval.Source: §A.1 · p. 33

A.2 The Lattice Theorem for Stable Matchings

The lattice theorem states that market-clearing cutoff vectors form a complete lattice. The paper uses this structure to prove uniqueness of stable matchings with equal cutoffs.

A.2 The Lattice Theorem for Stable Matchings

  • The set of market-clearing cutoffs forms a complete lattice under the defined operators.Source: §A.2 · pp. 33–34
  • The lattice result supplies maximum and minimum cutoff vectors for the equal-cutoffs lemmas.Source: §A.2 · p. 34
  • The equal-cutoffs lemmas show that these extremal vectors have identical cutoffs and coincide, yielding a unique stable matching.Source: §A.2 · p. 34

B Proofs for Section 3

The proofs establish uniqueness of the market-clearing cutoff by showing that its greatest and least values coincide under both monoculture and polyculture. Theorem 1’s proof proceeds through parts (i) and (ii).

B Proofs for Section 3

  • Symmetry makes the greatest and least market-clearing cutoff vectors constant across firms, reducing uniqueness to showing their common values are equal.The proof treats monoculture and polyculture separately.Source: B Proofs for Section 3 · p. 34
  • Under monoculture, assuming the greatest cutoff exceeds the least creates a positive-measure set where match probabilities differ, contradicting equal matched mass.The proof uses strict increase of F_X on the noise support to establish the probability difference.Source: B Proofs for Section 3 · pp. 34–35
  • For polyculture, the argument likewise applies with X(m): Pr[v + X(m) > P+] < Pr[v + X(m) > P−] on I = (P−−X+, P−−X−), a set of positive η-measure.Source: B Proofs for Section 3 · p. 35

B.1 Proof of Theorem 1

  • Theorem 1’s proof addresses part (i) before part (ii).Source: §B.1 · p. 36

B.1.1 Theorem 1(i)

The proof uses a concentration threshold under polyculture to establish Theorem 1(i). For sufficiently many firms, the threshold is close to the value separating the top S proportion of applicants.

B.1.1 Theorem 1(i)

  • Lemma 10 asserts that when D is maximum concentrating, its stated conclusions hold for every ε, δ > 0 once m is sufficiently large; the excerpt does not specify those conclusions.Source: §B.1.1 · p. 36
  • The value Ppoly − E[X(m)] is a threshold because an applicant with that value has expected maximum score exactly equal to Ppoly.Source: §B.1.1 · p. 37
  • The threshold is near vS, and matching probability under polyculture shifts from nearly zero below it to almost one above it as m grows.vS is the value above which exactly an S proportion of applicants lie.Source: §B.1.1 · p. 37

B.1.2 Theorem 1(ii)

Under monoculture, the cutoff and an applicant’s match probability remain fixed as the number of firms changes. Nevertheless, college welfare is suboptimal because a positive-measure set of applicants has an intermediate probability of being matched.

B.1.2 Theorem 1(ii)

  • The monoculture cutoff Pmono is the same for every m, so each applicant’s probability of exceeding it is constant as the number of firms changes.Source: §B.1.2 · p. 38
  • College welfare is suboptimal under monoculture.Source: §B.1.2 · p. 39
  • A positive-measure set of applicants has a matching probability strictly between zero and one under monoculture.The proof identifies the interval as (Pmono−X+, Pmono−X−).Source: §B.1.2 · p. 39

B.2 Proofs for Section 3.2

Theorem 2 compares applicants’ likelihood of matching and their match rank across the two cultures. Under monoculture, any applicant who receives an offer matches to their top choice.

B.2 Proofs for Section 3.2

  • An applicant’s probability of a top-choice match is the probability their score exceeds the relevant cutoff, with separate cutoffs for monoculture and polyculture.Source: §B.2 · p. 39
  • Any applicant receiving an offer under monoculture receives offers from all firms and matches to their top choice.Source: §B.2 · p. 39
  • The proof compares matching probabilities on the nonempty interval (vS, Pmono−X−), which intersects the applicant-value support.Source: §B.2 · p. 40

C Proofs for Section 4

The proofs use symmetry and market-clearing arguments to establish properties of cutoffs and matching probabilities. They show that the extreme market-clearing cutoffs coincide and that polyculture matching probability increases with application count, strictly so for some values.

Proof of Lemma 5

  • By symmetry, any permutation of a market-clearing cutoff vector is also market-clearing.The proof then identifies the constant vectors (P+, …, P+) and (P−, …, P−) as the greatest and least elements of the complete lattice of market-clearing cutoffs.Source: C Proofs for Section 4 · p. 40
  • P+ = P−: the proof rules out distinct greatest and least market-clearing cutoffs by showing they would imply different total matched measures.It identifies a positive-measure interval where the probability of exceeding P+ is strictly below that of exceeding P−, contradicting market clearing.Source: C Proofs for Section 4 · pp. 40–41

Proof of Theorem 3

  • Theorem 3 part (i) follows from the equality Pmono = Pmono,κ.Source: C Proofs for Section 4 · p. 41
  • For polyculture, the probability of matching given k applications increases with k, and is strictly increasing for values in the specified interval.The proof uses that FX(Ppoly,κ) lies strictly between 0 and 1 when v ∈ (Ppoly,κ−X+, Ppoly,κ−X−).Source: C Proofs for Section 4 · p. 41
Loading 2312.09841v1…