3.1.1. Un criterio normativo: la estabilidad

Se asume que, al revelar las preferencias a un mecanismo, tanto médicos como hospitales desearían que la asignación cumpliese con dos requisitos: 1) que no estén asignados a un hospital/médico que no les sea aceptable (que prefieran no tener a nadie antes que esa asignación); y 2) que no exista un par conformado por un médico y un hospital que se prefieran mutuamente al hospital y el médico que les haya asignado por el mecanismo. En el primer caso, este requisito es llamado “racionalidad individual” y en el segundo se dice que no hay un “par bloqueador”. Una asignación que cumplan ambos criterios es llamada estable.

Ejemplo 1. Consideremos un mercado compuesto por seis médicos, m ₁, m ₂, m ₃, m ₄, m ₅ y m ₆, y cuatro hospitales, h ₁, h ₂, h ₃ y h ₄ que desean contratar, cada uno, solo a un médico. Las preferencias de cada agente son las siguientes.

 

Una posible asignación es:

 

En este caso, hay que notar que la asignación no es estable por violar ambas condiciones: al médico m ₃ se le asignó el hospital h ₄ aun cuando este hospital no es aceptable para el médico; por lo que se está violando la condición de racionalidad individual. Aunado a ello, el hospital h ₁ está asignado al médico m ₁ cuando prefiere al médico m ₃ y de manera recíproca, el médico m₃ prefiere el hospital h ₁ al hospital que le fue asignado, h ₄; por lo que (m ₃, h ₁) forman un par bloqueador a la asignación.

El concepto de solución propuesto por Gale y Shapley (1962), por lo tanto, no es trivial de cumplir. Sin embargo, la buena noticia que los autores nos tienen en el primer resultado fundamental que prueban, es la existencia de una asignación estable en cualquier mercado “uno-a-uno”. El argumento para comprobar la existencia de una asignación con estas características es constructivo. Para ello, los autores formalizan el algoritmo de “Aceptación Diferida” (DA por sus siglas en inglés), el cuál siempre produce una asignación estable.

3.1.2. El algoritmo DA

En esta sección presentaremos el algoritmo y su correspondiente corrida en el mercado de emparejamiento con el ejemplo anterior.

El otro lado del mercado, los hospitales, consideran las ofertas recibidas y se quedan con su oferta recibida favorita. El hospital h ₁ recibió ofertas de los médicos m ₁ y m ₃, escoge m ₃; el hospital h ₂ solo recibió oferta del médico m ₂ y, como es aceptable, se queda con él; el hospital h ₃ recibe ofertas de los médicos m ₅ y m ₆, ambos son aceptables, pero m ₆ es su preferido, por lo que tentativamente se queda con m ₆; el hospital h ₄ recibe una oferta del médico m ₄, al no ser una opción aceptable, rechaza la oferta. Por lo tanto, la segunda asignación tentativa es

 

Paso genérico: en cada iteración, los médicos no asignados hacen ofertas en el sentido decreciente de sus preferencias a los hospitales a quienes nunca hicieron ofertas; los hospitales comparan su asignación tentativa con las nuevas ofertas recibidas y quedan tentativamente asignados con su mejor opción.

Las rondas son iterativas hasta que ya no haya médicos no asignados ni ofertas que hacer de parte de los médicos no asignados, ni más médicos a quienes rechazar o aceptar. Así se va creando una secuencia de asignaciones tentativas en donde, en cada paso, los médicos no asignados hacen ofertas al mejor hospital dentro de los que todavía no han hecho una oferta, y los hospitales escogen su mejor opción entre su asignación tentativa anterior y las ofertas recibidas. Por lo tanto, el proceso termina cuando todos los médicos están asignados o los médicos sin asignar ya hicieron ofertas a todos sus hospitales aceptables.

Continuando con estos principios, en el siguiente paso, siendo no asignados los médicos m ₁, m ₄ y m ₅, emiten las siguientes ofertas:

El hospital h ₂ está asignado al médico m ₂, sin embargo, prefiere la oferta del médico m ₁, con el que se queda; el hospital h ₃ también prefiere su nueva opción, el médico m ₄, a su asignación tentativa, el médico m ₆; el hospital h ₄ por fin recibe una oferta aceptable con la que se queda, la del médico m ₅; el hospital h ₁ por su parte no recibe nueva oferta, se queda con el médico m ₃; la nueva asignación tentativa es:

 

En el siguiente paso, las ofertas emitidas por los médicos sin asignación son:

Ambas ofertas son mejores que las asignaciones tentativas de h ₁ y h ₄, por lo que son aceptadas y la nueva asignación tentativa es:

 

En el siguiente paso, el médico m ₃ hace una oferta al hospital h ₃, la cuál es rechazada ya que este hospital prefiere su asignación tentativa, el médico m ₄; mientras tanto, el médico m ₅ ya hizo ofertas a todos sus hospitales aceptables y todas han sido rechazadas, por lo que se quedará sin par. El nuevo emparejamiento tentativo es el mismo que el anterior:

 

En el siguiente paso el médico m ₃ hace oferta a su último hospital aceptable, h ₂. La oferta es rechazada, por lo que la asignación final producida en este mercado por el algoritmo DA es:

 

3.1.3. Existencia

Se puede observar que en el algoritmo DA, el lado del mercado que hace las ofertas (los médicos en nuestro ejemplo), las emite en el sentido decreciente de sus preferencias. Por construcción del algoritmo, los médicos no repiten una oferta a un mismo hospital. Además, no hacen ofertas a hospitales que no sean aceptables, por lo que la condición de racionalidad individual se cumple para este lado del mercado. Considerando el lado del mercado que recibe las ofertas, se llega a la misma conclusión. Observemos que, en la primera asignación, la asignación vacía, nadie está asignado a nadie. En los siguientes pasos del algoritmo, los hospitales comparan las eventuales ofertas recibidas de parte de médicos con su actual asignación y escoge su opción preferida. Por lo tanto, a lo largo de la secuencia de asignaciones tentativas solo van mejorando en su selección o se mantienen igual; llamamos esta una propiedad de monotonicidad. Además, como la asignación inicial de la secuencia es la vacía (la cual es individualmente racional) también lo son las subsecuentes; en particular, la asignación final.

Para comprobar que el algoritmo DA genera una asignación estable, falta verificar que en la asignación final no haya ningún par bloqueador. Supongamos que no sea el caso, que existe un par compuesto por un médico m y un hospital h que se prefieren mutuamente a la asignación producida por el algoritmo DA. Como m prefiere h a su asignación final y las ofertas se hacen el sentido decreciente de las preferencias de los médicos, este le tuvo que haber hecho una oferta en un paso intermedio del algoritmo. Dado que m y h no están emparejados en la asignación final, significa que ya sea en el paso en donde se hizo la oferta o posteriormente, esta oferta fue rechazada por h. En el paso en que h rechazo a m, por construcción, fue porque tenía una oferta mejor. Por monotonicidad, h siguió mejorando o se quedó con esta opción preferida hasta el final, por lo que no puede ser que h bloqueé con m la asignación final.

Es importante recalcar que el uso del algoritmo DA no es necesario para comprobar la existencia de una asignación estable, Sotomayor (1996) propone una prueba no constructiva de la existencia, tanto cuando los agentes tienen preferencias estrictas que cuando tienen indiferencias.

Más allá de su atractivo normativo y de la existencia de una asignación en cualquier mercado, el concepto de estabilidad ha ganado fuerza dentro y fuera de la literatura académica por una regularidad documentada en Roth (1991) donde se observa que los mercados centralizados que implementan una asignación estable sobreviven, los otros desaparecen.

3.2.1. Multiplicidad de asignaciones estables

Hemos visto que en un mercado uno-a-uno siempre existe al menos una asignación estable. Sin embargo, no hemos hablado si esta asignación es única o no. En el siguiente ejemplo podremos observar que no solo puede haber múltiples asignaciones estables, sino que realmente el número de ellas puede ser grande.

El ejemplo 2 (Problema 4, p. 45 Knuth (1976) no considera un mercado laboral, sino un mercado de matrimonio formado por cuatro mujeres (a: Antoinette, b: Brigitte, c: Cunégonde, d: Donatienne) y cuatro hombres (A: Anatole, B: Branabé, C: Camille, D: Dominique) con las siguientes preferencias:

 

El lector puede comprobar que en este mercado existen diez asignaciones estables:

 

En este sentido, el criterio de estabilidad no es suficiente para apuntar a una asignación en particular. Vemos a continuación que existe un criterio para desempatar entre las asignaciones, además este criterio es compatible con el algoritmo DA.

3.2.2. Oposición de interés entre ambos lados del mercado

En el caso de múltiples asignaciones estables, podríamos preguntarnos si un lado del mercado está siendo favorecido versus el contrario. Es decir, podrían existir asignaciones donde los médicos estuviesen de acuerdo que es una mejor asignación a otra, a pesar de su estabilidad. ¿A qué lado del mercado deberíamos favorecer si hay que escoger entre más de una asignación estable? La respuesta no parece tener sentido si interpretamos el modelo de asignación como un mercado de matrimonio ¿Por qué favorecer en particular a los miembros del conjunto mujeres, o los miembros del conjunto hombres? Al contrario, en un mercado laboral donde se involucran médicos y hospitales, parece natural favorecer en la medida de lo posible a los médicos cuando se pretende mejorar sus condiciones laborales. El siguiente resultado establece que cuando usamos el algoritmo DA en donde los médicos hacen ofertas, se alcanza, en cualquier mercado, la asignación estable unánimemente preferida por los médicos y menos preferida por los hospitales. Por lo tanto, si nos restringimos asignaciones estables, la oposición de interés es entre ambos lados del mercado, no tanto entre médicos y entre hospitales. En otras palabras, quien propone bajo el algoritmo DA será el lado del mercado que mayor satisfacción tenga en la asignación estable, entre las otras posibles asignaciones estables existentes.

El argumento es el siguiente: consideramos el algoritmo DA cuando hacen ofertas los médicos y suponemos que produce una asignación estable que no es unánimemente preferida por los médicos a las demás asignaciones estables, específicamente que existe por lo menos un médico m que prefiere otra asignación estable $\mu$ . Dado que en el algoritmo los médicos hacen ofertas en el orden decreciente de sus preferencias, entonces esto significa que antes de hacer oferta al hospital de la asignación final del algoritmo DA, hizo oferta y resultó rechazado por el hospital de la asignación preferida. Sea m ₁ él o uno de los médicos a quien(es) ocurre por primera vez este rechazo, digamos por parte del hospital h ₁. Esto ocurre solo si este hospital h ₁ recibió oferta de parte de un médico m ₂ que prefiere a m ₁. Como m ₂ no es el primer médico en ser rechazado de su asignación estable preferida a la del algoritmo DA, digamos h ₂, prefiere el hospital h ₁ a h ₂; por lo tanto, m ₂ y h ₁ son un par bloqueador de esta asignación $\mu$ , la cual no es estable, en contradicción con nuestro supuesto.

Una característica del algoritmo DA es que las ofertas son emitidas de manera simultánea por todos los médicos no asignados. ¿Cómo cambiaría el resultado anterior si las ofertas se hicieran de manera secuencial? ¿Tendrá entonces un impacto sobre la asignación final el orden en que se hacen las ofertas? Revisando los argumentos presentados en la subsección 3.1.3. y en el párrafo anterior, vemos que aplican directamente a la variante del algoritmo en donde las ofertas se hacen de manera secuencial, por lo que se llegará a la misma asignación estable unánimemente preferida por el lado del mercado que hace las ofertas. Nos falta establecer cuál es la peor asignación estable para el lado del mercado que recibe las ofertas, los hospitales.

Para ello nos apoyamos sobre el Lema de descomposición el cual establece que cuando tenemos dos asignaciones estables, $\mu$ y ${\mu }^{\prime }$ , y un médico m que prefiere estrictamente su asignación en $\mu$ , digamos el hospital h, a su asignación en ${\mu }^{\prime }$ , digamos el hospital h', tanto h como h' están asignados en ambas asignaciones, además prefieren estrictamente sus respectivas asignaciones en ${\mu }^{\prime }$ a su asignación en $\mu$ . Supongamos que no fuera el caso. Sin pérdida de generalidad, suponemos que el hospital h prefiere su asignación en $\mu$ , m, a su asignación en ${\mu }^{\prime }$ ; entonces, ya que supusimos que el médico m prefiere el hospital h a h', m y h formarían un par bloqueador a la asignación ${\mu }^{\prime }$ , en contradicción con su propriedad de estabilidad.

En el ejemplo anterior, en donde vemos que la asignación estable unánimemente preferida por las mujeres y menos preferida por los hombres es

 

y la asignación estable unánimemente preferida por los hombres y menos preferida por las mujeres es

 

Existen otras asignaciones estables sobre las cuales no hay unanimidad en preferencia, por ejemplo

 

y

 

donde las mujeres a y b así como los hombres C y D prefieren la primera asignación $\mu$ . Mientras que las mujeres c y d y los hombres A y B prefieren la segunda, ${\mu }^0$ . Como se observa, no hay unanimidad entre mujeres u hombres para ordenar ambas asignaciones. Con esto, observamos una propiedad llamativa que vamos a formular utilizando médicos y hospitales. Cuando uno considera dos asignaciones estables $\mu$ y ${\mu }^{\prime }$ los siguientes conjuntos: el de los médicos que prefieren estrictamente $\mu$ a ${\mu }^{\prime }$ , M( $\mu$ ) el de los médicos que prefieren estrictamente ${\mu }^{\prime }$ a $\mu$ , M( ${\mu }^{\prime }$ ), el de los hospitales que prefieren estrictamente $\mu$ a ${\mu }^{\prime }$ , H( $\mu$ ), y el de los hospitales que prefieren estrictamente ${\mu }^{\prime }$ a $\mu$ , H( ${\mu }^{\prime }$ ), un médico en M( $\mu$ )/M( ${\mu }^{\prime }$ ) está asignado, tanto en la asignación $\mu$ como en la asignación ${\mu }^{\prime }$ , a un hospital en H( ${\mu }^{\prime }$ )/H( $\mu$ . Esta propriedad se llama el Lema de descomposición Knuth (1976). En nuestro ejemplo M( $\mu$ ) = {a,b}, M( ${\mu }^{\prime }$ ) = {c,d}, H( ${\mu }^{\prime }$ )={A,B} y H( $\mu$ ) = {C,D}. El argumento para establecer el Lema es el siguiente: consideramos un médico que pertenezca al conjunto M( $\mu$ ), tratándose de preferencias estrictas, está asignado a un hospital en $\mu$ , digamos con el hospital h; por estabilidad de la otra asignación, ${\mu }^{\prime }$ , no puede ser que el hospital h prefiera el médico m a su asignación en ${\mu }^{\prime }$ , por lo que el hospital h pertenece a H( ${\mu }^{\prime }$ )={A,B}. Se puede repetir el argumento para cualquier médico en M( $\mu$ ); por lo tanto, la cardinalidad del conjunto H( ${\mu }^{\prime }$ ) es mayor o igual a la cardinalidad del conjunto M( $\mu$ ). Simétricamente podemos establecer que en la asignación ${\mu }^{\prime }$ a un médico m' que prefiere estrictamente su asignación en $\mu$ al hospital h, y que la cardinalidad del conjunto H( ${\mu }^{\prime }$ ) es menor o igual a la cardinalidad del conjunto M( $\mu$ ). Por lo tanto, ambos conjuntos tienen la misma cardinalidad, siendo la asignación uno-a-uno, por lo que los agentes están asignados tanto en $\mu$ como en ${\mu }^{\prime }$ con agentes en M( $\mu$ ) y H( ${\mu }^{\prime }$ ) respectivamente.

3.2.3. El teorema de los hospitales rurales

Vimos en el mercado del Ejemplo 1 que el algoritmo DA produce una asignación estable en donde dos médicos, m ₃ y m ₅, se quedaban sin hospital. Esto puede pasar tanto porque hay un desbalance entre el número de plazas abiertas y el número de médicos postulados a cada una de ellas, o porque el currículo de algunos médicos no es atractivo para los hospitales. También puede pasar que algunos hospitales no sean atractivos para los médicos, en particular si están ubicados en una ciudad en donde es difícil que su pareja encuentre trabajo. ¿Cómo es posible que los médicos estén de acuerdo para escoger su asignación favorita, cuando algunos quedan sin asignar en la mejor asignación estable para los médicos? Esto implica que si un médico queda sin hospital en la asignación producida por el algoritmo DA, queda sin asignar en cualquier asignación estable. Este es un caso particular del llamado “Teorema de hospitales rurales” que postula que, si un agente queda no asignado en una asignación estable, lo será en cualquier asignación estable. Sino fuera el caso, estos agentes preferirían estrictamente la asignación en la cual están asignados a algún hospital a la en donde quedan sin asignar. Sin embargo, el Lema de Descomposición nos dice que, si un agente prefiere una asignación a otra, está asignado en ambas, en contradicción con nuestro supuesto.

3.5.1. El problema de la elección escolar

Si bien estamos analizando el mercado de asignación entre hospitales y médicos, en esta sección cambiaremos de ejemplo al emparejamiento escolar para ser consistentes con la literatura y sus ejemplos. Abdulkaderoglu y Sönmez (2003) introducen el problema de la elección escolar: los estudiantes de una misma circunscripción pueden escoger en qué escuela inscribirse. Sin embargo, el cupo de cada escuela hace que no todos podrán conseguir su primera elección, por lo que las escuelas admiten los alumnos con base en el resultado de un conjunto de criterios definidos por la ley local, el cual define el orden de prelación de los alumnos (proximidad a la escuela, en particular la admisión de hermanas/os en esta escuela, desempeño escolar, resultado de un examen, sorteo en caso de empate). Con ello, se permite implementar el siguiente principio: una asignación de alumnos a escuelas es justa si, cuando un alumno no es aceptado en una escuela, todos los alumnos aceptados tienen mejor calificación que el alumno rechazado. Por lo tanto, los alumnos aceptados tienen prioridad en el orden de prelación de la escuela y, así, una asignación justa no enfrenta reclamo justificado.

Una clase es un subconjunto de alumnos, por lo que se podría volver a considerar preferencias sustituibles para ordenar las posibles cohortes de alumnos, incorporando a la definición la cuota de alumnos que corresponde a cada escuela. Sin embargo, no sería un procedimiento adecuado por dos motivos: en primer lugar, las escuelas desconocen a los alumnos, por lo que no les es posible considerar si serán complementos o sustitutos; en segundo lugar, porque el concepto de justicia presentado en el párrafo anterior pide que el orden de los subconjuntos de agentes responda al orden individual proveniente ordenes de prioridad. Llamamos este tipo de órdenes “responsivas”: los órdenes de las escuelas son responsivas si todos los alumnos son admisibles para las escuelas y sumar un alumno admisible mejora el subconjunto. Es la propriedad de racionalidad individual, además cuando una escuela considera sumar el alumno a ₁ o el alumno a ₂ a cualquier subconjunto, tiene mayor prioridad este mismo subconjunto aumentado de a ₁ al subconjunto aumentado de a ₂ si y solo si el alumno a ₁ hizo un mejor examen de admisión que el alumno a ₂.

El concepto surgió en el contexto de preferencias. Vemos un ejemplo de preferencias que son sustituibles, pero no responsivas.

Ejemplo 5. Consideremos un mercado con tres médicos, m ₁ y m ₂, y m ₃ y dos hospitales h ₁ y h ₂, con las siguientes preferencias,

 

Las preferencias del hospital h ₁ son sustituibles, mas no responsivas al considerar al médico m ₁ y la posibilidad de añadir al médico m ₂ o al médico m ₃, el hospital opta por el médico individualmente peor evaluado, m ₂. Otra violación de la definición de responsividad es que al sumar al subconjunto {m ₁,m ₂} el médico admisible m ₃, el subconjunto no mejora sino que se vuelve no admisible. Las preferencias del hospital h ₂ son responsivas, así como sustituibles.

El lector interesado en ahondar en la Teoría del emparejamiento puede comprobar que el conjunto de preferencias responsivas es contenido en el subconjunto sustituibles, y que los resultados establecidos en el modelo uno-a-uno se extienden en el modelo varios-a-uno cuando las preferencias de los hospitales son responsivas.

Formalmente, el problema de la elección escolar parece idéntico al problema de emparejamiento hospitalario, solo cambiamos la nomenclatura: lo que llamamos preferencias para los hospitales ahora se llama orden de prelación y una asignación estable ahora se llama asignación justa. De hecho, podemos adaptar los argumentos anteriores para comprobar que en el problema de la elección estudiantil siempre existe una asignación justa. La interpretación de un orden de relación en términos de bienestar, sin embargo, contrasta el análisis que llevamos a cabo en la siguiente sección.

3.5.2. Eficiencia en el sentido de Pareto

En el análisis de bienestar se toma en cuenta las preferencias de los agentes, no los órdenes de prelación por considerar que las escuelas son objetos. Esta diferencia, sutil a primera vista, cambia la perspectiva sobre el mercado. La primera consecuencia es que se desvanece la oposición de interés establecida en el modelo del matrimonio, por lo tanto, en el modelo de la asignación estudiantil existe una asignación focal, la asignación justa unánimemente preferida por los estudiantes.

Vemos ahora que puede existir otra asignación igualmente atractiva. Para ello, recordamos el criterio de eficiencia en el sentido de Pareto que establece que una asignación $\mu$ es eficiente en el sentido de Pareto si y solo si no existe otra asignación ${\mu }^{\prime }$ preferida o indiferente para todos los agentes, y estrictamente preferida por lo menos por un agente. Vemos en el siguiente ejemplo que una asignación justa puede no ser Pareto eficiente, y viceversa.

Ejemplo 6: Consideremos un mercado con tres alumnos, a ₁ y a ₂, y a ₃ y tres escuelas e ₁, e ₂ y e ₃, con las siguientes preferencias y prioridades,

 

La asignación justa preferida de los alumnos es

 

Esta asignación es dominada en el sentido de Pareto por la asignación

 

la cual es estrictamente preferida por los alumnos a ₁ y a ₂, cuando ambas asignaciones son indiferentes para el alumno a ₃.

¿Conviene escoger la mejor asignación estable para los alumnos o escoger la asignación eficiente en el sentido de Pareto?

Con este resultado concluimos con el repaso de la literatura de los mercados bilaterales à la Gale y Shapley (1962).

5.2. Nuevas perspectivas sobre el dilema entre Justicia y eficiencia de Pareto

Abdulkaderoğlu y Sönmez (2003) plantean el problema de la elección escolar como una disyuntiva entre los axiomas de justicias y de Eficiencia de Pareto. Ante ello, adaptan un algoritmo a este problema que se denomina mecanismo de Ciclos de Intercambios Optimales (C.I.P.), Top Trading Cycle, el cual siempre produce una asignación estable. Este mecanismo no es manipulable, de modo que resulta una elección ventajosa para quienes optan por la noción de eficiencia por encima de la justicia.

Dos trabajos, en particular, dan una relectura al problema. En primer lugar, Kesten (2010) demuestra que, cuando uno considera la secuencia de asignaciones generadas por el D.A. en donde hacen oferta los alumnos y la asignación generada es justa, sin embargo no es Pareto eficiente, entonces existen algunos alumnos, llamados interruptores, que podrían consentir a omitir su prioridad sobre algunas escuelas ya que no representa ningún beneficio para ellos- no son alcanzables en la asignación estable- sin embargo impiden llegar a una asignación Pareto eficiente. Además, propone el mecanismo preciso para llevar a cabo este procedimiento, el llamado efficiency-adjusted DA mechanism (EADAM).

El EADAM permite la existencia de envidia justificada, sin embargo, consentida. Así, se aleja del axioma de justicia para conseguir una asignación Pareto eficiente. Kesten (2010, sin embargo, no propone un concepto de justicia, menos exigente que el original, que cumpla la asignación producida por el EADAM. Esta proeza se consigue en Troyan et al. (2020), donde los autores llaman esta propiedad estabilidad esencial (essential fairness). Por lo que ambas publicaciones hacen del EADAM un mecanismo central de la teoría de emparejamiento.