Todo mundo conhece: "João amava Teresa que amava Raimundo que amava Maria que amava Joaquim que amava Lili que não amava ninguém. João foi para os Estados Unidos, Teresa para o convento, Raimundo morreu de desastre, Maria ficou para tia, Joaquim suicidou-se e Lili casou com J. Pinto Fernandes que não tinha entrado na história."

Será que a matemática poderia ter ajudado os personagens de Carlos Drummond de Andrade a terem finais mais felizes?

O problema do casamento pode ser formulado da seguinte forma, na versão clássica (mencionarei outra daqui a pouco).

Temos dois grupos de pessoas: "homens" e "mulheres". Cada homem tem uma lista de mulheres com quem aceitaria se casar, ordenada pela sua preferência. Do mesmo modo, cada mulher tem uma lista de homens aceitáveis, elencada na ordem de sua preferência.

Como emparelhar os homens e as mulheres de modo a melhor atender essas preferências? Será que existe sempre algum emparelhamento estável ("à prova de divórcio"), que não deixe separada nenhuma dupla (formada por um homem e uma mulher) que prefeririam ficar juntos do que com seus cônjuges?

Pois bem, a resposta é sim! Mais ainda, um emparelhamento estável pode ser obtido usando o seguinte método.

Inicialmente, cada mulher pede em namoro seu homem preferido, o primeiro na sua lista. Cada homem rejeita as mulheres fora de sua lista de mulheres aceitáveis; caso tenha recebido pedidos de aceitáveis, aceita temporariamente aquela em melhor posição na lista e rejeita as demais.

Isto encerra a primeira rodada, com alguns homens e mulheres comprometidos temporariamente, e outros ainda solteiros.

Em seguida, cada mulher que permanece solteira pede em namoro seu homem preferido dentre os aceitáveis que não a rejeitaram. Caso não exista mais nenhum nessas condições, fica solteira até o final.

Novamente, cada homem nega os pedidos das indesejadas e, se tiver recebido um ou mais convites das aceitáveis, une-se àquela em melhor posição, rejeitando as demais. Pode até dispensar a namorada aceita antes, se for o caso, e trocá-la por outra que esteja fazendo o pedido e que ele prefira.

Este procedimento vai sendo repetido até que nenhuma mulher seja rejeitada. Nesse ponto todas ou estão comprometidas ou foram rejeitadas pelos seus homens aceitáveis. No primeiro caso, o compromisso torna-se definitivo e o casamento é celebrado. No segundo, fica solteira. Homens sem pedidos também ficam solteiros.

Este método foi proposto em 1962 por David Gale (1921-2008), matemático americano, e Lloyd Shapley (1923-2016), matemático e economista britânico.

Em trabalho publicado na revista "American Mathematical Monthly", provaram matematicamente que este método sempre produz um emparelhamento estável num número finito de etapas.

Além disso, o resultado é o emparelhamento ótimo para as mulheres, ou seja, dentre todos os estáveis o que melhor atende as suas preferências.

Claro que podemos trocar os papéis de homens e mulheres e, nesse caso, obteremos o emparelhamento estável ótimo para os homens. Mas o que é melhor para as mulheres é pior para os homens e vice versa: quem sai ganhando é sempre o sexo que tem a iniciativa de fazer o pedido.

Nesse mesmo artigo "College admission and the stability of marriage" (em tradução livre, "Entrada na universidade e a estabilidade do casamento"), Gale e Shapley também resolvem outro problema relacionado, relativo ao processo seletivo para universidades.

De um lado, universidades, cada uma oferecendo certo número de vagas para alunos. Do outro, candidatos com uma lista de instituições onde aceitaria se matricular, ordenadas por preferência. Cada universidade também tem sua lista de alunos que aceitaria receber, ordenada por sua preferência.

O problema é como alocar os candidatos às vagas para melhor atender às preferências das duas partes.

Em particular, deseja-se que essa correspondência seja estável, isto é, que não exista nenhuma dupla formada por uma universidade U e um estudante E tal que E prefere U à universidade que o admitiu (ou está sem nada e prefere U a ficar sem nada), e U prefere E a algum estudante que admitiu (ou prefere dar uma vaga a E do que ficar sem preenchê-la).

Mais uma vez, Gale e Shapley provam existir sempre um emparelhamento estável.

A prova é simples, mas engenhosa: consideram cada vaga como se fosse uma universidade diferente e então o processo seletivo transforma-se num "casamento" dos candidatos com as vagas. Desta forma, o problema fica reduzido ao problema anterior, que explicamos como resolver. Esta observação ajuda a entender por que a matemática é tão poderosa: como estuda padrões, ou seja, características profundas que são comuns a diferentes situações, ela é capaz de aplicar ideias de um problema (casamento) a outro que parece completamente diferente (vestibular).

Embora na época do artigo os autores desconhecessem aplicações, este modelo se adequa perfeitamente à situação em que a preferência das universidades se baseia na nota de um exame, como é o caso do Brasil e outros países.

O algoritmo de Gale-Shapley, com os candidatos fazendo as propostas às universidades, assegura aos alunos a distribuição estável ótima das vagas universitárias. Não haveria impedimento a usá-lo no Sisu (Sistema de Seleção Unificada), mas, até onde sabemos, isso não é feito.

Questionados sobre a natureza de seu trabalho, Gale e Shapley sempre se declararam matemáticos. Aliás Gale dizia que "qualquer argumento que seja usado com suficiente precisão é matemático". Por suas contribuições, em 2012 Shapley recebeu o prêmio Nobel da Economia, partilhado com o americano Alvin Roth, nascido em 1951, que liderou a aplicação da teoria do emparelhamento aos mercados da vida real. A essa altura, Gale já havia falecido.

Marilda Sotomayor, da FGV/RJ, pesquisadora pioneira da teoria do emparelhamento, colaborou muitos anos com Gale e também com Roth, com quem escreveu o livro "Two-sided matchings. A study in game theoretic modeling and analysis".

Em seus trabalhos, ela menciona muitas outras aplicações da teoria, por exemplo na alocação de médicos residentes em hospitais universitários, na admissão de estudantes em universidades brasileiras, nos mecanismos de leilões ou no alojamento de estudantes em dormitórios.

Este último, conhecido como problema do companheiro de quarto ("roommate problem"), pode ser visto como uma versão flexível do problema do casamento em que não há "homens" e "mulheres", apenas pessoas que serão agrupadas em duplas segundo as suas preferências. Gale e Shapley provaram que este problema nem sempre tem solução estável.

Marcelo Viana - matemático e diretor-geral do Impa, é ganhador do Prêmio Louis D., do Institut de France.

Fonte: coluna jornal FSP