Week 8 Tutorial: Run Gale–Shapley by Hand

Execute the stable matching algorithm on a small preference table, from both sides

17 April 2028

Before the tutorial

Bring the week 8 deck’s worked example fresh in mind — this session repeats the exercise on a fresh table you haven’t seen. Deciding who does the dishes afterwards is, once again, not covered.

In the tutorial

Working in pairs, run the algorithm by hand: propose, hold, reject, repeat, until every match is final. Then swap which side proposes and re-run on the same preferences. Compare the two outcomes.

Afterwards

If the two runs gave different matches — they usually do — you’ve just demonstrated the proposer-optimal / receiver-optimal asymmetry yourself, which sets up week 9’s question directly: stability was never the whole story.

Printable handout

SLOP2470 — Tutorial 8 handout

Run Gale–Shapley by Hand

Monday 17 April 2028

Bring

The week 8 deck's worked example, fresh in mind

What happens in the room

In pairs, run the algorithm by hand on a fresh preference table: propose, hold, reject, repeat until every match is final
Swap which side proposes and re-run on the exact same preferences
Compare the two outcomes and find at least one person whose match changed
Debrief: this is the proposer-optimal / receiver-optimal asymmetry, demonstrated rather than just claimed

The spec

What you bring to the session. Written so a reader can tell whether it has been met without asking you.

you ran the algorithm to completion on a supplied preference table
you ran it again with the proposing side reversed
you can point to at least one person whose outcome changed between the two runs

Teaching team

Professor Barry Gaining — tutor