5
$\begingroup$

I'm thinking of the following problem: There's a set $M$ of men and a set $W$ of women; furthermore there's a set $S$ of "possible marriages". Each possible marriage is a triple $(m, w, x)$, consisting of a man $m \in M$, a woman $w \in W$ and some arbitrary piece of extra information $x$.

For a man $m$, let $S_m = \{(m', w', x) \in S \mid m = m'\}$ be the set of possible marriages involving him, and for any woman $w$, let $S_w = \{(m', w', x) \in S \mid w = w'\}$ be the set of possible marriages involving her.

Instead of ranking the women he would marry, a man $m$ ranks the possible marriages: There is a total ordering $\leq_m$ defined on $S_m$. Similarly, for any woman $w$, there is a total ordering $\leq_w$ defined on $S_w$.

The problem is to find a stable matching. A stable matching is now a subset $X \subseteq S$ such that

  • every person is matched at most once, that is, for each man $m$, the intersection $X \cap S_m$ has at most one element, and for each woman $w$, the intersection $X \cap S_w$ has at most one element, and
  • $X$ is stable in the sense that for each possible marriage $s \in S$ between a man $m$ and a woman $w$, either

  • $m$ is in a marriage that is at least as good for him as $s$, that is, there is some $s' \in X \cap S_m$ such that $s' \geq_m s$, or
  • $w$ is in a marriage that is at least as good for her as $s$, that is, there is some $s' \in X \cap S_w$ such that $s' \geq_w s$.

The classical stable marriage problem is equivalent to the restricted version of this problem where for each possibe marriage $(m, w, x) \in S$, the "extra information" $x$ is required to be some fixed dummy value.

Has anybody studied this generalization and given it some name? If not, is there some naming convention for "this kind of generalization"?

$\endgroup$
7
$\begingroup$

Yes, this has been studied. Look up "matching with contracts" and the earlier papers by Crawford & Knoer (1981), and Kelso & Crawford (1982) in Econometrica.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! Crawford & Knoer (1981) and Kelso & Crawford (1982) seem to be more restricted, but "matching with contracts" (which seems to be introduced in Hatfield & Milgrom (2005)) seems to be exactly what I was looking for! $\endgroup$ – dankness Sep 13 '17 at 1:44
  • $\begingroup$ @dankness It is actually possible to embed the Hatfield & Milgrom model in the Kelso and Crawford model. See this paper. $\endgroup$ – Michael Greinecker Sep 13 '17 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.