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.

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s