Stable Matching Problem

Question 1

Describa el Stable Matching Problem

Answer 1

Dados:

• 2 conjuntos de n integrantes 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

Question 2

Provea un ejemplo del Stable Matching Problem

Answer 2

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.

Question 3

¿Qué es un matching perfecto "S"?

Answer 3

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.

Question 4

¿Cuándo una pareja (d1,e1) de un matching es inestable?

Answer 4

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.

Question 5

¿Cuándo un matching es ‘estable’ ?

Answer 5

Un matching es estable cuando:

• Es perfecto (cada elemento aparece una sola vez)
• No contiene inestabilidades

Question 6

Para un mismo caso, ¿existe un único matching estable?

Answer 6

No. Para un mismo caso, pueden existir diferentes matchings estables.

Question 7

Explique brevemente el Algoritmo de Gale Shapley

Answer 7

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.

Question 8

¿Qué consecuencias tiene el algoritmo Gale Shapley?

Answer 8

• 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.

Question 9

¿Cuál es la complejidad del algoritmo Gale Shapley?

Answer 9

O(n^2)

Question 10

¿Cuál es el resultado de Gale Shapley?

Answer 10

El resultado es un matching perfecto y sin inestabilidades.

1. 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ó.
2. Al terminar, todos los solicitantes estarán en pareja y el matching será perfecto.
3. 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.

Question 11

¿A qué se le llama el mejor y peor compañero válido en Gale Shapley?

Answer 11

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.

Question 12

El matching que retorna Gale Shapley, ¿contiene a los mejores compañeros válidos de los solicitantes o de los requeridos?

Answer 12

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.

Question 13

¿Cuáles son las posibles variantes de Gale Shapley?

Answer 13

1. Diferente cantidad de solicitantes que requeridos
2. Preferencia con empates
3. Preferencias incompletas
4. Agrupación de 1 a muchos (solicitante con varios cupos)
5. Agrupación de muchos a 1 (requerido con varios cupos)
6. Agrupación de y a x (vinculación de muchos a muchos)
7. Los conjuntos no son bipartitos

Question 14

Variante de Gale Shapley: Diferente cantidad de solicitantes que de requeridos.

1. ¿Cómo se define un matching estable?
2. ¿Cómo se ajusta el modelo?

Answer 14

1. 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 requerido sin pareja al que un solicitante prefiera por sobre su pareja actual.
• No existe un requerido en pareja tal que se prefieran entre sí con otro solicitante.
• No existe un solicitante sin pareja tal que un requerido lo prefiera por sobre su pareja actual.
• No existe un solicitante con 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.

Question 15

Variante de Gale Shapley: Preferencias Incompletas.

1. ¿Cómo se define un matching estable?
2. ¿Cómo se ajusta el modelo?

Answer 15

1. 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.

2. 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.

Question 16

Variante de Gale Shapley: Indiferencia y Preferencia Estricta.

1. ¿Cómo se define un matching debilmente estable y un matching super estable?
2. ¿Cómo se ajusta el modelo?

Answer 16

1.
Ahora se dice que un elemento:

• Prefiere estrictamente a x por sobre y si
  Pref(x) > Pref(y)
• Le es indiferente x de y si
  Pref(x) = Pref(y)

Entonces se define a una pareja como debilmente estable si no existe otra pareja tal que se prefiera estrictamente con participantes de otra (puede serle indiferente su pareja actual respecto de otra). Los requeridos cambian de pareja sólo si el solicitante es preferido estrictamente por sobre el actual.

Se define a una pareja como super estable si no existe otra pareja tal que exista algún tipo de preferencia (estricta o indiferente) con alguno de sus elementos.

2. Para obtener un matching debilmente estable:
   Se hacen cambios sólo si se prefiere de forma estricta a otro solicitante.

Para obtener un matching super estable:
Si el solicitante le pide a un requerido, el requerido acepta.

Una vez que se ocupa el solicitante, por cada uno de los otros elementos sucesores en la lista de preferencias del requerido:
- Se eliminan las parejas, si existen.
- Se eliminan entre sí de sus listas de preferencias.

Luego, si hay requeridos con múltiples parejas, se eliminan las parejas y se quitan entre sí de su lista de preferencias. Esto es porque queremos parejas super estables, sin indiferencias.

Esto se repite mientras exista solicitante sin pareja que no haya agotado sus propuestas.

Si se termina y todos están en pareja, se devuelve el matching. De lo contrario, no existe un matchung super estable.

Question 17

Variante de Gale Shapley: Solicitante con varios cupos.

1. ¿Cómo se define un matching estable?
2. ¿Cómo se ajusta el modelo?

Answer 17

1. Una pareja es estable si no existe un requerido tal que el solicitante y él se prefieran por sobre sus parejas actuales; o si no existe un requerido libre tal que el solicitante lo prefiere por sobre su pareja actual.

Un matching estable debe ser perfecto y cumplir esta condición.

2. Se agrega un contador de parejas actuales por solicitante. Cada vez que se compromete, se resta uno. Cada vez que es liberado, se suma uno.

Question 18

Variante de Gale Shapley: Requerido con varios cupos.

1. ¿Cómo se define un matching estable?
2. ¿Cómo se ajusta el modelo?

Answer 18

1. El matching estable es igual al del solicitante con varios cupos: no debe existir un requerido tal que con un solicitante en pareja se prefieran entre sí por sobre sus parejas actuales, ni un solicitante o requerido libre tal que otro requerido o solicitante en pareja lo prefiera por sobre su pareja actual.
2. El requerido se compromete siempre que tenga cupo. Si no tiene cupo, requiere conocer su solicitante de menor preferencia.

Esto modifica la complejidad, porque tenemos que tener un heap para comparar preferencias.

Question 19

Variante de Gale Shapley: Requerido y Solicitante con varios cupos.

1. ¿Cómo se define un matching estable?
2. ¿Cómo se ajusta el modelo?

Answer 19

1. No cambia la definición de matching estable.
2. Se necesita un heap por cada pareja de requeridos y un contador para los solicitantes.

El solicitante propone a requeridos mientras tenga cupo, y los requeridos aceptan si tienen cupo o si la propuesta supone una mejora respecto de las parejas actuales.

Question 20

Resuelva con Gale Shapley

Directores
d1 → e4, e3, e1, e2
d2 → e2, e1, e4, e3
d3 → e1, e2, e3, e4
d4 → e1, e2, e3, e4

Equipos
e1 → d2, d3, d1, d4
e2 → d3, d2, d1, d4
e3 → d3, d1, d2, d4
e4 → d1, d2, d3, d4

Answer 20

{(d1,e1), (d2,e2), (d3, e3), (d4,e4)} es un matching perfecto.

Question 21

Resuelva con Gale Shapley con indiferencias

Preferencias solicitantes
a 1, (2, 4), 3, 5
b 5, (1, 2), 4, 3
c 2, 1, 3, (4, 5)
d 5, 4, (3, 2), 1
e 1, (2, 3), 5, 4

Preferencias acompañantes
1 b, c, (a, e), d
2 a, b, d, (e, c)
3 (a, b), c, d, e
4 b, c, a, e, d
5 d, e, (b, a), c

Answer 21

(1,b), (2,a), (3,c), (4,e), (5,d) es un matching super estable