Matching Markets: When Prices Can’t Do the Job

Computational Analysis of Social Complexity
Fall 2026, Spencer Lyon

Prerequisites

L11.01–L12.01
Auctions (week 9)
Graphs (week 3)
DataFrames and CSV (weeks 1–2)

Outcomes

Define stability and blocking pairs in two-sided matching
Implement Gale–Shapley deferred acceptance and a stability checker in Julia
Explain proposer-optimality and its market-design consequences
Analyze a real marketplace dataset from a two-sided perspective

References

Easley and Kleinberg, Chapter 10: Matching Markets (required)
The Prize in Economic Sciences 2012: Stable Allocations and the Practice of Market Design (required)
Gale and Shapley (1962), “College Admissions and the Stability of Marriage”
Roth, Who Gets What—and Why (optional)
Matchmakers (Evans and Schmalensee, 2016) (optional)

You Need a Kidney¶

Roughly 100,000 people are on the U.S. organ-transplant waitlist
Paying someone for a kidney is a felony in the United States, and organ sales are prohibited nearly everywhere
Yet thousands of transplants happen each year between people who began as strangers
- An incompatible donor–patient pair can swap with another pair
- An algorithm searches for compatible cycles and chains
Algorithms from the same matching family assign every U.S. medical resident to a hospital and many New York City students to public schools
Some markets are repugnant to clear with prices—or simply too complex—so we design the match
This marriage of theory and practice earned Alvin Roth and Lloyd Shapley the 2012 Nobel Prize in Economic Sciences

When a Price Is Not the Answer¶

Last time we separated a platform’s price structure from its price level
But what if the right price is illegal, unacceptable, or not enough to identify who should meet whom?
A hospital cares which doctor it hires; a doctor cares which hospital hires them
These are two-sided markets, but the central object is a pair—not a transaction price
Today we replace willingness-to-pay with preference rankings

Build 1: The Stable Matching Problem¶

We have two equally sized sides: doctors $D$ and hospitals $H$
Every doctor ranks every hospital; every hospital ranks every doctor
There are no prices in this model
A matching $\mu$ pairs each doctor with one hospital
A doctor–hospital pair $(d,h)$ is a blocking pair when:
- Doctor $d$ prefers hospital $h$ to $\mu(d)$ , and
- Hospital $h$ prefers doctor $d$ to its assigned doctor
A matching is stable when it has no blocking pair

Stability Is an Equilibrium Concept¶

Recall Nash equilibrium from week 8: no player can profitably deviate on their own
Stability asks a closely related question: can two agents profitably deviate together?
The deviations here are pairwise
If a blocking pair exists, the announced matching is fragile
- The doctor and hospital would rather abandon it and match with each other
Stable does not mean fair, unique, or socially optimal
It means the matching can defend itself against every pairwise objection

A Tiny Market: Find the Block¶

Doctors’ rankings:
- $D_1: H_1 \succ H_2 \succ H_3$
- $D_2: H_1 \succ H_2 \succ H_3$
- $D_3: H_2 \succ H_1 \succ H_3$
Hospitals’ rankings:
- $H_1: D_2 \succ D_1 \succ D_3$
- $H_2: D_1 \succ D_3 \succ D_2$
- $H_3: D_3 \succ D_2 \succ D_1$
Start with $\mu_0 = \{(D_1,H_1),(D_2,H_2),(D_3,H_3)\}$
Look at $(D_2,H_1)$ :
- $D_2$ prefers $H_1$ to $H_2$
- $H_1$ prefers $D_2$ to $D_1$
So $(D_2,H_1)$ is a blocking pair and $\mu_0$ is not stable

Fixing the Match by Hand¶

Swap the first two assignments:
- $\mu_1 = \{(D_1,H_2),(D_2,H_1),(D_3,H_3)\}$
$D_2$ now has their first choice
$D_1$ wants $H_1$ , but $H_1$ prefers its current doctor $D_2$
$D_3$ wants $H_2$ or $H_1$ , but both hospitals prefer their current doctors
No doctor–hospital pair wants to leave together
Therefore $\mu_1$ is stable
Checking every pair works for $3 \times 3$ ; we need an algorithm for $50 \times 50$

Build 2: Deferred Acceptance¶

Gale and Shapley’s deferred-acceptance algorithm proceeds in rounds
1. Each unmatched proposer proposes to their best choice that has not rejected them
2. Each receiver tentatively holds its best offer so far and rejects the rest
3. Rejected proposers try their next choice
4. Repeat until no proposer is unmatched
Tentative is doing important work: a receiver may trade up later
The process must stop because no proposer visits the same receiver twice
The remarkable result: it always stops at a stable matching

using Random
using Statistics
using Plots
using DataFrames
using CSV
using Downloads

Rankings as Matrices¶

Each row of a preference matrix lists options from best to worst
Algorithms also need the inverse representation: the rank assigned to each option
Example: if row 1 is [2, 1, 3], option 2 has rank 1 and option 1 has rank 2
We will keep both representations because each makes a different operation simple

doctor_prefs = [
    1 2 3;
    1 2 3;
    2 1 3
]

hospital_prefs = [
    2 1 3;
    1 3 2;
    3 2 1
]

function preference_ranks(preferences)
    n_people, n_options = size(preferences)
    ranks = zeros(Int, n_people, n_options)
    for person in 1:n_people
        for (rank, option) in enumerate(preferences[person, :])
            ranks[person, option] = rank
        end
    end
    return ranks
end

doctor_rank = preference_ranks(doctor_prefs)
hospital_rank = preference_ranks(hospital_prefs)

Hand-Coding the Algorithm¶

held_by_receiver[h] records the proposer tentatively held by receiver $h$
next_choice[d] records where proposer $d$ should apply next
Our queue contains proposers who are currently unmatched
Rejection sends a proposer to the back of that queue

function deferred_acceptance(proposer_prefs, receiver_rank)
    n_proposers, n_receivers = size(proposer_prefs)
    n_proposers == n_receivers || error("This version expects equal sides")
    size(receiver_rank) == (n_receivers, n_proposers) || error("Rank dimensions do not match")

    next_choice = ones(Int, n_proposers)
    held_by_receiver = zeros(Int, n_receivers)
    proposal_queue = collect(1:n_proposers)
    queue_head = 1

    while queue_head <= length(proposal_queue)
        proposer = proposal_queue[queue_head]
        queue_head += 1
        next_choice[proposer] <= n_receivers || error("A proposer exhausted all choices")

        receiver = proposer_prefs[proposer, next_choice[proposer]]
        next_choice[proposer] += 1
        incumbent = held_by_receiver[receiver]

        if incumbent == 0
            held_by_receiver[receiver] = proposer
        elseif receiver_rank[receiver, proposer] < receiver_rank[receiver, incumbent]
            held_by_receiver[receiver] = proposer
            push!(proposal_queue, incumbent)
        else
            push!(proposal_queue, proposer)
        end
    end

    matching = zeros(Int, n_proposers)
    for receiver in 1:n_receivers
        matching[held_by_receiver[receiver]] = receiver
    end
    return matching
end

mu_tiny = deferred_acceptance(doctor_prefs, hospital_rank)
collect(zip(["D1", "D2", "D3"], ["H$(h)" for h in mu_tiny]))

function is_stable(matching, proposer_rank, receiver_rank)
    n = length(matching)
    sort(matching) == collect(1:n) || return false

    receiver_partner = zeros(Int, n)
    for proposer in 1:n
        receiver_partner[matching[proposer]] = proposer
    end

    for proposer in 1:n, receiver in 1:n
        current_receiver = matching[proposer]
        current_proposer = receiver_partner[receiver]
        proposer_wants = proposer_rank[proposer, receiver] < proposer_rank[proposer, current_receiver]
        receiver_wants = receiver_rank[receiver, proposer] < receiver_rank[receiver, current_proposer]
        proposer_wants && receiver_wants && return false
    end
    return true
end

bad_matching = [1, 2, 3]
(
    hand_solution = mu_tiny,
    hand_solution_is_stable = is_stable(mu_tiny, doctor_rank, hospital_rank),
    original_match_is_stable = is_stable(bad_matching, doctor_rank, hospital_rank),
)

Scaling Up: A Random $50 \times 50$ Market¶

Hand inspection becomes impossible quickly
We will give every participant an independent random ranking
Then we will time deferred acceptance and check all 50² possible pairs
Recall our ABMs: simple local rules can generate an orderly aggregate outcome
Here repeated proposals and rejections generate global stability

Random.seed!(6318)
n = 50
random_preferences(n) = permutedims(reduce(hcat, [randperm(n) for _ in 1:n]))

doctor_prefs_50 = random_preferences(n)
hospital_prefs_50 = random_preferences(n)
doctor_rank_50 = preference_ranks(doctor_prefs_50)
hospital_rank_50 = preference_ranks(hospital_prefs_50)

elapsed_50 = @elapsed mu_50 = deferred_acceptance(doctor_prefs_50, hospital_rank_50)
(stable = is_stable(mu_50, doctor_rank_50, hospital_rank_50), seconds = elapsed_50)

Reveal: Who Gets to Propose?¶

The algorithm sounds symmetric, but it is not
Run deferred acceptance twice on the same market:
- Once with doctors proposing
- Once with hospitals proposing
Both outcomes will be stable
When multiple stable matchings exist, each side prefers to control the proposals
Let’s begin with the smallest market where the difference is visible

Exercise 1: Two Stable Matchings¶

Consider this $2 \times 2$ preference profile:
- $D_1: H_1 \succ H_2$ and $D_2: H_2 \succ H_1$
- $H_1: D_2 \succ D_1$ and $H_2: D_1 \succ D_2$
Show that both the diagonal and cross matchings are stable
Predict: which matching does doctor-proposing deferred acceptance find?
Which matching does hospital-proposing deferred acceptance find?
Explain each answer using the absence of a blocking pair

doctor_prefs_2 = [1 2; 2 1]
hospital_prefs_2 = [2 1; 1 2]
doctor_rank_2 = preference_ranks(doctor_prefs_2)
hospital_rank_2 = preference_ranks(hospital_prefs_2)

mu_doctors_propose = deferred_acceptance(doctor_prefs_2, hospital_rank_2)
h_to_d = deferred_acceptance(hospital_prefs_2, doctor_rank_2)
mu_hospitals_propose = invperm(h_to_d)

(doctors_propose = mu_doctors_propose, hospitals_propose = mu_hospitals_propose)

function average_rank(matching, rank_matrix)
    mean(rank_matrix[person, matching[person]] for person in eachindex(matching))
end

(
    doctors_propose_stable = is_stable(mu_doctors_propose, doctor_rank_2, hospital_rank_2),
    hospitals_propose_stable = is_stable(mu_hospitals_propose, doctor_rank_2, hospital_rank_2),
    doctor_ranks = (average_rank(mu_doctors_propose, doctor_rank_2), average_rank(mu_hospitals_propose, doctor_rank_2)),
    hospital_ranks = (average_rank(invperm(mu_doctors_propose), hospital_rank_2), average_rank(invperm(mu_hospitals_propose), hospital_rank_2)),
)

Algorithm Design Is Market Power¶

Both matchings are stable—but they distribute rank very differently
Doctor-proposing deferred acceptance gives every doctor their best outcome among all stable matchings
Hospital-proposing deferred acceptance gives every hospital its best stable outcome
This is proposer-optimality
The NRMP redesigned its algorithm in 1997 to be applicant-proposing precisely because the choice of proposer matters
Deferred acceptance is also strategy-proof for proposers: truthful rankings are a dominant strategy for that side
Recall second-price auctions from week 9: a different mechanism, but the same truthfulness flavor
A neutral-looking line of algorithm design can shift market power

Exercise 2: Hospitals Have Capacity¶

The real NRMP is many-to-one: a hospital can accept $q_h > 1$ residents
Modify deferred acceptance so each hospital tentatively holds up to its capacity
When a hospital is full, it should reject its least-preferred held doctor
What must the returned matching contain when total capacity exceeds the number of doctors?

function deferred_acceptance_capacities(proposer_prefs, receiver_rank, capacities)
    # TODO: track a collection of tentative matches at each receiver
    # TODO: reject the worst held proposer when capacity is exceeded
    # TODO: return one receiver (or 0 if unmatched) for each proposer
    return nothing
end

Exercise 3: Measure the Proposer Advantage¶

Generate 100 random $20 \times 20$ markets
Run deferred acceptance from both sides in every market
Record the average rank achieved by proposers and receivers
Plot histograms for the two distributions
Is the proposer advantage present in every realization, or only on average?
What conclusion would you report to a market designer?

function proposer_advantage_experiment(; markets=100, n=20, seed=1202)
    Random.seed!(seed)
    proposer_average_ranks = Float64[]
    receiver_average_ranks = Float64[]
    # TODO: generate preferences and run deferred acceptance `markets` times
    # TODO: push each side's average rank into the vectors above
    # TODO: make side-by-side histograms and interpret the result
    return proposer_average_ranks, receiver_average_ranks
end

# Run after completing the TODOs:
# proposer_ranks, receiver_ranks = proposer_advantage_experiment()
nothing

Build 3: Platforms Mix Matching and Prices¶

Deferred acceptance is useful when prices cannot—or should not—do the job
Most platforms in the wild combine both instruments
- Airbnb recommends and ranks listings: matching
- Hosts post nightly rates and guests choose budgets: prices
The platform also manages cross-side network effects between hosts and guests
Let’s use Inside Airbnb data to inspect one local market
The download is optional: every analysis cell also works offline

airbnb_url = "https://data.insideairbnb.com/united-states/nc/asheville/2025-06-11/visualisations/listings.csv"
airbnb_path = "airbnb_listings.csv"

# Any city CSV from https://insideairbnb.com/get-the-data/ works identically.
if !isfile(airbnb_path)
    try
        Downloads.download(airbnb_url, airbnb_path)
    catch err
        @warn "Airbnb download unavailable; continuing in offline mode" exception=(err, catch_backtrace())
    end
end

data_available = isfile(airbnb_path)

airbnb = DataFrame()
if data_available
    try
        airbnb = CSV.read(airbnb_path, DataFrame)
    catch err
        @warn "Cached Airbnb file could not be read; continuing in offline mode" exception=(err, catch_backtrace())
        data_available = false
    end
end

if data_available
    first(select(airbnb, [:name, :host_name, :room_type, :price, :reviews_per_month]), 6)
else
    DataFrame(status=["Offline: place a cached city file at $(airbnb_path) to run the lab."])
end

Price Distributions by Room Type¶

A shared room and an entire home are not the same product
Pooling them would confuse composition with price differences
Prices may also contain missing values or arrive as currency strings
We will clean the field, use skipmissing, and trim only the plot at the 99th percentile
The original rows remain untouched

function clean_price(x)
    ismissing(x) && return missing
    x isa Number && return Float64(x)
    cleaned = filter(c -> c != '$' && c != ',', String(x))
    parsed = tryparse(Float64, cleaned)
    return parsed === nothing ? missing : parsed
end

if data_available
    airbnb.price_clean = clean_price.(airbnb.price)
end
nothing

if data_available
    room_types = sort(collect(skipmissing(unique(airbnb.room_type))))
    all_prices = Float64.(collect(skipmissing(airbnb.price_clean)))
    price_cap = isempty(all_prices) ? 1.0 : quantile(all_prices, 0.99)
    p_room = plot(xlabel="Nightly price (USD)", ylabel="Listings", title="Asheville prices by room type")
    for room in room_types
        room_mask = coalesce.(airbnb.room_type .== room, false)
        values = Float64.(collect(skipmissing(airbnb.price_clean[room_mask])))
        values = filter(p -> 0 <= p <= price_cap, values)
        isempty(values) || histogram!(p_room, values; bins=30, alpha=0.45, label=String(room))
    end
    p_room
else
    plot(title="Price distribution unavailable offline", legend=false)
end

Discuss the Price Plot¶

Which room type has the highest typical nightly price? Is that surprising?
Compare spread as well as the center: where is host-side product differentiation strongest?
The right tail reminds us that a platform hosts several submarkets, not one homogeneous good

Reviews per Month and Price¶

Reviews are an imperfect proxy for booking activity
Price is an imperfect proxy for quality
A scatter plot will not identify a demand curve
- Expensive listings may also be larger, better located, or available less often
Still, the joint distribution can reveal segmentation and unusual listings
We again skip missing values explicitly

if data_available
    review_values = Float64[]
    scatter_prices = Float64[]
    for row in eachrow(airbnb)
        if !ismissing(row.reviews_per_month) && !ismissing(row.price_clean)
            push!(review_values, Float64(row.reviews_per_month))
            push!(scatter_prices, Float64(row.price_clean))
        end
    end
    review_cap = isempty(review_values) ? 1.0 : quantile(review_values, 0.99)
    scatter_cap = isempty(scatter_prices) ? 1.0 : quantile(scatter_prices, 0.99)
    visible = (review_values .<= review_cap) .& (scatter_prices .<= scatter_cap) .& (scatter_prices .>= 0)
    scatter(review_values[visible], scatter_prices[visible]; alpha=0.35, markersize=3, legend=false,
        xlabel="Reviews per month", ylabel="Nightly price (USD)", title="Activity and price")
else
    plot(title="Review–price scatter unavailable offline", legend=false)
end

Discuss the Scatter Plot¶

Is there a clear relationship, or mostly a cloud?
Which mechanisms could produce a negative association between price and reviews per month?
Why would interpreting this picture causally be a mistake? Name at least two omitted variables

Who Supplies the Listings?¶

The original story of Airbnb was peer-to-peer: one host, one spare room, one guest
But platform growth can invite professional operators
We will count listings by host and display the largest portfolios
This is a same-side concentration question nested inside a cross-side marketplace

if data_available
    host_rows = airbnb[.!ismissing.(airbnb.host_id), [:host_id, :host_name]]
    host_counts = combine(groupby(host_rows, [:host_id, :host_name]), nrow => :listing_count)
    sort!(host_counts, :listing_count, rev=true)
    top_hosts = first(host_counts, min(15, nrow(host_counts)))
    labels = [ismissing(name) ? "Host $(id)" : String(name) for (id, name) in zip(top_hosts.host_id, top_hosts.host_name)]
    bar(reverse(labels), reverse(top_hosts.listing_count); orientation=:horizontal, legend=false,
        xlabel="Number of listings", ylabel="Host", title="Largest host portfolios", size=(800, 500))
else
    plot(title="Host concentration unavailable offline", legend=false)
end

Discuss Host Professionalization¶

Do the largest portfolios look like occasional home sharing or a professional lodging business?
How might professional hosts change same-side competition among hosts?
How might they change cross-side value for guests through consistency, variety, or market power?
Is Airbnb still peer-to-peer? The answer may depend on whether we describe the technology, the typical host, or the typical listing

Exercise 4: Quantify Professionalization¶

Compute the share of listings held by hosts with 10 or more listings
Also compute the share of hosts with 10 or more listings
Why are these two denominators telling different stories?
What does your result imply for the platform’s “peer-to-peer” framing?

if data_available
    # TODO: use `host_counts.listing_count` from the previous analysis
    # TODO: compute listing share = listings held by 10+ hosts / all listings
    # TODO: compute host share = hosts with 10+ listings / all hosts
    nothing
else
    nothing
end

The Platforms Unit in One Slide¶

L11.01: Platforms create value by connecting sides through same-side / cross-side network effects
L11.02: They solve a chicken-and-egg problem, fight toward critical mass, and may experience tipping
L12.01: They choose price structure as well as price level, often subsidizing one side
Today: They sometimes replace prices with matching algorithms entirely
Multihoming can soften lock-in, but it does not remove the platform’s power to rank, recommend, price, or match
Stable matching shows that the rules connecting agents determine who benefits—even when no money changes hands
Matchmaking is the oldest business model—and maybe the newest: GPU and model marketplaces are two-sided markets for intelligence itself

Closing the Semester¶

We began with networks: who is connected to whom?
We added games: how do incentives shape choices?
We built ABMs: how do simple local rules create emergent outcomes?
We studied agents: how do decision-makers perceive, act, and adapt?
We ended with platforms and matching: who writes the rules that connect everyone?
Across the semester, one question kept returning:
- How do individual choices aggregate into collective outcomes?
Your final project is your chance to answer that question for a system you care about
Thank you for bringing your questions, code, and ideas to the course
Next time is yours: the final project is where you design the model, run the computation, and tell us what the collective outcome means

Matching Markets: When Prices Can’t Do the Job

You Need a Kidney¶

When a Price Is Not the Answer¶

Build 1: The Stable Matching Problem¶

Stability Is an Equilibrium Concept¶

A Tiny Market: Find the Block¶

Fixing the Match by Hand¶

Build 2: Deferred Acceptance¶

Rankings as Matrices¶

Hand-Coding the Algorithm¶

Scaling Up: A Random 50×5050 \times 5050×50 Market¶

Reveal: Who Gets to Propose?¶

Exercise 1: Two Stable Matchings¶

Algorithm Design Is Market Power¶

Exercise 2: Hospitals Have Capacity¶

Exercise 3: Measure the Proposer Advantage¶

Build 3: Platforms Mix Matching and Prices¶

Price Distributions by Room Type¶

Discuss the Price Plot¶

Reviews per Month and Price¶

Discuss the Scatter Plot¶

Who Supplies the Listings?¶

Discuss Host Professionalization¶

Exercise 4: Quantify Professionalization¶

The Platforms Unit in One Slide¶

Closing the Semester¶

Scaling Up: A Random $50 \times 50$ Market¶