Discrete mathematics in Computer Science: Stable matching

Question

I am trying to understand the proof of the theorem below but do not understand definition of employer optimal. Do all employer pair with top optimal candidate means employer optimal or just at least one of employer? Could you rephrase the whole proof below?

Theorem: The matching output by the Propose-and-Reject algorithm is job/employer optimal.

Proof. Suppose for sake of contradiction that the matching is not employer optimal. Then, there exists a day on which some job had its offer rejected by its optimal candidate; let day k be the first such day. On this day, suppose J was rejected by C ∗ (its optimal candidate) in favor of an offer from J ∗ . By the definition of optimal candidate, there must exist a stable matching T in which J and C ∗ are paired together. Suppose T looks like this: {...,(J,C ∗ ),...,(J ∗ ,C ′ ),...}. We will argue that (J ∗ ,C ∗ ) is a rogue couple in T, thus contradicting stability.

First, it is clear that C ∗ prefers J ∗ to J, since she rejected an offer from J in favor of an offer from J ∗ during the execution of the propose-and-reject algorithm. Moreover, since day k was the first day when some job had an offer rejected by its optimal candidate, before day k, job J ∗ had not had its offer rejected by its optimal candidate. Since J ∗ made an offer to C ∗ on day k, this implies that J ∗ likes C ∗ at least as much as its optimal candidate, and therefore at least as much as C ′ (its partner in the stable matching T). Therefore, (J ∗ ,C ∗ ) form a rogue couple in T, and so T is not stable. Thus, we have a contradiction, implying the matching output by the propose-and-reject algorithm must be employer/job optimal

Answer 1

To understand what optimal means in this context, let's first define the term feasible.

1. A candidate C is a feasible match for an employer J if there exists a stable matching where (C,J) are matched.
2. A candidate C is the optimal match for an employer J if C is the highest-ranked feasible match for J.

(Note that optimal does not necessarily mean the highest-ranked candidate on the list, since the highest ranked candidate on an employer's list might not be feasible.)

To answer your question:

When we say that a matching M is employer optimal, we mean that in M, all employers are paired with their optimal match.