This session was devoted to three different perspectives on Gale and Shapley’s stable matching problem. The first, is traditional wherein nothing more than a command of the English language coupled with a patience for moderately long chains of reasoning is needed. The second, is Adachi’s (from his OR letters paper) lattice formulation of the question and an example to illustrate how it can be generalized to other settings. The third, based on Vandevate’s characterization of the convex hull of stable matchings. I also stuck in a new result that fills a much needed gap in the literature that I hope is correct (if incorrect perhaps it will stimulate others).

**1. Stable Matchings **

The stable matching problem was introduced by Gale and Shapley as a model of how to assign students to colleges. One can view it as the ordinal version of the SS model. The problem has a set~ of men and a set~ of women. Each has a strict preference ordering over the elements of and each has a strict preference ordering over the men. The preference ordering of agent~ is denoted and means agent~ ranks above . One can accommodate the possibility of an agent choosing to remain single by including for each man (woman) a dummy woman (man) in the set () that corresponds to being single (or matched with oneself). With this construction we can assume .

A matching is called \index{matching!unstable}**unstable** if there are two men and two women , such that

- is matched to ,
- is matched to ,
- and and

The pair is called a **blocking pair**. A matching that has no blocking pairs is called **stable**.

Given the preferences of the men and women, its always possible to find a stable matching using the deferred acceptance algorithm.

**Deferred Acceptance Algorithm, male-propose 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 amongst 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.
- Process repeats until no man has a woman to propose to or each woman has at most one proposal.

Theorem 1The male propose algorithm terminates in a stable matching.

**Proof:** When it terminates, it clearly does so in a matching. Suppose the matching is not stable. Then, there exists a blocking pair with matched to , say, and matched to . Since is blocking and , in the proposal algorithm, would have proposed to before . Since was not matched with by the algorithm it must be because received a proposal from a man that she ranked higher than . Since the algorithm matches her to it follows that . This contradicts the fact that is a blocking pair.

One could describe an algorithm where the females propose and the outcome would also be a stable matching and possibly different from the one returned using the male propose version. Thus, not only is a stable matching guaranteed to exist but there can be more than one. If there can be more than one stable matching, is there a reason to prefer one to another?

Denote a matching by . The woman matched to man in the matching is denoted . Similarly, is the man matched to woman . A matching is **male-optimal** if there is no stable matching such that or for all with for at least one . Similarly define **female-optimal**.

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

**Proof:** Let be the matching returned by the male-propose algorithm. Suppose is not male optimal. Then, there is a stable matching such that or for all with for at least one . Therefore, in the application of the proposal algorithm there must be an iteration where some man proposes to before since and is rejected by woman . Consider the first such iteration. Since woman rejects she must have received a proposal from a man she prefers to man . Since this is the first iteration at which a male is rejected by his partner under it follows that man ranks woman higher than . Summarizing, and implying that is not stable, a contradiction.

You can replace the word “male” by the word “female” in the statement of the theorem. There is no stable matching that is simultaneously optimal with respect to males *and* females.

A stable matching is immune to a pair of agents opting out of the matching (the blocking pair). 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 that satisfies the following two conditions:

- for all
- and for all .

Stability is a special case of this dominance condition when we restrict attention to sets~ consisting of a single couple. The set of undominated matchings is called the **core** of the matching game.

Theorem 3The core of the matching game is the set of all stable matchings.

Now assume the preference orderings of the agents are private information to the agent.

Theorem 4The direct mechanism associated with the male propose algorithm is strategy proof for the males.

**Proof:** If not, there is a preference profile for the men, such that man , say, can misreport his preferences and obtain a better match. Formally, let be the stable matching obtained by applying the male proposal algorithm to the profile . Suppose reports the preference ordering instead. Let be the matching that results when the male-proposal algorithm is applied to the profile . For a contradiction suppose . For convenience write to mean that or .

Let be the set of men better off under matching than matching . We show that for any and that . In other words, . For a contradiction suppose . In particular . Now, because , and stability of wrt implies . Stability of wrt requires that , otherwise would block . Therefore, .

Now, for any , because during execution of the male-propose algorithm on , each rejects at some iteration. Let be the last man in to make a proposal during execution of male-propose algorithm. This proposal is made to who, by choice of , must have rejected at some earlier iteration. This means that when proposes to , she must reject a pending proposal from such that . As , we have . Therefore, form a blocking pair for wrt (since ).

The mechanism associated with the male propose algorithm is not strategy proof for the females.

**2. A Lattice Formulation **

We describe a proof (due to Adachi; Fleiner also independently but later) of the existence of stable matchings using Tarski’s fixed point theorem.

Call an assignment of women to men such that each man is assigned to at most one woman (but a woman may be assigned to more than one man) a **male semi-matching**. The analogous object for women will be called a **female semi-matching**. For example, assigning each man his first choice would be a male semi-matching. Assigning each woman her third choice would be an example of a female semi-matching.

A pair of male and female semi-matchings will be called a **semi-matching** denoted , , etc. An example of a semi-matching would consist of each man being assigned his first choice and each woman being assigned her last choice.

The woman assigned to man under the semi-matching will be denoted . If man is assigned to no woman under , then . Similarly for . Next, define a partial order over the set of semi-matchings. Write if

- or for all , and,
- or for all .

Therefore if all the men are better off under than in and all the women are worse off under than in .

Next, define the meet and join operations. Given two semi-matchings and define as follows:

- if otherwise ,
- if otherwise

Define as follows:

- if otherwise ,
- if otherwise

With these definitions it is easy to check that the set of semi-matchings form a compact lattice.

Now define a function on the set of semi-matchings that is non-decreasing. Given a semi-matching define to be the following semi-matching:

- is man ‘s most preferred woman from the set . If this set is empty, set .
- is woman ‘s most preferred man from the set . If this set is empty set .

It is clear that maps semi-matchings into semi-matchings.

Theorem 5There is a semi-matching such that and that is a stable matching.

**Proof:** We use Tarski’s theorem. To apply it we need to check that is non-decreasing. Suppose . Pick any . From the definition of , the women are worse off under than in . Thus

and so or When considering the women, for each we must have (because the women are worse off under than under ):

Therefore, .

As the conditions of Tarski’s theorem hold, there is a semi-matching such that . We show that the semi-matching is a stable matching.

By the definition of a semi-matching we have for every , single valued as is for all . To show that is a matching, suppose not. Then there is a pair , say, such that . Since it follows that is ‘s top ranked choice in and ‘s top ranked choice in . From this it follows that if , then, . As , we can assume, WLOG that . However, which is woman ‘s top ranked choice in . Since belongs to this set, we get a contradiction.

To show that is stable, suppose not. Then, there is a blocking pair . Let and , and . As blocks , and . Now which is man ‘s top ranked choice from . But this set contains which is ranked higher by man than , a contradiction.

** 2.1. Splittable Stable Marriage **

To show how versatile Adachi’s lattice approach is, we examine an extension due to Sethuraman and Teo called the splittable stable marriage problem.

We have two disjoint agents, say,`sellers” (indexed by or ) and “buyers” (indexed by or ). Imagine a “market” for a product that is infinitely divisible. Seller has units to sell; buyer wishes to buy and the quantity of sale between and can be at most (“capacity” constraint). Each agent has a strict preference ordering over agents on the opposite side. For convenience assume each agent ranks themselves last. Assume that the number of buyers is equal to the number of sellers. In the sequel the set of sellers will be , and the set of buyers will be .

A **splittable marriage** is defined as an matrix such that:

Here is the quantity of the product sold by seller to buyer , if neither nor is ; if and , then is the additional quantity that buyer would like to buy but cannot; and if and , then is the additional quantity that seller would like to sell but cannot.

A **blocking pair** for a splittable marriage is a pair of agents and such that

- ;
- ; and
- .

If blocks , the agents and can do better by trading more with each other, and giving up some of the quantities they transact with less-preferred agents. A **splittable stable marriage** is a splittable marriage that is not blocked.

Next we define the appropriate generalization of semi-matching. A **demand-list** for seller is a vector that satisfies (1) and (3). Similarly, a demand-list for buyer is a vector that satisfies (2) and (3).

The demand-lists of sellers and buyers can be encoded by matrices and . Assume matrices and have their rows indexed by the sellers and the columns indexed by the buyers. Specifically, has rows and columns, whereas has rows and columns.

The seller demand-list matrix is a valid “matching” of the sellers, but not a valid matching of the sellers to the buyers. Similarly, for the buyer demand-list matrix .

Let and be a collection of seller and buyer demand-lists respectively. Define partial orders and on the sets and respectively. For any two elements ,

Similarly, for any two elements ,

(Notice the change in the direction of the inequality in the definition of .)

Given any , let be defined as follows:

Similarly, let be defined as follows:

The matrices and can be computed as follows: for each seller, compute the entries corresponding to his row, starting with the most preferred buyer. Clearly, and are in , and are, respectively, the greatest lower bound and the least upper bound of and . Again, the meet and join of any two elements of can be defined in a similar way. Thus and are lattices. By replacing “min” and “max” with “inf” and “sup” respectively, we can infer that meets and joins exist for arbitrary subsets of elements of or ; hence and are *complete* lattices. The lattice of interest is the product lattice with the partial order defined as follows:

From standard results from lattice theory we see that is a complete lattice.

Call demand-lists and **compatible** if for all . Any splittable stable marriage can be viewed as a pair of compatible demand-lists: for any seller and buyer , set and to be ; allocate the remaining supply and unfulfilled demand to the last entries in each row and column of and respectively. The converse is false.

Next we need an appropriate monotone function on the lattice . As intuition, suppose the buyers form a coalition and “agree” to hand over their demand-list to the sellers. How should the sellers respond? Clearly, the sellers would “update” their demand-lists as follows:

Notice that appears on both sides of (1). One way to perform this update is as follows: for each seller, update the entries corresponding to his row, starting with the most preferred buyer. In this manner, the “old” demand-list of is never used in the update. We call this the *canonical* computation.

Similar considerations suggest:

Again, Eq.(2) can be computed as follows: for each buyer, update the entries corresponding to his row, starting with the most preferred seller.

Equations (1) and (2) have identical right hand sides. Unsurprisingly, compatible demand-lists arising from solutions of Equations (1) and (2) correspond to splittable stable marriages.

Lemma 6If and are solutions to Equations (1) and (2), then for defines a splittable stable marriage.

**Proof:** By the hypothesis of the lemma, and are identical. Thus,

So if , either or .

We next show that the computations of Eqs.(1) and (2) define monotone maps.

Theorem 7For , let be the seller demand-list obtained from Eq.~(1). Then,

**Proof:** Consider seller and buyer . Since , by definition,

Therefore

If is ‘s most preferred buyer, follows from the definition. Inductively, we can argue along these lines that .

Similarly:

Theorem 8For , let be the buyer demand-list obtained from Eq.~(2). Then,

Consider the function defined on as follows:

We claim that is monotone. Why? Let . Then , and so ; similarly, , and so . Thus . By Tarski’s theorem, has a fixed point. This fixed point is clearly a splittable stable marriage.

One can generalize even further. Let and be two monotone integer valued submodular functions. Define a splittable matching to be any . Preferences would defined similarly. Each buyer seeks to get at much as possible from their most preferred seller subject to feasibility etc.

**3. An LP Formulation **

Vandevate identified a collection of linear inequalities that describe the convex hull of stable matchings. For each man and woman let if man is matched with woman and zero otherwise.

Then, every stable matching must satisfy the following.

Let be the polyhedron defined by these inequalities.

The first two constraints of ensure that each agent is matched with exactly one other agent of the opposite sex. The third constraint ensures stability by ruling out blocking pairs (call it the blocking constraint). To see why, suppose and . Then man is matched to a woman, that he ranks below . Similarly, woman is matched to a man she ranks below . This would make the pair a blocking pair.

Lemma 9Suppose . Let . Then, implies that

**Proof:** Consider .The dual to this program is

subject to

Set and . Substituting this into the dual constraints yields:

Choose any and set . This choice of is clearly dual feasible. It has an objective function value of and so, is dual optimal. The lemma now follows by complementary slackness.

The proof below is due to Sethuraman and Teo.

Theorem 10Suppose . Then, is the convex hull of stable matchings.

**Proof:** Choose any weight vector and let

With each member of we associate an interval . For each , partition the associated interval into subintervals of length for all . Arrange these subintervals left to right by by man ‘s decreasing preference over . For each woman , partition the associated interval into subintervals of length for all . Arrange these subintervals left to right by by woman ‘s increasing preference over .

Lemma 6 means the subinterval spanned by in and coincides. Pick a random number uniformly in (0, 1] and construct a semi-matching in the following way:

- Match to if lies in the subinterval of spanned by .
- Match to if lies in the subinterval of spanned by .

By Lemma 6, is matched to iff is matched to . Furthermore, no two men can be matched to the same woman, and similarly no two women can be matched to the same man. So the above semi-matching gives rise to a perfect matching. To show this matching is stable, consider man who is matched to but prefers . Then, in , the subinterval corresponding to is to the left of the subinterval corresponding to . Because is matched to , it means that is to the right of the subinterval corresponding to in . Therefore, is to the left of the subinterval corresponding to in . In other words, is matched to someone she prefers to . Set iff man is matched to woman by the randomized scheme above. Then

Thus, we have exhibited a probability distribution over stable matchings whose expected objective function value coincides with . It follows then, that there is a stable matching with objective function value .

** 3.1. A Subgradient Algorithm **

The LP approach requires that we know that . It would be nice to verify this independently of the proposal algorithm. Here I will outline (not warranted correct) how one can show directly from the LP that . If woman is man ‘s first choice set . If woman is man ‘s second choice set and so on. Consider:

Let be the multiplier associated with the blocking constraints and the multiplier associated with the constraint for all . Consider the following Lagrangean relaxation of the optimization problem:

subject to

This is easy to solve. For each man choose the woman that maximizes

In case of a tie, chooses the top ranked woman.

Initially set . Let be the value of the multipliers at start of iteration . Denote by the optimal choice of given the multipliers . If we will say that man proposed to woman . Given we adjust by as follows:

- Set
- Set for all .
- Set
- Set

Stop once is an assignment. By complementary slackness this must be an optimal stable assignment. Call the dual adjusted rank.

Suppose at iteration , .

**Case 1** If among all such that , man is woman ‘s top ranked choice, .

Because is woman ‘s top ranked choice it follows that . Because it follows that .

**Case 2** If among all such that , man is not woman ‘s top ranked choice, .

Because is not woman ‘s top ranked choice it follows that . Because it follows that .

**Case 3** If and for all such that , then .

Clearly and . Also, .

**Case 4** If and for at least one such that , then .

Clearly and . Also, .

**Case 5** If then, then .

Clearly, . Also, .

Let . I show first that . Consider first the case . Suppose man proposed to woman and man is woman ‘s top choice among those who have proposed. Then the dual adjusted rank of woman by man declines by exactly 1 (see case 1). The dual adjusted rank of all other women decline by at least 1 (case 2 to 4). Note that case 5 does not apply in this iteration. Therefore, in the next iteration man will continue to propose to woman . More generally, any woman who receives a proposal in iteration continues to receive a proposal in iteration . Suppose this holds until iteration . Suppose man proposes to woman in iteration and man is woman ‘s top choice among those who have proposed at iteration . By cases (1-4) the dual adjusted rank for all woman ranked below declines by at least 1. Consider a woman . By case 5

However, because any woman who received a proposal before iteration continues to receive a proposal at iteration . Thus the dual adjusted rank of all women ranked above decline by at least 1. Because man did not proposes to these women in iteration their dual adjusted rank must be at least 2 smaller than . Thus, woman continues to have the highest dual adjusted rank for man and at iteration , man will continue to propose to woman .

Next, I show there must be some such that . If not, then, it must be the case that . Because there must be a woman who is overdemanded. Consider a man who has proposed to her at iteration who is not her top choice among those proposing to her. Notice the following:

- By case 2,
- By case 5 for all such that , .
- By case 5, for all such that , .
- By case 3, for all , . Note, for all such it must be that .

To summarize, the dual adjusted rank of all women such that , goes down by at least 2. That means in all subsequent iterations, man must propose to a woman ranked at or above in . Eventually, there is a woman, , say, that man keeps proposing to. This means that the dual adjusted rank of all women in declines by at least 2 while the dual adjusted rank of all women outside of declines by exactly 1. Eventually, some woman outside of must have a dual adjusted rank that is largest and man will propose to her, contradiction.

## 1 comment

February 9, 2012 at 6:36 am

gia suGrateful to you for this article