O algoritmo de Gale e Shapley de 1962 tornou os mercados de matching honestos

David Gale e Lloyd Shapley publicaram 'College Admissions and the Stability of Marriage' na American Mathematical Monthly em 1962. Eles perguntaram se emparelhamentos estáveis — atribuições nas quais nenhum par de agentes preferiria estar um com o outro — sempre existem em mercados bilaterais como casamento ou admissão universitária.

A resposta deles foi construtiva: o algoritmo de aceitação diferida, no qual um lado propõe e o outro mantém ofertas provisórias, sempre termina em um emparelhamento estável. O mesmo procedimento dá ao lado proponente seu melhor resultado estável possível, e é por isso que a ordenação verídica é a estratégia dominante para os proponentes.

Cinquenta anos depois, a Real Academia Sueca de Ciências concedeu o prêmio de economia de 2012 a Shapley e Alvin Roth 'pela teoria das alocações estáveis e pela prática do desenho de mercados'. Roth havia mostrado que a estabilidade explica quais mercados reais sobrevivem, e reconstruiu o matching de residência médica, a escolha de escolas e a troca de rins com base nesse algoritmo.

A aceitação diferida encontra um emparelhamento estável para todos

A existência somada a um algoritmo tornou a estabilidade utilizável, não abstrata.

Listas de preferências verídicas tornaram-se a estratégia dominante para os proponentes.

Deu aos designers uma lente: mercados estáveis sobrevivem, instáveis colapsam.

Impulsionou reformulações práticas na medicina, na educação e na troca de órgãos.

Antes de construir um mercado, verifique se o mecanismo de matching é estável e à prova de estratégia: se a declaração falsa compensa, o mercado se enche de manipulação. Um algoritmo que torna a honestidade ótima é desenho de mercado.

O algoritmo tornou-se o motor da reformulação do matching de residência médica nos EUA, da escolha de escolas em Boston e Nova York e das cadeias de troca de rins — todos citados na láurea do Nobel. Gale-Shapley é hoje vocabulário padrão em desenho de mercados, pesquisa operacional e ciência da computação.