Warning: include(/homepages/15/d499802527/htdocs/blogfrangalian/wp-content/themes/blue-with-grey/functions.php): failed to open stream: Permission denied in /homepages/15/d499802527/htdocs/blogfrangalian/wp-settings.php on line 497

Warning: include(): Failed opening '/homepages/15/d499802527/htdocs/blogfrangalian/wp-content/themes/blue-with-grey/functions.php' for inclusion (include_path='.:/usr/lib/php7.1') in /homepages/15/d499802527/htdocs/blogfrangalian/wp-settings.php on line 497
Algoritmo de aceptación diferida - Fran GalianFran Galian

Algoritmo de aceptación diferida

El otro día, hablando con un amigo y sus dificultades para encontrar una pareja adecuada, le dije: «¿Por qué no usas matemáticas para encontrar pareja?» Después de varios chistes y bromas aludiendo a su total incapacidad para socializar le expliqué en que consistía el algoritmo:

Este es uno de los muchos modelos de emparejamientos bilaterales en los que varios agentes son emparejados de dos en dos. Puede ser usado por una agencia matrimonial, un portal de encuentros, etc.

El objetivo es encontrar un emparejamiento estable en el cual, a nadie le gusta mas otra pareja posible que su pareja actual, recordando mucho al Óptimo de Pareto, en el cual no se puede encontrar una mejora sin que alguno de los individuos salga desfavorecido.

Tomemos un conjunto de n elementos donde la mitad son hombres y la otra mitad mujeres: es decir n/2 hombres y n/2 mujeres, por ejemplo en un salón de baile.

  • Paso 1: Cada hombre le propone bailar a la mujer que mas le gusta.
  • Paso 2: Cada mujer anota en su carné de baile la lista de propuestas que recibe.
  • Paso 3: Una vez que todos los hombres han propuesto bailar a la mujer que mas les gusta, cada mujer rechaza a todos los pretendientes salvo al que mas le gusta.
  • Paso 4: Los pretendientes rechazados proponen bailar a la siguiente mujer de su lista.
  • Paso 5: Se vuelve al paso 2 y se itera nuevamente hasta que todas las mujeres han recibido una oferta.

Este algoritmo, siempre producirá un emparejamiento estable puesto que si tomamos a un hombre emparejado, no existirá otra pareja que le guste mas y el sea aceptado, puesto que si existiera, le habría pedido bailar antes que a la pareja actual. En cuanto a ella, si le gustara mas, no habría sido rechazado anteriormente.

Con este emparejamiento, se encuentra el óptimo para los hombres, pero pueden ser intercambiados los papeles y se encontraría el óptimo para ellas.

Volviendo a la realidad, es un algoritmo frívolo pero es ampliamente utilizado en la actualidad, como por ejemplo en la selección de estudiantes de muchas universidades de EEUU, en la selección de médicos en hospitales, etc.

Así que no lo olvidéis, la próxima vez que vayáis a un baile, llevad papel y lápiz y haced una lista de las posibles parejas de baile. Nunca se sabe…





Como siempre, puedes invitarme a un café o un refresco. Gracias.

, ,

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *