SEÇÃO I

» 4ª Unidade: Modelos de Jogos

• Ruído, Alternância e Evolução.

Da mesma forma que os jogos de soma zero não eram suficientes para descreverem todo tipo de interação entre dois agentes racionais, o modelo padrão do Dilema dos Prisioneiros Iterado apresentava muitas limitações em sua representação das relações sociais ou biológicas, em um nível mais profundo. Acrescentar elementos presentes em interações reais, que por simplicidade foram inicialmente omitidos, tornaria a simulação mais precisa, apesar de sua complexidade. Afinal, ruídos, equívocos, troca de papéis e evolução da posição dos agentes são frequentes nas relações observada no dia-a-dia dos organismos vivos.

Durante o período da Guerra Fria (1945-1989), não raro, enganos eram cometidos sob a suspeita de espionagem por partes dos dois blocos políticos rivais - soviéticos e capitalistas. Lamentavelmente, alguns desses erros eram fatais. Houve casos de aviões de passageiros terem sido abatidos por sobrevoarem próximos à fronteira das regiões mais conflitantes. Em 1983, 269 pessoas a bordo de um aparelho de uma empresa aérea sul koreana foram sacrificados em nome da segurança militar e suspeita de espionagem, quando o avião invadiu o espaço aéreo da extinta União Soviética. Erros são uma constante na vida de seres racionais imperfeitos. Apenas ignorá-los pode custar mais caro do que tentar aprender com eles. Nesse sentido, elaborar simulações que consideram a probabilidade de erros e estratégias capazes de aprender com eles, recuperando rapidamente a cooperação, ajuda a depurar a avaliação das condições que permitem a manutenção duradoura e bem sucedida de um empreendimento comum (1).

Jogos simultâneo, com ou sem erro, raramente acontecem no mundo real. Na maioria das vezes, as ações são efetuadas em resposta a uma atitude anterior executa. Alternar a sequência de ações entre agentes permite descrever as relações sociais de forma mais realista. Tendo em mente essas observações triviais, desde que Martin Nowak e Karl Sigmund propuseram modelos de Dilema dos Prisioneiros alternativos, várias estratégias factíveis puderam ser moldadas. Isso proporcionou uma refinada descrição dos comportamentos cooperadores através de estratégias mais sofisticadas.

Métodos de Simulação

Para poder incluir alternância de movimentos e a probabilidade de erros no Dilema dos Prisioneiros repetido, uma forma mais precisa e compacta de apresentar os resultados e estratégias formulados foi proposta. A partir da matriz básica do Dilema dos Prisioneiros e as condições de relacionar os ganhos (T > R > P > S e 2R > T + S). Os valores do modelo padrão de Axelrod, T=5, R=3, P=1, S=0, foram alterados para atender a relação

onde "c" é igual ao pagamento que o jogador recebe quando sua opção é desertar; "a" significa o que ele recebe quando coopera; "b" é o resultado do outro jogador ao cooperar e "d" quando deserta. Logo, para o líder - o primeiro a jogar -, em uma só rodada, desertar é melhor que cooperar, enquanto para o outro, trivialmente a cooperação do líder é melhor que a deserção. Além disso, a diferença entre a deserção e a cooperação para o líder é menor do que o ganho do oponente com sua cooperação em relação à deserção.

Por conta dessas condições em que a simetria entre os jogadores é quebrada no Dilema dos Prisioneiros alternado, enquanto ambos jogam "C", a recompensa será "a" mais "b" (R = a + b); um "D" mútuo equivale a "c" mais "d" (P = c + d); mas se o líder coopera e o outro deserta, aquele receberá "a" pela sua cooperação e "d" pela deserção do outro (S = a + d); finalmente o desertor do cooperador recebe "c" e "b" ao qual é tentado (T = c + b). O que vale dizer que existe uma equação em que

Entretanto, essa igualdade não é satisfeita pela distribuição de valores de Axelrod, que leva ao seguinte resultado:

Contudo, os ganhos T=4; R=3; P=1 e S=0 satisfazem àquela equação (2). Com essa nova tabela pronta, as decisões dos agentes foram restritas a informações de umas poucas rodadas, a fim de tornar difusa a escolha entre "C" e "D" sobre as probabilidades das interações baseadas em uma memória curta. Assim, os erros de avaliação das chances de uma determinada escolha poderiam ser considerados na aplicação de uma regra (3).

Em seguida, estabeleceu-se que os resultados R, S, T, e P de um jogador, na ordem em que aparecem na matriz, desde as opções "C" ou "D", seriam numerados respectivamente como 1, 2, 3 e 4, em um conjunto de ações para um participante, onde p₁ é igual ao resultado da recompensa para ambos na jogada anterior. Então, a estratégia p'= (p'₁, p'₂, p'₃, p'₄) de um jogador passa a ser descrita por meio das escolhas entre 0 e 1, para a probabilidade de cooperar. Desse modo, por exemplo, OPO pode ser instruída pela regra (1, 0, 1, 0) que manda cooperar sempre que o outro coopera (1) e desertar (0), quando tiver recebido "S" ou "P" na rodada anterior. Nos casos extremos, (0, 0, 0, 0) equivale a SEMPRE D e (1, 1, 1, 1), SEMPRE C. Já RANDÔMICA é a estratégia (0.5, 0.5, 0.5, 0.5), ou sempre jogar "cara ou coroa" para saber o que irá fazer a cada lance. PAVLOV, a estratégia vencedora na simulação simultânea com erro - ou ruído -, está contida em (1, 0, 0, 1), isto é, manter a cooperação depois de receber "R" e a deserção com "T"; trocando de posição depois de ganhar "S" e "P".

No modelo alternado de Nowak e Sigmund, generosa OPO (GOPO) foi vitoriosa quando variava suas ações para punição em 2/3 das vezes (1, 0, 1, 2/3). Em sua versão pura, ou determinista, GOPO também é conhecido por FIRM BUT FAIR (FIRME MAS JUSTO) e joga como uma tolerante versão de OPO (1, 0, 1, 1). De fato, FIRME MAS JUSTO (doravante, FMJ) é um híbrido de OPO e PAVLOV.

Lembrar o Passado

David Kraines e Vivian Kraines consideram que o Dilema dos Prisioneiros Alternado (DPA) com probabilidade de erro é a representação mais fidedigna dos encontros entre dois agentes com interesses parcialmente conflitantes. Para ampliar tal simulação a seres inteligentes, incluíram como artifício a possibilidade de se recordar até quatro resultados anteriores. Agentes com memória de quatro lances prévios podem lembrar de duas escolhas atrás feitas por si e seu oponente. De tal modo, que a seleção das estrtégias poderia ser moldada como uma evolução darwiniana (4).

Na maior parte das relações entre indivíduos, as decisões e suas respectivas lições são encaradas alternadamente. A execução sequencial do Dilema é exemplificada por vários exemplos de interações sociais como a retribuição de trabalho entre fazendeiros que colhem suas safras em temporadas defasadas. Ter uma memória que considera as decisões passadas capacita os agentes a recordarem os resultados dos últimos encontros ocorridos entre as partes. Cada uma destas tem de escolher entre cooperar ou desertar alternadamente, durante uma longa série de movimentos indefinidos. Depois que o segundo jogador realizar sua ação, ambos recebem o ganho relativo ao resultado conjunto, como na figura 1.

Figura 1 - DPA (5)
Decisão	1	2	3	4	5	6	7
Jogador I	C	...	D	...	D	...	C
Jogador II	...	c	...	c	...	d	...
Resultados
I	...	R	T	T	T	P	S
II	...	R	S	S	S	P	T

As séries de deliberações executadas de acordo com as escolhas anteriores do outro jogador podem variar, como uma estratégia mista, a uma taxa de probabilidade relativa à sequência ocorrida, enquanto agentes determinados cooperam ou desertam com probabilidade 0 ou 1. A confusão ou erro acontecem entre agentes falíveis, que não são capazes de cooperar ou desertar com segurança absoluta, precisam recorrer a cálculos probabilísticos para terem reveladas a frequência pela qual irão ou não cooperar (6).

Os pagamentos de cada jogador também variam conforme a probabilidade de cada um cooperar e obedecem a um estado de equilíbrio de probabilidade, ou cadeia de Markov, que apresenta uma matriz com os possíveis resultados para cada tipo de estratégia mista (7). O modelo adaptativo dinâmico utilizado partiu de uma população inicial distribuída uniformemente que pratica uma mesma estratégia com grande número de descendentes com uma pequena variação em relação a seus pais. Esses sucessores sobrevivem e passam suas características principais à próxima geração à medida que conseguem obter o maior ganho de sobrevivência.

De um a quatro passos, a capacidade de memorização foi testada no DPA de Kraines e Kraines. A partir do terceiro nível de memória, a estratégia tolerante TOUGH LOVE (AMOR BRUTO - AB) aparece entre as famílias mais bens sucedidas. AB é uma combinação de PAVLOV com OPO. Na verdade, trata-se de uma variedade estocástica de GOPO, que toma decisões variando conforme o padrão (1 - E, E, 1 - E, 1 - E), onde E representa a possibilidade de erro entre 0 e 1 (0 < E < 1). Intuitivamente, é um cooperador recíproco que pune deserções imotivadas e esquece as deserções de um oponente contrito. Permanece firme na punição, quando ao menos três lances anteriores não permitem identificar quem começou a deserção. Porém, ao contrário de PAVLOV não é capaz de explorar a generosidade do outro jogador, caso venha equivocadamente desertar, agindo sem remorso em favor da retomada da cooperação (8).

Nas condições de aleatoriedade de DPA, as características que favoreceram a procriação foram a aptidão para cooperar com estratégias que são idênticas consigo, a capacidade de explorar cooperadores incondicionais e de resistir à exploração de quem sempre deserta. Assim, a memória ampla de jogadores inteligentes permitiria o reconhecimento de seus semelhantes, com os quais cooperariam, atuando como SEMPRE C, enquanto rechaçam todos exploradores contumazes. Memórias de quatro lances atrás, proporcionam a um cenário com 1000 agentes iniciais, ao final de 4000 gerações, com E = 0.01, comportar a formação de grupos de estratégias que usavam protocolos e convenções próprias para restabelecerem a cooperação depois de uma deserção errada. A diferença de protocolos levou cada grupo a sustentar ganhos altos entre aqueles que cooperam com seus pares do que com os de fora do grupo, por não agirem da mesma forma. Destarte, os grupos se tornaram resistentes a invasores, sendo AB uma das estratégias mais efetivas, por repelirem os SEMPRE D e refazerem a cooperação rapidamente com suas cópias, depois de movimentos defeituosos (9).

Embora os jogadores com memória de até quatro lances tivessem apresentado resultados cooperativos avançados, alguns tipos de estratégias evoluíam para estratégias generosas ou caíam na pura deserção, como aqueles que partiam do algoritmo PAVLOV. Nem sempre ter grande memória significou ser mais vantajoso para cooperação. Com duas memórias apenas, 30% da população resultante se envolveu em cooperação, enquanto o dobro de memória avançou a cooperação apenas para 44%. A maioria dos sobreviventes não participavam em nenhuma cooperação no final da simulação DPA realizada por David e Vivian Kraines (10).

Modelando a Evolução

As tentativas de imitar a evolução no computador não são exclusivas da teoria dos jogos ou da cooperação. Paralelo ao desenvolvimento dessas pesquisas, teóricos do caos e dos sistemas dinâmicos, na matemática e na física, desde os anos 1970, vinham tentando descobrir um algoritmo que reproduzisse em máquinas a diversidade de organismos presentes na natureza. O próprio John von Neumann - que, além da teoria dos jogos, foi um dos personagens principais do desenvolvimento dos computadores e da Inteligência Artificial - já havia lançado as bases para a criação de "vírus" eletrônicos, pequenos programas que eram capazes de reprodução autônoma. Von Neumann, na década dos 1950, aplicou o conceito dos autômatos celulares, cujo modelo havia sido desenvolvido pelo seu colega matemático, o polonês Stanislaw Marcin Ulam (1909-1984), que pretendia criar um mecanismo automático que simulasse a criatividade da evolução (11).

Em termos da teoria dos caos, esses autômatos celulares formam um sistema dinâmico complexo que se multiplica em uma rede quadriculada, como um infinito tabuleiro de xadrez. Cada quadrado reage com aqueles que lhe são adjacentes, seguindo uma regra simples. Os autômatos progridem em vários estados sucessórios, conforme o comportamento de suas casas vizinhas e os seus próprios comandos internos. Ao longo do tempo, toda rede modifica sua configuração em consequência da mudança constante de estado de suas células. As informações contidas em cada autômato celular permite a criação de organismos complexos e dinâmicos que avançam por toda rede e revelam uma estrutura global em parte dependente das regras de cada célula, mas que não pode ser estritamente determinada por estas (12).

Regras diferentes produzem padrões diversificados em uma rede composta por autômatos celulares. A vida artificial, que podia surgir de jogos desenvolvidos a partir de 1970 - como o Jogo da Vida do matemático britânico John Horton Conway -, progredia em pesquisas matemáticas até encontrar-se em 1992, no segundo congresso de Vida Artificial - promovido por Christopher Gale Langton -, com o Dilema dos Prisioneiros Iterado, apresentado no artigo do físico sueco Kristian Lindgren, que além de simples trocas de estados internos trazia os ingredientes cruciais para interpretação da evolução, que são competição e seleção (13).

Lindgren desenvolveu seu modelo tendo por base a interação entre indivíduos iniciada por Axelrod. Axelrod tinha elaborado uma variante evolutiva do DPI com o intuito de testar a robustez de OPO. Construiu uma sequência de torneios virtuais que começavam com populações compostas pelas diversas regras participantes dos campeonatos fixos anteriores. As estratégias bem sucedidas continuavam presentes nas rodadas posteriores, ocupando cada vez mais o lugar daqueles que fracassavam nas etapas passadas. O número crescente de cópias das estratégias vitoriosas nas sucessivas gerações do torneio simulavam a procriação das espécies melhor adaptadas ao ambiente.

(...) Suponha que as interações tomem a forma de um Dilema dos Prisioneiros. Quando dois animais se encontram, podem cooperar entre si, não cooperar entre si, ou um animal poderia explorar o outro. Suponha também que cada animal pode reconhecer indivíduos com os quais já tenha interagido e possa lembrar aspectos relevantes de sua intenção, tal como se o outro fosse usualmente cooperador. Uma rodada do torneio pode então ser olhada como uma simulação de uma simples geração de tal animal, com cada regra de decisão sendo empregada por um largo número de indivíduos. (...) Um dado animal pode interagir com outro animal usando sua própria regra de decisão, bem como pode aparecer um animal usando outra regra (AXELROD, R. The Evolution of Cooperation, cap. 2, p. 49).

Na perpectiva ecológica privilegiada por Axelrod, nenhuma mutação poderia ser introduzida, enquanto nos modelos evolucionários propriamente ditos, realizados depois, permitiam o surgimento de novas regras de comportamento no ambiente das novas gerações. Jogos evolucionários de DPI, como os promovidos por Nowak, Sigmund, Lindgren e os Kraines proporcionavam inclusão de diferentes aspectos evolutivos: erros, má compreensão, mudança de resultados, dimensão territorial, migrações e adaptações à atitude do outro. Modelos mais realistas chegam agora a assumir que uma população monomórfica de estratégias pode ser ligeiramente modificada por gerações que se diferenciam aos poucos de seus ancestrais. A habilidade de sobrevivência e reprodução depende, então, da capacidade de reconhecer essas pequenas variações em seus parentes, reagindo com maior ou menor tolerância, de acordo com a magnitude das tranformações.

Nos DPI evolutivos, as interações podem ser, portanto, modeladas localmente, como nos autômatos celulares que atuam espacialmente com seus vizinhos laterais, ou globalmente, quando cada indivíduo interage com todos ao longo do jogo. A dimensão espacial é a principal diferença entre esses dois tipos de jogos. A ocupação territorial muda de forma evidente de um modelo para o outro. No modelo de automatos celulares, os parasitas podem ser rechaçados por avanços da onda espiral de alguma espécie, ou seja, regiões de estratégias cooperadoras podem resistir à exploração de trapaceiros, apresentando uma estabilidade no domínio territorial que não pode ser percebida no modelo todos contra todos (14).

A territorialidade afeta a evolução da cooperação em vários aspectos. Quando a mistura aleatória das estratégias ocupa o espaço, a reciprocidade pode sustentar a cooperação com uma estrutura social mínima. A reciprocidade também permitiu que pequenos grupos de visitantes pudessem penetrar em uma população mesquinha (meanies). Diversificação social surge se há identificação de membros em um grupo; a reputação pode então ser construída entre os jogadores. O domínio de uma estratégia hegemônica passa a depender da correspondência da maioria das estratégias existentes, se for benéfica para cada um e para o todo, em geral. Por fim, a interação entre vizinhos promoveu o crescimento de estratégias que em outro cenário não poderiam subsistir - tal como a inocente SEMPRE C, que pode estabelecer regiões seguras mesmo em um cenário onde SEMPRE D prolifera, desde que os cooperadores da fronteira em contato com os desertores sejam substituídos pelos bens sucedidos cooperadores do núcleo do grupo nas gerações seguintes (15).

Notas
1. Veja WU, J. AXELROD, R. "How to Cope with Noise in the Iterated Prisoner's Dilemma", p.1.
2. T=3; R=2; P=1 e S=0, que foram utilizadas na primeira apresentação do DP neste curso, também correspondem a essas condições iniciais.
3. Veja NOWAK, M. & SIGMUND, K. The Alternating Prisoner's Dilemma, § 2, 220-221.
4. Veja KRAINES, D & KRAINES, V. Protocols for Cooperation, § 1, p. 1.
5. Tabela adaptada de KRAINES, D & KRAINES, V. Op. cit., § 2, p. 4.
6. Veja KRAINES, D. & KRAINES, V. Idem, § 3, pp. 4-6.
7. KRAINES, D. & KRAINES, V. ibidem, § 5, p. 8 e NOWAK, M. & SIGMUND, K. Op. cit., § 3, p. 221 utilizam a seguinte matriz para reprensentar os possíveis pagamentos de um jogador que usa a estratégia p, contra um outro que use p':

p1p'1	p1(1 - p'1)	(1 - p1)p'1	(1 - p1)(1 - p'1)
p2p'3	p2(1 - p'3)	(1 - p2)p'3	(1 - p2)(1 - p'3)
p3p'2	p3(1 - p'2)	(1 - p3)p'2	(1 - p3)(1 - p'2)
p4p'4	p4(1 - p'4)	(1 - p4)p'4	(1 - p4)(1 - p'4)

8. Veja KRAINES, D. & KRAINES, V. ibidem, § 8, p. 14, mas antes destes NOWAK, M. & SIGMUND, K. Op. cit., § 4, p. 222 já adiantavam, sem nomear AB, que tal padrão com baixo nível de ruído, em geral, sempre surge como vencedor em uma corrida evolucionária.
9. Veja KRAINES, D. & KRAINES, V. ibidem, § 10, p. 17.
10. Veja KRAINES, D. & KRAINES, V. ibidem, § 18, p. 28.
11. Veja DENNETT, D. A Perigosa Idéia de Darwin, cap.8, § 7, p. 231.
12. Veja LEWIN, R. Complexidade, cap. 3, p. 63.
13. Veja LINDGREN, Kr. "Evolutionary Phenomena in Single Dynamics", in LANGTON, Ch. G et al. Artificial Life II, pp. 295-311.
14. Veja LINDGREN, Kr. "Evolution of Behaviour in the Prisoner's Dilemma", p. 13.
15. Veja AXELROD, R. The Evolution of Cooperation, cap. 8, pp. 167-168 e LINDGREN, Kr. Op. cit., p. 25.

AXELROD, R. The Evolution of Cooperation. - Nova York: Basic Books, 1984.

DENNETT, D. C. A Perigosa Idéia de Darwin; trad. Talita M. Rodrigues. - Rio de Janeiro: Rocco, 1998.

KRAINES, D.P. & KRAINES, V. Y. "Protocols for Cooperation". mar 2001. Disponível na Internet via http://www.math.duke.edu/~dkrain/ProtCoop.pdf

LEWIN, R. Complexidade; trad. Marta R. Schmidt. - Rio de Janeiro: Rocco, 1994.

LINDGREN, Kr. "Evolutionary Phenomena in Single Dynamics", in LANGTON, Ch. G et al. Artificial Life II, pp. 295-311. - Redwood: Addison-Wesley, 1992.

________. "Evolution of Behaviour in the Prisoner's Dilemma". Disponível na Internet via www.business.auc.dk/evolution/evolecon/evolgames/Lindgren.pdf. Arquivo consultado em 2005.

NOWAK, M.A. & SIGMUND, K. "The Alternating Prisoner's Dilemma". Journal Theoretical Biology, n° 168, pp. 219-226, 1994.

WU, J. & AXELROD, R. "How to Cope with Noise in the Iterated Prisoner's Dilemma". Journal of Conflict Resolution, n° 39, pp. 183-189, março de 1995.