Stable Matching Problem Flashcards
Describa el Stable Matching Problem
Dados:
- 2 conjuntos de
nintegrantes A y B:
A = {a_1, …, a_n}
B = {b_1, …, b_n}
- Una función de preferencia que para cada integrante de A, rankea a cada integrante de B
- Una función de preferencia que para cada integrante de B, rankea a cada integrante de A
=> Se busca construir parejas estables entre A y B
Provea un ejemplo del Stable Matching Problem
Se tienen n directores técnicos (conjunto D) y n equipos (conjunto E).
Cada director técnico d_i tiene una lista ordenada de preferencias de los equipos, sin indiferencias ni empates.
Cada equipo e_i tiene una lsita ordenada de preferencias de los directores técnicos, sin indiferencias ni empates.
Se llamará matching "S" al conjunto de pares (d,e) tal que: cada e aparece como mínimo en un par de S y cada d aparece como mínimo en un par de S.
¿Qué es un matching perfecto "S"?
Un conjunto de pares (d,e) tal que cada ‘e’ y cada ‘d’ aparecen en un par del conjunto S.
Además, todas las parejas del matching deben ser estables.
¿Cuándo una pareja (d1,e1) de un matching es inestable?
Una pareja (d1,e1) es inestable cuando existe otra pareja (d2,e2) tal que:
- d1 prefiere a e2
- e2 prefiere a d1
(Se prefieren con elementos de otra pareja y es mutuo)
O cuando d1 prefiere a un requerido que se encuentra libre respecto de su pareja actual.
¿Cuándo un matching es ‘estable’ ?
Un matching es estable cuando:
- Es perfecto (cada elemento aparece una sola vez)
- No contiene inestabilidades
Para un mismo caso, ¿existe un único matching estable?
No. Para un mismo caso, pueden existir diferentes matchings estables.
Explique brevemente el Algoritmo de Gale Shapley
De los dos conjuntos del Stable Matching Problem, uno toma el papel de solicitante y el otro de requeridos.
El algoritmo es iterativo:
1. Un solicitante que aún no tiene pareja le pide al requerido de su mayor preferencia que no le haya pedido antes.
2. Si el requerido no tiene pareja, acepta.
3. Si la tiene, pero lo prefiere respecto de su compañero actual, deja al actual y lo acepta.
4. El desplazado regresa al grupo de los que aún no tienen pareja.
El proceso se repite mientras quede algún solicitante sin pareja que no haya agotado sus opciones.
¿Qué consecuencias tiene el algoritmo Gale Shapley?
- Una vez que un requerido está en pareja, no vuelve a quedar libre. Puede cambiar de pareja si lo prefiere, pero siempre para mejorar la situación actual.
- Las parejas de los solicitantes tienden a empeorar con el tiempo o, en el mejor de los casos, se mantiene igual.
¿Cuál es la complejidad del algoritmo Gale Shapley?
O(n^2)
¿Cuál es el resultado de Gale Shapley?
El resultado es un matching perfecto y sin inestabilidades.
- Si el solicitante está desocupado, entonces existe algún requerido al que aún no le solicitó. Imaginemos que tengo n requeridos todos en pareja, entonces significa que tengo n+1 solicitantes y no es posible => si hay un solicitante desocupado, hay algún requerido al que no le solicitó.
- Al terminar, todos los solicitantes estarán en pareja y el matching será perfecto.
- El matching final no tiene inestabilidades, porque si hubiese un par de (solicitante, requerido) que no estén juntos y se prefieran entre sí, el solicitante ya le hubiese pedido al requerido, y el requerido hubiese cambiado de pareja.
=> Por lo tanto, el resultdo es un matching estable.
¿A qué se le llama el mejor y peor compañero válido en Gale Shapley?
r es un compañero válido de s si existe algún M matching estable que contenga a la pareja (r,s).
Pero r es el mejor compañero válido de s si s lo prefiere por sobre todos sus compañeros válidos.
Vale lo inverso, para definir al peor compañero válido.
El matching que retorna Gale Shapley, ¿contiene a los mejores compañeros válidos de los solicitantes o de los requeridos?
El resultado retorna el matching con los mejores compañeros válidos de los solicitantes.
Cada solicitante está emparejado con el mejor compañero válido posible en el contexto de sus preferencias y la disponibilidad de sus compañeros.
Los requeridos, por otra parte, quedan emparejados con su peor pareja válida.
¿Cuáles son las posibles variantes de Gale Shapley?
- Diferente cantidad de solicitantes que requeridos
- Preferencia con empates
- Preferencias incompletas
- Agrupación de 1 a muchos (solicitante con varios cupos)
- Agrupación de muchos a 1 (requerido con varios cupos)
- Agrupación de
yax(vinculación de muchos a muchos) - Los conjuntos no son bipartitos
Variante de Gale Shapley: Diferente cantidad de solicitantes que de requeridos.
- ¿Cómo se define un matching estable?
- ¿Cómo se ajusta el modelo?
- Esta variante no arroja un matching estable tradicional.
Se puede encontrar un matching sin inestabilidades, pero no un matching perfecto.
=> Se redefine el matching estable como:
- No existe un
requeridosin pareja al que un solicitante prefiera por sobre su pareja actual. - No existe un
requeridoen pareja tal que se prefieran entre sí con otro solicitante. - No existe un
solicitantesin pareja tal que un requerido lo prefiera por sobre su pareja actual. - No existe un
solicitantecon pareja tal que se prefieran entre sí con un requerido.
Un matching es estable si:
- No tiene parejas inestables bajo las condiciones anteriores.
- No existen solicitante y requerido que se prefieran entre sí, sin pareja.
- Se inventan elementos ficticios con prioridades inventadas, completando los faltantes de los requeridos.
- Se agregan prioridades para los ficticios en los solicitantes, siendo estos los peores compañeros válidos.
- Se ejecuta Gale Shapley
- Se eliminan las parejas que tengan un elemento ficticio.
Variante de Gale Shapley: Preferencias Incompletas.
- ¿Cómo se define un matching estable?
- ¿Cómo se ajusta el modelo?
- La lista de preferencias de los solicitantes y requeridos son un subespacio de la totalidad de las opciones.
=> Se define una pareja como estable si:
- Están en sus listas de preferencias
- No existe requerido aceptable sin pareja al que el solicitante prefiera por sobre su actual.
- No existe requerido en pareja tal que con un solicitante se prefieran entre sí.
- No existe solicitante sin pareja al que un requerido prefiera por sobre su actual.
- No existe solicitante en pareja tal que con un requerido en pareja se prefieran entre sí.
Un matching es estable si no tiene parejas inestables bajo las condiciones anteriores.
- El modelo es igual a Gale Shapley, sólo que ahora cabe la posibilidad de que el requerido no considere aceptable al solicitante (no lo tenga en su lista de preferencias). En ese caso, lo rechaza.
