CCT-UFCA/Ciência da Computação/Introdução à Teoria dos Jogos/Remoção de estratégias estritamente dominadas

Remoção de estratégias estritamente dominadas

Considerando $s_{i}$ e $s_{i}^{'}$ estratégias do jogador $i$ , assim como $S_{-}i$ o conjunto de todos os perfis de estratégia dos jogadores restantes exceto o do jogador $i$ , e $s_{-}i$ um perfil de ação dos outros jogadores, formalmente falando temos que $s_{i}$ estritamente domina $s_{i}^{'}$ se: $\forall s_{-}i\in S_{-}i,U_{i}(s_{i},s_{-}i)>U_{i}(s_{i}^{'},s_{-}i)$ .

Intuitivamente falando, para qualquer escolha possível dos outros jogadores o jogador $i$ sempre ganha mais escolhendo $s_{i}$ do que $s_{i}^{'}$ , ou seja, não importa o que os outros jogadores façam $s_{i}$ sempre será melhor que $s_{i}^{'}$ . De maneira complementar dizemos que uma estratégia $s_{i}^{'}$ é estritamente dominada por $s_{i}$ se $s_{i}$ estritamente domina $s_{i}^{'}$ .

Dentro desse contexto um importante conceito de solução que podemos explorar é o de remoção de estratégias estritamente dominadas, que consiste em remover iterativamente estratégias estritamente dominadas até que não seja mais possível. O resultado gerado por esse processo geralmente coincide em um equilíbrio de Nash daquele jogo, do contrário o resultado obtido gera uma simplificação do mesmo jogo.

Exemplo 1: considere o jogo abaixo:

1/2	L	C	R
U	$3,0$	$2,1$	$0,0$
M	$1,1$	$1,1$	$5,0$
D	$0,1$	$4,2$	$0,1$

Analisando o jogo sobre a perspectiva do jogador 2, temos que R é estritamente dominada por C, pois independente da escolha do jogador 1 C sempre resultará em um valor de utilidade estritamente maior que R, conforme é possível observar ao analisar todas as possibilidades de escolha do jogador 1:

Jogador 1 escolhe U: estratégia C resulta em utilidade maior que R pois 1>0.
Jogador 1 escolhe M: estratégia C resulta em utilidade maior que R pois 1>0.
Jogador 1 escolhe D: estratégia C resulta em utilidade maior que R pois 2>1.

Logo removeremos a estratégia R do jogador 2.

1/2	L	C
U	$3,0$	$2,1$
M	$1,1$	$1,1$
D	$0,1$	$4,2$

Analisando o jogo resultante sobre a perspectiva do jogador 1 temos que a estratégia M é estritamente dominada por U, pois independente da escolha do jogador 2 U sempre resultará em um valor de utilidade estritamente maior que M, conforme é possível observar ao analisar todas as possibilidades de escolha do jogador 2:

Jogador 2 escolhe L: estratégia U resulta em utilidade maior que M pois 3 > 1.
Jogador 2 escolhe C: estratégia U resulta em utilidade maior que M pois 2 > 1.

Logo removeremos a estratégia M do jogador 2.

1/2	L	C
U	$3,0$	$2,1$
D	$0,1$	$4,2$

Analisando o jogo resultante sobre a perspectiva do jogador 2 temos que a estratégia L é estritamente dominada por C, pois independente da escolha do jogador 1 C sempre resultará em um valor de utilidade estritamente maior que L, logo removeremos a estratégia C.

1/2	C
U	$2,1$
D	$4,2$

Por fim, analisando o jogo resultante sobre a perspectiva do jogador 1 temos que a estratégia U é estritamente dominada por D, pois independente da escolha do jogador 2 D sempre resultará em um valor de utilidade estritamente maior que U, logo removeremos a estratégia U, chegando em uma versão simplificada do jogo composta apenas pelo perfil de ação ({D, C}) que corresponde ao equilíbrio de nash puro desse jogo.

Exemplo de aplicação prática

Um exemplo notável da influência de estratégias dominantes sobre um fenômeno comportamental real pode ser verificado pelo artigo de e B.A Baldwin and G.B Meese (1979) ”Social Behavior in Pigs Studied by Means of Operant Conditioning” Animal Behavior, Vol27, p 947-957.

Nesse estudo foi criado um cenário isolado onde dois porcos de tamanhos diferentes encontram-se em uma jaula, em que a comida é colocada no lado oposto a um botão apenas quando esse é pressionado por um dos porcos. O experimento criado pelos pesquisadores foi modelado de acordo com os seguintes cenários e condições:

Se locomover para acionar o botão custa 2 unidades de energia de comida (-2 de utilidade).
Se o porco maior chegar na comida primeiro, significa que ele escolheu esperar enquanto o porco menor apertou o botão, então: 1, 9 (1 para o pequeno e 9 para o grande).
Se o porco menor chegar na comida primeiro significa que ele escolheu esperar enquanto o porco maior acionou o botão, então: 4,6.
Se os dois chegarem na comida ao mesmo tempo significa que ambos escolheram apertar o botão, então: 3,7.

Tais cenários e circunstâncias podem ser expressas como o jogo na forma normal abaixo com os seguintes valores de utilidade:

pequeno/grande	Apertar botão	Esperar
Apertar botão	$1,5$	$-1,9$
Esperar	$4,4$	$0,0$

Utilizando o conceito de remoção de estratégias estritamente dominadas chegamos no resultado correspondente ao perfil de ação a = {(Esperar, Apertar botão)}. Esse experimento foi extensivamente testado 10 vezes em cenários onde os porcos foram deixados sozinhos e juntos na jaula, tendo cada teste duração de 15 minutos, resultando na seguinte tabela de verificação quando a frequência que cada porco acionou o botão em cada cenário:

	sozinho	juntos
porco pequeno	75	105
porco grande	70	5

Repare que para o cenário onde ambos se encontram juntos foi verificado que o porco maior aperta o botão em uma frequência muito maior que o porco pequeno, o que coincide com o resultado que encontramos no jogo na formal normal onde o porco pequeno escolhe esperar enquanto o grande aciona o botão, isso significa que porcos são racionais? Não, apenas sugerem que porcos aprendem e respondem a incentivos o que reflete em não escolherem estratégias estritamente dominadas, evidenciando que podemos utilizar a teoria dos jogos e o conceito de remoção de estratégias dominadas para modelar e prever diversas situações do mundo real.