Uma Introdução a Teoria dos Jogos - IME-USP

[Pages:64]Uma Introdu??o a Teoria dos Jogos

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

II Bienal da SBM Universidade Federal da Bahia 25 a 29 de outubro de 2004

Suma?rio

1 Descric?~ao informal da teoria dos jogos

1

1.1 Introduc?~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Histo?ria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 O que ?e um jogo? . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Soluc?~oes de um jogo . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Estrat?egias mistas . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6 Soluc?~oes em estrat?egias mistas . . . . . . . . . . . . . . . . . 15

1.7 Exist^encia de soluc?~oes . . . . . . . . . . . . . . . . . . . . . 23

2 O teorema minimax de von Neumann

24

2.1 Jogos de soma constante com dois jogadores . . . . . . . . . 24

2.2 Equil?ibrio de Nash em estrat?egias puras . . . . . . . . . . . . 26

2.3 Equil?ibrio de Nash em estrat?egias mistas . . . . . . . . . . . 29

2.4 O teorema minimax de von Neumann . . . . . . . . . . . . . 31

3 O teorema de equil?ibrio de Nash

38

4 A forma extensa de um jogo

49

4.1 Representac?~ao de um jogo via alfabetos e a?rvores . . . . . . 49

4.2 Conversa~o entre as formas normal e extensa . . . . . . . . . 58

Bibliografia

61

Cap?itulo 1

Descri?c~ao informal da teoria dos jogos

1.1 Introduc?~ao

A teoria dos jogos ?e uma teoria matema?tica criada para se modelar fen^omenos que podem ser observados quando dois ou mais "agentes de decis~ao" interagem entre si. Ela fornece a linguagem para a descric?~ao de processos de decis~ao conscientes e objetivos envolvendo mais do que um indiv?iduo.

A teoria dos jogos ?e usada para se estudar assuntos tais como eleic?~oes, leilo~es, balanc?a de poder, evoluc?~ao gen?etica, etc. Ela ?e tamb?em uma teoria matema?tica pura, que pode e tem sido estudada como tal, sem a necessidade de relacion?a-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 t?ecnico estrito de como deciso~es s~ao feitas e de como a economia funciona. O desenvolvimento da teoria ainda na~o atingiu este patamar e, hoje, a teoria dos jogos ?e mais estudada em seus aspectos matema?ticos puros e, em aplicac?~oes, ela ?e usada como uma ferramenta ou alegoria que auxiliam no entendimento de sistemas mais complicados.

Neste texto trataremos da Teoria Econ^omica dos Jogos, que na~o deve ser confundida com a Teoria Combinato?ria dos Jogos [4, 11, 5, 2, 6, 7], iniciada por Sprague [20] e Grundy na d?ecada de 30. Enquanto que a primeira tem motivac?~oes predominante econo^micas e procura estabelecer m?etodos para se maximizar o ganho (payoff ), a segunda se concentra nos aspectos combinato?rios de jogos de mesa (por exemplo, ser o jogador a fazer o u?ltimo

2

II Bienal da Sociedade Brasileira de Matem?atica

movimento em um jogo de nim [1]) e na~o permite "elementos imprevis?iveis" como o lanc?amento de um dado ou o baralhamento de cartas.

1.2 Histo?ria

Registros antigos sobre teoria dos jogos remontam ao s?eculo XVIII. Em correspond^encia dirigida a Nicolas Bernoulli, James Waldegrave analisa um jogo de cartas chamado "le Her " e fornece uma soluc?~ao que ?e um equil?ibrio de estrat?egia mista (conceito que nos familiarizaremos posteriormente). Contudo, Waldegrave na~o estendeu sua abordagem para uma teoria geral. No in?icio do s?eculo XIX, temos o famoso trabalho de Augustin Cournot sobre duopo?lio [3]. Em 1913, Ernst Zermelo publicou o primeiro teorema matem?atico da teoria dos jogos [21], o teorema afirma que o jogo de xadrez ?e estritamente determinado, isto ?e, em cada est?agio do jogo pelo menos um dos jogadores tem uma estrat?egia em ma~o que lhe dara? a vito?ria ou conduzira? o jogo ao empate. Outro grande matema?tico que se interessou em jogos foi Emile Borel, que reinventou as soluc?~oes minimax e publicou quatro artigos sobre jogos estrat?egicos. Ele achava que a guerra e a economia podiam ser estudadas de uma maneira semelhante.

Figura 1.1: Ernst Zermelo.

Em seu in?icio, a teoria dos jogos chamou pouca atenc?~ao. O grande matem?atico John von Neumann mudou esta situac?~ao. Em 1928, ele demonstrou que todo jogo finito de soma zero com duas pessoas possui uma soluc?~ao em

Descri?c~ao informal da teoria dos jogos

3

estrat?egias mistas [18]. A demonstrac?~ao original usava topologia e ana?lise

Figura 1.2: John von Neumann.

funcional e era muito complicada de se acompanhar. Em 1937, ele forneceu uma nova demonstrac?~ao baseada no teorema do ponto fixo de Brouwer. John von Neumann, que trabalhava em muitas a?reas da ci^encia, mostrou interesse em economia e, junto com o economista Oscar Morgenstern, publicou o cla?ssico "The Theory of Games and Economic Behaviour " [19] em 1944 e, com isto, a teoria dos jogos invadiu a economia e a matema?tica aplicada.

Figura 1.3: Oscar Morgenstern.

Em 1950, o matema?tico John Forbes Nash Ju?nior publicou quatro artigos importantes para a teoria dos jogos na~o-cooperativos e para a teoria de barganha. Em "Equilibrium Points in n-Person Games" [14] e "Non-cooperative

4

II Bienal da Sociedade Brasileira de Matem?atica

Games" [16], Nash provou a exist^encia de um equil?ibrio de estrat?egias mistas para jogos na~o-cooperativos, denominado equil?ibrio de Nash, e sugeriu uma abordagem de estudo de jogos cooperativos a partir de sua reduc?~ao para a forma na~o-cooperativa. Nos artigos "The Bargaining Problem" [15] e "TwoPerson Cooperative Games" [17], ele criou a teoria de barganha e provou a exist^encia de soluc?~ao 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 pr^emio Nobel por suas contribuic?~oes para a Teoria dos Jogos.

1.3 O que ?e um jogo?

A teoria dos jogos pode ser definida como a teoria dos modelos matem?aticos que estuda a escolha de deciso~es ?otimas sob condic?~oes de conflito. O elemento ba?sico em um jogo ?e o conjunto de jogadores que dele participam. Cada jogador tem um conjunto de estrat?egias. Quando cada jogador escolhe sua estrat?egia, temos enta~o uma situa?c~ao ou perfil no espac?o de todas as situac?~oes (perfis) poss?iveis. Cada jogador tem interesse ou prefer^encias para cada situac?~ao no jogo. Em termos matema?ticos, cada jogador tem uma

Descri?c~ao informal da teoria dos jogos

5

Figura 1.5: John Harsanyi.

Figura 1.6: Reinhart Selten.

6

II Bienal da Sociedade Brasileira de Matem?atica

fun?c~ao utilidade que atribui um nu?mero real (o ganho ou payoff do jogador) a cada situac?~ao do jogo.

Mais especificamente, um jogo tem os seguintes elementos ba?sicos: existe um conjunto finito de jogadores, representado por G = {g1, g2, . . . , gn}. Cada jogador gi G possui um conjunto finito Si = {si1, si2, . . . , simi} de opc?~oes, denominadas estrat?egias puras do jogador gi (mi 2). Um vetor s = (s1j1, s2j2, . . . , snjn), onde siji ?e uma estrat?egia pura para o jogador gi G, ?e denominado um perfil de estrat?egia pura. O conjunto de todos os perfis de estrat?egia pura formam, portanto, o produto cartesiano

n

S = Si = S1 ? S2 ? ? ? ? ? Sn,

i=1

denominado espa?co de estrat?egia pura do jogo. Para jogador gi G, existe uma func?~ao utilidade

ui : S R s ui(s)

que associa o ganho (payoff) ui(s) do jogador gi a cada perfil de estrat?egia pura s S.

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

A situac?~ao ?e a seguinte: dois ladro~es, Al e Bob, s~ao capturados e acusados de um mesmo crime. Presos em selas separadas e sem poderem se comunicar entre si, o delegado de planta~o faz seguinte proposta: cada um pode escolher entre confessar ou negar o crime. Se nenhum deles confessar, ambos ser~ao submetidos a uma pena de 1 ano. Se os dois confessarem, enta~o ambos tera~o pena de 5 anos. Mas se um confessar e o outro negar, enta~o o que confessou ser?a libertado e o outro sera? condenado a 10 anos de prisa~o. Neste contexto, temos

G = {Al, Bob}, SAl = {confessar, negar}, SBob = {confessar, negar}, S = {(confessar, confessar), (confessar, negar), (negar, confessar), (negar, negar)}.

As duas fun?c~oes utilidade

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download