Pregunta 1 (30 puntos)

En Santiago hay 6 corazones disponibles para trasplante, uno en cada hospital público de la ciudad. Adicionalmente, hay 6 pacientes receptores en lista de espera. Queremos asignar cada corazón a un receptor de modo que la asignación sea estable (sin parejas bloqueantes hospital–paciente). A continuación, definimos los conjuntos de hospitales y de pacientes receptores: \[H = \{H1,H2,H3,H4,H5,H6\}\] \[P = \{r1,r2,r3,r4,r5,r6\}\] Además, asumimos la siguiente hipótesis de compatibilidad universal: cualquier hospital \(H_i\) puede donar a cualquier paciente \(r_j\). A continuación, detallamos las preferencias de cada hospital y paciente, las cuáles podrían ser motivadas por aspectos como –por ejemplo– la logística.

Apliquen el algoritmo de casamiento estable al caso en que los hospitales proponen corazones a pacientes.

Solución

Pregunta 2 (30 puntos)

Considere el emparejamiento estable obtenido en la iteración 13 de la Pregunta 1. Para \(i \in \left\{1,2,3,4,5,6\right\}\), defina \(r\left(H_i\right)\) como el paciente en P al cual finalmente fue asignado el corazón de \(H_i\). Entonces, podemos definir la función costo de \(H_i\) por:

De modo similar, dado \(j ∈ \{1,2,3,4,5,6\}\), defina \(H\left(r_j\right)\) como el hospital en H que finalmente entregó el corazón a \(r_j\) . Al igual que antes, podemos definir también la función costo de \(r_j\) por:

Definimos respectivamente el costo de los hospitales, el costo de los pacientes y el costo total por:

Estos costos son asociados al emparejamiento estable obtenido en la pregunta anterior.

  1. (10 puntos) Calcule los costos \(C_H\), \(C_r\) y \(C_T\) para el emparejamiento estable de la Pregunta 1.

  2. (10 puntos) Analice los valores obtenidos para los costos; ¿cuál costo es mayor, \(C_H\) o \(C_r\)? ¿Puede explicar el motivo? ¿Qué habría pasado si los pacientes comienzan proponiendo a los hospitales en el algoritmo de casamiento estable (es decir, los pacientes a la izquierda y los hospitales a la derecha en el grafo bipartito)?

  3. (10 puntos) Si fueran los encargados de coordinar los trasplantes de corazón a nivel nacional, ¿qué criterio usarían para equilibrar los costos de los emparejamientos?

Solución

Parte (a)

Es conveniente hacer una tabla para calcular \(C_H\), \(C_r\) y \(C_T\):

Tabla 1. Costos de los \(H_i\)

Tabla 2. Costos de los \(r_i\)

Entonces el costo total es: \[C_T = C_H + C_r\] \[\therefore C_T = 6 + 9\] \[\therefore C_T = 15\]

Parte (b)

Claramente, \(C_r\) es mayor. La explicación es que los hospitales comienzan proponiendo a los pacientes, y por ende, siempre eligen a su máxima preferencia entre las posibilidades restantes. En cambio, los pacientes solamente tienen la opción de rechazar un hospital entre dos alternativas.

Hay que aplicar el algoritmo, ahora con los pacientes proponiendo, para encontrar el casamiento estable a la que se llega.

Parte (c)

Para equilibrar, y a la vez minimizar, los costos de hospitales y pacientes, buscaría asignar a cada hospital a su preferencia máxima, y asimismo haría lo mismo para los pacientes, dentro de lo factible. Si llegara a una diferencia entre los costos, realizaría reasignaciones hasta igualar ambos costos totales: \(C_H\) y \(C_r\).