As mulheres seriam mais felizes se pedissem os homens em casamento

 

stock-illustration-9711255-modern-girls-don-t-wait


{1}/ O verdadeiro papel do estudante

Em 2012, o Prêmio Nobel de Economia foi para dois americanos, Alvin E. Roth e Lloyd S. Shapley. Marilda Sotomayor, professora na Faculdade de Economia, Administração e Contabilidade da Universidade de São Paulo, conhece os dois pessoalmente, e já escreveu artigos e livros com Alvin Roth. Em 2010, ela ajudou a organizar um congresso sobre teoria dos jogos em São Paulo (SP); graças a seu trabalho e prestígio, apareceram quatro ganhadores do Nobel: John Nash, Robert Aumann, Erick Maskin, e Roger Myerson. Em outras palavras, vale a pena ouvir o que ela tem a dizer, e ela acha que não é papel do professor pegar o aluno pela mão e ensiná-lo a aplicar a teoria: é papel do professor explicar a teoria, e do aluno achar aplicações.


stock-illustration-2975142-egghead


 

{2}/ Marilda: “Minha cabeça é de matemático.”

Alvin Roth e Lloyd Shapley admiravam o trabalho de um matemático americano brilhante, David Gale, que só não ganhou o Nobel de economia em 2012 porque morreu em 2008. (Lloyd e David assinaram um artigo científico juntos; Alvin e David trocaram correspondência.) Pois Marilda escreveu cinco artigos com Gale. No entanto, apesar de tudo o que sabe, nunca deu consultoria a uma empresa. “Minha cabeça é de matemático”, diz Marilda. “Só sei fazer duas coisas: escrever artigos científicos e dar aulas.” Quando começou a ficar famosa, passou a atrair bons estudantes de mestrado e de doutorado para a FEA, e eles queriam instruções a respeito de como aplicar a teoria dos jogos a problemas da administração e da economia. Ela tinha de ser firme: “Eu não dou aplicações!” De tanto dizer isso, hoje os alunos já não a pressionam mais.

Marilda diz que aplicar matemática teórica a situações práticas dá trabalho em demasia. “Modelar uma situação real da economia leva um tempão, e, quando você vai ver o que usou de teoria naquilo tudo, usou só um pouquinho.” Acha que, do ponto de vista do aluno, e do ponto de vista do profissional, vale a pena usar a teoria para compreender a realidade, mas, do ponto de vista do professor em sala de aula, com tempo curto para passar toda a matéria, não vale a pena. “Ao longo do curso de introdução à teoria dos jogos, eu prefiro ir mais fundo na teoria, e cito as aplicações apenas de passagem. É papel do aluno identificar qual ferramenta teórica ele pode usar numa situação prática. Para que ele possa cumprir seu papel, tenho de focar não nas aplicações, mas na teoria.”


stock-illustration-6193403-don-t-be-sad


 

{3}/ A entrevista em si

Como você veio a trabalhar com teoria dos jogos?

Eu sou matemática, sempre fui, mas fiz minha tese de doutorado sobre crescimento econômico, e meu orientador, Jack Schechtman, havia sido orientando do David Gale, que também era especialista em crescimento econômico. Então, para resumir, em 1983 eu e meu marido [que também é matemático] fomos para a Universidade da Califórnia em Berkeley. Fui especificamente para estudar crescimento econômico com Gale, mas, quando cheguei, na primeira reunião que tivemos, ele ouviu explicações sobre meu doutorado, bateu palmas, e me disse:

— Não estou mais interessado nessa área.

[risos] Saí daquela reunião pensando: “E agora?” Fiquei uns dois meses meio perdida, lendo artigos sobre crescimento econômico na biblioteca, tentando me virar sozinha. Meu humor estava péssimo! Até que meu marido me deu um conselho:

— Você está aqui ao lado de um gênio, que é o David Gale, e não está tirando nenhum proveito disso. Por que não conversa com ele, pergunta no que ele está interessado, e se interessa também?

Foi o que fiz. Gale me disse que estava interessado em “matchings”, e me perguntou:

— Quer saber o que é isso?

Eu disse que sim, e ele me deu um livro e dois artigos científicos. Num dos artigos [de Dubins & Freedman] havia explicações sobre o agora famoso algoritmo Gale-Shapley, todo formalizado em linguagem de computador. [Veja explicações sobre o algoritmo Gale-Shapley na seção 5 mais abaixo.] Fiquei um mês tentando assimilar todo o material. Até aquele momento, matemática para mim era limites, derivadas, integrais. Eu não imaginava um texto teórico cujo exemplo principal tratava de casamentos entre homens e mulheres! Eu li aquilo tudo com extremo cuidado, linha por linha, símbolo por símbolo. Quando acabei, marquei uma reunião com Gale, na qual eu disse que tinha lido tudo, e que achava que tinha compreendido tudo.

Havia um teorema num dos artigos. O teorema dizia que, caso os pares sejam feitos com o algoritmo Gale-Shapley, nenhum jogador, e nenhum grupo de jogadores, consegue manipular o resultado do jogo, isto é, consegue um casamento melhor do que o casamento obtido com o algoritmo — seja um casamento estável, seja instável. [Sobre a palavra “casamento”, no singular, veja a seção 4.] A demonstração do teorema se estendia por umas 20 páginas. Bem, Gale estava escrevendo um artigo com Gabrielle Demange, uma francesa, e ambos usavam esse teorema como ponto de partida.

Quando eu já estava saindo da sala dele, Gale me chamou de volta, e tinha um pedaço de papel nas mãos. Devia estar por ali, em cima da mesa, numa gaveta, bem ao alcance. Nesse papel havia um lema. Ele me disse que tinha tentado provar aquele lema, sem sucesso, mas que, se eu pudesse prová-lo, ele seria capaz de reduzir aquela prova de 20 páginas para uma prova de três linhas.

[Lembrete: Um “lema” é um teorema, mas que o matemático prova com o propósito declarado de simplificar a prova de outro teorema.]

— Se a gente provasse esse lema — Gale me explicou — eu poderia explicar esse assunto numa única aula.

Esse ponto é importante, porque, se é muito difícil demonstrar uma afirmação, o professor tende a não abordá-la em sala de aula.

Isso aconteceu numa sexta-feira. Na segunda-feira, a prova estava pronta. Não me pergunte como — não sei explicar como atinei com a demonstração tão depressa. É claro que minha mente funcionou bem porque eu tinha lido o livro e os dois artigos com extremo cuidado.

Na segunda-feira, quando eu lhe disse que o lema estava provado, ele ficou desconfiado de mim. Fui à lousa e fui escrevendo a demonstração, linha por linha, e ele ficou a meu lado, de pé, muito sério. Antes mesmo que eu terminasse, ele começou a bater palmas e a gritar:

— Brava! Brava! Você demonstrou! Você demonstrou!

Isso foi de manhã. À tarde, ele apareceu no meu escritório já com o artigo manuscrito (não havia computador naquela época). Esse foi o primeiro artigo que escrevemos juntos. Até aquele dia, eu tinha de marcar hora para falar com ele, e demorava. Daquele dia em diante, acabou a formalidade entre nós, e ficamos amigos. Às vezes, ele entrava na minha sala com umas fórmulas num papel e me perguntava:

— Verdadeiro ou falso?

[risos] Nem sempre eu sabia por que estava demonstrando uma afirmação. Ele já me dava a afirmação pronta, e eu só ia entender sua importância quando lia o manuscrito completo. Era um acordo bom para nós dois: naquela época, eu achava mais difícil escrever a introdução, pois teoria dos jogos era novo para mim, e eu não sabia distinguir o que era importante do que não era. Fiquei dois anos em Berkeley, e eu e Gale produzimos dessa forma cinco artigos.

Você demonstrou o algoritmo Gale-Shapley de outra forma?

A demonstração do Gale e do Shapley era o próprio algoritmo, isto é, era construtiva. [Os autores davam ao leitor um procedimento, um ‘como fazer’.] Eu consegui escrever uma demonstração não construtiva de que existe sempre um único casamento ótimo para todos os homens: todos os homens, sem exceção, vão preferir este casamento a todos os outros casamentos possíveis, se houver mais de um. Minha demonstração não construtiva foi publicada em 1996.

[Numa demonstração não construtiva, o matemático demonstra que certa afirmação é verdadeira, sem contudo explicar como alguém pode construir os objetos matemáticos mencionados na demonstração.]

Demonstrações não construtivas têm uma vantagem: podemos usar o argumento central em outros contextos matemáticos, ou em outros jogos cujas características principais sejam semelhantes ao jogo do casamento. Por exemplo, o Shapley e o Herbert Scarf recorreram uma demonstração complicada, não construtiva, para demonstrar a existência de uma solução ótima no mercado de casas. Com adaptações ao argumento que publiquei em 1996, também consegui uma demonstração não construtiva, mas curta e simples.

Existem aspectos mal compreendidos sobre os casamentos?

Um aspecto pouco compreendido é que o objetivo do jogo não é obter pares estáveis, simplesmente, mas casamentos estáveis: um casamento é um subconjunto de todos os casamentos possíveis, e um casamento estável é um subconjunto que não contém nenhum par bloqueante. [Veja a seção 4.] Em outras palavras, num casamento estável não existe nenhum par em que o homem deseja outra mulher, de outro par, e que esse desejo seja correspondido. Se houver a existência de um par bloqueante, isso não é bom, porque aí o casamento não será duradouro; se esse casamento for entre estudantes e instituições de ensino, por exemplo, a presença de pares bloqueantes significa que as instituições e os estudantes vão exigir mudanças o tempo todo.

Existem outros aspectos pouco compreendidos nesse jogo. Para que o algoritmo Gale-Shapley funcione, deve existir um método pelo qual os agentes ou jogadores possam elaborar sua lista de preferências: quanto mais informações os jogadores de um grupo [o das mulheres, por exemplo] obtêm sobre o outro grupo [o dos homens], melhor. Além disso, não pode existir aceites definitivos: se os homens propõem, o algoritmo só funciona caso as mulheres possam aceitar a proposta temporariamente, até que um homem melhor proponha, de modo que as mulheres estão sempre fazendo upgrade, isto é, trocando um menos querido por um mais querido.

Na realidade, esse algoritmo são dois algoritmos, pois o resultado ótimo depende de quem propõe: caso exista mais de um casamento estável no subconjunto dos casamentos estáveis, então, se os homens fazem ofertas para as mulheres, o algoritmo produzirá o melhor casamento estável possível do ponto de vista dos homens, e o pior casamento estável do ponto de vista das mulheres; da mesma forma, se as mulheres fazem ofertas para os homens, conseguirão o casamento estável ótimo para as mulheres, e os homens ficarão com o pior casamento estável. Isso é contraintuitivo.

Outra coisa contraintuitiva: suponha que escolas e estudantes realizam o algoritmo de modo que as escolas preencham suas vagas e os estudantes consigam uma vaga numa escola. Se as escolas propõem, e se um estudante não consegue vaga em nenhuma escola, ele não pode culpar o algoritmo dizendo que favorece as escolas: um resultado meu e de Gale diz que, em todos os casamentos estáveis, não importa qual lado proponha, o conjunto dos jogadores sem par é sempre o mesmo. Essa ideia também vale para as escolas que ficam com vaga sem preencher. Nesse sentido, o algoritmo Gale-Shapley não beneficia nem escolas nem estudantes.

É verdade que Alvin Roth não descobriu o NRMP? [Sobre o NRMP, que é um procedimento realizado por um órgão do governo americano, veja a seção 6.]

Quando Gale e Shapley conceberam o algoritmo [a publicação ocorreu em 1962], não achavam que podia ser aplicado numa situação real, isto é, não achavam que haveria um mercado com características semelhantes às do casamento. Mas, em 1974, Gale deu uma palestra sobre o assunto, que um médico assistiu. No fim da palestra, o médico foi conversar com ele e disse que o NRMP usava um algoritmo parecido.

No artigo que Gale e eu escrevemos em 1983, já mencionávamos o caso do NRMP. Gale mandou esse artigo para Alvin Roth. Contudo, o nosso artigo só foi publicado em 1985, e numa revista de matemática — a meu pedido. Em 1984, Alvin publicou um artigo no qual estudava o NRMP tão completamente quando pôde na ocasião; publicou numa revista de economia, e citava o artigo Gale-Sotomayor como referência. No fim das contas, os economistas acham que Roth descobriu o NRMP — é o que sugere o documento da Academia Real Sueca de Ciências, que explica os motivos no Nobel de 2012. O Alvin tem muitos méritos, mas não foi o de descobrir a existência do NRMP.

O que o Alvin fez foi estudar o NRMP a fundo, e se perguntar os porquês de tudo o que descobriu. Ele fez modelagem matemática no sentido estrito da expressão: estudou causas, consequências, história, mudanças — tudo. Seu mérito foi ter provado que, na prática, se uma instituição usa um algoritmo para produzir uniões estáveis, então o procedimento e a própria instituição ganham estabilidade, pois ninguém anseia por mudanças. Ele mostrou que a definição teórica de equilíbrio coincide com o equilíbrio na prática, e que podemos usar a teoria dos jogos para compreender melhor o que acontece na economia.

Qual é a natureza de sua colaboração com Alvin Roth?

A FEA está organizando um seminário sobre teoria dos jogos, que ocorrerá em 2014, para comemorar meus 70 anos. A parte científica é minha responsabilidade, e quatro ganhadores do prêmio Nobel confirmaram presença.

Em parte, esse prestígio vem do fato de que eu e o Alvin escrevemos um livro juntos, que foi publicado em 1990 [Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis]. Ele organizou a escrita, e eu a matemática. Na época, nossa ambição era juntar num único livro toda a teoria existente sobre uniões.

Ocorre que, até a ocasião desse livro, a teoria de uniões atraía mais matemáticos que economistas — Gale, Alvin, Shapley, Demange, e eu somos matemáticos. Posso dizer que, naquela época, os economistas não tinham uma base boa em matemática… Quando eu trabalhava com Gale, ele pegava minhas demonstrações e as enxugava ao máximo: elas ficavam elegantíssimas, e curtas. Depois, quando eu estava trabalhando com o Alvin, ele me chamava e dizia:

— Marilda, por que isso aqui implica isso aqui?

Eu olhava aquilo e não me lembrava. Pedia um tempo, ia para meu escritório, e por fim lembrava: “Ah! É por causa disso, disso, e disso.” Então eu ia e explicava para o Alvin o raciocínio, ele escrevia o texto do livro para deixá-la óbvia, e eu fazia os ajustes necessários na parte matemática. Ele estava determinado a escrever um livro que um leitor não matemático pudesse acompanhar. É claro que a beleza e a elegância das demonstrações de Gale se perdeu, mas o livro, no fim das contas, ficou tão óbvio que podia ser lido antes de dormir. Isso atraiu muito leitor que não era matemático, e por conta dessa iniciativa a teoria cresceu. Hoje, a teoria dos jogos deve ter uns 30 tópicos; só essa parte de uniões tem três tópicos: análise e modelagem de mercados de casamentos, escolha de escolas, e desenho de mercados. Essa parte já não cabe mais num livro de 280 páginas.

Demonstrações no melhor estilo matemático são muito estimulantes. Matemáticos gostam de obrigar outros matemáticos a pensar. É gostoso quando a gente pega uma demonstração elegante e sintética e a consegue compreender. Contudo, quando olho os teoremas que eu mesma provei, com frequência não consigo me lembrar de todos os passos: eu olho aquilo, que eu mesma escrevi, e não consigo entender tudo de primeira. De certa forma, me relaciono com o texto como se fosse uma leitora comum, e não sua autora. Até hoje, antes de dar uma aula, eu me preparo: revejo todas as demonstrações que pretendo explicar durante a aula, revejo por que certas coisas implicam outras coisas, para não acontecer de pôr alguma coisa no quadro que não possa explicar rapidamente. E olha que estou dando o mesmo curso de introdução à teoria dos jogos há 15 anos! {FIM DA ENTREVISTA}


stock-illustration-76589449-romantic-love-couple-wedding-bride-and-groom


 

{4}/ Matchings ou uniões

Marilda em geral usa a palavra “matchings”, que, nesta reportagem, foi trocada por uniões, pares, combinações, casamentos, conforme o contexto. Uniões fazem parte da teoria dos jogos cooperativos; é a parte da teoria na qual os participantes do jogo só ganham alguma coisa quando se juntam em coalizões. “Um exemplo”, diz Marilda, “é a união entre patrão e empregado. O patrão precisa do empregado para obter o lucro; o empregado precisa do patrão para obter o salário. Se ambos não conseguem se juntar numa coalizão, não ganham nada.”

O analista pode pensar nisso como dois conjuntos disjuntos de jogadores, sendo que o objetivo do jogo é formar coalizões. Num formato mais simples, os jogadores formam pares — o que se parece muito com um casamento, e por isso o especialista em teoria dos jogos com frequência recorre à imagem do casamento para explicar algum ponto da teoria. Se houver dois conjuntos, um com cinco homens (h1, h2, h3, h4, h5), outro com cinco mulheres (m1, m2, m3, m4, m5), o analista pode compor 120 maneiras distintas de casar essas 10 pessoas. (Excluindo, claro, casamentos homossexuais…) Cada uma dessas maneiras (ou cada um desses subconjuntos do conjunto das 120 maneiras possíveis) é chamada de casamento, no singular. Assim, {(m1, h1), (m2, h2), (m3, h3), (m4, h4), (m5, h5)} é um casamento; {(m1, h2), (m2, h3), (m3, h4), (m4, h5), (m5, h1)} é outro casamento; ambos são subconjuntos do conjunto com os 120 casamentos possíveis. Alguns desses casamentos são estáveis, isto é, duradouros; alguns são instáveis, pois contêm pelo menos um “par bloqueante” — um par no qual um dos cônjuges gostaria de desfazer o casamento atual para se casar de novo, e que tenha a capacidade de fazer isso.

Para visualizar a força da teoria, o analista troca homens por escolas e mulheres por alunos; homens por empresas e mulheres por funcionários; homens por doadores de rim e mulheres por receptores de rim; etc. David Gale e Lloyd Shapley provaram, com um algoritmo, que em situações assim o analista sempre acha no mínimo um casamento estável, isto é, um casamento no qual não existem pares bloqueantes. Um dos cônjuges pode até desejar o cônjuge de outro casal, mas seu desejo não é correspondido, e por isso o infeliz tem de achar um jeito de se dar por feliz com o cônjuge atual.


stock-illustration-21579020-abstract-net-background


 

{5}/ O algoritmo Gale-Shapley

O analista supõe que os homens hk sabem tudo o que precisam saber sobre as mulheres mp, e vice-versa. (O número k de homens não precisa ser igual ao número p de mulheres para que o algoritmo funcione.) Também supõe que cada homem listou as mulheres com as quais gostaria de se casar em ordem de preferência, da mais preferida à menos preferida; o mesmo para as mulheres. Caso o analista permita que os homens proponham casamento às mulheres, o algoritmo funciona assim (mais ou menos):

1) O homem h1 propõe casamento à primeira mulher de sua lista (m1).

2) Se a mulher m1 está livre, h1 e m1 ficam noivos.

3) Se a mulher m1 está noiva, mas prefere h1 a seu noivo atual, m1 dispensa seu noivo atual e h1 e m1 ficam noivos. (Neste algoritmo, diz Marilda, não existem aceites definitivos: as mulheres sempre podem trocar o homem atual por um homem mais querido.)

3) Se a mulher m1 rejeita h1, h1 propõe casamento à segunda mulher de sua lista (m2).

4) Assim que h1 estiver noivo ou não tiver mais a quem propor casamento, o analista dá a vez ao homem h2, e repete todo o processo para h2.

5) E assim por diante para todos os homens hk. O algoritmo só termina quando todos os homens ou estão noivos ou já não têm a quem propor casamento. (Que dó!)

Se o número de homens é igual ao de mulheres, todos se casam. Os matemáticos já puderam provar várias coisas sobre o algoritmo:

● Visto que os homens propõem, o algoritmo Gale-Shapley produz o casamento estável ótimo para os homens, isto é, nenhum homem desse casamento verá nenhuma vantagem em nenhum outro casamento estável.

● Visto que os homens propõem, o algoritmo produz o pior casamento estável para as mulheres, caso o casamento ótimo para os homens seja diferente do casamento ótimo para as mulheres. Em outras palavras: se os homens propõem, e se o casamento ótimo para os homens é diferente do casamento ótimo para as mulheres, então pelo menos uma mulher deste casamento verá todas as vantagens do mundo em ter qualquer outro casamento estável. Contudo, não terá o poder de mudar o casamento atual, pois todos os homens estão contentes com o que obtiveram.

● Porque o algoritmo produz um casamento estável, isso significa que não existe no casamento assim produzido nenhum par bloqueante, isto é, nenhum homem que deseje uma mulher de outro casal, e cujo desejo seja correspondido — ou vice-versa.

● Caso o número de homens seja diferente do número de mulheres, ou caso homens e mulheres não sejam obrigados a incluir todos os membros do sexo oposto na sua lista (algo do tipo “se eu não me casar com m1, m5 ou m7, daí não me caso com ninguém”), então o conjunto dos homens e mulheres sem par é o mesmo em todos os casamentos estáveis.

● Na verdade, o algoritmo é muito forte: nenhum jogador consegue um casamento melhor do que aquele obtido pelo algoritmo, seja casamento estável, seja casamento instável. Mas esse é um detalhe técnico difícil de explicar.


stock-illustration-21139047-pulling-up-an-arrow


 

{6}/ O NRMP e “desenho de mercado”

NRMP é a sigla de National Resident Matching Program, ou programa americano de alocação de médicos residentes. A missão dos funcionários do NRMP é alocar estudantes de medicina, no estágio da residência, a hospitais.

Antes da criação do NRMP, ninguém nos Estados Unidos ficava contente com a alocação de residentes — nem hospitais, nem estudantes. Depois da criação do NRMP, todos pararam de reclamar. Por quê?

Num artigo de 1984, Alvin Roth mostrou que, antes do NRMP, o algoritmo de alocação gerava pares bloqueantes; depois do NRMP, o algoritmo gerava casamentos estáveis, isto é, sem pares bloqueantes. Para afirmar isso, Alvin precisou estudar o NRMP a fundo (com a cooperação do próprio NRMP): ele e seus colegas examinaram milhares de registros, atas de reunião, essas coisas. Feito o estudo, publicado o artigo, Alvin foi além: usou o que descobriu, e seus conhecimentos de matemática e de teoria dos jogos, para propor melhorias no NRMP. As melhorias foram implementadas, e o NRMP passou a funcionar ainda melhor. Nascia assim a expressão “desenho de mercado”: pegue um mercado, estude esse mercado em detalhes, e use a matemática mais moderna a seu alcance para fazê-lo funcionar melhor. {FIM}


stock-illustration-6193405-woman-don-t-cry

Observação: Publiquei esta reportagem pela primeira vez na revista Cálculo: Matemática para Todos, edição 29, junho de 2013, pág. 16. A versão que acabou de ler foi revista e corrigida.