Evolução da Cooperação - PDF

Evolução da Cooperação  O problema da cooperação Em que condições pode a cooperação emergir num mundo de egoístas sem/com a intervenção de uma autoridade central?  Evolução da cooperação Perceber porque existe cooperação na natureza e nas sociedades humanas Desenvolver meca...

Evolução da Cooperação  O problema da cooperação Em que condições pode a cooperação emergir num mundo de egoístas sem/com a intervenção de uma autoridade central?  Evolução da cooperação Perceber porque existe cooperação na natureza e nas sociedades humanas Desenvolver mecanismos para promover a cooperação em sociedades “reais” e “arDficiais“  Na Biologia Do ponto de vista da teoria da selecção natural, os comportamentos cooperaDvos são aparentemente desvantajosos Problema: então porque existem comportamentos de cooperação na natureza?  Na Biologia ‐ exemplos Gritos de alarme quando são detectados predadores em algumas espécies de aves e macacos ParDlha de alimento em algumas espécies de morcegos  Humanos Gestão de recursos (pastagens, oceanos, etc.) Trocas comerciais Acordos entre países e parDdos políDcos Etc.  Teoria dos jogos (TJ) As interacções são modeladas através de um jogo TJ clássica: considera‐se que os agentes são racionais Cada jogador sabe que o outro sabe que o outro sabe que o outro sabe, etc.  Jogos ‐ representação Os jogos representam‐se frequentemente através da sua matriz de ganhos Exemplo: Cooperar Traír Cooperar 3, 3 0, 5 Traír 5, 0 1, 1  Equilíbrio de Nash (EN) Uma combinação de estratégias é um EN se nenhum jogador Dver vantagem em mudar unilateralmente de estratégia Todos os jogos têm um EN O EN pode consisDr em jogadas mistas – Ex: (Jog1: 50% C/50% T; Jog2: 70% C / 30% T)  Dilema do Prisioneiro Cooperar Traír Cooperar 3, 3 0, 5 Equilíbrio de Nash: (T, T) Traír 5, 0 1, 1 Conclusão: neste jogo não se deve cooperar No entanto, se ambos os jogadores cooperassem ganhariam mais, daí o dilema  Snowdric Cooperar Traír Cooperar 3, 3 2, 4 Equilíbrios de Nash: Traír 4, 2 0, 0 – (C, T), (T, C) e uma combinação de estratégias mistas que depende do valor relaDvo dos ganhos Se considerarmos apenas estratégia puras, neste jogo deve fazer‐se o contrário do que o outro faz (jogo de anD‐coordenação)  Dilema do Prisioneiro Iterado O jogo é jogado várias vezes por jogadores: – Capazes de reconhecer outros jogadores – Com memória: os jogadores lembram‐se do que aconteceu em jogos anteriores  Dilema do Prisioneiro Iterado Se o jogo for jogado N vezes: – No N‐ésimo jogo ambos traem porque não existem consequências futuras – No N‐ésimo‐1 jogo ambos traem porque, sabendo qual o resultado do úlDmo jogo, não existem incenDvos para cooperar – etc.  Dilema do Prisioneiro Iterado Se o jogo for jogado um número indeterminado de vezes: – O raciocínio anterior não se aplica porque existe a possibilidade de o outro jogador ripostar no futuro Passamos a ter o problema de saber quais as condições necessárias e suficientes para que a cooperação possa emergir  Torneio de Axelrod Vários invesDgadores foram convidados a enviar uma estratégia para jogar o Dilema do Prisioneiro Iterado As estratégias jogaram todas umas contra as outras Ganhou a estratégia mais simples: TIT‐FOR‐TAT  TIT‐FOR‐TAT Coopera na primeira vez; a parDr daí faz sempre o que o parceiro fez no jogo anterior Exemplo: – TIT‐FOR‐TAT: C T C C C T T T C – Jogador Ad‐hoc: T C C C T T T C C  TIT‐FOR‐TAT O sucesso do TIT‐FOR‐TAT depende de 4 factores: – Não ser o primeiro a traír – Retaliação imediata de traições – Esquecer rapidamente traições anteriores – ExisDrem fortes possibilidades de os jogadores se voltarem a encontrar  Teoria dos jogos evolucionária Estudo da cooperação sob um ponto de vista evolucionário (dinâmico) A adaptabilidade de um agente depende da proporção relaDva dos diferentes Dpos de fenóDpos existentes na população  Teoria dos jogos evolucionária Não se considera que os agentes são racionais Ganho (jogos) ≡ Adaptabilidade (fitness)  Teoria dos jogos evolucionária Existem duas abordagens diferentes: 1. UDlização do conceito de estratégia evoluDvamente estável 2. UDlização de populações explícitas e estudo das caracterísDcas dinâmicas dessas populações  Estratégia evoluDvamente estável Uma estratégia é EEE se uma população de agentes que usam essa estratégia não pode ser invadida por um mutante raro que adopte uma estratégia diferente  Estratégia evoluDvamente estável Consideremos as estratégias s e m s é EEE se 1. G(s, s) ≥ G(m, s) ou se 2. G(s, s) = G(m, s) e G(s, m) ≥ G(m, m) Nota: G(s1, s2) = ganho de s1 quando joga com s2  Estratégia evoluDvamente estável Exemplos (Dilema do Prisioneiro): – Cooperar incondicionalmente não é EEE – TFT é EEE se o futuro for suficientemente importante – Traír incondicionalmente é EEE, o que tem fortes implicações para a evolução da cooperação  Estratégia evoluDvamente estável Explicações possíveis para a evolução da cooperação: – Altruísmo entre familiares (teoria do gene egoísta) – Agrupamento: permite que agentes do mesmo Dpo interajam sobretudo entre si (relacionado com o ponto anterior)  Equação de replicação populações explícitas Vamos considerar uma população panmícDca: – Todos podem interagir com todos Equação de replicação (populações grandes): variação de i adaptabilidade média proporção da estratégia i adaptabilidade de i Jogos simétricos de dois jogadores Num jogo simétrico os jogadores desempenham exactamente o mesmo papel A matriz de ganhos pode ser representada do seguinte modo S1 S2 S1 g11 g12 S2 g21 g22  Equação de replicação 1. g11 > g21 e g12 > g22 ➔ S1 domina S2 S1 S2 2. g11 < g21 e g12 < g22 ➔ S2 domina S1 S1 S2 equilíbrio estável Equilíbrio instável  Equação de replicação 3. g11 > g21 e g12 < g22 ➔ S1 e S2 são bi‐estáveis S1 S2 (g22 – g12) / (g11 – g12 – g21 + g22)  Equação de replicação 4. g11 < g21 e g12 > g22 ➔ S1 e S2 coexistem S1 S2 (g22 – g12) / (g11 – g12 – g21 + g22) 5. g11 = g21 e g12 = g22 ➔ Deriva aleatória  Equação de replicação‐ exemplos Dilema do Prisioneiro C T – T domina C 3 0 T 5 1 Snowdric C T – C e T coexistem C 3 2 T 4 0  Estratégias reacDvas estocásDcas Cada estratégia é representada por S(p, q) onde – p: probabilidade de cooperar se o outro cooperou – q: probabilidade de cooperar se o outro traiu A população é iniciada aleatoriamente O que acontece se for uDlizada a equação de replicação?  Estratégias reacDvas estocásDcas Dilema do Prisioneiro Na maior parte das vezes, T ≈ (0, 0) domina Por vezes, o TIT‐FOR‐TAT ≈ (1, 0), suplanta T Mas, uma população de TFTs tem um mau desempenho na presença de erros O TFT é depois subsDtuído pelo TFT‐Generoso ≈ (1, ω)  Estratégias estocásDcas As estratégias reacDvas têm em conta apenas a acção anterior do outro jogador Vamos agora considerar o conjunto de todas as estratégias estocásDcas com memória 1 (p1, p2, p3, p4) probabilidade de cooperar se as acções anteriores foram (CC, CT, TC, TT)  Estratégias estocásDcas Dilema do Prisioneiro Começa por acontecer o mesmo que acontece para as estratégias reacDvas Depois, o TFT‐Generoso é subsDtuído pela estratégia PAVLOV ≈ (1, 0, 0, 1)  Estratégias estocásDcas O TFT é um bom catalisador da cooperação, mas… – Não é capaz de corrigir erros – Não impede uma deriva para a estratégia Cooperar incondicionalmente A estratégia PAVLOV não tem estes problemas  Jogos evolucionários espaciais Em muitas situações não é realista considerar população panmícDcas Em muitas situações cada agente interage apenas com um pequeno sub‐conjunto da população  Jogos evolucionários espaciais Uma população de agentes que interage durante muitas iterações Em cada iteração, cada agente joga o jogo com os seus vizinhos (topologia de interacção) Em cada iteração, um ou mais agentes actualizam a sua estratégia (dinâmica de actualização)  Jogos evolucionários espaciais A actualização de estratégias é realizada uDlizando uma regra de transição que pode modelar: – O facto de os agentes tentarem imitar os vizinhos mais bem sucedidos – Um processo evoluDvo em que as estratégias menos bem sucedidas tendem a ser subsDtuídas por estratégias mais bem sucedidas  JEEs ‐ Topologias de interacção Grelhas regulares Redes de escala livre Redes de mundo pequeno  JEEs – Dinâmicas de actualização Dinâmica síncrona: em cada iteração todos os agentes actualizam a sua estratégia em simultâneo Dinâmica sequencial: em cada iteração apenas um agente actualiza a sua estratégia Dinâmica assíncrona estocásDca: em cada iteração cada agente é actualizado com probabilidade α (taxa de sincronismo)  JEEs – Regras de transição Melhor vizinho: imitar sempre o vizinho mais bem sucedido Regra proporcional: a probabilidade de um vizinho ser imitado é proporcional ao seu ganho Equação de replicação: escolher um vizinho v aleatoriamente; Se gv > gi, imitar v com probabilidade  Cooperação em populações estruturadas Em 1992 MarDn Nowak e Robert May mostraram que é possível a sobrevivência de cooperadores incondicionais sem memória Condições: Dilema do Prisioneiro, grelha regular 2D, dinâmica síncrona, regra melhor vizinho  Cooperação em populações estruturadas A estrutura espacial permite que os cooperadores se organizem em grupos Deste modo, os cooperadores interagem sobretudo entre si As redes de escala livre suportam mais cooperadores (J. Pacheco (UL) e F. F. Santos)  Influência da dinâmica de actualização Em geral, uma dinâmica assíncrona suporta mais cooperadores Com uma dinâmica síncrona acontecem mais trocas de estratégia entre agentes vizinhos As trocas de estratégia destroem os grupos de cooperadores Topologias de interacção dinâmicas A topologia de interacção pode mudar com o tempo A escolha de parceiros pode ser baseada, por exemplo – Na experiência individual – Na informação fornecida por outros agentes (reputação)  Reputação ‐ exemplo eBay: após uma interacção, cada agente pode avaliar o comportamento do seu parceiro – A avaliação pode ser 1 (posiDva), 0 (neutral) ou ‐1 (negaDva) – A reputação de um agente é a soma dos valores dados nos úlDmos seis meses  Reputação Problemas que podem ocorrer em sistemas de reputação – Os agentes podem menDr, por exemplo, para proteger ou prejudicar outros agentes – Coligação de agentes de modo a forjar a sua reputação – Um agente com má reputação pode sair do sistema e entrar com outra idenDdade  Bibliografia The EvoluDon of CooperaDon, Robert Axelrod, Penguin Science EvoluDonary Dynamics, MarDn Nowak, Harvard University Press EvoluDonary games on graphs, György Szabó e Gábor Fáth Review on computaDonal trust and reputaDon models, Jordi Sabater and Carles Sierra