# Man Proposes OR Woman Proposes – “Matches” Happen Algorithmically and are Economically Walrasian Rather than Keynesian. Note Quote & Didactics.

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

1. m is matched to w
2. m’ is matched to w’, and
3. 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 {(m1, w1), (m2, w2), (m3, w3)}. This is an unstable matching since (m1, w2) is a blocking pair. The matching {(m1, w1), (m3, w2), (m2, w3)}, however, is stable. Now looking at the figure above, m1 proposes to w2, m2 to w1, and m3 to w1. At the end of this round, w1 is the only woman to have received two proposals. One from m3 and the other from m2. Since she ranks m3 above m2, she keeps m3 and rejects m2. Since m3 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 w3. Now each woman has only one proposal and the algorithm terminates with the matching {(m1, w2), (m2, w3), (m3, w2)}.

The male propose algorithm terminates in a stable matching.

Suppose not. Then ∃ a blocking pair (m1, w1) with m1 matched to w2, say, and w1 matched to m2. Since (m1, w1) is blocking and w1m1 w2, in the proposal algorithm, m1 would have proposed to w1 before w2. Since m1 was not matched with w1 by the algorithm, it must be because w1 received a proposal from a man that she ranked higher than m1. Since the algorithm matches her to m2 it follows that m2w1 m1. This contradicts the fact that (m1, w1) 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 m1, 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 m1 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 ν(m1) ≻m1 μ(m1). For notational convenience let a ≽m b mean that a ≻m b or a = b.

First we show that m1 can achieve the same effect by choosing an ordering ≻̄ where woman ν(m1) 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 m1 its top choice with respect to π2, m1 cannot be part of this blocking pair. Now the preferences of all agents other than m1 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 λ(m1) = ν(m1).

Let’s assume that ν(m1) is the top-ranked woman in the ordering ≻. Now we show that the set B = {mj : μ(mj) ≻mj ν(mj)} is empty. This means that all men, not just m1, 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 mj ∈ B is rejected by their match under μ, i.e., μ(mj). Consider the first iteration of the proposal algorithm where some mj is rejected by μ(mj). This means that woman μ(mj) has a proposal from man mk that she ranks higher, i.e., mkμ(mj) mj. Since mk was not matched to μ(mj) under μ it must be that μ(mk) ≻mk μ(mj). Hence mk ∈ B , otherwise μ(mj) ≽ mkν(mk) ≽mk μ(mk) ≻mk μ(mj), which is a contradiction. Since mk ∈ B and mk has proposed to μ(mj) at the time man mj proposes, it means that mk must have been rejected by μ(mk) prior to mj being rejected, contradicting our choice of mj.

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 {(m1, w2), (m2, w3), (m3, w1)}. In the course of the algorithm the only woman who receives at least two proposals is w1. She received proposals from m2 and m3. She rejects m2 who goes on to propose to w3 and the algorithm terminates. Notice that w1 is matched with her second choice. Suppose now that she had rejected m3 instead. Then m3 would have gone on to proposes to w2. Woman w2 now has a choice between m1 and m3. She would keep m3 and reject m1, who would go on to propose to w1. Woman w1 would keep m1 over m2 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.