Introdução a teoria dos jogos

Introdução a teoria dos jogos

(Parte 1 de 7)

UmaIntrodução a Teoria dos Jogos

Brígida Alexandre Sartini, Gilmar Garbugio, Humberto José Bortolossi Polyane Alves Santos e Larissa Santana Barreto

I Bienal da SBM

Universidade Federal da Bahia 25 a 29 de outubro de 2004

Sumario

1.1 Introducao1
1.2 Historia2
1.3 O que e um jogo?4
1.4 Solucoes de um jogo8
1.5 Estrategias mistas12
1.6 Solucoese me strategias mistas15
1.7 Existencia de solucoes23

1 Descricao informal da teoria dos jogos 1

2.1 Jogos de soma constante com dois jogadores24
2.2 Equilıbrio de Nash em estrategias puras26
2.3 Equilıbrio de Nash em estrategias mistas29
2.4 O teorema minimax de von Neumann31

2 O teorema minimax de von Neumann 24

3 O teorema de equilıbrio de Nash 38

4.1 Representacao de um jogo via alfabetos e arvores49
4.2 Conversao entre as formas normal e extensa58

4 A forma extensa de um jogo 49 Bibliografia 61

Capıtulo 1 Descricao informal da teoria dos jogos

1.1 Introducao

A teoria dos jogos e uma teoria matematica criada para se modelar fenomenos que podem ser observados quando dois ou mais “agentes de decisao” interagem entre si. Ela fornece a linguagem para a descricao de processos de decisao conscientes e objetivos envolvendo mais do que um indivıduo.

A teoria dos jogos e usada para se estudar assuntos tais como eleicoes, leiloes, balanca de poder, evolucao genetica, etc. Ela et ambem uma teoria matematica pura, que pode e tem sido estudada como tal, sem a necessidade de relaciona-la com problemas comportamentais ou jogos per se.

Algumas pessoas acreditam que a teoria dos jogos formara em algum dia o alicerce de um conhecimento tecnico estrito de como decisoes sao feitas e de como a economia funciona. O desenvolvimento da teoria ainda nao atingiu este patamar e, hoje, a teoria dos jogos e mais estudada em seus aspectos matematicos puros e, em aplicacoes, ela e usada como uma ferramenta ou alegoria que auxiliam no entendimento de sistemas mais complicados.

Neste texto trataremos da Teoria Economica dos Jogos, que nao deve ser confundida com a Teoria Combinatoria dos Jogos [4, 1, 5, 2, 6, 7], iniciada por Sprague [20] e Grundy na decada de 30. Enquanto que a primeira tem motivacoes predominante economicas e procura estabelecer metodos para se maximizar o ganho (payoff ), a segunda se concentra nos aspectos combinatorios de jogos de mesa (por exemplo, ser o jogador a fazer o ultimo

2 I Bienal da Sociedade Brasileira de Matematica movimento em um jogo de nim [1]) e nao permite “elementos imprevisıveis” como o lancamento de um dado ou o baralhamento de cartas.

1.2 Historia

Registros antigos sobre teoria dos jogos remontam ao seculo XVIII. Em correspondencia dirigida a Nicolas Bernoulli, James Waldegrave analisa um jogo de cartas chamado “le Her” e fornece uma solucao que eu me quilıbrio de estrategia mista (conceito que nos familiarizaremos posteriormente). Contudo, Waldegrave nao estendeu sua abordagem para uma teoria geral. No inıcio do seculo XIX, temos o famoso trabalho de Augustin Cournot sobre duopolio [3]. Em 1913, Ernst Zermelo publicou o primeiro teorema matematico da teoria dos jogos [21], o teorema afirma que o jogo de xadrez e estritamente determinado,i sto e, em cada estagio do jogo pelo menos um dos jogadores tem uma estrategia em mao que lhe daraav itoria ou conduzira o jogo ao empate. Outro grande matematico que se interessou em jogos foi Emile Borel, que reinventou as solucoes minimax e publicou quatro artigos sobre jogos estrategicos. Ele achava que a guerra e a economia podiam ser estudadas de uma maneira semelhante.

Figura 1.1: Ernst Zermelo.

Em seu inıcio, a teoria dos jogos chamou pouca atencao. O grande matematico John von Neumann mudou esta situacao. Em 1928, ele demonstrou que todo jogo finito de soma zero com duas pessoas possui uma solucao em

Descricao informal da teoria dos jogos 3 estrategias mistas [18]. A demonstracao original usava topologia e analise

Figura 1.2: John von Neumann.

funcional e era muito complicada de se acompanhar. Em 1937, ele forneceu uma nova demonstracao baseada no teorema do ponto fixo de Brouwer. John von Neumann, que trabalhava em muitas areas da ciencia, mostrou interesse em economia e, junto com o economista Oscar Morgenstern, publicou oc lassico “The Theory of Games and Economic Behaviour” [19] em 1944 e, com isto, a teoria dos jogos invadiu a economia e a matematica aplicada.

Figura 1.3: Oscar Morgenstern.

Em 1950, o matematico John Forbes Nash Junior publicou quatro artigos importantes para a teoria dos jogos nao-cooperativos e para a teoria de barganha. Em “Equilibrium Points in n-Person Games” [14] e “Non-cooperative

4 I Bienal da Sociedade Brasileira de Matematica

Games” [16], Nash provou a existencia de um equilıbrio de estrategias mistas para jogos nao-cooperativos, denominado equilıbrio de Nash, e sugeriu uma abordagem de estudo de jogos cooperativos a partir de sua reducao para a forma nao-cooperativa. Nos artigos “The Bargaining Problem” [15] e “Two- Person Cooperative Games” [17], ele criou a teoria de barganha e provou a existencia de solucao para o problema da barganha de Nash.

Figura 1.4: John Forbes Nash.

Em 1994, John Forbes Nash Jr. (Universidade de Princeton), John Harsanyi Universidade de Berkeley, California) e Reinhard Selten (Universidade de Bonn, Alemanha) receberam o premio Nobel por suas contribuicoes para a Teoria dos Jogos.

1.3 O que e um jogo?

A teoria dos jogos pode ser definida como a teoria dos modelos matematicos que estuda a escolha de decisoes otimas sob condicoes de conflito. O elemento basico em um jogo e o conjunto de jogadores que dele participam. Cada jogador tem um conjunto de estrategias. Quando cada jogador escolhe sua estrategia, temos entao uma situacao ou perfil no espaco de todas as situacoes (perfis) possıveis. Cada jogador tem interesse ou preferencias para cada situacao no jogo. Em termos matematicos, cada jogador tem uma

Descricao informal da teoria dos jogos 5 Figura 1.5: John Harsanyi.

Figura 1.6: Reinhart Selten.

6 I Bienal da Sociedade Brasileira de Matematica funcao utilidade que atribui um numero real (o ganho ou payoff do jogador) ac adas ituacao do jogo.

Mais especificamente, um jogo tem os seguintes elementos basicos: existe um conjunto finito de jogadores, representado por G = {g1,g2,...,g n}.

Cada jogador gi ∈ G possui um conjunto finito Si = {si1,si2,...,s imi } de opcoes, denominadas estrategias puras do jogador gi (mi ≥ 2). Um ve- e uma estrategia pura para o jogador gi ∈ G,e denominado um perfil de estrategia pura. O conjunto de todos os perfis de estrategia pura formam, portanto, o produto cartesiano

denominado espaco de estrategia pura do jogo. Para jogador gi ∈ G, existe uma funcao utilidade

que associa o ganho (payoff) ui(s) do jogador gi a cada perfil de estrategia pura s ∈ S.

Exemplo 1.1 (O dilema do prisioneiro) Possivelmente o exemplo mais conhecido na teoria dos jogos eo dilema do prisioneiro. Ele foi formulado por Albert W. Tucker em 1950, em um seminario para psicologos na Universidade de Stanford, para ilustrar a dificuldade de se analisar certos tipos de jogos.

As ituacao e a seguinte: dois ladroes, Al e Bob, sao capturados e acusados de um mesmo crime. Presos em selas separadas e sem poderem se comunicar entre si, o delegado de plantao faz seguinte proposta: cada um pode escolher entre confessar ou negar o crime. Se nenhum deles confessar, ambos serao submetidos a uma pena de 1 ano. Se os dois confessarem, entao ambos terao pena de 5 anos. Mas se um confessar e o outro negar, entao o que confessou sera libertado e o outro sera condenado a 10 anos de prisao. Neste contexto, temos

As duas funcoes utilidade

Descricao informal da teoria dos jogos 7 uAl: S → R e uBob: S → R sao dadas por

(que representam os ganhos (payoffs)d eA l) e

(que representam os ganhos (payoffs) de Bob). Eu ma pratica se representar os payoffs dos jogadores atraves de uma matriz, denominada matriz de payoffs.

Bob confessar negar

Nesta matriz, os numeros de cada celula representam, respectivamente, os payoffs de Al e Bob para as escolhas de Al e Bob correspondentes a celula.

Exemplo 1.2 (A batalha dos sexos) Um 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, entao o homem tem satisfacao maior do que a mulher. Por outro lado, se eles forem juntos ao cinema, entao a mulher tem satisfacao maior do que o homem. Finalmente, se eles saırem sozinhos, entao ambos ficam igualmente insatisfeitos. Esta situacao tambem pode ser modelada como um jogo estrategico. Temos:

As duas funcoes utilidade uhomem: S → R e umulher: S → R sao descritas pela seguinte matriz de payoffs:

8 I Bienal da Sociedade Brasileira de Matematica

Mulher futebol cinema

(Parte 1 de 7)

Comentários