Monthly Archive

You are currently browsing the monthly archive for February 2012.

Krugman on Hypocrisy

February 17, 2012 in Uncategorized | by Jonathan Weinstein | 4 comments

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.

Market Design Class (Session 3)

February 7, 2012 in Auctions, Mechanism design, Operations research | by rvohra | 1 comment

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~ ${M}$ of men and a set~ ${W}$ of women. Each ${m \in M}$ has a strict preference ordering over the elements of ${W}$ and each ${w \in W}$ has a strict preference ordering over the men. The preference ordering of agent~ ${i}$ is denoted ${\succ_i}$ and ${x \succ_i y}$ means agent~ ${i}$ ranks ${x}$ above ${y}$ . 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 ${W }$ ( ${M}$ ) that corresponds to being single (or matched with oneself). With this construction we can assume ${|M| = |W|}$ .

A matching is called \index{matching!unstable}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' \succ_m w}$ and ${m \succ_{w'} m'}$

The pair ${(m,w')}$ 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 1 The 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 ${(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 \succ_{m_1} 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 \succ_{w_1} m_1}$ . This contradicts the fact that ${(m_1, w_1)}$ is a blocking pair. ${\Box}$

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 ${\mu}$ . The woman matched to man ${m}$ in the matching ${\mu}$ is denoted ${\mu(m)}$ . Similarly, ${\mu(w)}$ is the man matched to woman ${w}$ . A matching ${\mu}$ is male-optimal if there is no stable matching ${\nu}$ such that ${\nu(m) \succ_m \mu(m)}$ or ${\nu(m) = \mu(m)}$ for all ${m}$ with ${\nu(j) \succ_j \mu(j)}$ for at least one ${j \in M}$ . Similarly define female-optimal.

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

Proof: Let ${\mu}$ be the matching returned by the male-propose algorithm. Suppose ${\mu}$ is not male optimal. Then, there is a stable matching ${\nu}$ such that ${\nu(m) \succ_m \mu(m)}$ or ${\nu(m) = \mu(m)}$ for all ${m}$ with ${\nu(j) \succ_j \mu(j)}$ for at least one ${j \in M}$ . Therefore, in the application of the proposal algorithm there must be an iteration where some man ${j}$ proposes to ${\nu(j)}$ before ${\mu(j)}$ since ${\nu(j) \succ_j \mu(j)}$ and is rejected by woman ${\nu(j)}$ . Consider the first such iteration. Since woman ${\nu(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 ${\nu}$ it follows that man ${i}$ ranks woman ${\nu(j)}$ higher than ${\nu(i)}$ . Summarizing, ${i \succ_{\nu(j)} j}$ and ${\nu(j) \succ_i \nu(i)}$ implying that ${\nu}$ is not stable, a contradiction. ${\Box}$

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 ${\mu'}$ dominates a matching ${\mu}$ if there is a set ${S \subset M \cup W}$ that satisfies the following two conditions:

${\mu'(m), \mu'(w) \in S}$ for all ${m,w \in S}$
${\mu'(m) \succ_m \mu(m)}$ and ${\mu'(w) \succ_w \mu(w)}$ for all ${m,w \in S}$ .

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.

Theorem 3 The 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 4 The direct mechanism associated with the male propose algorithm is strategy proof for the males.

Proof: If not, there is a preference profile ${\pi =(\succ_{m_1}, \succ_{m_2}, \ldots, \succ_{m_n})}$ for the men, such that man ${m_1}$ , say, can misreport his preferences and obtain a better match. Formally, let ${\mu}$ be the stable matching obtained by applying the male proposal algorithm to the profile ${\pi}$ . Suppose ${m_1}$ reports the preference ordering ${\succ_* }$ instead. Let ${\nu}$ be the matching that results when the male-proposal algorithm is applied to the profile ${\pi^1 = (\succ_*, \succ_{m_2}, \ldots, \succ_{m_n})}$ . For a contradiction suppose ${\nu(m_1) \succ_{m_1} \mu(m_1)}$ . For convenience write ${a \succeq _{m} b}$ to mean that ${a \succ_m b}$ or ${a=b}$ .

Let ${R = \{m: \nu(m) \succ_m \mu(m)\}}$ be the set of men better off under matching ${\nu}$ than matching ${\mu}$ . We show that for any ${m \in R}$ and ${w = \nu(m)}$ that ${m' = \mu(w) \in R}$ . In other words, ${S = \{w: \nu(w) \in R\} = \{w: \mu(w) \in R\}}$ . For a contradiction suppose ${m' \not \in R}$ . In particular ${m' \neq m_1}$ . Now, ${w \succ_m \mu(m)}$ because ${m \in R}$ , and stability of ${\mu}$ wrt ${\pi}$ implies ${m' \succ_w m}$ . Stability of ${\nu}$ wrt ${\pi^1}$ requires that ${\nu(m') \succ_{m'} w}$ , otherwise ${(m',w)}$ would block ${\nu}$ . Therefore, ${m' \in R}$ .

Now, ${\mu(w) \succ_w \nu(w)}$ for any ${w \in S}$ , because during execution of the male-propose algorithm on ${\pi}$ , each ${w \in S}$ rejects ${\nu(w) \in R}$ at some iteration. Let ${m}$ be the last man in ${R}$ to make a proposal during execution of male-propose algorithm. This proposal is made to ${w = \mu(m) \in S}$ who, by choice of ${m}$ , must have rejected ${\nu(w)}$ at some earlier iteration. This means that when ${m}$ proposes to ${w}$ , she must reject a pending proposal from ${m' \not \in R}$ such that ${m' \succ_w \nu(w)}$ . As ${m' \not \in R}$ , we have ${w \succ_{m'} \mu(m') \succeq_{m'} \nu(m')}$ . Therefore, ${(m', w)}$ form a blocking pair for ${\nu}$ wrt ${\pi^1}$ (since ${m' \neq m_1}$ ). ${\Box}$

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 ${\mu}$ , ${\nu}$ , 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 ${m}$ under the semi-matching ${\mu}$ will be denoted ${\mu(m)}$ . If man ${m}$ is assigned to no woman under ${\mu}$ , then ${\mu(m) = m}$ . Similarly for ${\mu(w)}$ . Next, define a partial order over the set of semi-matchings. Write ${\mu \succeq \nu}$ if

${\mu(m) \succ_m \nu(m)}$ or ${\mu(m) = \mu(m)}$ for all ${m \in M}$ , and,
${\mu(w) \prec_w \nu(w)}$ or ${\mu(w) = \nu(w)}$ for all ${w \in W}$ .

Therefore ${\mu \succeq \nu}$ if all the men are better off under ${\mu}$ than in ${\nu}$ and all the women are worse off under ${\mu}$ than in ${\nu}$ .

Next, define the meet and join operations. Given two semi-matchings ${\mu}$ and ${\nu}$ define ${\lambda = \mu \vee \nu}$ as follows:

${\lambda(m) = \mu(m)}$ if ${\mu(m) \succ_m \nu(m)}$ otherwise ${\lambda (m) = \nu (m)}$ ,
${\lambda(w) = \mu(w)}$ if ${\mu(w) \prec_w \nu(w)}$ otherwise ${\lambda (w) = \nu (w).}$

Define ${\lambda' = \mu \wedge \nu}$ as follows:

${\lambda'(m) = \mu(m)}$ if ${\mu(m) \prec_m \nu(m)}$ otherwise ${\lambda (m) = \nu (m)}$ ,
${\lambda(w) = \mu(w)}$ if ${\mu(w) \succ_w \nu(w)}$ otherwise ${\lambda (w) = \nu (w).}$

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

Now define a function ${f}$ on the set of semi-matchings that is non-decreasing. Given a semi-matching ${\mu}$ define ${f(\mu)}$ to be the following semi-matching:

${f(\mu)(m)}$ is man ${m}$ ‘s most preferred woman from the set ${\{w: m \succeq_w \mu(w) \} }$ . If this set is empty, set ${f(\mu)(m) = m}$ .
${f(\mu)(w)}$ is woman ${w}$ ‘s most preferred man from the set ${\{m: w \succeq_m \mu(m)\}}$ . If this set is empty set ${f(\mu)(w) = w}$ .

It is clear that ${f}$ maps semi-matchings into semi-matchings.

Theorem 5 There is a semi-matching ${\mu}$ such that ${f(\mu) = \mu}$ and that ${\mu}$ is a stable matching.

Proof: We use Tarski’s theorem. To apply it we need to check that ${f}$ is non-decreasing. Suppose ${\mu\succeq \nu}$ . Pick any ${m \in M}$ . From the definition of ${\succeq}$ , the women are worse off under ${\mu}$ than in ${\nu}$ . Thus

$\displaystyle \{w: m \succ_w \nu(w)\} \subseteq \{w: m \succ_w \mu(w)\}$

and so ${f(\mu)(m) \succ_m f(\nu)(m)}$ or ${f(\mu)(m) = f(\nu)(m).}$ When considering the women, for each ${w \in W}$ we must have (because the women are worse off under ${\mu}$ than under ${\nu}$ ):

$\displaystyle \{m: w \succ_m \mu(m)\} \subseteq \{m: w \succ_m \nu(m)\}.$

Therefore, ${f(\nu)(w) \succ_w f(\mu)(w) }$ .

As the conditions of Tarski’s theorem hold, there is a semi-matching ${\mu}$ such that ${f(\mu) = \mu}$ . We show that the semi-matching is a stable matching.

By the definition of a semi-matching we have for every ${m \in M}$ , ${\mu(m)}$ single valued as is ${\mu(w)}$ for all ${w \in W}$ . To show that ${\mu}$ is a matching, suppose not. Then there is a pair ${m_1, m_2 \in M}$ , say, such that ${\mu(m_1) = \mu(m_2) = w^*}$ . Since ${f(\mu) = \mu}$ it follows that ${w^*}$ is ${m_1}$ ‘s top ranked choice in ${\{w: m_1 \succeq_w \mu(w) \}}$ and ${m_2}$ ‘s top ranked choice in ${\{w: m_2 \succeq_w \mu(w) \}}$ . From this it follows that if ${\mu(w^*) = m_3}$ , then, ${m_1, m_2 \succeq _{w^*} m_3}$ . As ${m_1 \neq m_2}$ , we can assume, WLOG that ${m_2 \succ_{w^*} m_3}$ . However, ${m_3 =\mu(w^*) = f(\mu^*)(w^*)}$ which is woman ${w^*}$ ‘s top ranked choice in ${\{m: w^* \succeq_m \mu(m) \}}$ . Since ${m_1}$ belongs to this set, we get a contradiction.

To show that ${\mu}$ is stable, suppose not. Then, there is a blocking pair ${(m^*,w^*)}$ . Let ${w' = \mu(m^*)}$ and ${m' = \mu(w^*)}$ , ${m' \neq m^*}$ and ${w^* \neq w'}$ . As ${(m^*,w^*)}$ blocks ${\mu}$ , ${m^* \succ_{w^*} m'}$ and ${w^* \succ_{m^*} w'}$ . Now ${w' = \mu(m^*) = f(\mu)(m^*)}$ which is man ${m^*}$ ‘s top ranked choice from ${\{w: m^* \succ_w \mu(w), m^* = \mu(w) \} }$ . But this set contains ${w^*}$ which is ranked higher by man ${m^*}$ than ${w'}$ , a contradiction. ${\Box}$

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 ${i}$ or ${m}$ ) and “buyers” (indexed by ${j}$ or ${w}$ ). Imagine a “market” for a product that is infinitely divisible. Seller ${i}$ has ${s_i \geq 0}$ units to sell; buyer ${j}$ wishes to buy ${t_j \geq 0}$ and the quantity of sale between ${i}$ and ${j}$ can be at most ${u_{ij}}$ (“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 ${\{m_1, m_2, \ldots, m_n\}}$ , and the set of buyers will be ${\{w_1, w_2, \ldots, w_n\}}$ .

A splittable marriage is defined as an ${(n+1) \times (n+1)}$ matrix ${Z = (z_{ij})}$ such that:

$\displaystyle \sum_{i=1}^{n+1} z_{ij} = t_j\,\, \forall j$

$\displaystyle \sum_{j=1}^{n+1} z_{ij} = s_i, \,\, \forall i$

$\displaystyle z_{ij} \leq u_{ij}, \,\, \forall i, j$

$\displaystyle z_{ij} \geq 0, \,\, \forall i, j$

$\displaystyle z_{n+1, n+1} = 0$

Here ${z_{i,j}}$ is the quantity of the product sold by seller ${i}$ to buyer ${j}$ , if neither ${i}$ nor ${j}$ is ${n+1}$ ; if ${i = n+1}$ and ${j < n+1}$ , then ${z_{ij}}$ is the additional quantity that buyer ${j}$ would like to buy but cannot; and if ${i < n+1}$ and ${j = n+1}$ , then ${z_{ij}}$ is the additional quantity that seller ${i}$ would like to sell but cannot.

A blocking pair for a splittable marriage ${Z}$ is a pair of agents ${m_i}$ and ${w_j}$ such that

${z_{ij} < u_{ij}}$ ;
${\sum_{k: k \geq_i j} z_{ik} < s_i}$ ; and
${\sum_{k: k \geq_j i} z_{kj} < t_j}$ .

If ${(i,j)}$ blocks ${Z}$ , the agents ${i}$ and ${j}$ 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 ${i}$ is a vector ${x^i \equiv (x_{i,1}, x_{i,2}, \ldots, x_{i,n}, x_{i,(n+1)})}$ that satisfies (1) and (3). Similarly, a demand-list for buyer ${j}$ is a vector ${y^j \equiv (y_{1,j}, y_{2,j}, \ldots, y_{n,j}, y_{(n+1),j})}$ that satisfies (2) and (3).

The demand-lists of sellers and buyers can be encoded by matrices ${X}$ and ${Y}$ . Assume matrices ${X}$ and ${Y}$ have their rows indexed by the sellers and the columns indexed by the buyers. Specifically, ${X}$ has ${n}$ rows and ${(n+1)}$ columns, whereas ${Y}$ has ${(n+1)}$ rows and ${n}$ columns.

The seller demand-list matrix ${X}$ 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 ${Y}$ .

Let ${L_s}$ and ${L_b}$ be a collection of seller and buyer demand-lists respectively. Define partial orders ${\geq_s}$ and ${\geq_b}$ on the sets ${L_s}$ and ${L_b}$ respectively. For any two elements ${X, \hat{X} \in L_s}$ ,

$\displaystyle X \geq_s \hat{X} \;\;\;\; {\rm if} \;\;\; \forall i, j,\;\; \sum_{k:k \geq_i j} x_{ik} \geq \sum_{k:k \geq_i j} \hat{x}_{ik}.$

Similarly, for any two elements ${Y, \hat{Y} \in L_b}$ ,

$\displaystyle Y \geq_b \hat{Y} \;\;\;\; {\rm if} \;\;\; \forall i, j,\;\; \sum_{l:l \geq_j i} x_{lj} \leq \sum_{l:l \geq_j i} \hat{x}_{lj}.$

(Notice the change in the direction of the inequality in the definition of ${\geq_b}$ .)

Given any ${X, \hat{X} \in L_s}$ , let ${M \equiv X \wedge \hat{X}}$ be defined as follows:

$\displaystyle M_{ij} \; = \; \min \{ \sum_{k:k \geq_i j} x_{ik}, \sum_{k:k \geq_i j} \hat{x}_{ik} \} - \sum_{k:k >_i j} M_{ik}.$

Similarly, let ${J \equiv X \vee \hat{X}}$ be defined as follows:

$\displaystyle J_{ij} \; = \; \max \{ \sum_{k:k \geq_i j} x_{ik}, \sum_{k:k \geq_i j} \hat{x}_{ik} \} - \sum_{k:k >_i j} J_{ik}.$

The matrices ${M}$ and ${J}$ can be computed as follows: for each seller, compute the entries corresponding to his row, starting with the most preferred buyer. Clearly, ${M}$ and ${J}$ are in ${L_s}$ , and are, respectively, the greatest lower bound and the least upper bound of ${X}$ and ${\hat{X}}$ . Again, the meet and join of any two elements of ${L_b}$ can be defined in a similar way. Thus ${(L_s, \vee, \wedge)}$ and ${(L_b, \vee, \wedge)}$ 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 ${L_s}$ or ${L_b}$ ; hence ${(L_s, \vee, \wedge)}$ and ${(L_b, \vee, \wedge)}$ are complete lattices. The lattice of interest is the product lattice ${L \equiv (L_s, L_b)}$ with the partial order ${\geq}$ defined as follows:

$\displaystyle (X, Y) \geq (\hat{X}, \hat{Y}) \;\;\; {\rm if} \;\; X \geq_s \hat{X} \; {\rm and} \; Y \geq_b \hat{Y}.$

From standard results from lattice theory we see that ${L}$ is a complete lattice.

Call demand-lists ${X}$ and ${Y}$ compatible if ${X_{ij} = Y_{ij}}$ for all ${ 1 \leq i, j \leq n}$ . Any splittable stable marriage ${Z}$ can be viewed as a pair of compatible demand-lists: for any seller ${i}$ and buyer ${j}$ , set ${X_{ij}}$ and ${Y_{ij}}$ to be ${Z_{ij}}$ ; allocate the remaining supply and unfulfilled demand to the last entries in each row and column of ${X}$ and ${Y}$ respectively. The converse is false.

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

$\displaystyle X_{ij} = \min \{ u_{ij}, \max (t_j - \sum_{l: l >_j i} Y_{lj}, 0),\; \max (s_i - \sum_{k: k >_i j} X_{ik}, 0) \}. \ \ \ \ \ (1)$

Notice that ${X_{.,.}}$ 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 ${X}$ is never used in the update. We call this the canonical computation.

Similar considerations suggest:

$\displaystyle Y_{ij} = \min \{ u_{ij}, \max (t_j - \sum_{l: l >_j i} Y_{lj}, 0),\; \max (s_i - \sum_{k: k >_i j} X_{ik}, 0) \}. \ \ \ \ \ (2)$

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 6 If ${X}$ and ${Y}$ are solutions to Equations (1) and (2), then ${Z \equiv (X_{ij})}$ for ${1 \leq i, j \leq n}$ defines a splittable stable marriage.

Proof: By the hypothesis of the lemma, ${X}$ and ${Y}$ are identical. Thus,

$\displaystyle X_{ij} = \min \bigg\{ u_{ij}, \; \max\bigg(t_j - \sum_{l: l >_j i} X_{lj}, 0\bigg),\; \max\bigg(s_i - \sum_{k: k >_i j} X_{ik}, 0\bigg) \bigg\}.$

So if ${X_{ij} < u_{ij}}$ , either ${\sum_{l: l \geq_j i} X_{lj} \; = \; t_j}$ or ${\sum_{k: k \geq_i j} X_{ik} \; = \; s_i}$ . ${\Box}$

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

Theorem 7 For ${Y \in L_b}$ , let ${f(Y)}$ be the seller demand-list obtained from Eq.~(1). Then,

$\displaystyle Y \geq_b \hat{Y} \;\; \Rightarrow \;\; f(Y) \geq_s f(\hat{Y}).$

Proof: Consider seller ${i}$ and buyer ${j}$ . Since ${Y \geq_b \hat{Y}}$ , by definition,

$\displaystyle \sum_{l:l \geq_j i} y_{lj} \; \leq \; \sum_{l:l \geq_j i} \hat{y}_{lj}.$

Therefore

$\displaystyle t_j - \sum_{l:l \geq_j i} y_{lj} \; \geq \; t_j - \sum_{l:l \geq_j i} \hat{y}_{lj}.$

If ${j}$ is ${i}$ ‘s most preferred buyer, ${(f(Y))_{ij} \geq_i (f(\hat{Y}))_{ij}}$ follows from the definition. Inductively, we can argue along these lines that ${f(Y) \geq_s f(\hat{Y})}$ . ${\Box}$

Similarly:

Theorem 8 For ${X \in L_s}$ , let ${g(X)}$ be the buyer demand-list obtained from Eq.~(2). Then,

$\displaystyle X \geq_s \hat{X} \;\; \Rightarrow \;\; g(X) \geq_b g(\hat{X}).$

Consider the function ${h}$ defined on ${L}$ as follows:

$\displaystyle h(X,Y) := (g(Y), f(X)).$

We claim that ${h}$ is monotone. Why? Let ${(X, Y) \geq (\hat{X}, \hat{Y})}$ . Then ${Y \geq_b \hat{Y}}$ , and so ${g(Y) \geq_s g(\hat{Y})}$ ; similarly, ${X \geq_s \hat{X}}$ , and so ${f(X) \geq_b f(\hat{X})}$ . Thus ${h(X,Y) \geq h(\hat{X}, \hat{Y})}$ . By Tarski’s theorem, ${h}$ has a fixed point. This fixed point is clearly a splittable stable marriage.

One can generalize even further. Let ${f}$ and ${g}$ be two monotone integer valued submodular functions. Define a splittable matching to be any ${z \in P(f) \cap P(g)}$ . 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 ${m}$ and woman ${w}$ let ${x_{mw} = 1}$ if man ${m}$ is matched with woman ${w}$ and zero otherwise.

Then, every stable matching must satisfy the following.

$\displaystyle \sum_{w \in W}x_{mw} = 1\,\, \forall m \in M$

$\displaystyle \sum_{m \in M}x_{mw} =1\,\, \forall w \in W$

$\displaystyle \sum_{j \prec_m w}x_{mj} + \sum_{i \prec_w m}x_{iw} + x_{mw} \leq 1\,\, \forall m \in M, w \in W$

$\displaystyle x_{mw} \geq 0 \,\, \forall m \in M, w \in W$

Let ${P}$ be the polyhedron defined by these inequalities.

The first two constraints of ${P}$ 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 ${\sum_{j \prec_m w}x_{mj} = 1}$ and ${\sum_{i \prec_w m} x_{iw} = 1}$ . Then man ${m}$ is matched to a woman, ${j}$ that he ranks below ${w}$ . Similarly, woman ${w}$ is matched to a man she ranks below ${m}$ . This would make the pair ${(m,w)}$ a blocking pair.

Lemma 9 Suppose ${P \neq \emptyset}$ . Let ${x \in P}$ . Then, ${x_{ij} > 0}$ implies that

$\displaystyle \sum_{j \prec_m w}x_{mj} + \sum_{i \prec_w m}x_{iw} + x_{mw} = 1.$

Proof: Consider ${\min \{\sum_i \sum_j x_{ij}: x \in P\}}$ .The dual to this program is

$\displaystyle \max \sum_{i \in M}\alpha_i + \sum_{j \in W}\beta_j - \sum_{i \in M}\sum_{j \in W} \nu_{ij}$

subject to

$\displaystyle \alpha_i + \beta_j - \sum_{k \in W: k \succeq_{i} j}\nu_{ik} - \sum_{k \in M: k \succ_{j} i}\nu_{kj} \leq 1\,\, \forall\,\, i \in M \,\,,j \in W$

$\displaystyle \nu_{ij} \geq 0\,\, \forall\,\, i \in M \,\,,j \in W$

Set ${\alpha_i = \sum_{j \in W}\nu_{ij}}$ and ${\beta_j = \sum_{i \in M}\nu_{ij}}$ . Substituting this into the dual constraints yields:

$\displaystyle \sum_{k \in W:k \prec_i j}\nu_{ik} + \sum_{k \in M:k \prec_j i}\nu_{kj} + \nu_{ij} \leq 1\,\, \forall\,\, i \in M \,\,,j \in W.$

Choose any ${x^* \in P}$ and set ${\nu_{ij} = x^*_{ij}}$ . This choice of ${\nu}$ is clearly dual feasible. It has an objective function value of ${\sum_{i \in M}\sum_{j \in W}x^*_{ij}}$ and so, is dual optimal. The lemma now follows by complementary slackness. ${\Box}$

The proof below is due to Sethuraman and Teo.

Theorem 10 Suppose ${P \neq \emptyset}$ . Then, ${P}$ is the convex hull of stable matchings.

Proof: Choose any weight vector ${\{c_{ij}\}_{i \in M, j \in W}}$ and let

$\displaystyle x^* \in \arg \max \{\sum_i \sum_j c_{ij}x_{ij}: x \in P\}.$

With each member of ${M \cup W}$ we associate an interval ${(0,1]}$ . For each ${i \in M}$ , partition the associated interval ${(0,1]_i}$ into subintervals of length ${x^*_{ij}}$ for all ${j \in W}$ . Arrange these subintervals left to right by by man ${i}$ ‘s decreasing preference over ${W}$ . For each woman ${j \in W}$ , partition the associated interval ${(0,1]_j}$ into subintervals of length ${x^*_{ij}}$ for all ${i \in M}$ . Arrange these subintervals left to right by by woman ${j}$ ‘s increasing preference over ${M}$ .

Lemma 6 means the subinterval spanned by ${x^*_{ij}}$ in ${(0,1]_i}$ and ${(0,1]_j}$ coincides. Pick a random number ${U}$ uniformly in (0, 1] and construct a semi-matching in the following way:

Match ${i \in M}$ to ${k \in W}$ if ${U}$ lies in the subinterval of ${(0,1]_i}$ spanned by ${x^*_{ik}}$ .
Match ${j \in W}$ to ${i \in M}$ if ${U}$ lies in the subinterval of ${(0,1]_j}$ spanned by ${x^*_{ij}}$ .

By Lemma 6, ${i \in M}$ is matched to ${j \in W}$ iff ${j \in W}$ is matched to ${i \in M}$ . 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 ${i}$ who is matched to ${j \in W}$ but prefers ${k \in W}$ . Then, in ${(0,1]_i}$ , the subinterval corresponding to ${x^*_{ik}}$ is to the left of the subinterval corresponding to ${x^*_{ij}}$ . Because ${i \in M}$ is matched to ${k \in W}$ , it means that ${U}$ is to the right of the subinterval corresponding to ${x^*_{ik}}$ in ${(0,1]_i}$ . Therefore, ${U}$ is to the left of the subinterval corresponding to ${x^*_{ik}}$ in ${(0,1]_j}$ . In other words, ${j \in W}$ is matched to someone she prefers to ${i \in M}$ . Set ${X^U_{ij} = 1}$ iff man ${i}$ is matched to woman ${j}$ by the randomized scheme above. Then

$\displaystyle E(\sum_{i \in M}\sum_{j \in W}c_{ij}X^U_{ij}) = \sum_{i \in M}\sum_{j \in W}c_{ij}E(X^U_{ij})) = \sum_{i \in M}\sum_{j \in W}c_{ij}x^*_{ij}.$

Thus, we have exhibited a probability distribution over stable matchings whose expected objective function value coincides with ${c \cdot x^*}$ . It follows then, that there is a stable matching with objective function value ${c \cdot x^*}$ . ${\Box}$

3.1. A Subgradient Algorithm

The LP approach requires that we know that ${P \neq \emptyset}$ . 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 ${P \neq \emptyset}$ . If woman ${ j}$ is man ${ i}$ ‘s first choice set ${ r_{ij} = n}$ . If woman ${ j}$ is man ${ i}$ ‘s second choice set ${ r_{ij} = n-1}$ and so on. Consider:

$\displaystyle \max \{\sum_{m \in M}\sum_{w \in W}r_{mw}x_{mw}: x \in P\}.$

Let ${\nu}$ be the multiplier associated with the blocking constraints and ${p}$ the multiplier associated with the constraint ${\sum_{w \in W}x_{mw} = 1}$ for all ${m}$ . Consider the following Lagrangean relaxation of the optimization problem:

$\displaystyle \max \sum_{m \in M}\sum_{w \in W} [r_{mw} - p_w - \nu_{mw} - \sum_{k \in W:k \succ_m w } \nu_{mk} - \sum_{k \in M: k \succ_w m} \nu_{km}]x_{mw}$

subject to

$\displaystyle \sum_{w \in W}x_{mw} = 1\,\, \forall m \in M$

$\displaystyle x_{mw} \geq 0\,\, \forall (m,w)$

This is easy to solve. For each man ${m \in M}$ choose the woman ${w \in W}$ that maximizes

$\displaystyle r_{mw} - p_w - \nu_{mw} - \sum_{k \in W:k \succ_m w } \nu_{mk} - \sum_{k \in M: k \succ_w m} \nu_{km}.$

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

Initially set ${(p, \nu) = 0}$ . Let ${(p^t, \nu^t)}$ be the value of the multipliers at start of iteration ${t}$ . Denote by ${x^t}$ the optimal choice of ${x}$ given the multipliers ${(p^t, \nu^t)}$ . If ${x^t_{mw} = 1}$ we will say that man ${m}$ proposed to woman ${w}$ . Given ${x^t}$ we adjust ${(p^t, \nu^t)}$ by ${(p, \nu)}$ as follows:

Set ${p_j = 0}$
Set ${\nu_{ij} = x^t_{ij}}$ for all ${i,j}$ .
Set ${(p^{t+1}, \nu^{t+1}) = (p^t, \nu^t) + (p, \nu)}$
Set ${r^{t+1}_{mw} = r^t_{mw} - x^t_{mw} - \sum_{k \in W:k \succ_m w } x^t_{mk} - \sum_{k \in M: k \succ_w m} x^t_{km}.}$

Stop once ${x^t}$ is an assignment. By complementary slackness this must be an optimal stable assignment. Call ${r^t}$ the dual adjusted rank.

Suppose at iteration ${t}$ , ${x^t_{mw} = 1}$ .

Case 1 If among all ${i \in M}$ such that ${x^t_{iw} = 1}$ , man ${m}$ is woman ${w}$ ‘s top ranked choice, ${r^{t+1}_{mw} = r^t_{mw} - 1}$ .
Because ${i}$ is woman ${w}$ ‘s top ranked choice it follows that ${\sum_{k \in M: k \succ_w m} x^t_{km} = 0}$ . Because ${x^t_{mw} = 1}$ it follows that ${\sum_{k \in W:k \succ_m w } x^t_{mk} = 0}$ .

Case 2 If among all ${i \in M}$ such that ${x^t_{iw} = 1}$ , man ${m}$ is not woman ${w}$ ‘s top ranked choice, ${r^{t+1}_{mw} \leq r^t_{mw} - 2}$ .
Because ${i}$ is not woman ${w}$ ‘s top ranked choice it follows that ${\sum_{k \in M: k \succ_w m} x^t_{km} \geq 1}$ . Because ${x^t_{mw} = 1}$ it follows that ${\sum_{k \in W:k \succ_m w } x^t_{mk} = 0}$ .

Case 3 If ${w \succ_m j}$ and ${x^t_{kj} = 0}$ for all ${k \in M}$ such that ${k \succ_j m}$ , then ${r^{t+1}_{mj} = r^t_{mj}-1}$ .
Clearly ${\sum_{k \in M: k \succ_w m} x^t_{km} = 0}$ and ${x^t_{mj} = 0}$ . Also, ${\sum_{k \in W:k \succ_m w } x^t_{mk} = 1}$ .

Case 4 If ${w \succ_m j}$ and ${x^t_{kj} = 1}$ for at least one ${k \in M}$ such that ${k \succ_j m}$ , then ${r^{t+1}_{mj} \leq r^t_{mj} - 2}$ .
Clearly ${\sum_{k \in M: k \succ_w m} x^t_{km} \geq 1}$ and ${x^t_{mj} = 0}$ . Also, ${\sum_{k \in W:k \succ_m w } x^t_{mk} = 1}$ .

Case 5 If ${j \succ_m w}$ then, then ${r^{t+1}_{mj} = r^t_{mj} - \sum_{k \in M: k \succ_j m} x^t_{km}}$ .
Clearly, ${x^t_{mj} = 0}$ . Also, ${\sum_{k \in W:k \succ_m w } x^t_{mk} = 0}$ .

Let ${P^t = \{w \in W: \sum_{m \in M}x_{mw} \geq 1\}}$ . I show first that ${P^t \subseteq P^{t+1}}$ . Consider first the case ${t=0}$ . Suppose man ${m}$ proposed to woman ${w}$ and man ${m}$ is woman ${w}$ ‘s top choice among those who have proposed. Then the dual adjusted rank of woman ${w}$ by man ${m}$ 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 ${m}$ will continue to propose to woman ${w}$ . More generally, any woman who receives a proposal in iteration ${0}$ continues to receive a proposal in iteration ${1}$ . Suppose this holds until iteration ${t}$ . Suppose man ${m}$ proposes to woman ${w}$ in iteration ${t}$ and man ${m}$ is woman ${w}$ ‘s top choice among those who have proposed at iteration ${t}$ . By cases (1-4) the dual adjusted rank for all woman ranked below ${w}$ declines by at least 1. Consider a woman ${j \succ_m w}$ . By case 5

$\displaystyle r^{t+1}_{mj} = r^t_{mj} - \sum_{k \in M: k \succ_j m} x^t_{km}.$

However, ${\sum_{k \in M: k \succ_j m} x^t_{km} \geq 1}$ because any woman who received a proposal before iteration ${t}$ continues to receive a proposal at iteration ${t}$ . Thus the dual adjusted rank of all women ranked above ${w}$ decline by at least 1. Because man ${m}$ did not proposes to these women in iteration ${t}$ their dual adjusted rank must be at least 2 smaller than ${r^t_{mw}}$ . Thus, woman ${w}$ continues to have the highest dual adjusted rank for man ${m}$ and at iteration ${t+1}$ , man ${m}$ will continue to propose to woman ${w}$ .

Next, I show there must be some ${t}$ such that ${P^t = W}$ . If not, then, it must be the case that ${P^t = P^{t+1} = \ldots \subset W}$ . Because ${P^t \subset W}$ there must be a woman ${w}$ who is overdemanded. Consider a man ${m}$ who has proposed to her at iteration ${t}$ who is not her top choice among those proposing to her. Notice the following:

By case 2, ${r^{t+1}_{mw} \leq r^t_{mw} - 2.}$
By case 5 for all ${j \in P^t}$ such that ${w \succ_m j}$ , ${r^{t+1}_{mj} \leq r^t_{mj} -2}$ .
By case 5, for all ${j \in P^t}$ such that ${j \succ_m w}$ , ${r^{t+1}_{mj} \leq r^t_{mj} -1}$ .
By case 3, for all ${j \not \in P^t}$ , ${r^{t+1}_{mj} = r^t_{mj} - 1}$ . Note, for all such ${j}$ it must be that ${w \succ_m j}$ .

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

Razors and Blades

February 7, 2012 in Uncategorized | by rvohra | 6 comments

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!

The Elsevier Boycott

February 1, 2012 in Uncategorized | by rvohra | 6 comments

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.

Monthly Archive

Krugman on Hypocrisy

Market Design Class (Session 3)

Razors and Blades

The Elsevier Boycott

Email Subscription

Entries by:

Recent Posts

Recent Comments

Blogroll

Archives

Meta