Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Dilema do Priosioneiro
−5 0−20 −1
Confess
Remain Silent
Confess Remain Silent
Dois suspeitos de terem cometido um crime conjuntamente
A polícia não possui provas suficientes para condená-los!!!
T > R > P > S
Decisão Racional
O indivíduo toma uma decisão que é a melhor opção para ele, qualquer que seja a decisão do oponente.
Deserção
DeserçãoCooperação
Deserção é individualmente racional!!!
Cooperação não é racional!!!
Qual a relação deste problema com a biologia evolucionária?
Moléculas replicantes
Formação das primeiras células
Formação de organismos multicelulares
Humanos colaboram em larga escala
Grupos, cidades, estados, países
Organismos tão diversos como amebas e elefantes frequentemente vivem em grupos. Por quê estes e muitos outros animais formam sociedades complexas?
Cooperação permite especialização
Organismos são inerentemente competitivos
Organismos são inerentemente competitivos
O princípio evolucionário “sobrevivência do mais apto” parece
predispor organismos ao egoísmo
Cooperação é generalizada na natureza
Cooperação é em geral vantajosa para o grupo de cooperadores
como um todo
3 05 1
C D
C
D
C CooperarD Desertar
O que você deveria fazer? Cooperar ou desertar?
Se a outra pessoa cooperar podemos escolher entre:(1) Receber 3 pontos pela sua cooperação;(2) Receber 5 pontos pela sua deserção.
Deserção é a melhor opção!
Se a outra pessoa desertar podemos escolher entre:(1) Receber 0 pontos pela sua cooperação;(2) Receber 1 ponto pela sua deserção.
Deserção é novamente a melhor opção!
Em resumo, deserção é a melhor opção independentemente da opção do outro jogador
De uma forma racional, o outro jogador chegará a mesma conclusão
Ambos acabarão recebendo 01 ponto.
Cooperação mútua
Ambos recebem 03 pontos
Cooperação mútua leva a um maior payoff do que a deserção
mútua
C C
C C
CCC
DC C
C C
CCC
D C C
C C
CCC
DC D
D D
CDC
D C C
C C
CCC
DD D
D D
DDD
D
C D
D domina C
Evolução da deserção
Evolução natural favorece a deserção!
Cooperadores frequência xDesertores frequência 1 - x
Payoff médio dos cooperadores 3x
Payoff médio dos desertores 5x + 1 – x = 4x + 1
Desertores sempre terão fitness maior que cooperadores
População mista
Dilema do Prisioneiro Iterado
Considere a matriz payoff
R ST P
C D
C
D
Dilema do Prisioneiro: T > R > P > SCondição adicional (jogo repetido): 2R > T + P
O jogo não é realizado uma única vez, mas é repetido diversas vezes entre os mesmos dois jogadores.
ReciprocidadeDireta
Jogo: m repetições
Estratégias
GRIMCoopera na primeira rodada e então continua a
cooperar enquanto o oponente não deserta. Não perdoa.
ALL DSempre deserta
A matriz payoff é dada por
mR S+ m−1 PT+ m−1 P mP
GRIM A LL D
GRIM
ALL D
Se mR > T + (m-1)P, então GRIM é um equilíbrio de Nash estrito quando competindo com ALL D.
Se toda população usa GRIM, então ALL D não pode invadir: seleção se opõe a ALL D em baixa frequência. GRIM é estável contra uma invasão por ALL D se o número de rounds, m, excede um valor crítico
m>T−PR−P
Encontramos um mecanismo para estabilizar cooperação uma vez que ele tenha se estabelecido.
Número fixo de rounds m
mR m−1 R+Sm−1 R+T m−1 R+P
GRIM GRIM*
GRIM
GRIM*
GRIM é dominado por GRIM*.
GRIM* idêntico ao GRIM, porém deserta na última geração.
GRIM* é dominado por GRIM**, ... ,GRIM**...* é dominado por ALL D
Número de rounds m não é exatamente conhecido (estratégia humana, biológica) não sabemos exatamente quando a interação irá cessar.
Número fixo de rounds variável
Probabilidade de que um novo round seja jogado.
m=1
1−ω(número esperado de rounds)
mR S+ m−1 PT+ m−1 P mP
GRIM A LL D
GRIM
ALL D
GRIM é estável se
mT−PR−P
É GRIM a melhor estratégia? E se o oponente deserta apenas uma única vez de forma a verificar se pode prosseguir desta forma? Não é melhor voltar a cooperar com este indivíduo novamente?
Uma estratégia com algum mecanismo de reconciliação deve obter um payoff maior que o GRIM!!!
Em cada rodada do jogo: CC, CD, DC, DD 24 estratégias determinísticas que consideram apenas a última rodada do jogo.
216 estratégias determinísticas que consideram as duas últimas rodadas.
Há estratégias determinísticas que consideram as m últimas rodadas.
24m
É impossível realizar simulações que consideram todas as estratégias possíveis em um Dilema do Prisioneiro iterado!!!
Campeonato de Axelrod (1978)
Estratégias:ALL D – deserta em cada rodada do jogo.Poor-Trusting-Fool – coopera em cada rodada do jogo.Random – coopera ou deserta aleatoriamente.Go-by-Majority – coopera na primeira rodada. Nas rodadas subsequentes, analisa a história das ações do outro jogador. Adota a ação majoritária.Tit-for-Tat – coopera na primeira rodada. Subsequentemente, reproduz a ação do outro jogador na rodada anterior.
Regra:•Cada estratégia joga contra todas as outras estratégias.•A estratégia vencedora é aquela que acumular maior payoff.
14 estratégias foram submetidas
E a estratégia vencedora foi ...
Tit-for-tat (TFT) submetida por Anatol Rapoport
Segundo Campeonato de Axelrod: 63 estratégias
Foram submetidas estratégias que poderiam ter ganho o primeiro campeonato. Entre elas, tit-for-two-tats submetida por John Maynard Smith. Anatel Rapoport foi o único a submeter tit-for-tat.
Novamente tit-for-tat (TFT) foi a estratégia vencedora!!!
Características de TIT-FOR_TAT
É uma estratégia gentil Em cada jogo, tit-for-tat obtém no máximo a mesma pontuação que seu oponente. Nunca superior. TFT é aparentemente bastante exitosa em induzir cooperação de outras estratégias.
TFT ALL D
TFT
ALL D
A matriz payoff para TFT versus ALL D é a mesma da GRIM versus ALL D.
TFT pode resistir invasão por ALL D se
mR S+ m−1 PT+ m−1 P mP
mT−PR−P
Jogos em Populações Finitas
Finitude Estocasticidade
Deriva aleatória Seleção dependente da frequência
Resultado do jogo evolucionário
Calcular probabilidade de fixação para decidir se seleção favorece uma
estratégia em detrimento da outra
Biólogos estão interessados nos conceitos de equilíbrio de Nash estrito ou estratégia evolutivamente estável
Seleção natural protege populações com tais estratégias de serem invadidas por mutantes
Populações finitas
Novas condições devem ser obtidas
Considere um jogo entre duas estratégias. A e B, com matriz payoff
a bc d
A B
A
B
N Tamanho da população
i Número de indivíduos A
N - i Número de indivíduos B
O payoff esperado para A e B em uma população que contém i indivíduos A é respectivamente dado por
F i=a i−1 +b N−i
N−1
Gi=ci+d N−i−1
N−1
Na formulação tradicional: payoff esperado fitness
mede a intensidade de seleção. Na formulação determinística essa dependência desaparece.
f i=1−ω+ωF i
gi=1−ω+ωG i
Fitness de A
Fitness de B
caso neutro); (fitness inteiramente determinado pelo payoff)
Processo de Moran
i variável de estado
pi,i+1=if i
if iN−i g i
N−iN
pi,i−1= N−i g i
if i N−i gi
iN
A probabilidade de que o processo permaneça no estado i é simplesmente
pi,i=1−pi,i+1−pi,i−1
Novamente p0,0=pN,N=1 (Dois estados absorventes)
γi=p i,i−1
pi,i+1
=gi
f i
Como a probabilidade de fixação de A, é dada por
ρA =x1=1
1∑j=1
N−1
∏k=1
j
γ k
Então
ρA=1
1∑k=1
N−1
∏i=1
k g i
f i
No limite de 0
ρA≈1N
11−αN−β ω/6
α=a+2b−c−2d β=2a +b+c−4d
Se A
> 1/N, então seleção favorece a fixação de A. Isto equivale a N>
a N−2 +b 2N−1 >c N+1 +d 2N−4
Para grandes populações
a+2b>c+2d
Considere o seguinte jogo: a > c e b < d. A e B são as melhores respostas para eles mesmos (bi-estáveis).
Se frequência de A é alta A tem fitness maior que B
Se frequência de B é alta B tem fitness maior que A
Há um ponto onde os fitness são iguais Fi = G
i
x=d−b
a−b−c+d
A desigualdade leva à condição x* < 1/3.
Se x* < 1/3 então seleção favorece a fixação de A em B (A > 1/N). A bacia
de atração de B é menor que 1/3.
B A
Se a > c e b > d, então A domina. Neste caso, x*<0 e a desigualdade a + 2b > c + 2d ainda é válida.
Se A domina B, seleção favorece a fixação de A, e se opõe a fixação de B.
Estabilidade evolutiva em populações finitas
Os resultados apresentados têm consequência imediata para o conceito de estabilidade evolutiva.
Estratégia evolutivamente estável (populações infinitas)
a bc d
A B
A
B
B é ESS se Se d > b Se d = b e a < c
Seleção se opõe à expansão de uma fração infinitesimal de A em uma população infinitamente grande de B.
Para uma população finita B é uma estratégia evolutivamente estável (ESSN)
Seleção se opõe a A invadir B (um único mutante A em uma população de B tem menor fitness).
b(N-1) < c + d(N-2)
Seleção se opõe a A eliminar B, o que significa que
A< 1/N.
a(N-2) + b(2N - 1) < c(N+1) + d(2N-4)
Para N = 2, ambas condições levam a b < c.Para N grande, as duas condições levam a b < d e x* > 1/3.
Para pequenas populações, o conceito tradicional de ESS não é necessário nem suficiente. Para grandes populações, ele é necessário mas não suficiente.
Tit-for-tat pode invadir ALL D
TFT ALL D
TFT
ALL D
Tanto TFT como ALL D são estáveis contra invasão pela outra estratégias.
TFT pode manter cooperação, e da mesma forma ALL D pode manter deserção.
mR S+ m−1 PT+ m−1 P mP m>
T−PR−P
ρA=1
1∑k=1
N−1
∏i=1
k g i
f i
Utilizando a matriz payoff, temos que o payoff esperado de TFT e ALL D são respectivamente
F i=mR i−1 S+ m−1 P N−i
N−1
Gi=T+ m−1 P i+mP N−i−1
N−1
f i=1−ω+ωF i
gi=1−ω+ωG i
Fitness de TFT
Fitness de ALL D