Maths IA · Modelling · topic 97 of 97
Matching students to places: the Gale-Shapley algorithm · IB Maths IA idea: guide, sample graph and step-by-step plan
no blocking pair = stableEvery student ranks the schools and every school ranks the students. Can you pair them so that no student and school would both rather swap? Gale and Shapley proved you always can, and gave a method that finds it.
- ✓ you like proofs by contradiction and want a real use for one
- ✓ you want to combine a proof with a simulation
- ✓ you are curious how schools, hospitals or exchange programmes assign places
The big idea
A matching is stable if no student and school both prefer each other to their assigned partners. In the deferred acceptance method, free students propose down their lists and each school holds its best offer so far. It always stops, and the result is always stable. Both claims have short proofs, one by counting proposals and one by contradiction. Graph theory is AI HL content and the proofs suit AA HL, so both groups can use this topic with some self-study. The algorithm is routine. The marks come from the proofs and the simulation: why the proposing side gets its best stable outcome, and how the average number of proposals grows with the number of students.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Count the most proposals that can ever be made and show the algorithm must stop.
→ A counting argument: each student proposes to each school at most once, so there are at most n² proposals. Check it on a small case.Suppose a blocking pair exists and show this contradicts the rule that schools only trade up.
→ A proof by contradiction written out in full, then tested on matchings found by brute force.Run the algorithm with students proposing, then with schools proposing, and compare the two stable matchings.
→ The proposing side gets its best possible stable partner for every member. Prove it by induction or find a counterexample to fairness.For small n, list all matchings and test each for stability to find how many are stable.
→ Exhaustive checking that links to counting principles. See how the number of stable matchings varies with the preferences.Generate random preference lists, run the algorithm, and record the number of proposals as n grows.
→ A simulation with a theoretical comparison, about n ln n. Find a reason using the coupon-collector problem.Model school or university place allocation, or a residency match, from published rules.
→ Real rules add quotas and ties. State what changes in the proofs and what does not.Your Maths IA research question: run the check
who proposes, who ranks?Write your own question first. Then make sure it ticks every box:
- Names the matching problem: who proposes, who ranks, and how many on each side.
- Says what is proved and what is simulated, and how the two are linked.
- Defines stable precisely, with the condition for a blocking pair.
- Says how random preferences are generated and how many trials each point uses.
- States what is left out: ties, quotas, couples and strategic ranking.
The model
Preference lists on both sides, the three steps of the method, and the one pattern that makes a matching unstable. Draw a small example of your own.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
Where matching problems appear, what stable means, and a prediction before any proof.
Preference lists, the deferred acceptance method and a worked example with every step shown.
A counting proof that the algorithm terminates, with the bound checked on your example.
A proof by contradiction, written clearly, with a brute-force check on a small case.
The proposers-optimal result, proved or tested, and what it means for fairness.
A simulation for several n with a comparison to n ln n and a reason for it.
Back to your aim: what you proved, what you measured and how well they agree.
Quotas, ties, honest ranking and real systems. Say which assumption a real school system breaks first.
Where the algorithm, proofs and rules came from.
What your Maths IA graph could look like
error bars, not just meansMade-up values to show the form of a strong graph: the average number of proposals against the number of students, with a theory curve. Yours will look different. example only
- One point per n, each the mean of many simulated runs. Say how many.
- Show spread, for example error bars of two standard errors, so the reader can see the noise.
- Plot the theory curve on the same axes and say where it comes from.
- If your points sit consistently above the curve, say why before the reader asks.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictRead how the Gale-Shapley method works. Before any proof, guess how many proposals it takes for 4 students and 4 schools.
- Run a small caseMake preference lists for 4 students and 4 schools and run the method by hand, writing down every proposal.
- Check stability by brute forceList all 24 matchings of your small case and test each for a blocking pair. Compare with the algorithm's result.
- Trial run (1 lesson)Write the proof that the algorithm ends, and test the bound on your example. Fix the idea before the harder proof.
- Prove it is stableWrite the proof by contradiction. Say exactly which rule of the algorithm each step uses.
- Compare the two sidesRun the method with schools proposing. Compare the matchings and say who gains and who loses.
- Go further, with a reasonSimulate proposals for many n and compare with n ln n, or study quotas. HL: this is where the rigour for criterion E comes from.
- Explain the growthUse the coupon-collector idea to explain why proposals grow like n ln n, and say what the argument assumes.
- Reflect as you goAfter every result write one line on what it means for real admissions and what it assumes. These lines become your evaluation.
- Cut, check, then sendCheck every proof is complete, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Counting proposals – Show every student proposes to each school at most once, so the algorithm stops after at most proposals.
- Proof by contradiction – Assume a blocking pair exists and show it contradicts the rule that a school only trades up.
- Proof by induction – Show no student is ever rejected by a partner that is stable for them, which gives the proposer-optimal result.
- Expected value – Model proposals as a coupon-collector process to get as an upper bound on the expected number.
- Simulation – Generate random preferences, run the algorithm and compare mean proposals with using standard errors.
Key equations
Syllabus links
- 1.15Proof by induction, contradiction and counterexampleHL
- 1.6Simple deductive proof
- 4.7Discrete random variables and expected value
- 3.14Graph theory: vocabulary and types of graphHL
- 4.5Basic probability and expected frequency
- 4.7Discrete random variables and expected value
Read up first
Data and sources to start from
Simulate random preferences, and optionally compare with published rules of a real matching system such as a medical residency match.
References to cite
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
- Knuth, D. E. (1997). Stable marriage and its relation to other combinatorial problems. American Mathematical Society.
- The Royal Swedish Academy of Sciences. (2012). The Prize in Economic Sciences 2012 [Press release and advanced information].
- Roth, A. E. (2015). Who gets what and why: The new economics of matchmaking and market design. Houghton Mifflin Harcourt.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
an example is not a proof- Calling a matching 'best' without saying for whom. The method favours the proposing side.
- Proving stability by example. An example is a check, not a proof.
- Forgetting that a school may drop a held offer for a better one, so proposals are not decisions.
- Using too few simulation runs and calling the curve a fit.
- Claiming the average is exactly n ln n. Compare with the data and say how close it is.
- Ignoring that real students can gain by ranking dishonestly under some rules.
More Maths IA ideas like this
Exam timetables: how few sessions are needed?●●●
When should you stop looking? The 37% rule●●●
Walk every bridge once: from Königsberg to your city●●○
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.