Discrete mathematics and graph theory · Maths EE idea · Solid

Stable matchings

A research question to start from

Why does the Gale–Shapley algorithm always produce a stable matching, and why does it favour the side that proposes?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

An algorithm with elegant proofs of termination, stability and optimality.

Mathematics you would need

Matchings
Proof by contradiction
Termination arguments
Optimality

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Run the algorithm on small examples.
Prove termination and stability.
Prove proposer-optimality and discuss fairness.

Scope and difficulty

Solid. Solid.

Pitfalls

Economics essay.
Proofs replaced by examples.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Gale-Shapley proof stability proposer optimal. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.