Mostrando postagens com marcador teoria dos jogos. Mostrar todas as postagens
Mostrando postagens com marcador teoria dos jogos. Mostrar todas as postagens

quarta-feira, 26 de dezembro de 2012

Conhecimento Comum

Há umas três semanas atrás eu escrevi sobre teoria dos jogos, um assunto pelo qual eu tenho muito interesse, mais particularmente sobre o problema conhecido como Dilema do Prisioneiro. Naquele post eu comentei os prós e contras de cada possível estratégia, sempre considerando a premissa original de que cada prisioneiro tem que tomar sua decisão sem conhecer a decisão do outro. Partindo desta premissa, e não levando em conta nenhum outro interesse que não o interesse de cada prisioneiro em diminuir a própria pena, testemunhar contra o outro prisioneiro é a Estratégia Dominante.


Essa estratégia tem um porém. Por um lado, se o Prisioneiro A testemunhar e o Prisioneiro B ficar em silêncio, o Prisioneiro A realmente fica com a melhor solução possível, que é ser libertado; no entanto, se o Prisioneiro B também testemunhar, o Prisioneiro A fica não com a segunda melhor solução (sentença de 1 ano), e sim com a terceira melhor opção (5 anos). Assim, ao usar a estratégia dominante, um prisioneiro tem 50% de chances de ser libertado, caso o outro opte por ficar em silêncio, e 50% de chances de pegar 5 anos de cadeia, caso o outro também escolha testemunhar (e, caso os dois façam essa mesma análise da situação, é isso que vai acontecer). 

Mesmo que os dois prisioneiros pudessem se comunicar, ou se tivessem combinado previamente uma estratégia para o caso de serem capturados, seria impossível chegar a um acordo em que os dois fossem libertados. Seria possível, porém, chegar a um acordo em que ambos recebessem uma pena de 1 ano (a segunda melhor solução). Assim, ao invés de uma estratégia "cada um por si" em que cada um teria 50% de chances de conseguir a melhor solução e 50% de chances de conseguir a terceira melhor, eles poderiam escolher uma estratégia em que ambos teriam a garantia de conseguir a segunda melhor solução. Ao adotar esta estratégia de colaboração, os prisioneiros estariam trocando a possibilidade de uma solução ótima pela certeza de uma solução boa. É uma boa estratégia para quem prefere correr menos riscos, ou para situações em que os dois se importam um com o outro o suficiente para um não querer prejudicar o outro, mas não o suficiente para estarem dispostos a se sacrificar um pelo outro.

Obviamente, essa estratégia depende do quanto um prisioneiro confia no outro, já que, mesmo que eles combinem uma estratégia juntos, cada um vai cumprir (ou não) a sua parte do acordo separadamente. Mas existe um outro conceito importante de teoria dos jogos que precisa ser levado em conta ao escolher-se uma estratégia: o conceito de Conhecimento Comum.

Conhecimento comum é mais do que algo que as duas partes sabem: é algo que uma parte sabe, a outra parte também, e uma sabe que a outra sabe. No exemplo dos dois prisioneiros, mesmo um confiando no outro, para que a colaboração seja possível, é necessário que:
  1. Os dois conheçam essa estratégia e suas vantagens. Se um dos dois não souber que podem diminuir o risco adotando uma estratégia de colaboração, este vai adotar a estratégia dominante e adeus, colaboração.
  2. Cada um saiba que o outro também sabe disso. Mesmo sabendo que a estratégia de colaboração oferece menos risco, se um prisioneiro não souber que o outro também sabe disso, ele vai assumir que o outro vai adotar a estratégia dominante (testemunhar) e, para se defender, vai testemunhar também. Novamente, adeus colaboração.
Assim, para que os dois prisioneiros colaborem, é preciso que as vantagens da estratégia de colaboração sejam conhecimento comum. Caso contrário, um deles (ou ambos) vai ter que assumir o risco e torcer para o outro saber o mesmo que ele.

Espero não ter feito uma confusão danada com esse negócio de "eu sei que você sabe que eu sei que você sabe etc". Na próxima vez que eu escrever sobre teoria dos jogos, vou falar mais sobre isso.

segunda-feira, 3 de dezembro de 2012

O Dilema do Prisioneiro

Eu acho teoria dos jogos um assunto fascinante. Tive meu primeiro contato com o assunto através de um livro cujo nome agora me escapa, porque a história em si não me causou muita impressão. O livro era de ficção, mas tinha uma cena logo no início em que um dos personagens explicava para o outro o Dilema do Prisioneiro, e foi o suficiente para eu me interessar pelo assunto. A teoria dos jogos é utilizada na análise de situações estratégicas em que os participantes têm que escolher um dentre vários possíveis cursos de ação e tomar decisões tentando chegar ao melhor resultado possível. Ou seja, praticamente qualquer situação com mais de um participante envolvido. O termo "jogo", nesse caso, se refere não a uma atividade recreativa e sim a qualquer situação em que um indivíduo tem que tomar decisões sabendo que suas escolhas irão influenciar um resultado final mais ou menos favorável para ele (inclusive, claro, jogos recreativos).

Alguns anos depois, eu descobri o Open Yale Courses. A Universidade de Yale disponibiliza online vários cursos super interessantes e entre eles, pra minha alegria, um de Teoria dos Jogos oferecido pelo Departamento de Economia. Trata-se de cursos que são presenciais para os alunos da universidade e que são disponibilizados de forma gratuita para o público em geral no site da universidade. Apesar de não darem direito a nenhum tipo de certificado ou crédito para os alunos ouvintes, os cursos são ministrados levando em conta o público online: o professor sabe que existe gente assistindo o curso à distância e dá todo o curso se dirigindo a essas pessoas tanto quanto aos alunos presentes em sala de aula. É possível assistir (e baixar) todas as aulas (vídeo, áudio, transcrições das aulas e todo o material escrito fornecido para os alunos do curso presencial): até o que o professor escreve no quadro é fotografado e disponibilizado de forma organizada para os alunos ouvintes. A única coisa que não dá pra fazer é tirar dúvidas com o professor ou entregar os trabalhos para avaliação.

Enfim, voltando ao Dilema do Prisioneiro. A representação clássica desse problema é a seguinte:

Existem dois prisioneiros: Prisioneiro A e Prisioneiro B. Eles são colocados em celas separadas e sem possibilidade de comunicação um com o outro, e a ambos é oferecido o mesmo acordo: se um deles testemunhar contra o outro e o outro permanecer calado, o que testemunhou será libertado e o que ficou em silêncio será condenado a 10 anos de cadeia. Se os dois ficarem em silêncio, cada um será condenado a 1 ano de cadeia. Se ambos testemunharem um contra o outro, cada um será condenado a 5 anos de cadeia. Como os prisioneiros estão incomunicáveis, cada um vai ter que tomar a sua decisão sem saber qual a decisão que o outro vai tomar, daí o dilema. Os números podem variar, mas a ideia, essencialmente, é esta:


Analisando o problema de forma 100% egoísta, o Prisioneiro A pensa: "Cinco anos é melhor do que dez, e ser libertado é melhor do que um ano. Independente do que o Prisioneiro B faça, a melhor opção para mim é testemunhar contra ele." Em teoria dos jogos, diz-se que, neste caso, testemunhar contra o outro prisioneiro é a Estratégia Dominante.

Estratégia dominante é aquela que trará o melhor resultado para quem a adotar, independente do que a outra parte faça. Neste caso, se B testemunhar contra A, A vai obter um resultado melhor se testemunhar contra ele (5 anos de cadeia ao invés de 10) e, se B ficar calado, A também vai obter um resultado melhor testemunhando contra ele (ser libertado ao invés de pegar 1 ano de cadeia). E a recíproca é verdadeira: quer A testemunhe contra B, quer fique calado, B obterá um resultado melhor testemunhando contra ele. Desta forma, um testemunha contra o outro e ambos pegam 5 anos de cadeia cada um.

Para determinar que uma estratégia é a estratégia dominante, no entanto, é essencial definir o que é significa "melhor resultado" para o jogador. Se estivermos simplesmente comparando números (5 < 10 e 0 < 1), testemunhar contra o outro prisioneiro é sem dúvida a estratégia dominante, mas, ao aplicar esse problema ao mundo real, outras variáveis são introduzidas.

A análise inicial do problema foi feita considerando que a única preocupação de cada prisioneiro é receber a pena mais curta possível ou, de preferência, ser libertado imediatamente: as implicações dessa estratégia para o outro prisioneiro são irrelevantes. Neste caso, testemunhar contra outro prisioneiro é sem dúvida a estratégia dominante. Quantificando os resultados, temos:


Agora, se incluirmos na equação o peso de testemunhar contra outra pessoa, sabendo que isso fará com que ela vá para a cadeia, os resultados mudam.

Se, para o Prisioneiro A, a ideia de se beneficiar prejudicando o Prisioneiro B causa muita angústia e sentimento de culpa, a pontuação da estratégia "testemunhar contra o outro" diminui, pois a culpa por aumentar a pena do outro diminui a satisfação de diminuir a própria pena. Se a culpa neste caso valer 10 pontos negativos, a estratégia dominante para o Prisioneiro A passa a ser ficar em silêncio: a indulgência prometida por colaborar com a polícia não compensa a culpa que ele vai sentir por ter prejudicado o Prisioneiro B.


No outro extremo do espectro, temos o Prisioneiro B com tanta raiva do Prisioneiro A que o fato de estar aumentando a sua sentença é um bônus na satisfação de estar diminuindo a própria. Com isso, a pontuação da estratégia "testemunhar contra o outro" aumenta. No exemplo abaixo, a satisfação por prejudicar o outro vale 5 pontos.


Outros aspectos cruciais a considerar são as interações futuras entre os prisioneiros (um dia o prisioneiro que pegou a pena maior vai sair da cadeia e encontrar aquele que o entregou) e como a decisão de testemunhar ou não contra outro prisioneiro vai influenciar a reputação de cada um. Às vezes vale a pena abrir mão de uma vantagem imediata para ganhar a confiança e/ou o respeito da outra parte, tornando mais fáceis as interações futuras. Quando um vendedor alerta o cliente que o produto que ele está prestes a comprar tem um similar mais barato e igualmente eficaz, ele está diminuindo a sua comissão na venda atual, mas pode estar garantindo comissões futuras se a sua honestidade servir para fidelizar o cliente. Por outro lado, a fidelização do cliente pode ter uma pontuação baixa se comparada com a comissão da venda atual se o vendedor estiver com a corda no pescoço para atingir a meta de vendas do mês.

O importante é entender que, para tomar uma decisão, saber quais serão as consequências de cada possível estratégia é essencial, mas não mais essencial do que saber qual é a "pontuação" de cada alternativa para o jogador. O que para uma pessoa é um preço alto demais para pagar, para outra é um sacrifício que vale a pena e vice-versa.

Quando eu tiver paciência de escrever mais sobre o assunto, vou continuar esse post falando sobre colaboração.