Algoritme de Gale-Shapley

En matemàtiques, economia i informàtica, el algoritme de Gale-Shapley (també conegut com a algoritme d'acceptació diferida, algoritme de proposta i rebuig, o algoritme Boston Pool) és un algoritme per a trobar una solució al problema de emparejamiento estable. Deu el seu nom a David Gale i Lloyd Shapley, que ho varen publicar en 1962, encara que ya s'utilisava en el Programa Nacional de Emparejamiento de Residents des de principis de la década de 1950. Shapley i Alvin E. Roth (que va senyalar la seua aplicació anterior) varen guanyar el Premi Nobel d'Economia de 2012 per un treball que incloïa este algoritme.

El problema de emparejamiento estable busca emparellar números iguals de participants de dos tipos, utilisant les preferències de cada participant. El emparejamiento deu ser estable: cap parella de participants no emparellats deu preferir-se mútuament a la seua parella assignada. En cada ronda de l'algoritme de Gale-Shapley, els participants no emparellats d'un tipo proponen un emparejamiento al següent participant de la seua llista de preferències. Cada proposta s'accepta si el seu destinatari la preferix a la seua parella actual. El procediment resultant és un mecanisme veraç des del punt de vista dels participants proponentes, que reben el seu emparejamiento més preferit en consonancia con l'estabilitat. En canvi, els destinataris de les propostes reben la seua emparejamiento menys preferit. L'algoritme pot eixecutar-se en un temps quadràtic del número de participants i llineal del tamany de l'entrada de l'algoritme.

El problema del emparejamiento estable, i l'algoritme de Gale-Shapley que ho resol, tenen àmplies aplicacions en el món real, com emparellar estudiants de medicina nortamericanes en residències i aspirants universitaris francesos en escoles. Per a més informació, vore Problema del matrimoni estable § Aplicacions.

Antecedents

Artícul principal → Problema del matrimoni estable.

El problema de emparejamiento estable, en la seua forma més bàsica, pren com entrada números iguals de dos tipos de participants (n solicitants d'ocupació i n empleadores, per eixemple), i un orde per a cada participant que dona la seua preferència sobre a quí emparellar entre els participants de l'atre tipo. Un emparejamiento emparella a cada participant d'un tipo en un participant de l'atre tipo. Un emparejamiento no és estable si:

1. Hi ha un element A del primer conjunt emparellat que preferix algun element B donat del segon conjunt emparellat sobre l'element en el que A ya està emparellat, i
2. B també preferix A a l'element en el que ya coincidix B.

En atres paraules, un emparejamiento és estable quan no existix un parell (A, B) en el que abdós participants es preferixquen mútuament als seus companyers emparellats. Si existix tal parella, el emparejamiento no és estable, en el sentit de que els membres d'esta parella preferirien abandonar el sistema i emparellar-se entre sí, deixant possiblement a atres participants sense emparellar. Sempre existix un emparejamiento estable, i el problema algorítmic que resol l'algoritme de Gale-Shapley és trobar-ho.

El problema del emparejamiento estable també s'ha denominat problema del matrimoni estable, utilisant una metàfora del matrimoni entre hòmens i dònes, i moltes fonts descriuen l'algoritme de Gale-Shapley en térmens de propostes de matrimoni. No obstant, esta metàfora ha segut criticada per sexiste i poc realiste: els passos de l'algoritme no reflectixen en exactitut el comportament humà típic o inclús estereotipat.

Solució

Archiu:Gale-Shapley.gif

Animació que mostra un eixemple de l'algoritme de Gale-Shapley

En 1962, David Gale i Lloyd Shapley varen demostrar que, per a qualsevol número igual de participants de cada tipo, sempre és possible trobar un emparejamiento en el que totes les parelles siguen estables. En 1984, Alvin E. Roth va observar que, en essència, el mateix algoritme ya s'utilisava en la pràctica des de principis de la década de 1950, com el «algoritme Boston Pool» utilisat pel Programa Nacional de Emparejamiento de Residents.

L'algoritme de Gale-Shapley implica una série de «rondes» (o «iteraciones»). En térmens de solicitants d'ocupació i empleadores, pot expressar-se del següent modo:

• En cada ronda, un o varis empleadores en llocs vacants fan una oferta de treball al candidat que preferixquen, d'entre els que encara no hagen fet una oferta.
• Cada candidat que ha rebut una oferta l'evalua en relació en el seu lloc actual (si ho té). Si el candidat encara no està amprat, o si rep una oferta d'un empleador que li agrada més que el seu empleador actual, accepta la millor oferta nova i queda emparellat en el nou empleador (possiblement deixant a un empleador anterior en un lloc vacant). En cas contrari, rebugen la nova oferta.
• Este procés es repetix fins que totes les empreses cobrixen les seues vacants o agoten les seues llistes de candidats.

Detalls de l'aplicació i anàlisis temporal

Per a aplicar l'algoritme de forma eficaç, cada empleador deu ser capaç de trobar ràpidament al seu següent candidat, i cada candidat deu ser capaç de comparar ràpidament els empleadores. Una forma de fer-ho és numerar a cada candidat i a cada empleador d'1 a $n$, a on $n$ és el número de empleadores i candidats, i almagasenar les següents estructures de senyes:

• Un conjunt de empleadores en llocs vacants

• Una matriu unidimensional indexada per empleadores, especificant l'índex de preferència del següent candidat al que el empleador enviaria una oferta, inicialment 1 per a cada empleador.
• Una matriu unidimensional indexada per candidats, especificant el seu empleador actual, inicialment un valor centinela com 0 indicant que estan desocupats.
• Una matriu bidimensional indexada per un candidat i un empleador, que especifica la posició d'eixe empleador en la llista de preferències del candidat.
• Una matriu bidimensional indexada per un patró i un número $i$ d'1 a $n$ nomenant al solicitant que és el empleador de cada preferència $i$ .

Configurar estes estructures de senyes requerix $O(n^2)$ temps. En estes estructures és possible trobar un empleador en un lloc sense cobrir, fer una oferta d'eixe empleador al seu següent candidat, determinar si l'oferta és acceptada i actualisar totes les estructures de senyes per a reflectir els resultats d'estos passos, en temps constant per oferta. Una volta que l'algoritme termina, la correspondència resultant es pot llegir de la matriu de empleadores per a cada candidat. Pot haver $O(n^2)$ ofertes ans que cada empleador es quede sense ofertes que fer, per lo que el temps total és de $O(n^2)$.

Encara que este llímit de temps és quadràtic en el número de participants, pot considerar-se com temps llineal quan es medix en térmens del tamany de l'entrada, dos matrius de preferències de tamany $O(n^2)$.

Garanties d'exactitut

Este algoritme garantisa que:

Tot s'emparella

Al final, no pot haver ni un candidat ni un empleador sense emparellar. Un empleador que no haja segut seleccionat al final del procés deu haver fet una oferta a tots els candidats. Pero un candidat que rep una oferta permaneix empleat durant el restant del procés, per lo que no pot haver candidats desocupats. Ya que el número de candidats i d'ofertes d'ocupació és igual, tampoc pot haver posats vacants.

El emparejamiento és estable

Cap candidat X i cap empleador I poden preferir-se mútuament a la seua parella final. Si I fa una oferta a X, llavors X només rebujaria a I despuix de rebre una oferta encara millor, per lo que X no pot preferir a I a la seua parella final. I si I deixa de fer ofertes abans d'aplegar a X en la seua llista de preferències, I no pot preferir a X a la seua parella final. En qualsevol cas, X i I no formen una parella inestable.