Saltar para o conteúdo

Dominância estratégica

Origem: Wikipédia, a enciclopédia livre.

Na teoria dos jogos, a dominância estratégica (comumente chamada simplesmente de dominância) ocorre quando uma estratégia é melhor do que outra para um jogador, não importando como os oponentes daquele jogador possam jogar. Muitos jogos simples podem ser resolvidos usando dominância. O oposto, a intransitividade, ocorre em jogos onde uma estratégia pode ser melhor ou pior do que outra estratégia para um jogador, dependendo de como os oponentes do jogador podem jogar.

Quando um jogador tenta escolher a "melhor" estratégia entre várias opções, esse jogador pode comparar duas estratégias A e B para ver qual é a melhor. O resultado da comparação é um dos seguintes:

  • B é equivalente a A: escolher B sempre dá o mesmo resultado que escolher A, não importa o que os outros jogadores façam.
  • B domina estritamente A: escolher B sempre dá um resultado melhor do que escolher A, não importa o que os outros jogadores façam.
  • B domina A fracamente: escolher B sempre dá um resultado pelo menos tão bom quanto escolher A, não importa o que os outros jogadores façam, e há pelo menos um conjunto de ações oponentes para o qual B dá um resultado melhor do que A (Observe que, se B domina estritamente A, então B domina fracamente A. Portanto, podemos dizer "B domina A" como sinônimo de "B domina fracamente A").[1]
  • B e A são intransitivos : B e A não são equivalentes, e B nem domina, nem é dominado por A. Escolher A é melhor em alguns casos, enquanto escolher B é melhor em outros casos, dependendo exatamente de como o oponente escolhe jogar. Por exemplo, B é "jogar pedra" enquanto A é "jogar tesoura" em Pedra, papel e tesoura.
  • B é fracamente dominado por A: há pelo menos um conjunto de ações dos oponentes para as quais B dá um resultado pior do que A, enquanto todos os outros conjuntos de ações dos oponentes dão a A o mesmo retorno que B. (Estratégia A fracamente domina B) .
  • B é estritamente dominado por A: escolher B sempre dá um resultado pior do que escolher A, não importa o que o (s) outro (s) jogador (es) façam. (A estratégia A domina estritamente B).

Essa noção pode ser generalizada para além da comparação de duas estratégias.

  • A estratégia B é estritamente dominante se a estratégia B dominar estritamente todas as outras estratégias possíveis.
  • A estratégia B é fracamente dominante se a estratégia B dominar fracamente ou estritamente todas as outras estratégias, mas algumas (ou todas) as estratégias são apenas fracamente dominadas por B.
  • A estratégia B é estritamente dominada se alguma outra estratégia existir que domine estritamente B.
  • A estratégia B é fracamente dominada caso exista alguma outra estratégia que domine fracamente B.

Estratégia: trata-se de um plano contingente completo para um jogador no jogo. Um plano contingente completo é uma especificação completa do comportamento de um jogador, descrevendo cada ação que um jogador executaria em cada ponto de decisão possível. Como os conjuntos de informações representam pontos em um jogo em que um jogador deve tomar uma decisão, a estratégia de um jogador descreve o que aquele jogador fará em cada conjunto de informações.[2]

Racionalidade: A suposição de que cada jogador age de uma forma que é projetada para realizar o que ele ou ela mais prefere, dadas as probabilidades de vários resultados; von Neumann e Morgenstern mostraram que, se essas preferências satisfazem certas condições, isso é matematicamente equivalente a maximizar um retorno. Um exemplo direto de maximização do retorno é o do ganho monetário, mas para o propósito de uma análise da teoria dos jogos, esse retorno pode ter qualquer resultado desejado. Por exemplo, recompensa em dinheiro, minimização do esforço ou desconforto, promoção da justiça ou acumulação de "utilidade" geral - a suposição de racionalidade afirma que os jogadores sempre agirão da maneira que melhor satisfaça sua ordenação do melhor para o pior dos vários resultados possíveis.[2]

Conhecimento comum: A suposição de que cada jogador tem conhecimento do jogo, conhece as regras e recompensas associadas a cada curso de ação e percebe que todos os outros jogadores têm o mesmo nível de compreensão. Essa é a premissa que permite a um jogador fazer um julgamento de valor sobre as ações de outro jogador, apoiado no pressuposto da racionalidade, em consideração ao selecionar uma ação.[2]

Dominância e Equilíbrio de Nash

[editar | editar código-fonte]
C D
C 1, 1 0, 0
D 0, 0 0, 0

Se uma estratégia estritamente dominante existe para um jogador em um jogo, esse jogador jogará essa estratégia em cada um dos equilíbrios de Nash do jogo. Se ambos os jogadores tiverem uma estratégia estritamente dominante, o jogo terá apenas um equilíbrio de Nash único. No entanto, esse equilíbrio de Nash não é necessariamente "eficiente", o que significa que é possível haver resultados de não equilíbrio do jogo que seriam melhores para ambos os jogadores. O jogo clássico usado para ilustrar isso é o Dilema do Prisioneiro.

Estratégias que são estritamente dominadas não podem fazer parte de um equilíbrio de Nash e, como tal, é irracional para qualquer jogador jogá-las. Por outro lado, estratégias fracamente dominadas podem fazer parte do equilíbrio de Nash. Por exemplo, considere a matriz de payoff ilustrada à direita.

A estratégia C domina fracamente a estratégia D. Considere jogar C: Se o oponente de alguém joga C, ganha 1; se o oponente jogar D, obtém 0. Compare isso com D, onde se obtém 0 independentemente da opção. Visto que em um caso, alguém se sai melhor jogando C em vez de D e nunca pior, C domina D fracamente. Apesar disso, {D,D} é um equilíbrio de Nash. Suponha que ambos os jogadores escolham D. Nenhum dos jogadores se sairá melhor se desviando unilateralmente — se um jogador mudar para jogar C, ainda obterá 0. Isso satisfaz os requisitos de um equilíbrio de Nash. Suponha que ambos os jogadores escolham C. Nenhum dos jogadores se sairá melhor se desviando unilateralmente - se um jogador mudar para jogar D, obterá 0. Isso também satisfaz os requisitos de um equilíbrio de Nash.

Eliminação iterada de estratégias estritamente dominadas (IESDS)

[editar | editar código-fonte]

A eliminação iterada (ou exclusão) de estratégias dominadas (também denominadas IESDS ou IDSDS) é uma técnica comum para resolver jogos que envolve a remoção iterativa de estratégias dominadas. Na primeira etapa, no máximo uma estratégia dominada é removida do espaço de estratégia de cada um dos jogadores, já que nenhum jogador racional jamais jogaria essas estratégias. Isso resulta em um novo jogo menor. Algumas estratégias — que não eram dominadas antes — podem ser dominadas no jogo menor. A primeira etapa é repetida, criando um novo jogo ainda menor e assim por diante. O processo para quando nenhuma estratégia dominada é encontrada para qualquer jogador. Esse processo é válido uma vez que se assume que a racionalidade entre os jogadores é de conhecimento comum, ou seja, cada jogador sabe que o resto dos jogadores é racional, e cada jogador sabe que o resto dos jogadores sabe que ele sabe que o resto os jogadores são racionais e assim por diante ad infinitum (ver Aumann, 1976).

Existem duas versões desse processo. Uma versão envolve apenas a eliminação de estratégias estritamente dominadas. Se, após a conclusão desse processo, houver apenas uma estratégia para cada jogador restante, esse conjunto de estratégias será o equilíbrio de Nash único.[3]

Exemplo passo-a-passo de exclusão de dominância estrita:

  1. C é estritamente dominado por A para o Jogador 1. Portanto, o jogador 1 nunca jogará a estratégia C. O jogador 2 sabe disso. (ver IESDS Figura 1)
  2. Das estratégias restantes (ver IESDS Figura 2), Z é estritamente dominado por Y e X para o Jogador 2. Portanto, o jogador 2 nunca jogará a estratégia Z. O jogador 1 sabe disso.
  3. Das estratégias restantes (ver IESDS Figura 3), B é estritamente dominado por A para o Jogador 1. Portanto, o jogador 1 nunca jogará B. O jogador 2 sabe disso.
  4. Das estratégias restantes (consulte a Figura 4 do IESDS), Y é estritamente dominada por X para o Jogador 2. Portanto, o jogador 2 nunca jogará Y. O jogador 1 sabe disso.
  5. Apenas uma estratégia racionalizável é deixada {A, X} que resulta em um payoff de (10,4). Este é o único Equilíbrio de Nash para este jogo.

Outra versão envolve a eliminação de estratégias estritamente dominadas e fracamente dominadas. Se, ao final do processo, houver uma estratégia única para cada jogador, esse conjunto de estratégias também será um equilíbrio de Nash. Porém, ao contrário do primeiro processo, a eliminação de estratégias fracamente dominadas pode eliminar alguns equilíbrios de Nash. Como resultado, o equilíbrio de Nash encontrado pela eliminação de estratégias fracamente dominadas pode não ser o único equilíbrio de Nash (em alguns jogos, se removermos estratégias fracamente dominadas em uma ordem diferente, podemos acabar com um equilíbrio de Nash diferente).

Exemplo passo-a-passo de exclusão de dominância fraca:

  1. O é estritamente dominado por N para o Jogador 1. Portanto, o Jogador 1 nunca jogará a estratégia O. E o Jogador 2 sabe disso. (ver IESDS Figura 5)
  2. U é fracamente dominado por T para o Jogador 2. Se o jogador 2 escolher T, então o equilíbrio final é (N, T)
  1. Aqui, O é estritamente dominado por N para o Jogador 1. Portanto, o Jogador 1 nunca jogará a estratégia O. E o Jogador 2 sabe disso. (ver IESDS Figura 6)
  2. T é fracamente dominado por U para o Jogador 2. Se o jogador 2 escolher U, então o equilíbrio final é (N, U)

Em qualquer caso, se por eliminação iterada de estratégias dominadas houver apenas uma estratégia restante para cada jogador, o jogo é chamado de jogo solucionável por dominância.

  • Arbitragem
  • Estratégia dominada por Max
  • Paradoxo de Newcomb
  • Dominância de risco
  • Estratégia vencedora

Referências

  1. Leyton-Brown, Kevin; Shoham, Yoav (janeiro de 2008). «Essentials of Game Theory: A Concise Multidisciplinary Introduction». Synthesis Lectures on Artificial Intelligence and Machine Learning (em inglês). 2: 36. doi:10.2200/S00108ED1V01Y200802AIM003 
  2. a b c Joel, Watson (9 de maio de 2013). Strategy: An Introduction to Game Theory Third ed. New York: [s.n.] ISBN 9780393918380. OCLC 842323069 
  3. Joel., Watson,. Strategy : an introduction to game theory (Second ed.). New York. ISBN 9780393929348.
Este artigo incorpora material de [[PlanetMath:{{{id}}}|Dominant strategy]] do PlanetMath, que é licenciado sob GFDL.