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

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 receita para formar duplas infalíveis? E será que a matemática tem alguma coisa a ver com isto?

Nos anos 1960, 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 and 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 para a 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 a 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 de matching ficaria adormecida por alguns anos, até a década de 80. Àquela altura, a matemática brasileira Marilda Sotomayor desembarcava na Universidade da California Berkeley e conhecia David Gale. Conta-se que ao adentrar a uma de suas aulas, Sotomayor anotou alguns problemas escritos no quadro. Em uma semana, havia resolvido menos da metade do que havia julgado uma lição de casa.

Assim, decidiu procurar Gale para sanar dúvidas e questionar (de fato, surpreender!) o professor da disciplina.

O que Marilda Sotomayor julgava uma lição de casa era, na verdade, uma lista de perguntas fundamentais da teoria. E as soluções que ela havia proposto reacenderam e avançaram substancialmente a área. A teoria de matching continuava a se desenvolver! Como continua até hoje, 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.