El algoritmo de Gale y Shapley de 1962 hizo honestos los mercados de emparejamiento

David Gale y Lloyd Shapley publicaron 'College Admissions and the Stability of Marriage' en American Mathematical Monthly en 1962. Se preguntaron si los emparejamientos estables —asignaciones en las que ningún par de agentes preferiría estar juntos— siempre existen en mercados bilaterales como el matrimonio o la admisión universitaria.

Su respuesta fue constructiva: el algoritmo de aceptación diferida, en el que una parte propone y la otra mantiene ofertas provisionales, siempre termina en un emparejamiento estable. El mismo procedimiento da a la parte proponente su mejor resultado estable posible, por lo que la ordenación veraz es la estrategia dominante para los proponentes.

Cincuenta años después, la Real Academia Sueca de Ciencias otorgó el premio de economía de 2012 a Shapley y Alvin Roth 'por la teoría de las asignaciones estables y la práctica del diseño de mercados'. Roth había demostrado que la estabilidad explica qué mercados reales sobreviven, y reconstruyó el emparejamiento de residencias, la elección de escuela y el intercambio de riñones sobre este algoritmo.

La aceptación diferida encuentra un emparejamiento estable para todos

La existencia más un algoritmo hicieron la estabilidad utilizable, no abstracta.

Las listas de preferencias veraces se convirtieron en la estrategia dominante para los proponentes.

Dio a los diseñadores una lente: los mercados estables sobreviven, los inestables colapsan.

Impulsó rediseños prácticos en medicina, educación e intercambio de órganos.

Antes de construir un mercado, comprobar que el mecanismo de emparejamiento es estable y a prueba de estrategias: si mentir reporta beneficios, el mercado se llena de manipulación. Un algoritmo que hace óptima la honestidad es diseño de mercados.

El algoritmo se convirtió en el motor del rediseño del emparejamiento de residencias de EE. UU., la elección de escuela en Boston y Nueva York, y las cadenas de intercambio de riñones —todos mencionados en la citación del Nobel. Gale-Shapley es ahora vocabulario estándar en diseño de mercados, investigación de operaciones y ciencias de la computación.