Outside the market slides 14 stability

A matching is stable if

1) it is individually rational and 2)

there are no blocking pairs

We may not expect an unstable matching to last long.

-A blocking pair will find each other.

-A person in an unacceptable match will break it.

Gneral features for stability Theorem

here is always at least one stable matching.

Theorem

Among all the stable matchings, there are

-one that is the favorite of all women (humanoids, etc.)

-one that is the favorite of all men (droids, etc.)

Algorithm

= mechanism / procedure / recipe / protocol

Woman-proposing Deferred Acceptance algorithm

-1:each woman proposes to her highest-ranked

acceptable man. (If there isn't one, she proposes to herself.)

-2: each woman crosses off any man who rejected her,

and then she proposes to her highest-ranked remaining

acceptable man. (If there isn't one, she proposes to herself.)

-3:Repeat until a step where no woman's proposal is rejected ⇒

that's the matching.

Man-proposing Deferred Acceptance algorithm

-Just like the woman-proposing DA algorithm, except that the

roles are switched.

-In the example, the man-proposing DA algorithm yields the

same matching as the woman-proposing DA algorithm.

(Check. How many steps?)

That won't always be the case.