Algoritmo del matrimonio estable de Poisson y Lebesgue

En esta etrada todavía no va a encontrarse mucha cosa muy nueva. Pero sí es importante para las entradas futuras hacer una descripción de cómo sería el algoritmo. El algoritmo del matrimonio estable fue introducido para el caso discreto en el que hay n mujeres y n hombres. La idea en términos muy coloquiales es la siguiente:

DESCRIPCIÓN (MUY) HEURÍSTICA

Suponga que en su barrio solo viven parejas casadas, y suponga que su esposa preferiría estar casada con su vecino y no con usted. Suponga además que su vecino también preferiría estar casado con su esposa y no con la esposa de él. Entonces, como su esposa y su vecino se quieren tanto mutuamente, ellos son una pareja inestable.  Si no hay parejas inestables se dice que el barrio es estable. Note que no basta con que su esposa quiera más a su vecino que a usted pa’ que usted esté en problemas; su vecino también tiene que querer más a su esposa que a la de él. Los dos se tienen que querer más entre ellos que a sus respectivas parejas. Esa aquí es la definición de estabilidad. Intuitivamente esto es acorde con los conceptos de deseo y codicia definidos en la entrada anterior.

Note además que el algoritmo no es solo machista al imaginarse que la esposa es la mala del paseo. También puede verse desde el lado feminista: imagínese la situación de la esposa del vecino. El marido de ella y su esposa (la del lector, no la del vecino), en nuestro ejemplo, siguen siendo la misma pareja inestable. El comentario no busca ser políticamente correcto; más que eso, es una característica interesante del algoritmo y sus generalizaciones.

Eso a nivel matemático es lo que pide el modelo descrito en la entrada anterior: suponga que el conjunto de centros \Xi son los hombres del barrio y las mujeres son los puntos de \mathbb R^d,. Existe un algoritmo que genera un matrimonio estable para ese caso. El algoritmo puede verse como una generalización del propuesto por Gale y Shapley en los 60… así puesto, en la generalización que viene, vale la poligamia para los hombres.

¿Cómo funciona el algoritmo?

Piense de la siguiente manera: Cada hombre (cada centro \xi\in\Xi) tiene un volumen \alpha_\xi de mujeres con quienes se puede casar (lo que llamamos apetito en la entrada anterior).

Cada mujer (los puntos de \mathbb R^d) va a pedirle al hombre que más les gusta que se case con ella y el hombre va a recibirla si no ha copado su número máximo de matrimonios (satisfecho su apetito).

Si el hombre no ha alcanzado su número máximo de esposas, recibe a las que le propusieron matrimonio hasta llegar a ese volumen permitido (cuando satisface su apetito). Si recibe más propuestas que su número de matrimonios permitido, va a escoger las que más le gustan entre las que le propusieron matrimonio hasta colmar su capacidad y va a rechazar a las otras.

Las mujeres que fueron rechazadas pasan a pedirle matrimonio al segundo hombre que más les gusta y las mismas consideraciones del párrafo anterior son válidas también para el segundo hombre. Así cada mujer le pide matrimonio por orden de gusto a todos los hombres hasta que uno de ellos acepte su propuesta… o hasta que se acabe la cantidad de hombres disponibles, en cuyo caso ella quedará soltera. Las muy pocas mujeres a las que dos hombres les gusten igual, salen del juego.

DESCRIPCIÓN FORMAL

Como \Xi es un conjunto discreto de centros en \mathbb R^d, es claro que la medida de Lebesgue de sitios de \mathbb R^d equidistantes a dos centros es nula, luego \mathcal L-c.t. sitio x\in\mathbb R^d no es equidistante a ningún par de centros (donde \mathcal L es la medida de Lebesgue en \mathbb R^d). Ese conjunto de sitios equidistantes a dos centros fue el que en la entrada anterior llamamos \Delta.

Para cada entero positivo n, la etapa n consiste de dos partes:

  1. Cada sitio x\notin\Delta aplica al centro más cercano que no lo haya rechazado en ninguna de las etapas   anteriores.
  2. Para cada centro \xi, sea A_n(\xi) el conjunto de sitios que aplican al centro \xi en la etapa n (a) y defina el radio de rechazo

r_n(\xi)=\inf\left\{r:\mathcal{L}\left(A_n(\xi)\cap B(\xi,r)\right)\geq\alpha_{\xi}\right\}

donde el ínfimo de vacío es \infty. Entonces el centro \xi alista a todos los sitios en A_n(\xi)\cap B(\xi,r_n(\xi)) y rechaza a todos los sitios de A_n(\xi)\setminus B(\xi, r_n(\xi)).

Considere el sitio x\notin\Delta. Puesto que \Xi es discreto lo siguiente es elemental. O  todo centro recahza a x (en orden de distancia creciente de x), o para algún centro \xi y alguna etapa n, x es alistado por \xi en toda etapa después de n. En el primer caso hacemos \psi(x)=\infty (luego x no es reclamado); en el segundo caso hacemos \psi(x)=\xi.

Note que este algoritmo es la mejor para los sitios (son ellos los que escogen a qué centro quieren ir) mientras que es la peor para los centros que no pueden sino recibir lo que les llega. Existe una construcción similar que es la mejor para los centros y la peor para los sitios. Cada uno de estos algoritmos es llamado algoritmo de Gale-Shapley óptimo para los sitios y algoritmo de Gale-Shapley óptimo para los centros, respectivamente.

TEOREMA DE EXISTENCIA

Con la función \psi(\cdot) así construida es muy fácil ya probar el siguiente teorema:

Para cualquier conjunto discreto de centros \Xi\in\mathbb{R}^d, con apetito aleatorio \alpha  de distribución F y realización de apetito \alpha_\xi para todo centro \xi\in\Xi, existe una asignación estable \psi(\cdot) (que corresponde a la descrita en la sección anterior), F-c.c.

Cuando el conjunto de centros \Xi\subset\mathbb R^d es escogido de acuerdo a un proceso puntual ergódico \Pi con ley \textbf P e intesidad finita \lambda, puede mostrarse que \textbf P-c.c. y F-c.c. existe una única función de asignación estable para \Xi=[\Pi], donde los corchetes simbolizan el soporte del proceso, en este caso el proceso  puntual \Pi. Cuando el proceso puntual es un proceso de Poisson entonces la función de asignación asigna conjuntos borelianos en \mathbb R^d con medida de Lebesgue igual al apetito de cada centro Poisson… por eso se llama matrimonio estable de Poisson y Lebesgue.

Introducción a las asignaciones estables de Poisson y Lebesgue

La gráfica ilustra un modelo en un espacio bidimensional en el cual los centros se escogen aleatoriamente en el plano y cada centro tiene un apetito, un área que busca «comerse». Es una simulación de asignaciones (funciones matemáticas que cumplen ciertas propiedades) cuando los centros se escogen aleatoriamente, mediante un proceso de Poisson, y quieren «comerse» un volumen determinado del espacio. La cantidad de volumen que cada centro come se mide mediante una medida de Lebesgue. Se denomina territorio la cantidad de espacio que cada centro se come. Intuitivamente, puede describirse el modelo así: cada centro quiere comer las porciones más cercanas a él que no hayan sido comidas por otro centro en el espacio y un centro para de comer cuando ocurra una de dos cosas:

  1. El centro satisfizo su apetito.
  2. El centro no satisfizo su apetito pero no hay más volumen del espacio para comer pues «todo» el espacio ya fue comido por los otros centros.

Puede verse también intuitivamente que si los centros tienen «poco» apetito, habrá muchos lugares en el plano que no serán reclamados por ningún centro.

Suponga ahora que cualquier lugar a del plano pertenece al territorio de un centro A, pero a está más cerca de otro centro B que de A, si eso ocurre decimos que el punto a desea a B. El lugar a también va a desear al centro B si a no fue reclamada por ningún centro.

Ahora suponga que el centro B dentro de su territorio tiene un punto b que está más lejos de él que a pero a no hace parte del territorio de B. Entonces decimos que B codicia a a. Si B no satisfizo su apetito y el lugar a no pertenece a su territorio también decimos que B codicia a a.

Finalmente decimos que si a desea a B y B codicia a a entonces el par (a, B) no es estable. Si la función de asignación no tiene ningún par inestable, decimos que la asignación es estable.

Puede demostrarse que existe una función de asignaciones estables utilizando el algoritmo de Gale-Shapley para matrimonios estables, pero describir ese argumento será tema de otra entrada.

Nota final: la gráfica ilustra el caso bidimensional pero el modelo y su teoría se trabajan para cualquier dimensión, incluso cuando el número de dimensiones tiende a infinito.