Module 11 — Matching and Market Design

Core question

How should scarce, indivisible positions be assigned when prices are absent, restricted, or ethically inappropriate?

Learning outcomes

You will be able to:

• define a matching, blocking pair, stability, and justified envy;
• run deferred acceptance and explain proposer optimality;
• compare stability, strategy-proofness, and Pareto efficiency;
• execute top trading cycles and describe kidney-exchange constraints;
• audit a matching system for usability, congestion, and distribution.

1. Matching is not an auction without money

In one-to-one matching, each agent on side S ranks agents on side C and vice versa. A matching μ assigns each participant at most one partner and is reciprocal:

A pair (s,c) blocks μ if:

• s prefers c to μ(s); and
• c prefers s to μ(c).

A matching is stable if it is individually rational and has no blocking pair. Stability prevents a pair from wanting to bypass the mechanism; it is not identical to total-surplus maximisation.

2. Student-proposing deferred acceptance

Algorithm:

1. Every unassigned student applies to the highest-ranked school not yet tried.
2. Each school tentatively holds its highest-priority applicants up to capacity and rejects the rest.
3. Rejected students apply to their next choice.
4. Stop when no rejection occurs; tentative holdings become final.

Worked run

Student preferences:

• A: X ≻ Y ≻ Z
• B: X ≻ Z ≻ Y
• C: Y ≻ X ≻ Z

School priorities:

• X: C ≻ B ≻ A
• Y: A ≻ C ≻ B
• Z: B ≻ A ≻ C

Final matching: A–Y, B–Z, C–X.

3. What deferred acceptance guarantees

With strict preferences and responsive/substitutable school choice:

• the result is stable;
• student-proposing DA gives every student their best assignment among stable matchings;
• truthful preference reporting is a dominant strategy for students in the standard model;
• the receiving side need not have a truthful dominant strategy.

It does not guarantee the Pareto-best assignment among all matchings, because an unstable matching may make students better off while violating priorities. Strategy-proofness can also fail operationally when application lists are truncated, priorities are uncertain, or couples and complementarities break substitutability.

4. School priorities are not school welfare

Public-school choice often uses priorities—siblings, location, test score, lottery—not preferences representing a school's utility. Stability then means no justified envy: no student prefers a school where a lower-priority student received a place.

Design choices remain normative:

• neighbourhood versus city-wide access;
• lotteries versus exams;
• reserved seats and affirmative priorities;
• walk zones, siblings, and continuity;
• tie-breaking common across schools or independent.

The algorithm cannot decide which priorities are fair; it implements the priorities supplied.

5. Top trading cycles for owned objects

When agents have initial ownership, top trading cycles (TTC) works as follows:

1. each agent points to the owner of their favourite remaining object;
2. each object points to its owner;
3. at least one cycle exists; execute every cycle;
4. remove matched agents/objects and repeat.

Example: A owns 1 and wants 2≻1≻3; B owns 2 and wants 1≻2≻3; C owns 3 and wants 3 most. A and B swap through a two-cycle; C keeps 3. TTC is Pareto efficient and strategy-proof in the housing-market benchmark, but it pursues ownership and efficiency rather than school-priority stability.

6. Kidney exchange turns compatibility into a graph

A patient–donor pair is a node. A directed edge i→j means donor i can give to patient j. Feasible exchanges are cycles; a non-directed donor can start a chain.

Design must account for:

• medical compatibility and match quality;
• maximum cycle length and simultaneous surgery capacity;
• chain failure and timing;
• fairness across blood types, sensitisation, age, and waiting time;
• participation by hospitals with private local options.

Maximising the number of transplants can differ from maximising expected graft quality or giving priority to hard-to-match patients.

7. Practical market-design principles

Market design is engineering with strategic users. A mathematically attractive mechanism can fail if forms, deadlines, advice, or appeal rules change actual behaviour.

8. Evidence case: correlation neglect in school choice

Rees-Jones, Shorrer, and Tergiman run three incentivised school-choice experiments. When schools use a common priority—so admissions outcomes are correlated—participants choose more aggressive application strategies and omit attractive safety options relative to otherwise comparable independent assessments. Their tests point partly to correlation neglect (2024).

The implication is not simply “students should strategise better.” Designers can simplify probability communication, reduce harmful list constraints, provide decision support, or choose mechanisms less sensitive to mistaken beliefs. The evidence is experimental; real applications also involve advice, family constraints, heterogeneous stakes, and institutional trust.

9. Audit a matching market

Ask:

1. who may participate and who is missing?
2. are preferences, priorities, and capacities correctly represented?
3. which side has a truthful strategy?
4. what fairness concept is implemented?
5. can participants understand correlated risk and list constraints?
6. are there blocking pairs, empty places, or early contracting?
7. how are ties, appeals, late arrivals, and dynamic changes handled?

Practice

1. Verify that the worked DA matching has no blocking pair.
2. Run school-proposing DA and compare outcomes for both sides.
3. Construct a matching that Pareto improves students' assignments but violates one priority.
4. Execute TTC for four agents with one three-cycle and one self-cycle.
5. Design one communication intervention for correlated admissions and a test of its effect.

Quick check

• Stability prevents mutually preferred deviations; it is not total-surplus efficiency.
• Proposer-optimal DA is strategy-proof for the proposing side in the benchmark.
• Priorities are policy inputs, not discovered by the algorithm.
• TTC serves ownership exchange, while DA serves stability.
• Practical design includes cognition, timing, participation, and appeals.

Next: integrate choice, strategy, information, and welfare in a platform design.