Nem só de bolsas de valores e transações monetárias vive a economia. O prêmio Nobel da área neste ano foi concedido a dois  pesquisadores norte-americanos – o economista Alvin Roth e o economista e matemático Lloyd Shapley – responsáveis, nas palavras da Real Academia Sueca de Ciências, pela “proposição da teoria das alocações estáveis e pelo desenvolvimento da prática do desenho de mercado”.

Traduzindo, os economistas mostraram que existem matchings (combinações, em tradução livre) estáveis para certos sistemas não regidos pelas regras gerais do mercado, ou seja, que não envolvem necessariamente ou não são determinados somente por transações monetárias, como a distribuição de alunos pelas universidades em um sistema de avaliação unificada.

A economista brasileira Marilda Sotomayor, da Universidade de São Paulo (USP), é coautora – com Alvin Roth – do livro de referência na área, Two-sided matching: a study in game-theoretic modeling and analysis, e de uma série de artigos escritos em parceria com o laureado.

“A importância do matching para a economia é que economia é sobre a vida real e matching tem inúmeras aplicações à vida real”, avaliou a economista em nota distribuída pela USP. “Através dessa teoria, vários mercados têm sido melhor entendidos, o que tem ajudado na sua própria organização.”

De fato, os desdobramentos dos trabalhos de Shapley, na Universidade da Califórnia, e de Roth, na Universidade Harvard, têm sido empregados em diversos setores econômicos. Uma das aplicações mais importantes é o ‘desenho de mercados’, que utiliza versões e extensões da teoria proposta por Shapley para buscar algoritmos e soluções capazes de combinar de maneira mais eficiente as demandas dos grupos envolvidos num mesmo ‘mercado’, como o que envolve médicos recém-formados em busca do melhor hospital e hospitais em busca das melhores contratações.

Como descreve o próprio comitê do prêmio, mesmo tendo trabalhado de forma independente, “a combinação da teoria básica de Shapley e das pesquisas empíricas, dos experimentos e do design prático de Roth gerou um florescente campo de pesquisas e melhorou o desempenho de muitos mercados.”

Hoje, esse tipo de metodologia é utilizado pelos hospitais norte-americanos para a escolha de seus novos médicos entre os recém-formados e orientam complexos sistemas de doação de órgãos em diversas partes do país – com algoritmos desenvolvidos e aperfeiçoados pelo próprio Roth.

O matemático brasileiro Aloísio Pessoa de Araújo, da Fundação Getúlio Vargas (FGV), também acredita que a premiação faz justiça ao trabalho dos laureados. “A premiação de Roth era uma barbada, pelas muitas aplicações importantes de seu trabalho”, avalia. “Mas foi ótimo que o comitê tenha decidido homenagear Shapley, que lançou as bases para os estudos de matching e fez enormes contribuições para a teoria dos jogos [laureada no Nobel de 2005].”

Estabilidade

Na década de 1960, os economistas David Gale e Lloyd Shapley provaram que, partindo de uma hierarquia de preferências de participantes de dois grupos quaisquer, é possível, com um algoritmo simples e em um número finito de etapas, chegar a combinações (matchings) estáveis de seus elementos.

Um exemplo teórico utiliza o processo de admissão das universidades norte-americanas. Neles, estudantes e instituições teriam suas listas mútuas de preferência e as universidades começariam fazendo propostas aos estudantes mais bem ranqueados de acordo com seus critérios, que dariam respostas negativas ou positivas. As universidades rejeitadas poderiam fazer uma nova proposta ao próximo estudante da sua lista. Os que aceitassem uma proposta teriam liberdade de mudar de ideia caso fossem procurados por instituições mais bem ranqueadas por eles.

O processo continua até que nenhuma universidade tenha interesse em fazer outra oferta. No fim, os estudantes ficam com a melhor oferta que tiverem. Gale e Shapley mostraram matematicamente que o algoritmo sempre produz combinações estáveis, conceito também cunhado por eles, nas quais não seria possível formar associações mais adequadas, ou seja, onde um aluno pudesse ter mais interesse numa instituição do que naquela que escolheu se esta também tivesse mais interesse nele do que nos estudantes que selecionou.

Apesar do modelo Gale-Shapley ser matematicamente importante, foi o trabalho de Roth, a partir de 1984, que mostrou, na prática, a sua relevância. Ele publicou uma série de trabalhos que analisavam o mercado norte-americano de alocação de médicos recém-formados nas residências dos hospitais. Até a década de 1940, a concorrência obrigava as instituições a oferecer vagas aos estudantes muito antes da graduação, antes de escolherem uma área de atuação e com prazos que limitavam sua possibilidade de avaliar todas as oportunidades disponíveis.

Em resposta ao problema, foi criado o Programa Nacional de Combinação de Residentes (NRMP, da sigla em inglês), na década de 1950, que cruza as preferências dos estudantes em fim de curso e das instituições, chegando a uma lista de correlações ideal. Roth observou que o sistema podia ser descrito por um algoritmo que se encaixava na proposta de Gale-Shapley e mostrou que o sucesso do NRMP estava na sua capacidade de produzir combinações estáveis. 

Outras aplicações

Já nos anos 1990, Roth avaliou sistemas similares no Reino Unido e mostrou que aqueles que criavam combinações estáveis eram bem-sucedidos, enquanto os que adotavam outros métodos enfrentavam uma série de problemas. No entanto, nessa época o próprio NRMP passou a receber críticas por atender mais aos interesses dos hospitais do que dos médicos – de fato, o modelo de Gale-Shapley previa a criação de uma estabilidade sempre favorável ao lado proponente – no caso, os hospitais (confira a ilustração para mais detalhes). O próprio Roth propôs modificações no algoritmo, para incluir, por exemplo, a possibilidade de casais de médicos conseguirem residências em localidades próximas. O novo algoritmo foi adotado pelo NRMP em 1997. 

No moldelo de Gale-Shapley, a situação de estabilidade atingida varia de acordo com o grupo responsável por propor as negociações, sendo sempre favorável às preferências deste. (ilustração: Real Academia Sueca de Ciências)

Um algoritmo similar, também baseado no de Gale-Shapley, foi adotado em algumas localidades dos Estados Unidos, como na cidade de Nova Iorque, para a distribuição de alunos pelas universidades. O algoritmo reduziu em até 90% a quantidade de estudantes alocados em instituições pelas quais não tinham expressado interesse.

O modelo também serve de base para um sistema de orientação de transplantes de órgãos, em especial de rins, em diversas partes dos Estados Unidos. “O trabalho de Roth levou ao desenvolvimento de um algoritmo mais complexo, que realiza uma série de triangulações capazes de considerar limitações de tempo e compatibilidade, para orientar o sistema de doação de órgãos”, explica Aloísio Pessoa de Araújo, da FGV.

No Brasil, o matemático cita possíveis aplicações do modelo de Gale-Shapley em sistemas de seleção de residentes em hospitais e de alunos para programas de pós-graduação, como o da Associação Nacional dos Centros de Pós-graduação em Economia. “A associação realiza provas únicas para seleção integrada dos estudantes para diversas instituições, um processo em que cada centro valoriza determinados conteúdos e cada estudante tem suas instituições de preferência”, explica. “A própria Sotomayor foi convidada pela associação para propor alternativas que ajudem a aprimorar esse sistema, baseado na teoria de Shapley.”

Se você estranhou a ausência de David Gale entre os laureados, uma vez que a teoria também leva seu nome, eis a justificativa: Gale faleceu em 2008 e o Nobel tem como política não realizar homenagens póstumas.

Marcelo Garcia
Ciência Hoje On-line