Stable Marriage Problem

These flashcards cover key concepts, definitions, and outcomes related to the stable marriage problem as introduced in the lecture notes.

What is the stable marriage problem?

It involves finding a matching between boys and girls based on their preference lists, such that no rogue couples are formed.

What defines a rogue couple in a matching?

A rogue couple is defined as a pair of individuals who are not matched to each other but would prefer each other over their current partners.

In the context of the stable marriage problem, what does a stable matching ensure?

A stable matching ensures that there are no rogue couples.

What does M={(4,192), (6,50), (6,94), (b4, 93)} represent in the stable marriage problem?

It represents a specific matching between boys and girls.

What can be said about the matching where every girl is matched to her favorite boy?

It is a stable matching as per the defined criteria.

Is it possible for preference lists to be such that everyone is matched with the second person on their list?

No, it is not possible to arrange preference lists in that manner for all boys and girls.

When given preference lists, what does it mean for a couple to be 'not stable'?

It means that there exists at least one rogue couple among the matches.

In the stable marriage problem with n=2, what can be said about the preferred pairings?

It is impossible to have preference lists such that all individuals can be matched to their second choices.

How many stable matchings can occur with n boys and n girls?

The exact number of stable matchings is not known, but it is approximately factorial in terms of the number of participants.

Is there at least one stable matching for any preference list given in the stable marriage problem?

Yes, it is true that there is at least one stable matching for any set of preference lists.