A matemática da formação de um par perfeito

Por Edgard Pimentel

Será que existe uma receita para formar duplas infalíveis?

*

Arroz e feijão, Lisboa e o Tejo, Simon e Garfunkel, Ullmann e Bergman, John e Yoko. Pares, duplas, casais. Qual o segredo por trás de alguns pares que parecem perfeitos? Será que existe uma receita para formar duplas infalíveis? E será que a matemática tem alguma coisa a ver com isto?

Nos anos 60, havia um problema importante no sistema de saúde norte-americano, a respeito da alocação de médicos e médicas que haviam acabado de se formar em hospitais de todo o país. Como não eram nem os profissionais nem os hospitais que escolhiam quem iriam para onde, com frequência muitos médicos e médicas acabavam em locais que consideravam menos preferíveis, enquanto os hospitais não conseguiam contratar suas melhores opções.

Motivados por este problema – e por diversas outras questões que frequentam o imaginário matemático –, David Gale e Lloyd Shapley propuseram uma regra para a formação de pares. O que ficou conhecido como algoritmo de Gale-Shapley é uma receita que, se seguida, garante que os pares formados não se veem incentivados a se romper. Ou seja, um/a profissional não é capaz de trocar de hospital sem acabar em um cenário pior.

Gale e Shapley fundavam assim uma importante área de pesquisa em matemática, a teoria de matching, de central importância à teoria dos jogos. Eles haviam demonstrado que se houver dois grupos que têm um interesse mútuo (hospitais e médico/as, professores e escolas, pessoas e pessoas) é possível alocar integrantes de um grupo a integrantes do outro, sem que eles manifestem uma propensão a realocações. Para tanto, bastaria que cada um listasse os integrantes do outro grupo segundo sua ordem de interesse. E o algoritmo se encarregaria do resto.

Por falar em grupo, David Gale e Lloyd Shapley pertenceram a uma seleção de mentes verdadeiramente brilhantes, por assim dizer. Estudantes de doutorado na Princeton da virada dos anos 40 para os 50, tiveram como mentor Albert Tucker, que também orientara John Nash. Diz-se que foi Gale quem sugeriu um dos ingredientes fundamentais ao desenvolvimento do famoso equilíbrio de Nash.

Uma curiosidade sobre o método: ele opera por candidatura e descarte. Ou seja, integrantes de um grupo se candidatam a integrantes do outro. E os últimos decidem com quem permanecem pareados com base nas candidaturas que receberam. É possível provar em termos matemáticos que o grupo que se candidata tem um resultado melhor.

A teoria continuou a atrair a atenção de vários pesquisadores ao longo dos anos. No começos dos anos 80, durante um estágio de pós-doutorado na Universidade da California em Berkeley, a pesquisadora brasileira Marilda Sotomayor envolveu-se com a área. É desta época seu primeiro trabalho, dentre alguns, em colaboração com David Gale.

Alguns anos depois, em 1990, Marilda publicaria junto com o economista norte-americano Alvin Roth um dos livros clássicos da área, que acabou por contribuir para a divulgação do tema e atrair a atenção de diversos cientistas. Até hoje a teoria de matching continua a se desenvolver, com aplicações diversas a problemas em ciências da vida e à economia. Não por acaso a área foi agraciada com o prêmio Nobel de Economia de 2012.

É certo que o segredo para formar duplas perfeitas tem diversas camadas de adorável desafio. Mais verdade ainda é que parte da graça está em não haver receita. Mas quando o assunto é a curiosidade humana e a matemática, bem, este é um matching made in heaven.

*

Esta coluna foi produzida especialmente para a campanha #CientistaTrabalhando, que celebra o Dia Nacional da Ciência. Ao longo do mês de julho, colunistas cedem seus espaços para abordar temas relacionados ao processo científico, em textos escritos por convidados ou por eles próprios.

Edgard Pimentel é matemático e professor da PUC-Rio

Inscreva-se na newsletter do Serrapilheira para acompanhar mais novidades do instituto e do blog Ciência Fundamental.

Erramos: o texto foi alterado

Ao contrário do mencionado anteriormente, Marilda Sotomayor nunca fui estudante de David Gale ou assistiu a um curso por ele ministrado. Sua primeira contribuição à área foi a resolução de um problema em aberto, que David Gale estava tentando resolver havia cerca de um ano. Marilda Sotomayor e David Gale trabalharam juntos, em colaboração, durante dois anos e meio em Berkeley.