Luciano Huck coloca um Dilema dos Prisioneiros na TV

Versões televisivas do dilema dos prisioneiros não são incomuns. Silvio Santos em 2002 decidiu implementar um jogo chamado 7 e Meio em que na final dois oponentes, depois de terem derrotado outros adversários, ficavam frente a frente no palco e escolhiam entre o 7, que significava tentar ficar com o prêmio inteiro (não cooperando com o oponente) ou 1/2 (Meio), aceitando partilhar o prêmio (em que, no caso, os dois dividiriam uma quantia menor).

Sabendo-se que o Silvio Santos está sempre ligado no que acontece em programas de auditório dos Estados Unidos, é bem provável que o famoso patrono da SBT tenha copiado o 7 e Meio de versões televisivas do jogo que foram ao ar nos Estados Unidos.

O Dilema dos Prisioneiros é um dos jogos mais exemplares do estudo de economia e de Teoria dos Jogos. É bastante utilizado para se exemplificar o conceito de Equilíbrio de Nash e explorar suas consequências e conceitos. O jogo batizado foi por A. W. Tucker (orientador do Nash) de "Dilema dos Prisioneiros" e foi proposto pelos matemáticos Merrill Flood e Melvin Dresher, que tentaram entender melhor o recém publicado trabalho de John Nash de 1951, que definia um conceito de equilíbrio diferente daquele de maximin/minimax estipulado por Von Neumann e Morgenstern no livro que lançou os fundamentos da área de teoria dos jogos (Theory of Games and Economic Behaviour). O Dilema dos Prisioneiros pode ser definido de diversas formas, uma das mais interessantes descrições que encontrei sobre o jogo foi a que está presente no documentário The Trap Ep.2 (documentário crítico da BBC bastante interessante sobre Teoria dos Jogos, Economia, Política e tudo mais). O texto do documentário expõe o jogo da seguinte forma (tradução livre):

"Um jogo famoso foi desenvolvido na RAND para mostrar que, em qualquer interação, o egoísmo sempre leva para um resultado mais seguro. Ele foi chamado de "Dilema dos Prisioneiros". Há muitas versões, mas todas elas envolvem dois jogadores que devem decidir confiar ou trair um ao outro. Imagine que você roubou o diamante mais valioso do mundo. Você ficaria feliz em vendê-lo a um perigoso gangster, ele propôs encontrá-lo para que você fizesse a troca pelo dinheiro, mas você acha que ele poderá te matar. Então, ao invés disso, você oferece a ele levar o diamante para um lugar remoto (remote field, no original) e escondê-lo. Ao mesmo tempo, ele deverá ir para outro lugar remoto, a milhas de distância, e esconder o dinheiro. Então, você ligará para ele e cada um contará ao outro o lugar do esconderijo. Mas segundos antes de fazer essa ligação você percebe que você pode traí-lo: você fica com o diamante e pode ir pegar o dinheiro (enquanto isso o gangster se dirigiria para uma busca infrutífera em um lugar vazio). Mas no mesmo exato momento, você percebe que ele provavelmente está pensando na mesma coisa que você e que ele pode traí-lo. Não há como você prever como a outra pessoa irá se comportar. Este é o dilema. Mas o que as equações de Nash mostraram é que a escolha racional [deste jogo] é sempre trair a outra pessoa, pois dessa maneira, no pior caso, você ficará com o diamante, e no melhor deles, ficará com o diamante e o dinheiro. Mas se você confiar na outra pessoa você se arriscará a perder tudo pois ela poderá traí-lo, isto foi chamado de payoff do otário."

Não é que hoje vi rapidamente na televisão uma versão revisada do jogo no programa Caldeirão Do Huck. Na versão do Huck o jogo foi chamado de "Quem Fica Com Tudo?". Não vi o programa inteiro, parece que na versão do Huck também haviam mais jogadores, e dois foram selecionados para se aporem frente a frente na final. Pois bem, no programa transmitido de hoje havia duas jogadoras: Dahyanna e Laura. Na etapa final as jogadoras tinham duas opções: "Ficar com Tudo" (F) ou "Dividir" (D). Se ambas decidissem ficar com tudo (declarar F) ninguém ganharia nada. Se apenas uma delas decidisse dividir (declarar D) e a outra decidisse ficar com tudo (declarar F), a pessoa que declara F sozinha leva o maior prêmio e a que escolheu dividir fica com nada. Caso as duas escolham dividir elas ficam com um prêmio menor (asseguram o que elas já haviam conseguido na etapa anterior).

Vamos chamar de 'T' o maior premio e de 'm' o prêmio assegurado pela divisão. Caso os jogadores não cheguem num acordo eles ficam com zero. Suponhamos então que T > m > 0. O Dilema dos Prisioneiros apresentado no programa do Huck é uma forma ainda mais cruel do que sua versão original, pois o jogo não possui estratégia dominante e trair mutualmente não dá garantia nenhuma para nenhum dos jogadores. Vejamos o jogo do programa na sua forma normal em que os payoffs de Dahyanna são apresentados no lado esquerdo do parenteses e o de Laura no lado direito:

--------------------------_______________________

--------------------------|-----|-----Laura-----|

--------------------------|_____|_______________|

--------------------------|-----|-------|-------|

--------------------------|-----|---F---|---D---|

--------------------------|_____|_______|_______|

--------------------------|-----|-------|-------|

--------------------------|--F--|-(0,0)-|-(T,0)-|

---------------Dahyanna---|_____|_______|_______|

--------------------------|-----|-------|-------|

--------------------------|--D--|-(0,T)-|-(m,m)-|

--------------------------|_____|_______|_______|

Ao contrário do Dilema dos Prisioneiros usual, que possui apenas um equilíbrio, o jogo acima possui três equilíbrios de Nash, a saber as ações FF, FD ou DF. Quando estava assistindo o programa formulei rapidamente a matriz para conferir se o resultado do jogo coincidiria com a predição do equilíbrio. Na verdade, eu esperava mesmo que o equilíbrio não se verificasse dado que existem estudos mostrando que as pessoas tendem a cooperar mais (talvez uma certa aversão ao risco se aplicasse sobre as utilidades daqueles payoffs). O que me levantava a dúvida era de que, ao que me parecia, os prêmios de m eram muito menores do que os de T, ou seja, cooperar (Dividir) não dava nenhuma grande vantagem às jogadoras já que T >> m. Ainda assim, o resultado final permanecia um mistério, pois o jogo acima possui três equilíbrios e não apenas um único.

O resultado final de hoje foi o equilíbrio abaixo assinalado:

--------------------------_______________________

--------------------------|-----|-----Laura-----|

--------------------------|_____|_______________|

--------------------------|-----|-------|-------|

--------------------------|-----|---F---|---D---|

--------------------------|_____|_______|_______|

--------------------------|-----|-------|-------|

--------------------------|--F--|-(0,0)-|-(T,0)-|

---------------Dahyanna---|_____|_______|_______|

--------------------------|-----|-------|-------|

--------------------------|--D--|-(0,T)-|-(m,m)-|

--------------------------|_____|_______|_______|

Dahyanna decidiu jogar "Ficar com Tudo" e Laura decidiu na última hora "Dividir". Mais uma diferença em relação ao Dilema dos Prisioneiros original ocorreu no programa do Caldeirão do Huck: no jogo original os jogadores não se comunicam antes de tomarem suas decisões e no programa do Caldeirão isso era estimulado e televisionado. Laura ameaçou Dahyanna dizendo que iria jogar "Ficar com Tudo", mas que poderiam depois, em acordo externo ao que parece, 'rachar' o dinheiro. Ou seja, Laura acrescentou mais uma dimensão ao jogo (veja a forma extensiva abaixo), porém, Dahyanna rechaçou verbalmente a proposta dizendo que não podia confiar na Laura (afinal se Laura jogasse F ela não tinha realmente o que fazer e se tornaria indiferente). O final foi que Laura não manteve sua ameaça e jogou "Dividir" e Dahyanna jogou para ficar com tudo, deu o equilíbrio acima assinalado.

Como o jogo colocou uma comunicação, vamos analisar se a proposta da Laura era realmente crível. Para isso vejamos o jogo na forma extensiva. Laura propôs dividir o prêmio total caso Dahyanna concordasse em Dividir na primeira etapa, e sabemos que os valores de m são muito baixos, então, dividir o prêmio principal é ainda melhor que colaborar na primeira rodada (T/2 > m). No entanto, a proposta de colaboração da Laura não era crível como se diz em Teoria dos Jogos, pois nada poderia garantir à Dahyanna que Laura coloboraria depois do jogo encerrado, ou seja, que dividiria o prêmio maior. Vemos que os equilíbrios não se alteram de maneira nenhuma.

Figura 1 - Versão do Jogo na forma extensiva com alguma, simultâneo na primeira mas com uma proposta de divisão na segunda rodada.

Um melhor comportamento para a Laura seria parecer mais ameaçadora, fazendo Dahyanna de fato acreditar que ela jogaria F em qualquer circunstância. Ainda que isso deixasse Dahyanna indiferente, ganhando zero, isso aumentaria as chances de se pensar que uma cooperação posterior seria possível. Também ajudaria caso Laura tentasse mostrar que não atingir uma cooperação (os payoffs 0,0) é na verdade uma situação pior do que as outras situações, ou tentar mostrar que gostaria de ficar no (0,0) só para ver a amargura da adversária. Isso envolveria jogar com a subjetividade do outro e com a própria, sendo que os payoffs se tornariam mais subjetivos.

Finalmente, não dá pra prever muito o que vai acontecer nos jogos seguintes do "Quem Fica com Tudo?" isso porque existem três equilíbrios diferentes. Outro ponto interessante é que as pessoas podem aprender assistindo aos outros programas, se o aprendizado ocorrer, o equilíbrio FF pode se tornar mais comum. Porém, com o tempo, se FF é bastante comum, os jogadores podem aprender sobre isso e atingir um equilíbrio DD, mas se isso se tornar comum, desviar pode se tornar uma vantagem, enfim, uma série de considerações de jogos repedidos com jogadores diferentes pode acontecer aqui e a coisa ficar mais complexa.

P.S.: Em breve volto aqui para falar do IWGTS 2014 do qual participei como ouvinte nessa semana que se encerrou. O blog Prosa Econômica já postou sobre isso em um material com excelentes fotos.

Algoritmos de casamentos estáveis (sobre o Nobel de economia de 2012)

Caros leitores,

Segue uma matéria interessante do site da FEA/USP sobre a área em que estou trabalhando na minha tese de doutorado. Com previsão pra acabar AGORA!! :-) (espero em breve por convite para defesa).

Eis aqui o link e o texto:

http://www.fea.usp.br/noticias.php?i=1012

Palestra explica teoria do matching

Graduada em matemática em 1967, com décadas de experiência e seis pós-doutorados na bagagem, a professora Marilda Sotomayor foi a responsável pela apresentação "Matching vai à Estocolmo". Organizada pelo departamento de Economia e pelo CAVC, a palestra tinha como objetivo explicar o uso da teoria do matching e seu papel no trabalho de Alvin Roth e Lloyd Shapley, laureados com o prêmio Nobel em 2012.

O evento, que lotou a Sala da Congregação no dia 13 de novembro, se iniciou com uma breve explicação a respeito da teoria dos jogos, da qual o matching é um dos ramos. "Um jogo é um modelo matemático, uma representação abstrata de situações da vida real em que dois ou mais tomadores de decisão, que chamamos de jogadores, interagem de acordo com regras pré-estabelecidas e suas decisões afetam um ao outro.", explicou a professora, "A teoria dos jogos é um ramo da matemática que estuda o comportamento desses tomadores de decisão", completou. Podem ser feitas ainda duas distinções: a dos jogos cooperativos (em que os jogadores podem cooperar e formar as chamadas "coalizões") e não cooperativos (cada jogador joga apenas por si próprio).

"Informalmente, um matching é um pareamento entre os jogadores que não viola as regras do mercado. No mercado de casamentos, por exemplo, um matching é um conjunto de casamentos monogâmicos", disse a professora.

O marco inicial da pesquisa no ramo data de 1962, quando foi publicado, em uma parceria entre o próprio Shapley e o matemático David Gale, falecido em 2008, o artigo "College admissions and the stability of marriage". O artigo formula e resolve o problema da admissão de estudantes às universidades através de uma distribuição estável e satisfatória. A dupla desenvolveu um algoritmo que solucionava esse problema. Em 1975 foi descoberto por Gale que este algoritmo já estava sendo usado desde 1951 nos Estados Unidos para distribuir os médicos pelos hospitais, onde eles tinham de fazer um ano de residência. Este fato foi provado e divulgado oficialmente em 1983 num trabalho de David Gale e Marilda Sotomayor.

As evidências apontam que o trabalho mais relevante da teoria de matching foi, sem dúvida, o livro "Two-sided matching. A study in game-theoretic and analysis", de autoria de Roth e Sotomayor e publicado em 1990. Este livro compila toda a teoria existente até a sua publicação e um de seus maiores feitos foi atrair a atenção dos economistas para a área de matching. "Até então, matching era considerado coisa de matemático e para matemáticos", informa a professora. Segundo o Mathematical Reviews, dentre todas as publicações de Roth, o livro é, de longe, a que mais citações tem. A segunda publicação mais citada de Roth tem um terço das citações do livro. Os autores foram laureados com o Lanchester Prize de 1990 e foram homenageados em 2010 com o congresso "Roth and Sotomayor: Twenty years after", para celebrar os vinte anos da publicação do livro.

Alguns anos após a publicação do livro, enquanto Marilda Sotomayor continuava a liderar a teoria, Alvin Roth passou a liderar as aplicações de matching à Economia: Desenho de Mercados e transplante de órgãos. "Atuou na organização dos mercados de escolha de escolas públicas de primeiro grau em Boston e em Nova York. Modelou o mercado de transplante de rins como um mercado de matching e então, usando um algoritmo devido a Gale, conhecido na literatura como "top-trading cycles" propôs uma reformulação no sistema de alocação de rins para pacientes", disse a professora.

"O prêmio Nobel outorgado a Roth e Shapley representa uma vitória de todos os autores que contribuíram com seus trabalhos para o desenvolvimento dessa teoria", concluiu Marilda.

Para quem quiser aprender sobre o tema, eu escrevi umas modestas palavras em dezembro de 2011 sobre um dos matemáticos envolvidos na confecção do algoritmo inicial.

Outo lugar de consulta pode ser essa video-aula que descobri recentemente sobre o assunto, está bem didática:

Alguns Problemas Matemáticos Interessantes

Pessoal, algumas novidades do mundo econômico têm aparecido aí no fim de ano, algumas animadoras, outras nem tanto. Todos devem ter acompanhado a ascenção do Brasil para 6ª Economia mundial e visto os destaques da inflação, superávit primário e outros tópicos. Bom, como microeconomista que sou, não vou me concentrar nesses assuntos por hoje. Sobre a questão do 6º lugar, digo que é uma notícia boa e interessante, mas há bem pouco tempo, ainda no "Brasil-novo" pós 2003, estavamos em 11º. Enfim, se colocação de tamanho de PIB fosse indicativo de qualidade de vida para seus concidadãos a China já estava bem a muito tempo. A notícia é interessante para reforçar o tamanho de nossa economia.

Mas me concentro aqui em temas mais microeconômicos e matemáticos e alguns assuntos que aguardam um pouco para entrarem aqui no Blog. Um deles é um comparativo usando densidade relativa para saber qual é o melhor disco dos Beatles. Qual é o seu preferido?! Outro assunto nesse tema, e por vir aqui, é uma aplicação estatística ao problema de detecção de comportamentos diferentes: "o problema do chefe". Outro é um joguinho de Sodoku que fiz para o R, ainda não está pronto, pois meu algoritmo tenta achar um jogo válido entre os zilhões de jogos possíveis! A idéia do meu algoritimo é achar primeiro uma solução e depois cobrir os números de acordo com a facilidade que o jogador desejar. O fácil deve cobrir poucos números, o médio um pouco mais e assim por diante. Li em algum lugar que o Sudoku super profissional conta com apenas 16 números no grid inicial.  Os interessados já podem encontrar o jogo em um pacote "Sudoku" já disponível no R. Pelo menos a janelinha do meu sudoku (a da foto acima) é mais bacana. Quem não tem costume de usar o R e mesmo assim quer jogar um Sudoku e gerar jogos veja aqui nesse site.

Mas o propósito desse post no momento é convidá-los a conhecer o Problema do Casamento Estável (um joguinho muito interessante e didático), também conhecido como problema da dança de salão, desenvolvido pelo professor David Gale (1922-2008), da foto aí do lado, mais particularmente o algoritmo Gale-Shapley proposto em artigo de 1962. O problema consiste em alocar as pessoas de acordo com suas preferências da melhor maneira possível para os proponentes e que não dê empate. Imagine um salão de dança com o mesmo número de homens e mulheres. Esse problema envolve a escolha de um parceiro para a dança de acordo com as preferências. Suponhamos que os homens convidem primeiro as mulheres para dançar, então os homens propõem primeiro à mulher preferida. Mas e se mais de um homem convidar a mesma mulher para dançar? Então a mulher terá opção de escolha de acordo com as suas preferências. O problema pode ser invertido, com as mulheres propondo primeiro. O interessante é que nem sempre as soluções serão idênticas, o grupo que propõe primeiro tem maior chance de estar melhor, no mínimo estará igual a situação em que o outro grupo propõe. Um dos principais nomes nessa área é a profa. Marilda Sotomayor da faculdade de economia da USP que desenvolveu essa área, um dos seus artigos mais importantes é com o prof. Gale. Além disso é co-autora com Alvin Roth, outro nome importante da área, do livro "Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis".

Há poucos dias meu orientador, o prof. Eduardo Rios-Neto, me propôs lidar com esse problema para vermos uma questão de como são alocados os alunos de escolas públicas, uma aplicação importante que procura responder: "Será que podemos melhorar nosso ensino alocando melhor os estudantes?". E me debrucei a tentar o algoritmo na linguagem R, que tenho mais familiaridade. Hoje postei o resultado disso no R-Nabble, comunidade para usuários e desenvolvedores do R-project. Convido a todos que tiverem interesse, e lidam com o R, a me ajudarem e melhorar o algoritmo. É importante testá-lo para novos desenvolvimentos da aplicação de alocação de alunos entre escolas.

Um exemplo interessante de aplicação é a dissertação de Felipe Bardella mestrado da USP. Em que ele estudou a relação de preferências que os alunos candidatos da ANPEC faziam para o exame e os resultados da seleção. Suas conclusões levam que o mercado da ANPEC passou por um tempo de aprendizado e que se trata de um mercado descentralizado com solução próxima a do algoritimo NRMP. Os centros mais bem rankeados tem maior facilidade em fazer valer sua ordenação de preferências sobre os candidatos, os demais centros tem mais dificuldades o que insere maior instabilidade do processo para eles. Uma sugestão da dissertação de Bardella não foi ainda adotada pela ANPEC. Adoção de uma listagem maior do que 6 centros que é atualmente feita.