[Lecture] Gale Shapely matching

[jstac]

Background:

http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html
http://en.wikipedia.org/wiki/Stable_marriage_problem

In particular,

http://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm

[mmcky]

Moving this to the lectures monorepo. Under the pool model a new lecture is pitched to the shared pool rather than to a series — which product publishes it is a manifest decision made later — so this is the right home for the proposal even though the pool is still an empty placeholder pre-cutover.

Recording what exists before the move.

Nothing covers this. Org-wide searches for "deferred acceptance", "stable matching" and "assignment problem" all return zero.

One near-match to avoid conflating. Economic Networks has a Linear Assignment section, which it introduces as the problem "called matching in economics and linear assignment in mathematics", illustrated by matching workers to jobs. That is the transport-style problem — cardinal costs, minimise the total — and it is not what this issue asks for. Gale–Shapley works on ordinal preference lists with no transfers, and its object is stability rather than optimality. The two are worth explicitly distinguishing in any lecture, since the vocabulary overlaps.

We do already have an implementation, with caveats. QuantEcon/MatchingMarkets.py includes matchingmarkets/algorithms/DA.py with a gale_shapley deferred-acceptance function. Two things to know: the repo was last pushed in February 2021, and that implementation is built for dynamic matching markets — its agents carry time_to_critical and sojourn attributes — rather than the classic static stable-marriage problem. So it is a useful reference and probably not a dependency; the textbook algorithm is short enough to write directly.

Which product would select it. The natural first consumer is the intro product, where it sits alongside schelling.md, short_path.md and lp_intro.md — that series' cluster of algorithmic and agent-based topics. The NYC high-school application system in the linked article is a good motivating example, and lp_intro.md gives a useful contrast, since the assignment problem linear programming can express is the cardinal cousin of this one. Being pool content rather than series content, it could also be selected by a game-theory or market-design product later without being duplicated.

Moved from #4 as part of the disposition review in QuantEcon/meta#344.