Matching: set M of family-animal pairs where each family/animal is in at most one pair

Perfect Matching: each family/animal in exactly one pair (required to have same number of families as animals)

Instability (with respect to matching M): a pair (f, j) does not exist in M such that:

• (f, j’) exists in M, but f prefers j to j’
• (f’, j) exists in M, but j prefers f to f’

So (f, j) is the instability

Stable Matching: perfect matching with no instabilities