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.

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