Consider a set M of men and a set W of women. Each m ∈ M has a strict preference ordering over the elements of W and each w ∈ W has a strict preference ordering over men. Let us denote the preference ordering of an agent i by ≻_{i} and x ≻_{i} y will mean that agent i ranks x above y. Now a marriage or matching would be considered as an assignment of men to women such that each man is assigned to at most one woman and vice versa. But, what if the agent decides to remain single. This is possible by two ways, viz. if a man or a woman is matched with oneself, or for each man or woman, there is a dummy woman or man in the set W or M that corresponds to being single. If this were the construction, then, we could safely assume |M| = |W|. But, there is another impediment here, whereby a subversion of sorts is possible, in that a group of agents could simply opt out of the matching exercise. In such a scenario, it becomes mandatory to define a blocking set. As an implication of such subversiveness, a matching is called unstable if there are two men m, m’ and two women w, w’ such that

- m is matched to w
- m’ is matched to w’, and
- w’ ≻
_{m}w and m ≻_{w’}m’

then, the pair (m, w’) is a blocking pair. Any matching without the blocking pair is called stable.

Now, given the preferences of men and women, is it always possible to find stable matchings? For the same, what is used is Gale and Shapley’s * deferred acceptance algorithm*.

So, after a brief detour, let us concentrate on the male-proposal version.

First, each man proposes to his top-ranked choice. Next, each woman who has received at least two proposals keeps (tentatively) her top-ranked proposal and rejects the rest. Then, each man who has been rejected proposes to his top-ranked choice among the women who have not rejected him. Again each woman who has at least two proposals (including ones from previous rounds) keeps her top-ranked proposal and rejects the rest. The process repeats until no man has a woman to propose to or each woman has at most one proposal. At this point the algorithm terminates and each man is assigned to a woman who has not rejected his proposal. No man is assigned to more than one woman. Since each woman is allowed to keep only one proposal at any stage, no woman is assigned to more than one man. Therefore the algorithm terminates in a matching.

Consider the matching {(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{3})}. This is an unstable matching since (m_{1}, w_{2}) is a blocking pair. The matching {(m_{1}, w_{1}), (m_{3}, w_{2}), (m_{2}, w_{3})}, however, is stable. Now looking at the figure above, m_{1} proposes to w_{2}, m_{2} to w_{1}, and m_{3} to w_{1}. At the end of this round, w_{1} is the only woman to have received two proposals. One from m_{3} and the other from m_{2}. Since she ranks m_{3} above m_{2}, she keeps m_{3} and rejects m_{2}. Since m_{3} is the only man to have been rejected, he is the only one to propose again in the second round. This time he proposes to w_{3}. Now each woman has only one proposal and the algorithm terminates with the matching {(m_{1}, w_{2}), (m_{2}, w_{3}), (m_{3}, w_{2})}.

*The male propose algorithm terminates in a stable matching*.

Suppose not. Then ∃ a blocking pair (m_{1}, w_{1}) with m_{1} matched to w_{2}, say, and w_{1} matched to m_{2}. Since (m_{1}, w_{1}) is blocking and w_{1} ≻_{m1} w_{2}, in the proposal algorithm, m_{1} would have proposed to w_{1} before w_{2}. Since m_{1} was not matched with w_{1} by the algorithm, it must be because w_{1} received a proposal from a man that she ranked higher than m_{1}. Since the algorithm matches her to m_{2} it follows that m_{2} ≻_{w1} m_{1}. This contradicts the fact that (m_{1}, w_{1}) is a blocking pair.

Even if where the women propose, the outcome would still be stable matching. The only difference is in kind as the stable matching would be different from the one generated when the men propose. This would also imply that even if stable matching is guaranteed to exist, there is more than one such matching. Then what is the point to prefer one to the other? Well, there is a reason:

Denote a matching by μ. The woman assigned to man m in the matching μ is denoted μ(m). Similarly, μ(w) is the man assigned to woman w. A matching μ is male-optimal if there is no stable matching ν such that ν(m) ≻_{m} μ(m) or ν(m) = μ(m) ∀ m with ν(j) ≻_{j} μ(j) for at least one j ∈ M. Similarly for the female-optimality.

*The stable matching produced by the (male-proposal) Deferred Acceptance Algorithm is male-optimal*.

Let μ be the matching returned by the male-propose algorithm. Suppose μ is not male optimal. Then, there is a stable matching ν such that ν(m) ≻_{m} μ(m) or ν(m) = μ(m) ∀ m with ν(j) ≻_{j} μ(j) for at least one j ∈ M. Therefore, in the application of the proposal algorithm, there must be an iteration where some man j proposes to ν(j) before μ(j) since ν(j) ≻_{j} μ(j) and is rejected by woman ν(j). Consider the first such iteration. Since woman ν(j) rejects j she must have received a proposal from a man i she prefers to man j. Since this is the first iteration at which a male is rejected by his partner under ν, it follows that man i ranks woman ν(j) higher than ν(i). Summarizing, i ≻_{ν(j)} j and ν(j) ≻_{i} ν(i) implying that ν is not stable, a contradiction.

Now, the obvious question is if this stable matching is optimal w.r.t. to both men and women? The answer this time around is NO. From above, it could easily be seen that there are two stable matchings, one of them is male-optimal and the other is female-optimal. At least, one female is strictly better-off under the female optimality than male optimality, and by this, no female is worse off. If the POV is men, a similar conclusion is drawn. A stable marriage is immune to a pair of agents opting out of the matching. We could ask that no subset of agents should have an incentive to opt out of the matching. Formally, a matching μ′ dominates a matching μ if there is a set S ⊂ M ∪ W such that for all m, w ∈ S, both (i) μ′(m), μ′(w) ∈ S and (ii) μ′(m) ≻_{m} μ(m) and μ′(w) ≻_{w} μ(w). Stability is a special case of this dominance condition when we restrict attention to sets S consisting of a single couple. The set of undominated matchings is called the core of the matching game.

*The direct mechanism associated with the male propose algorithm is strategy-proof for the males*.

Suppose not. Then there is a profile of preferences π = (≻_{m1} , ≻_{m2} , . . . , ≻_{mn}) for the men, such that man m_{1}, say, can misreport his preferences and obtain a better match. To express this formally, let μ be the stable matching obtained by applying the male proposal algorithm to the profile π. Suppose that m_{1} reports the preference ordering ≻_{∗} instead. Let ν be the stable matching that results when the male-proposal algorithm is applied to the profile π^{1} = (≻_{∗}, ≻_{m2} , . . . , ≻_{mn}). For a contradiction, suppose ν(m_{1}) ≻_{m1} μ(m_{1}). For notational convenience let a ≽_{m} b mean that a ≻_{m} b or a = b.

First we show that m_{1} can achieve the same effect by choosing an ordering ≻̄ where woman ν(m_{1}) is ranked first. Let π^{2} = (≻̄ , ≻_{m2} , . . . , ≻_{mn}). Knowing that ν is stable w.r.t the profile π^{1} we show that it is stable with respect to the profile π^{2}. Suppose not. Then under the profile π^{2} there must be a pair (m, w) that blocks ν. Since ν assigns to m_{1} its top choice with respect to π^{2}, m_{1} cannot be part of this blocking pair. Now the preferences of all agents other than m_{1} are the same in π^{1} and π^{2}. Therefore, if (m, w) blocks ν w.r.t the profile π^{2}, it must block ν w.r.t the profile π^{1}, contradicting the fact that ν is a stable matching under π^{1}.

Let λ be the male propose stable matching for the profile π^{2}. ν is a stable matching w.r.t the profile π^{2}. As λ is male optimal w.r.t the profile π^{2}, it follows that λ(m_{1}) = ν(m_{1}).

Let’s assume that ν(m_{1}) is the top-ranked woman in the ordering ≻_{∗}. Now we show that the set B = {m_{j} : μ(m_{j}) ≻_{mj} ν(m_{j})} is empty. This means that all men, not just m_{1}, are no worse off under ν compared to μ. Since ν is stable w.r.t the original profile, π this contradicts the male optimality of μ.

Suppose B ≠ ∅. Therefore, when the male proposal algorithm is applied to the profile π^{1}, each m_{j} ∈ B is rejected by their match under μ, i.e., μ(m_{j}). Consider the first iteration of the proposal algorithm where some m_{j} is rejected by μ(m_{j}). This means that woman μ(m_{j}) has a proposal from man m_{k} that she ranks higher, i.e., m_{k} ≻_{μ(mj)} m_{j}. Since m_{k} was not matched to μ(m_{j}) under μ it must be that μ(m_{k}) ≻_{mk} μ(m_{j}). Hence m_{k} ∈ B , otherwise μ(m_{j}) ≽ m_{k}ν(m_{k}) ≽_{mk} μ(m_{k}) ≻_{mk} μ(m_{j}), which is a contradiction. Since m_{k} ∈ B and m_{k} has proposed to μ(m_{j}) at the time man m_{j} proposes, it means that m_{k} must have been rejected by μ(m_{k}) prior to m_{j} being rejected, contradicting our choice of m_{j}.

The mechanism associated with the male propose algorithm is not strategy-proof for the females. Let us see how this is the case by way of an example. The male propose algorithm returns the matching {(m_{1}, w_{2}), (m_{2}, w_{3}), (m_{3}, w_{1})}. In the course of the algorithm the only woman who receives at least two proposals is w_{1}. She received proposals from m_{2} and m_{3}. She rejects m_{2} who goes on to propose to w_{3} and the algorithm terminates. Notice that w_{1} is matched with her second choice. Suppose now that she had rejected m_{3} instead. Then m_{3} would have gone on to proposes to w_{2}. Woman w_{2} now has a choice between m_{1} and m_{3}. She would keep m_{3} and reject m_{1}, who would go on to propose to w_{1}. Woman w_{1} would keep m_{1} over m_{2} and in the final matching be paired with a her first-rank choice.

Transposing this on to economic theory, this fits neatly into the Walrasian equilibrium. Walras’ law is an economic theory that the existence of excess supply in one market must be matched by excess demand in another market so that it balances out. Walras’ law asserts that an examined market must be in equilibrium if all other markets are in equilibrium, and this contrasts with Keynesianism, which by contrast, assumes that it is possible for just one market to be out of balance without a “matching” imbalance elsewhere. Moreover, Walrasian equilibria are the solutions of a fixed point problem. In the cases when they can be computed efficiently it is because the set of Walrasian equilibria can be described by a set of convex inequalities. The same can be said of stable matchings/marriages. The set of stable matchings is fixed points of a nondecreasing function defined on a lattice.