Estoy pensando en el siguiente problema: Hay un conjunto $M$ de hombres y un conjunto $W$ de mujeres; además hay un conjunto $S$ de "posibles matrimonios". Cada matrimonio posible es un triple $(m, w, x)$ compuesto por un hombre $m \in M$ una mujer $w \in W$ y alguna pieza arbitraria de información extra $x$ .
Para un hombre $m$ , dejemos que $S_m = \{(m', w', x) \in S \mid m = m'\}$ sea el conjunto de posibles matrimonios en los que él participe, y para cualquier mujer $w$ , dejemos que $S_w = \{(m', w', x) \in S \mid w = w'\}$ sea el conjunto de posibles matrimonios con ella.
En lugar de clasificar a las mujeres con las que se casaría, un hombre $m$ clasifica los posibles matrimonios: Hay una ordenación total $\leq_m$ definido en $S_m$ . Del mismo modo, para cualquier mujer $w$ existe una ordenación total $\leq_w$ definido en $S_w$ .
El problema es encontrar un emparejamiento estable. Un emparejamiento estable es ahora un subconjunto $X \subseteq S$ tal que
-
cada persona se empareja como máximo una vez, es decir, por cada hombre $m$ la intersección $X \cap S_m$ tiene como máximo un elemento, y para cada mujer $w$ la intersección $X \cap S_w$ tiene como máximo un elemento, y
-
$X$ es estable en el sentido de que para cada matrimonio posible $s \in S$ entre un hombre $m$ y una mujer $w$ o bien
-
$m$ está en un matrimonio que es al menos tan bueno para él como $s$ es decir, hay algún $s' \in X \cap S_m$ tal que $s' \geq_m s$ ou
-
$w$ está en un matrimonio que es al menos tan bueno para ella como $s$ es decir, hay algún $s' \in X \cap S_w$ tal que $s' \geq_w s$ .
El problema clásico del matrimonio estable es equivalente a la versión restringida de este problema, en la que para cada matrimonio posible $(m, w, x) \in S$ la "información extra" $x$ debe ser un valor ficticio fijo.
¿Alguien ha estudiado esta generalización y le ha dado algún nombre? Si no es así, ¿existe alguna convención para denominar "este tipo de generalización"?
