[cdsmith]

To be clear, the algorithm is proposer-optimal only when compared to other stable matchings. It is still possible that there exists some other matching that would make all proposers happier. It just won't be stable: there will be some pair of proposer and proposee that could switch to immediately increase their happiness, BUT it would set off a chain reaction of further swaps that leave everyone less happy in the end. This was a bit surprising to me.

There's a variant where you run the deferred acceptance algorithm, but then only the proposees who never rejected anyone finalize their decision. All other proposees and their matched proposers split up, and the whole algorithm is run again with the unmatched participants. This time, you end up with a Pareto-optimal matching for the proposers, with respect to their stated preferences. That is, there's no possible way to make anyone happier without making someone else less happy. But it's not stable, and the algorithm is no longer strategy-proof. (In fact, one can prove that no strategy-proof algorithm can guarantee a Pareto-optimal matching!)