You are currently browsing the monthly archive for February 2012.

I am a big fan of Paul Krugman, but I think he missed something important in today’s column.

First, let’s go back to November. In this blog post, Krugman pointed out correctly that it is silly to perceive an inconsistency or “hypocrisy” when wealthy individuals promote progressive taxation. If Warren Buffett believes that the good of the nation is against his self-interest, this is civic-minded unselfishness, the furthest thing from hypocrisy. Furthermore, the belief that the wealthy should pay more should never be confused with hatred of the wealthy, or self-hatred; one does not imply the other.

Today, Krugman points out a supposed contradiction between (a) conservative opposition to the social safety net and (b) the fact that social programs send more benefits to red states (which tend to be poorer) than blue states. What, conservatives can’t be civic-minded? Just as it is not inconsistent for Mr. Buffett to fail to volunteer higher tax payments, it is not inconsistent to accept benefits while believing they shouldn’t exist. If I find myself playing Monopoly with the horribly misguided house rule that money is placed under Free Parking, am I morally compelled to refuse the money, on the grounds that I believe with all my heart it shouldn’t be there? Clearly, no. It would be hypocritical to complain about other players’ *accepting* the Free Parking money while I do so myself, but not hypocritical to advocate that the *rule itself* be changed so that no one receives money including me.

(Side note: One shouldn’t actually conclude from a state-by-state correlation that the individuals receiving benefits are the ones opposing them. It is equally possible, based only on such data, that seeing one’s red-state *neighbors* receive benefits leads one to oppose them.)

Finally, while I think failing to note the analogy with his previous post was a big omission today, I do think that other evidence in the column tends to recover Krugman’s point. He wants to show that support for conservative austerity measures is based not on principle and willingness to fairly share sacrifice, but on perceived self-interest, which is in some cases misperceived. The column cites a study by Suzanne Mettler stating that over 40% of those receiving benefits from Social Security, unemployment and Medicare believe they “have not used a government program.” This does suggest the possibility that some conservatives are opposed to such programs only “for other people.” A lack of self-awareness can facilitate the cloaking of self-interest in a purported principled stand, which would indeed be hypocrisy. In contrast, Mr. Buffett could hardly miss the fact that a “Buffett tax” would fall heavily on him.

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.

I’m at the point in my pricing class where I go on about the pricing of razors and blades. The widespread belief on this matter is captured by the following quote from Chris Evans, the author of a book called *FREE.*

Gillette made its real profit from the high margin on the blades.

Price razors low and make one’s living off the blades. Replace razors by aircraft engines and blades by parts or razors by game consoles and blades by games and you have a universal prescription. Does it make sense?

Suppose, initially, a monopoly supplier of razors and blades. Each razor will last 52 weeks and a pack of blades will last 4 weeks. Suppose a weeks worth of shaving to the buyer is worth $10. How could I price the razor and the blades? First, razor at $480 and blades free. Second, razor for free and pack of blades at $40. Third, any combination of the two that sucks out $480 from the buyer. In the absence of other considerations there is nothing to suggest price razors low and blades high is better than the reverse. If the buyer is liquidity constrained, high priced razor and low priced blade might be a bad idea. High priced razors and low priced razors also raise the possibility of hold up because after I sell you the razor, what is to stop me from jacking up the price of the blades?

OK, suppose one has settled on low price razor and high priced blade. This makes you vulnerable to a competitor with a lower priced blade compatible with your razor. If they enter, you would respond by raising the price of the razor and lowering the price of the blade. In this case, what about a competitor entering with a razor compatible with your blades? Now the competitors have you coming and going!

Well then, the problem appears to be the interoperability of razors and blades (maybe not, but that comes up later in the class). So, design a razor and blade system incompatible with the competitions. Now one is selling a system rather than the individual components. So, price the system rather than the individual components.

What then is the origin of the low priced razor high priced blade wisdom? Haven’t the faintest. If we turn to reverent authority, King Gillette, he introduced the razor and disposable blade around 1904. The razor and a pack of 12 blades sold for $5. Subsequent packs of a dozen blades were sold for $1. At that time, $5 was about 2 days wages for the average factory worker!

With Tim Gowers at the head, followed by a distinguished caravan of scholars a movement as emerged to boycott Elsevier.

Three arguments are offered in favor of the boycott that I reproduce below.

1)They charge exorbitantly high prices for their journals.

2) They sell journals in very large “bundles,” so libraries must buy a large set with many unwanted journals, or none at all. Elsevier thus makes huge profits by exploiting their essential titles, at the expense of other journals.

3)They support measures such as SOPA, PIPA and the Research Works Act, that aim to restrict the free exchange of information.

#2 caught my attention. Suppose, I offer you journal A and journal B as a bundle for $5000 a year. Suppose also, consistent with the premise of #2, you only read journal A but not B. Am I forcing you to consume journal B? No. I can always unbundle and offer you journal A alone for $5000 a year. Indeed, if no one reads journal B, why bother supporting it? I could junk it and reduce costs without reducing revenues! Thus, complaint # 2 taken at face value is either wrong headed or repeats complaint #1.

I should point out that I have published in some Elsevier journals, served on and still serve on some Elsevier boards.

## Recent Comments