Stable Matching Invariants
We are interested in invariants of the Mating Ritual described in the Notes for finding stable marriages when there are an equal number of boys and girls. Let Angelina and Jen be two of the girls, and Keith and Tom be two of the boys.
1 4 5
Which of the following predicates are preserved invariants of the Mating Ritual no matter what the preferences are among the boys and girls? (Remember that a predicate that is always false is a preserved invariant －check the definition to see why. Also, a preserved invariant doesn't need to be true initially, it just needs to stay true once it starts being true.)
Express your answer as a sequence of digits in increasing order separated by spaces, for example,
- Angelina is crossed off Tom's list, and she has a suitor that she prefers to Tom.
- Tom is serenading Jen.
- Tom is not serenading Jen.
- Tom's list of girls to serenade is empty.
- All the boys have the same number of girls left uncrossed in their lists.
- Jen is crossed off Keith's list, and Keith prefers Jen to anyone he is serenading.
- Jen is the only girl on Keith's list.
- Jen is crossed off Keith's list, and there is no set of stable marriages －not just the set produced by the Mating Ritual －in which Jen is married to Keith.
- Invariant: This is the basic invariant used to verify the Ritual.
- Not invariant: If Tom serenades Jen and gets rejected by her, he will stop serenading her.
- Not invariant: Tom might serenade Angelina, get rejected by her, and then serenade Jen next.
- Invariant: No girl will ever get added to Tom's list, so once his list is empty, it stays empty. This implies that Tom's list will never be empty, since the Ritual guarantees he will be married in the end. That is, this predicate is an invariant because it is always false. But it would still be an invariant even if we ran the Mating Ritual with more boys than girls, in which case Tom's list might become empty, but then would stay that way.
- Not invariant: Suppose all the boys like Angelina best. The she will reject all but her favorite, say it's Tom, on the first day. Now, on the second day, Tom's list will be one longer than all the other boys' lists.
- Invariant: Keith crosses off the girls he most prefers, so if Jen is crossed off, Keith likes her better than anybody that's left.
- Invariant: No girls get added to a list, so if Jen is the only girl on Keith's list, she must be the girl he marries at the end.
- Invariant: If Jen is crossed off Keith's list, then, since her suitors only become more desirable, she will wind up with a husband she prefers to Keith. But the Mating Ritual yields girl-pessimal marriages, so in every stable set of marriages, Jen will wind up with someone she prefers to Keith, and so will never be interested in having him as a rogue partner.