Gale–Shapley algorithm is man-optimal
We use the following notation:


$M$ is the set of men, $W$ the set of women.
For a man $m$ and a set $W'$ of women, $\max_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ if $W'$ is empty. We similarly define $\max_w M'$ for a woman $w$ and a set $M'$ of men.


One way to view the Gale–Shapley algorithm is as maintaining a graph $G$ of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:


Create a complete bipartite graph $G$ with the men on one side and the women on the other side. The initial set of edges is thus $\{(m,w) : m \in M, w \in W\}$.
For each man $m \in M$, let $\operatorname{top}(m) = \max \{w : (m,w) \in G\}$ be the woman $m$ most prefers among his possible matches at this point; $m$ proposes to $\operatorname{top}(m)$.
For each woman $w \in W$, let $\operatorname{best}(w) = \max \{m : \operatorname{top}(m) = w\}$ be the man $w$ most prefers among those who propose to her; $w$ chooses $\operatorname{best}(w)$ (if different from $\bot$).
Remove $(m,\operatorname{top}(m))$ from $G$ whenever $\operatorname{best}(\operatorname{top}(m)) \neq m$, that is, remove $m$'s top choice as a possibility if she rejects him.
If any edge was removed from $G$ in Step 4, go back to Step 2.
Return the matching in which each man $m \in M$ is married to $\operatorname{top}(m)$, and each woman $w \in W$ is married to $\operatorname{best}(w)$.


The idea of the algorithm is that at each point, in every stable marriage, every match $(m,w)$ is an edge in $G$. The reason is as follows. Suppose that in Step 4, $\operatorname{best}(\operatorname{top}(m)) \neq m$ for some man $m \in M$, and consider any marriage in which $m$ is married to $w = \mathrm{top}(m)$. Let $m' = \mathrm{best}(w)$, so that $w = \mathrm{top}(m')$. Obviously $w$ by definition prefers $m'$ to $m$. Since $w$ was $m'$'s top possible choice, $m'$ must be married to someone he prefers $w$ over. Therefore $(m',w)$ is an unstable pair. This shows that no stable marriage can contain $(m,w)$, and so we can safely remove it from $G$ in Step 4.

Throughout the algorithm, no man $m \in M$ is ever left alone, i.e. there is always some $w \in W$ such that $(m,w) \in G$; this is important, since otherwise the algorithm isn't well-defined. This property holds due to the following list of observations:


Once $\operatorname{best}(w) = m \neq \bot$ at some stage for some woman $w \in W$, $\operatorname{best}(w) \neq \bot$ from that point on, and never becomes less desirable than $m$ from the point of view of $w$. This is because at the next iteration, $\operatorname{top}(m) = w$, so $\operatorname{best}(w)$ is at least as good as $m$.
If $\operatorname{best}(w_1),\operatorname{best}(w_2) \neq \bot$ at some iteration for $w_1 \neq w_2 \in W$, then $\operatorname{best}(w_1) \neq \operatorname{best}(w_2)$ at that iteration. This is since $\operatorname{top}(\operatorname{best}(w_1)) = w_1 \neq w_2$.
Every time an edge $(m,w)$ is removed, $\operatorname{best}(w) \neq \bot$. This is because $w = \operatorname{top}(m)$.


Suppose now that all edges adjacent to some man $m \in M$ are removed, and consider the iteration in which the last edge adjacent to $m$ is removed. At this point, all edges $(m,w)$ were removed, so by (3) and (1), $\operatorname{best}(w) \neq \bot$ for all women $w \in W$. By (2), the mapping $\operatorname{best}\colon W\to M$ is one-to-one and so in bijection. In particular, $m = \operatorname{best}(w)$ for some woman $w \in W$. But this means that $w = \operatorname{top}(m)$ and so $(m,w)$ would not be removed in Step 4. We conclude that no man $m \in M$ is ever left isolated.

Since we only remove edges, eventually Step 6 will be reached. At this point, $\operatorname{best}(\operatorname{top}(m)) = m$ for all men $m \in M$, and so $\operatorname{top}$ and $\operatorname{best}$ are inverses. This shows that the output is well-defined and a matching.

Moreover, the matching is stable. Indeed, suppose that $(m,w)$ was an unstable pair, $m$ preferring $w$ over $\operatorname{top}(m)$, and $w$ preferring $m$ over $\operatorname{best}(w)$. Since $m$ prefers $w$ over $\operatorname{top}(m)$, necessarily $(m,w) \notin G$. When this edge was removed, $w$ preferred $\operatorname{best}(w)$ over $m$, and by (1), at the end $w$ still prefers $\operatorname{best}(w)$ over $m$, leading to a contradiction.

Finally, the matching is man-optimal. This is because in any stable marriage, a man $m \in M$ is matched to one of its neighbors in the final graph $G$. The marriage output by the algorithm matches $m$ to his top choice $\operatorname{top}(m)$, so it is optimal from the point of view of $m$.

Moreover, the matching is woman-pessimal. For suppose there were some stable matching in which some woman $w \in W$ is matched to a man which she prefers less than her match $m = \operatorname{best}(w)$ returned by the algorithm. Since $G$ represents the only possible matches in stable marriages, $m$ must be matched to some woman he prefers less than $w = \operatorname{top}(m)$. Thus $(m,w)$ is an unstable pair, and we reach a contradiction.

This exposition is taken from Section 6.3 of this paper, where other algorithms are described and analyzed, culminating in Subramanian's fixed point algorithm.