Algoritmo Gale-Shapley

Apesar das poucas chances, o nerd Leonard, da série de TV "Big Bang Theory", tinha mesmo de tentar conquistar a vizinha bonitona e loira Penny. Eventualmente poderia dar certo, como deu de fato. Isso não é coisa só de TV.

O estudo que rendeu ao matemático norte-americano Lloyd Shapley, 89, o Prêmio Nobel de Economia de 2012 (dividido com outro matemático dos EUA, Alvin Roth) é sobre combinações e parcerias. Os resultados podem ser aplicados em decisões como escolher uma escola para seu filho, racionalizar a doação de órgãos e até conseguir um casamento mais feliz.

Uma de suas conclusões na vida prática, segundo explica em entrevista ao UOL o economista e professor da FGV-SP Samy Dana, é a seguinte: uma pessoa nunca deve deixar de flertar com alguém só por achar que não tem chances.
[...]

UOL - Quais são os principais conceitos dos estudos que deram os prêmios Nobel de Economia deste ano a Alvin Roth e Lloyd Shapley?
Samy Dana - Os principais conceitos dos estudos dos pesquisadores são as alocações de recursos da melhor maneira possível. Esse é um tema bastante recorrente na economia, inclusive porque algumas pessoas definem a economia como o estudo dos recursos escassos.

Isso porque reconhecemos diversas situações em que os recursos, e não só os financeiros, como é mais comum pensar, estão mal distribuídos, podendo haver outra distribuição que melhorasse o bem-estar de todas as partes, sem prejudicar o de ninguém.

Essas distribuições melhores necessitam de alguma intervenção para acontecer, como um contrato ou uma instituição, porque, normalmente, as pessoas não têm informação perfeita e não conseguem atingi-las sozinhas.

[...]

Como as pesquisas ajudam a escolher uma escola para seu filho?
As pesquisas ajudaram nessa escolha no caso americano, onde há um processo de seleção nas escolas de Ensino Médio. Nos Estados Unidos, os estudantes devem concorrer às vagas para as escolas de ensino médio.

Como poucos podem chegar às melhores, com o passar do tempo, os estudantes estavam colocando como sua primeira opção as piores escolas, para ter a garantia de aprovação, embora não quisessem estudar lá. Após as pesquisas dos dois [ganhadores do Nobel], criou-se um sistema que reúne as inscrições de todos os alunos, que devem ranquear 12 escolas de seu interesse. As escolas também devem especificar seus critérios de preferência e, assim, o sistema seleciona a melhor alocação possível.

No caso brasileiro, algumas escolas particulares realizam seus próprios exames de seleção e, nesse caso, o modelo funcionaria da mesma forma, os alunos deveriam prestar os exames das escolas de que gostassem. Também deveria  ter, mentalmente, uma ordem de preferência, e estudar naquela em que fosse aprovado e estivesse na posição mais alta de sua lista.

De que forma os estudos facilitam ou racionalizam o transplante de órgãos?
Caso uma mulher tivesse problemas em seu rim, por exemplo, e seu marido quisesse doar um dos seus para ela, mas não fosse um doador compatível, eles deveriam esperar até que um doador anônimo surgisse. Tal evento poderia demorar muito a ocorrer ou nem mesmo acontecer.

Os pesquisadores sugeriram, então, a criação de um sistema com cadastro das necessidades dessas pessoas, de modo que pessoas das mais diversas regiões pudessem doar a outras desconhecidas e assim salvar a vida dos cônjuges. Esse sistema foi implementado e funcionou nos EUA.

Pode explicar como as teorias auxiliam na escolha de um parceiro para namorar ou casar?
Lloyd Shapley desenvolveu, com outro pesquisador, David Gale, o chamado algoritmo Gale-Shapley, para criar casamentos estáveis. Suponha quantidades iguais de homens e mulheres. O algoritmo prevê que, na primeira rodada [de encontros feitos no estudo], os homens deveriam propor casamento a sua mulher solteira preferida. Ela deveria dizer "talvez" ao proponente que mais gostasse e "não" aos demais. Assim, casais seriam provisoriamente formados.

Na rodada seguinte, os homens solteiros devem propor novamente às mulheres, e essas devem novamente dizer "talvez" aos proponentes que mais preferirem e "não" aos demais (podendo ser inclusive, o seu parceiro provisório). Ou seja, a uma mulher é permitido "mudar para melhor".

O modelo prevê que, uma vez que uma mulher se case, ela deve estar sempre casada, mesmo que com parceiros diferentes. No final das rodadas, não poderá haver nenhum homem ou mulher solteira, e garante-se que os casamentos formados serão estáveis.

O que garante que esses casamentos se tornem estáveis?

É que o homem e a mulher sabem que não podem ficar com ninguém melhor que aquele parceiro. Foram rejeitados nas outras possibilidades.

Pode-se dizer, então, que existe uma "fórmula do amor"?

Sim, essa fórmula poderia ser o algoritmo Gale-Shapley.

Como aplicá-la na vida real e achar seu par ideal?
Na vida real, aplicar o modelo é bastante complicado, pois uma pessoa nunca conhecerá todos os homens ou mulheres do país ou até mesmo do mundo, mas, simplificadamente, é possível inferir que uma pessoa nunca deve deixar de flertar com alguém que prefira só por achar que não tem chances com aquela pessoa.

Da mesma forma, alguém nunca deve ficar com uma pessoa, sendo que há outra que ela prefira, flertando com ela.

E tudo isso garante um casamento duradouro e feliz?
Não, isso é só um modelo. Na vida real, as pessoas podem mudar de preferências ao longo do tempo e o desgaste do convívio pode fazer com que elas queiram terminar seu relacionamento.