3.1.1. Un criterio normativo: a estabilidade

Asúmese que, ao revelar as preferencias a un mecanismo, tanto médicos como hospitais desexarían que a asignación cumprise dous requisitos: 1) que non estean asignados a un hospital/médico que non consideren aceptable (isto é, que prefiran non ter nada antes que esa asignación); e 2) que non exista un par conformado por un médico e un hospital que se prefiran mutuamente ao hospital e ao médico que lles foi asignado polo mecanismo. No primeiro caso, este requisito é chamado “racionalidade individual”, e no segundo dise que non hai un “par bloqueador”. Unha asignación que cumpra ambos os criterios é chamada estable.

Exemplo 1. Consideremos un mercado composto por seis médicos (m ₁, m ₂, m ₃, m ₄, m ₅ e m ₆) e catro hospitais (h ₁, h ₂, h ₃ e h ₄) no que cada hospital desexa contratar só un médico. As preferencias de cada axente son as seguintes:

 

Unha posible asignación é:

 

Neste caso, hai que notar que a asignación non é estable por violar ambas as condicións: ao médico m ₃ asignóuselle o hospital h ₄ aínda que este hospital non é aceptable para o médico, polo que se está violando a condición de racionalidade individual. Ademais diso, o hospital h ₁ está asignado ao médico m ₁ cando prefire o médico m ₃ e, de maneira recíproca, o médico m ₃ prefire o hospital h ₁ ao hospital que lle foi asignado, h ₄; polo tanto, (m ₃, h ₁) forman un par bloqueador á asignación.

O concepto de solución proposto por Gale e Shapley (1962), por tanto, non é doado de cumprir. Con todo, a boa noticia que os autores nos dan, no primeiro resultado fundamental que proban, é a existencia dunha asignación estable en calquera mercado “un-a-un”. O argumento para comprobar a existencia dunha asignación con estas características é construtivo. Para iso, os autores formalizan o algoritmo de “Aceptación Diferida” (DA polas súas siglas en inglés), o cal sempre produce unha asignación estable.

3.1.2. O algoritmo DA

Nesta sección presentaremos o algoritmo e a súa correspondente corrida no mercado de emparellamento co exemplo anterior.

No outro lado do mercado, os hospitais consideran as ofertas recibidas e quedan coa súa oferta favorita. O hospital h ₁ recibiu ofertas dos médicos m ₁ e m ₃, escolle m ₃; o hospital h ₂ só recibiu oferta do médico m ₂ e, como é aceptable, queda con el; o hospital h ₃ recibe ofertas dos médicos m ₅ e m ₆, ambos son aceptables pero m ₆ é o seu preferido, polo que tentativamente queda con m₆; o hospital h ₄ recibe unha oferta do médico m₄ pero, ao non ser unha opción aceptable, rexeita a oferta. Por tanto, a segunda asignación tentativa é

 

Paso xenérico: en cada iteración os médicos non asignados fanlles ofertas, no sentido decrecente das súas preferencias, aos hospitais a quen nunca llas fixeran; os hospitais comparan a súa asignación tentativa coas novas ofertas recibidas e asígnanse coa súa mellor opción.

As roldas son iterativas ata que xa non haxa médicos non asignados nin ofertas que facer por parte destes médicos, nin máis médicos a quen rexeitar ou aceptar. Deste xeito, vaise creando unha secuencia de asignacións tentativas onde, en cada paso, os médicos non asignados lle fan ofertas ao mellor hospital dentro daqueles aos que aínda non lles fixeran unha oferta, e os hospitais escollen a súa mellor opción entre a asignación tentativa anterior e as ofertas recibidas. Por tanto, o proceso termina cando todos os médicos están asignados ou cando os médicos sen asignar xa lles fixesen ofertas a todos os seus hospitais aceptables.

Continuando con estes principios, no seguinte paso os médicos non asignados m ₁, m ₄ e m ₅ emiten as seguintes ofertas:

O hospital h ₂ está asignado ao médico m ₂, con todo, prefire a oferta do médico m ₁, coa que queda; o hospital h ₃ tamén prefire a súa nova opción, o médico m ₄, á súa asignación tentativa, o médico m ₆; o hospital h ₄ por fin recibe unha oferta aceptable, a do médico m ₅, coa que queda; o hospital h ₁, pola súa banda, non recibe nova oferta, e queda co médico m ₃; a nova asignación tentativa é:

 

No seguinte paso, as ofertas emitidas polos médicos sen asignación son:

Ambas as ofertas son mellores que as asignacións tentativas de h ₁ e h ₄, polo que son aceptadas e a nova asignación tentativa é:

 

No seguinte paso, o médico m ₃ faille unha oferta ao hospital h ₃, a cal é rexeitada xa que este hospital prefire a súa asignación tentativa, o médico m ₄; mentres tanto, o médico m ₅ xa lles fixo ofertas a todos os seus hospitais aceptables e todas foron rexeitadas, polo que quedará sen par. O novo emparellamento tentativo é o mesmo que o anterior:

 

No seguinte paso, o médico m₃ faille unha oferta ao seu último hospital aceptable, h ₂. A oferta é rexeitada, polo que a asignación final producida neste mercado polo algoritmo DA é:

 

3.1.3. Existencia

Pódese observar que no algoritmo DA o lado do mercado que fai as ofertas (os médicos, no noso exemplo) emíteas no sentido decrecente das súas preferencias. Por construción do algoritmo, os médicos nunca repiten unha oferta a un mesmo hospital. Ademais, non fan ofertas a hospitais que non sexan aceptables, polo que a condición de racionalidade individual se cumpre para este lado do mercado. Considerando o lado do mercado que recibe as ofertas, chégase á mesma conclusión. Observemos que, na primeira asignación, a asignación baleira, ninguén está asignado a ninguén. Nos seguintes pasos do algoritmo, os hospitais comparan as eventuais ofertas recibidas de médicos coa súa actual asignación e escollen a súa opción preferida. Por tanto, ao longo da secuencia de asignacións tentativas ou van mellorando na súa selección ou mantéñense igual; chamámoslle a esta unha propiedade de monotonicidade. Ademais, como a asignación inicial da secuencia é a baleira (a cal é individualmente racional) tamén o son as subsecuentes; en particular, a asignación final.

Para comprobar que o algoritmo DA xera unha asignación estable, falta verificar que na asignación final non haxa ningún par bloqueador. Supoñamos que non é o caso, que existe un par composto por un médico m e un hospital h que se prefiren mutuamente á asignación producida polo algoritmo DA. Como m prefire h á súa asignación final, e as ofertas fanse no sentido decrecente das preferencias dos médicos, este tívolle que facer unha oferta nun paso intermedio do algoritmo. Dado que m e h non están emparellados na asignación final, significa que, xa sexa no paso onde se fixo a oferta ou posteriormente, esta oferta foi rexeitada por h. No paso en que h rexeitou a m, por construción do algoritmo tivo que ser porque tiña unha oferta mellor. Por monotonicidade, h seguiu mellorando ou quedou con esta opción preferida ata o final, polo que non pode ser que h bloquee con m a asignación final.

É importante recalcar que o uso do algoritmo DA non é necesario para comprobar a existencia dunha asignación estable. Sotomayor (1996) propón unha proba non construtiva da súa existencia tanto para cando os axentes teñen preferencias estritas como para cando teñen indiferenzas.

Máis aló do seu atractivo normativo e da existencia dunha asignación en calquera mercado, o concepto de estabilidade gañou forza dentro e fóra da literatura académica por unha regularidade documentada en Roth (1991), onde se observa que os mercados centralizados que aplican unha asignación estable sobreviven, mentres que os outros desaparecen.

3.2.1. Multiplicidade de asignacións estables

Vimos que nun mercado un-a-un sempre existe polo menos unha asignación estable. Con todo, non falamos se esta asignación é única ou non. No seguinte exemplo poderemos observar que non só pode haber múltiples asignacións estables, senón que realmente o número delas pode ser grande.

O exemplo 2 [Problema 4, p. 45 Knuth (1976)] non considera un mercado laboral, senón un mercado de matrimonio formado por catro mulleres (a: Antoinette, b: Brigitte, c: Cunégonde, d: Donatienne) e catro homes (A: Anatole, B: Branabé, C: Camille, D: Dominique) coas seguintes preferencias:

 

O lector pode comprobar que neste mercado existen dez asignacións estables:

 

Neste sentido, o criterio de estabilidade non é suficiente para apuntar unha asignación en particular. Vemos a continuación que existe un criterio para desempatar entre as asignacións e, ademais, este criterio é compatible co algoritmo DA.

3.2.2. Oposición de interese entrambos os lados do mercado

No caso de múltiples asignacións estables, poderiamos preguntarnos se un lado do mercado está a ser favorecido fronte ao contrario. É dicir, poderían existir asignacións onde os médicos estivesen de acordo en que unha asignación é mellor a outra, a pesar da súa estabilidade. A que lado do mercado deberiamos favorecer se hai que escoller entre máis dunha asignación estable? A resposta non parece ter sentido se interpretamos o modelo de asignación como un mercado de matrimonio. Por que favorecer en particular os membros do conxunto das mulleres, ou ben os membros do conxunto dos homes? Ao contrario, nun mercado laboral onde se involucran médicos e hospitais, parece natural favorecer na medida do posible os médicos, cando se pretende mellorar as súas condicións laborais. O seguinte resultado establece que cando usamos o algoritmo DA onde os médicos fan ofertas, alcánzase, en calquera mercado, a asignación estable unanimemente preferida polos médicos e a menos preferida polos hospitais. Por tanto, se nos restrinximos a asignacións estables, a oposición de interese é entrambos os lados do mercado, e non tanto entre médicos e entre hospitais. Noutras palabras, quen propón, baixo o algoritmo DA, será o lado do mercado que maior satisfacción teña na asignación estable entre as outras posibles asignacións estables existentes.

O argumento é o seguinte: consideramos o algoritmo DA cando fan ofertas os médicos, e supomos que produce unha asignación estable que non é unanimemente preferida por estes fronte ás demais asignacións estables; especificamente supoñemos que existe polo menos un médico m que prefire outra asignación estable $\mu$ . Dado que no algoritmo os médicos fan ofertas na orde decrecente das súas preferencias, entón isto significa que, antes de facerlle oferta ao hospital da asignación final do algoritmo DA, tivo que presentarlle oferta e ser rexeitado polo hospital da asignación preferida. Isto será así tanto se m ₁ é o médico que chamamos m como se é calquera dos médicos a quen lle ocorra por primeira vez este rexeitamento por parte do hospital, poñamos por caso, h ₁. Isto terá lugar só se este hospital h ₁ recibiu oferta de parte dun médico m ₂ e que o preferiu a m ₁. Como m ₂ non é o primeiro médico en ser rexeitado da súa asignación estable preferida á do algoritmo DA, digamos h ₂, preferirá o hospital h ₁ ao h ₂; por tanto, m ₂ e h₁ son un par bloqueador desta asignación $\mu$ , a cal non é estable, en contradición co noso suposto.

Unha característica do algoritmo DA é que as ofertas son emitidas de maneira simultánea por todos os médicos non asignados. Como cambiaría o resultado anterior se a ofertas se fixesen de maneira secuencial? Tería, entón, un impacto sobre a asignación final a orde en que se fan as ofertas? Revisando os argumentos presentados na subsección 3.1.3. e no parágrafo anterior, vemos que estes se aplican directamente á variante do algoritmo onde as ofertas se fan de maneira secuencial, polo que se chegará á mesma asignación estable unanimemente preferida polo lado do mercado que fai as ofertas. Fáltanos establecer cal é a peor asignación estable para o lado do mercado que recibe as ofertas, os hospitais.

Para iso, apoiámonos no Lema de descomposición, o cal establece que cando temos dúas asignacións estables, $\mu$ e ${\mu }^{\prime }$ , e mais un médico m que prefire estritamente a súa asignación en $\mu$ , digamos o hospital h, á súa asignación en ${\mu }^{\prime }$ , digamos o hospital h', tanto h como h' estarán adxudicados en ambas as asignacións. Ademais, confírmase que prefiren estritamente as súas respectivas asignacións en ${\mu }^{\prime }$ ás súas asignacións en $\mu$ . Supoñamos agora que non fose o caso. Sen perda de xeneralidade, consideramos que o hospital h prefire a súa asignación en $\mu$ , m, á súa asignación en ${\mu }^{\prime }$ ; entón, xa que supuxemos que o médico m prefire o hospital h a h', m e h formarían un par bloqueador á asignación ${\mu }^{\prime }$ , en contradición coa súa propiedade de estabilidade.

No exemplo anterior, vemos que a asignación estable unanimemente preferida polas mulleres e menos preferida polos homes é.

 

e a asignación estable unanimemente preferida polos homes e menos preferida polas mulleres é:

 

Existen outras asignacións estables sobre as que non hai unanimidade na preferencia, por exemplo:

 

e

 

onde as mulleres a e b, así como os homes C e D, prefiren a primeira asignación $\mu$ ; mentres que as mulleres c e d e os homes A e B prefiren a segunda, ${\mu }^0$ . Como se observa, non hai unanimidade entre mulleres ou homes á hora de ordenar ambas as asignacións. Con isto, detectamos unha propiedade rechamante que imos formular utilizando médicos e hospitais. Cando un considera dúas asignacións estables, $\mu$ e ${\mu }^{\prime }$ , obtemos os seguintes conxuntos: o dos médicos que prefiren estritamente $\mu$ a ${\mu }^{\prime }$ , M( $\mu$ ); o dos médicos que prefiren estritamente ${\mu }^{\prime }$ a $\mu$ , M( ${\mu }^{\prime }$ ); o dos hospitais que prefiren estritamente $\mu$ a ${\mu }^{\prime }$ , H( $\mu$ ); e o dos hospitais que prefiren estritamente ${\mu }^{\prime }$ a $\mu$ , H( ${\mu }^{\prime }$ ). Un médico en M( $\mu$ )/M( ${\mu }^{\prime }$ ) estará inscrito, tanto na asignación $\mu$ como na ${\mu }^{\prime }$ , a un hospital en H( ${\mu }^{\prime }$ )/H( $\mu$ ). Esta propiedade chámase o Lema de descomposición (Knuth (1976)). No noso exemplo, M( $\mu$ ) = {a,b}, M( ${\mu }^{\prime }$ ) = {c,d}, H( ${\mu }^{\prime }$ )={A,B} e H( $\mu$ ) = {C,D}. O argumento para establecer o Lema é o seguinte: consideramos un médico que pertenza ao conxunto M( $\mu$ ); tratándose de preferencias estritas, estará asignado a un hospital en $\mu$ , digamos ao hospital h. Debido á estabilidade da outra asignación, ${\mu }^{\prime }$ , non pode ser que o hospital h prefira o médico m á súa asignación en ${\mu }^{\prime }$ , polo que o hospital h debe pertencer a H( ${\mu }^{\prime }$ )={A,B}. Pódese repetir o argumento para calquera médico en M( $\mu$ ). Polo tanto, a cardinalidade do conxunto H( ${\mu }^{\prime }$ ) é maior ou igual á cardinalidade do conxunto M( $\mu$ ). Simetricamente, podemos establecer que na asignación ${\mu }^{\prime }$ a un médico m', que prefire estritamente a súa asignación en $\mu$ ao hospital h, a cardinalidade do conxunto H( ${\mu }^{\prime }$ ) é menor ou igual á cardinalidade do conxunto M( $\mu$ ). Xa que logo, ambos os conxuntos teñen a mesma cardinalidade, sendo a asignación un-a-un, polo que os axentes están asignados tanto en $\mu$ como en ${\mu }^{\prime }$ con axentes en M( $\mu$ ) e en H( ${\mu }^{\prime }$ ) respectivamente.

3.2.3. O teorema dos hospitais rurais

Vimos no mercado do exemplo 1 que o algoritmo DA producía unha asignación estable onde dous médicos, m ₃ e m ₅, quedaban sen hospital. Isto pode pasar tanto porque hai un desaxuste entre o número de prazas abertas e o número de médicos postulados para cada unha delas, ou porque o currículo dalgúns médicos non é atractivo para os hospitais. Tamén pode pasar que algúns hospitais non sexan atractivos para os médicos, en particular se están situados nunha cidade onde é difícil que a súa parella atope traballo. Como é posible que os médicos estean de acordo para escoller a súa asignación favorita, cando algúns quedan sen asignar na súa mellor asignación estable? Isto implica que se un médico queda sen hospital na asignación producida polo algoritmo DA, queda sen asignar en calquera asignación estable. Este é un caso particular do chamado “teorema dos hospitais rurais”, que postula que se un axente queda non asignado nunha asignación estable, tampouco o será en calquera outra asignación estable. Se non fose o caso, estes axentes preferirían estritamente a asignación na cal estivesen asignados a algún hospital a aquelas onde quedasen sen asignar. Con todo, o Lema de descomposición dinos que se un axente prefire unha asignación a outra, deberá estar asignado en ambas, en contradición co noso suposto.

3.5.1. O problema da elección escolar

Aínda que estamos a analizar o mercado de asignación entre hospitais e médicos, nesta sección cambiaremos de exemplo ao emparellamento escolar para ser consistentes coa literatura e cos seus exemplos. Abdulkaderoglu e Sönmez (2003) introducen o problema da elección escolar: os estudantes dunha mesma circunscrición poden escoller en que escola inscribirse. Non obstante, a cota de cada escola fai que non todos poidan conseguir a súa primeira elección, polo que as escolas admiten os alumnos con base no resultado dun conxunto de criterios definidos pola lei local (proximidade á escola, a admisión de irmáns/ás nela, desempeño escolar, resultado dun exame, sorteo en caso de empate), o cal define a orde de prelación dos alumnos. Con isto, pódese aplicar o seguinte principio: unha asignación de alumnos a escolas é xusta se cando un alumno non é aceptado nunha escola, todos os alumnos aceptados teñen mellor cualificación que o alumno rexeitado. Polo tanto, os alumnos aceptados teñen prioridade na orde de prelación da escola e, así, unha asignación xusta non comportará unha reclamación xustificada.

Unha clase é un subconxunto de alumnos, polo que se podería volver considerar preferencias substituíbles para ordenar as posibles cohortes de alumnos, incorporando á definición a cota de alumnos que corresponde a cada escola. Con todo, non sería un procedemento adecuado por dous motivos: en primeiro lugar, as escolas non coñecen os alumnos, polo que non lles é posible considerar se serán complementos ou substitutos; en segundo lugar, porque o concepto de xustiza presentado no parágrafo anterior pide que a orde dos subconxuntos de axentes responda á orde individual proveniente das ordes de prioridade. Chamámoslle a este tipo de ordes “responsivas”: as ordes das escolas son responsivas se todos os alumnos son admisibles para as escolas e a acción de sumar un alumno admisible mellora o subconxunto. É a propiedade de racionalidade individual. Ademais, cando unha escola considera sumar o alumno a ₁ ou o alumno a ₂ a calquera subconxunto, terá maior prioridade este mesmo subconxunto aumentado de a ₁ sobre o subconxunto aumentado de a ₂ só se o alumno a ₁ fixo un mellor exame de admisión que o alumno a ₂.

O concepto xurdiu no contexto de preferencias. Vemos un exemplo de preferencias que son substituíbles pero non responsivas.

Exemplo 5. Consideremos un mercado con tres médicos, m ₁ e m ₂, e m ₃, e dous hospitais, h ₁ e h ₂, coas seguintes preferencias:

 

As preferencias do hospital h ₁ son substituíbles mais non responsivas, cando ao considerar o médico m ₁ e a posibilidade de engadir o médico m ₂ ou o médico m ₃, o hospital opta polo médico individualmente peor avaliado, m ₂. Outra violación da definición de responsividade é que ao sumarlle ao subconxunto {m ₁, m ₂} o médico admisible m ₃, o subconxunto non mellora senón que se volve non admisible. As preferencias do hospital h ₂ son responsivas, así como substituíbles.

O lector interesado en profundar na teoría do emparellamento pode comprobar que o conxunto de preferencias responsivas está contido no subconxunto de substituíbles, e que os resultados establecidos no modelo un-a-un se estenden no modelo varios-a-un cando as preferencias dos hospitais son responsivas.

Formalmente, o problema da elección escolar parece idéntico ao problema do emparellamento hospitalario; só cambiamos a nomenclatura: o que chamamos preferencias para os hospitais, agora chámase orde de prelación; e unha asignación estable, agora chámase asignación xusta. De feito, podemos adaptar os argumentos anteriores para comprobar que no problema da elección estudantil sempre existe unha asignación xusta. Non obstante, a interpretación dunha orde de relación en termos de benestar contrasta coa análise que levamos a cabo na seguinte sección.

3.5.2. Eficiencia no sentido de Pareto

Na análise de benestar tómanse en conta as preferencias dos axentes, e non as ordes de prelación, por considerar que as escolas son obxectos. Esta diferenza, sutil a primeira vista, cambia a perspectiva sobre o mercado. A primeira consecuencia é que se desvanece a oposición de interese establecida no modelo do matrimonio. Por tanto, no modelo da asignación estudantil existe unha asignación focal, a asignación xusta unanimemente preferida polos estudantes.

Vemos agora que pode existir outra asignación igualmente atractiva. Para iso, lembramos o criterio de eficiencia no sentido de Pareto, que establece que unha asignación $\mu$ é eficiente, no sentido de Pareto, só se non existe outra asignación ${\mu }^{\prime }$ preferida ou indiferente para todos os axentes, e estritamente preferida cando menos por un axente. Vemos no seguinte exemplo que unha asignación xusta pode non ser Pareto eficiente, e viceversa.

Exemplo 6: Consideremos un mercado con tres alumnos, a ₁ e a ₂, e a ₃, e tres escolas, e ₁, e ₂ e e ₃, coas seguintes preferencias e prioridades:

 

A asignación xusta preferida polos alumnos é

 

Esta asignación é dominada no sentido de Pareto pola asignación

 

a cal é estritamente preferida polos alumnos a ₁ e a ₂, cando ambas as asignacións son indiferentes para o alumno a ₃.

Convén escoller a mellor asignación estable para os alumnos, ou ben escoller a asignación eficiente no sentido de Pareto?

Con este resultado concluímos co repaso da literatura dos mercados bilaterais conforme Gale e Shapley (1962).