Introdução à Teoria dos Jogos: Conceitos e Aplicações

Teoria dos Jogos Internet ATENÇÃO O CONTEÚDO AUDIOVISUAL DESTA AULA É EXCLUSIVO PARA FINS ACADÊMICOS ESTANDO PROTEGIDO PELAS LEIS DE PROPRIEDADE INTELECTUAL PROIBIDA A SUA CESSÃO OU OUTRA FORMA DE UTILIZAÇÃO NÃO AUTORIZADA Introdução A teoria dos jogos é uma teoria matemática criada para se modelar fenômenos que podem ser observados quando dois ou mais agentes de decisão interagem entre si Ela fornece a linguagem para a descrição de processos de decisão conscientes e objetivos envolvendo mais do que um indivíduo A teoria dos jogos é usada para se estudar assuntos tais como eleições leilões balança de poder evolução genética etc Ela é também uma teoria matemática pura que pode e tem sido estudada como tal sem a necessidade de relacionála com problemas comportamentais Introdução Algumas pessoas acreditam que a teoria dos jogos formará em algum dia o alicerce de um conhecimento técnico estrito de como decisões são feitas e de como a economia funciona O desenvolvimento da teoria ainda não atingiu este patamar e hoje a teoria dos jogos é mais estudada em seus aspectos matemáticos puros e em aplicações ela é usada como uma ferramenta ou alegoria que auxiliam no entendimento de sistemas mais complicados Neste texto trataremos da Teoria Econômica dos Jogos que não deve ser confundida com a Teoria Combinatória dos Jogos Enquanto que a primeira tem motivações predominantemente econômicas e procura estabelecer métodos para se maximizar o ganho payoff a segunda se concentra nos aspectos combinatórios de jogos de mesa por exemplo ser o jogador a fazer o último movimento em um jogo e não permite elementos imprevisíveis como o lançamento de um dado ou o baralhamento de cartas O que é um Jogo A teoria dos jogos pode ser definida como a teoria dos modelos matemáticos que estuda a escolha de decisões ótimas sob condições de conflito O elemento básico em um jogo é o conjunto de jogadores que dele participam Cada jogador tem um conjunto de estratégias Quando cada jogador escolhe sua estratégia temos então uma situação ou perfil no espaço de todas as situações perfis possíveis Cada jogador tem interesse ou preferências para cada situação no jogo Em termos matemáticos cada jogador tem uma unção utilidade que atribui um número real o ganho ou payoff do jogadora cada situação do jogo O que é um Jogo Mais especificamente um jogo tem os seguintes elementos básicos existe um conjunto finito de jogadores representado por Gg1 g2 gnCada jogador gi G possui um conjunto finito Sisi1 si2 simi de opções denominadas estratégias puras do jogador gimi2 Um vetor s s1j1 s2j2 snjn onde siji é uma estratégia pura para o jogador gi G é denominado um perfil de estratégia pura O conjunto de todos os perfis de estratégia pura formam portanto o produto cartesiano Denominado espaço de estratégia pura do jogo Para jogador gi G existe uma função utilidade que associa o ganho payoff uis do jogador gi a cada perfil de estratégia pura s S Exemplo 11 O dilema do prisioneiro Possivelmente o exemplo mais conhecido na teoria dos jogos é o dilema do prisioneiro Ele foi formulado por Albert W Tucker em 1950 em um seminário para psicólogos na Universidade de Stanford para ilustrar a dificuldade de se analisar certos tipos de jogos A situação é a seguinte dois ladrões Al e Bob são capturados e acusados de um mesmo crime Presos em selas separadas e sem poderem se comunicar entre si o delegado de plantão faz seguinte proposta cada um pode escolher entre confessar ou negar o crime Se nenhum deles confessar ambos serão submetidos a uma pena de 1 ano Se os dois confessarem então ambos terão pena de 5 anos Mas se um confessar e o outro negar então o que confessou será libertado e o outro será condenado a 10 anos de prisão Neste contexto temos GAlBob SAlconfessarnegar SBobconfessarnegar Sconfessarconfessarconfessarnegarnegarconfessarnegarnegar As duas funções utilidade que representam os ganhos payoffs de Bob É uma prática se representar os payoffs dos jogadores através de uma matriz denominada matriz de payoffs Nesta matriz os números de cada célula representam respectivamente os payoffs de Al e Bob para as escolhas de Al e Bob correspondentes a célula Exemplo 12 A batalha dos sexosUm homem e a sua mulher desejam sair para passear O homem prefere assistir a um jogo de futebol enquanto que sua mulher prefere ir ao cinema Se eles forem juntos para o futebol então o homem tem satisfação maior do que a mulher Por outro lado se eles forem juntos ao cinema então a mulher tem satisfação maior do que o homem Finalmente se eles saírem sozinhos então ambos ficam igualmente insatisfeitos Esta situação também pode ser modelada como um jogo estratégico Temos Soluções de um jogo Uma solução de um jogo é uma prescrição ou previsão sobre o resultado do jogo Existem vários conceitos diferentes de solução Investigaremos os dois conceitos mais comuns dominância e equilíbrio de Nash Considere o dilema do prisioneiro Como encontrar uma solução para o dilema de Bob e Al isto é que estratégias são plausíveis se os dois prisioneiros querem minimizar o tempo de cadeia Se analisarmos o jogo do ponto de vista de Al ele pode raciocinar da seguinte maneira Se analisarmos agora o jogo do ponto de vista de Bob podemos aplicar a mesma linha de raciocínio e concluir que Bob também irá confessar Assim ambos confessarão e ficarão presos por 5 anos Em termos da teoria dos jogos dizemos que os dois jogadores possuem uma estratégia dominante isto é todas menos uma estratégia é estritamente dominada que o jogo é resolúvel por dominância estrita iterada e que o jogo termina em uma solução que é um equilíbrio de estratégia dominante conceitos que definiremos a seguir Dominância Frequentemente iremos discutir perfis de estratégia na qual apenas a estratégia de um único jogador gi G irá variar enquanto que as estratégias de seus oponentes permanecerão fixas Denote por uma escolha de estratégia para todos os jogadores menos o jogador gi Desta maneira um perfil de estratégia pode ser convenientemente denotado por Dominância estrita iterada nada mais é do um processo onde se eliminam as estratégias que são estritamente dominadas Exemplo 13 Considere o jogo determinado pela matriz de payoffs abaixo Neste jogo para o jogador g2 a estratégia s21 é estritamente dominada pela estratégia s24 assim a primeira coluna da matriz pode ser eliminada Agora nesta matriz reduzida para o jogadorg1 as estrat égias s11 e s14 são estritamente dominadas pelas estratégias s12 e s13 respectivamente Portanto as linhas 1 e 4 podem ser eliminadas Além disso a estratégia s23 do jogador g2 é estritamente dominada pelas estratégia s22 Assim a coluna 2 também pode ser eliminada Obtemos então uma matriz reduzida 22 Finalmente a estratégia s24 do jogador g2 é estritamente dominada pela estratégias22e na matriz 21 resultante a estratégia s13 do jogador g1 é estritamente dominada pela estratégia s12 Vemos então que o resultado do jogo é 32 isto é o jogador g1 escolhe a estratégia s12 e o jogador g2 escolhe a estratégia s22 No exemplo acima a técnica de dominância estrita iterada forneceu um único perfil de estratégia como solução do jogo no caso o perfil s12 s22 Contudo pode acontecer da técnica fornecer vários perfis ou até mesmo fornecer todo o espaço de estratégia como é o caso da batalhados sexos onde não existem estratégias estritamente dominadas Solução estratégica ou equilíbrio de Nash Uma solução estratégica ou equilíbrio de Nash de um jogo é um ponto onde cada jogador não tem incentivo de mudar sua estratégia se os demais jogadores não o fizerem Exemplo 14 a No dilema do prisioneiro exemplo 11 o perfil de estratégia confessarconfessar é um equilíbrio de Nash De fato se um prisioneiro confessar e o outro não aquele que não confessou fica preso na cadeia 10 anos ao invés de 5 anos se tivesse confessado Além desse perfil não existem outros equilíbrios de Nash b Na batalha dos sexos exemplo 12 os perfis de estratégia futebol futebol e cinema cinema são os únicos equilíbrios de Nash do jogo UNIVERSIDADE CANDIDO MENDES