Men-Optimal Deferred Acceptance — Gale-Shapley & Stable Matching

Controls

Speed: 1.0s

Men's Preferences

Each row: most preferred → least preferred

Man	1st	2nd	3rd	4th

Women's Preferences

Each row: most preferred → least preferred

Woman	1st	2nd	3rd	4th

Algorithm Pseudocode

Men-Proposing Deferred Acceptance:

1. Each free man proposes to the
   highest-ranked woman on his list
   he has not yet proposed to.

2. Each woman who receives proposals
   holds her most-preferred suitor
   and rejects the rest.

3. Rejected men become free and
   propose to their next choice.

4. Repeat until no free men remain.

Time complexity: O(n²)
Space complexity: O(n²)

Step Log

Men-Optimal Stable Matching

This is the men-optimal stable matching. Every man is assigned his best possible partner across ALL stable matchings. Simultaneously, every woman receives her worst stable partner.