Notas em Teoria dos Jogos e Informaoy

Guilherme HamdanDepartamento de Economia, PUC-Minas e EPGE/FGV

Emanuel OrnelasDepartament of Economics, University of Georgia, USA

13 de novembro de 2006

Sumrio

1 Introduo 31.1 O Que Um Jogo? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Os Elementos Bsicos de Um Jogo . . . . . . . . . . . . . . . . . . . . . 7

2 Jogos Estticos de Informao Completa 112.1 Representao de Jogos Estticos de Informao Completa: Forma Nor-

mal ou Estratgica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Resoluo de Jogos Estticos de Informao Completa . . . . . . . . . . 17

2.2.1 Estratgias Estritamente Dominantes . . . . . . . . . . . . . . . 182.2.2 Estratgias Estritamente Dominadas . . . . . . . . . . . . . . . . 212.2.3 Estratgias racionalizveis (anlise de "melhores respostas") . . . 27

2.3 Equilbrio de Nash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.3.1 Estabilidade, existncia e unicidade do equilbrio de Nash . . . . 322.3.2 Equilbrio de Nash e Eliminao de Estratgias . . . . . . . . . . 352.3.3 Equilbrio de Nash com trs jogadores . . . . . . . . . . . . . . . 382.3.4 Discusso do conceito de equilbrio de Nash . . . . . . . . . . . . 39

2.4 Estratgias Mistas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.5 Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.5.1 Oligoplio de Cournot . . . . . . . . . . . . . . . . . . . . . . . . 562.5.2 Oligoplio de Bertrand . . . . . . . . . . . . . . . . . . . . . . . . 672.5.3 Oligoplio de Bertrand com bens diferenciados . . . . . . . . . . 692.5.4 O problema dos comuns . . . . . . . . . . . . . . . . . . . . . . . 71

Preliminar e incompleto. Gentileza no citar sem a permisso expressa dos autores.yTodos os direitos reservados.

1

3 Jogos Dinmicos de Informao Completa 743.1 Forma Extensiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.2 Induo Retroativa: jogos de informao completa e perfeita . . . . . . . 773.3 Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.3.1 O modelo de Stackelberg . . . . . . . . . . . . . . . . . . . . . . 853.3.2 Barganha sequencial . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.4 Equilbrio Perfeito em Subjogos . . . . . . . . . . . . . . . . . . . . . . . 92

4 Jogos Repetidos 1014.1 Jogos repetidos nitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.2 Jogos repetidos innitamente . . . . . . . . . . . . . . . . . . . . . . . . 1074.3 Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.3.1 Duoplio de Cournot repetido innitamente . . . . . . . . . . . . 1124.3.2 Poltica Monetria Temporalmente Consistente . . . . . . . . . . 114

5 Jogos bayesianos estticos e equilbrio bayesiano de Nash 1185.1 Cournot sob informao incompleta . . . . . . . . . . . . . . . . . . . . 118

6 Informao assimtrica e teoria dos contratos 1236.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.1.1 Dinmica do relacionamento . . . . . . . . . . . . . . . . . . . . 1246.2 Informao simtrica: rst-best . . . . . . . . . . . . . . . . . . . . . . . 125

6.2.1 Descrio do modelo . . . . . . . . . . . . . . . . . . . . . . . . . 1256.2.2 O contrato de informao simtrica . . . . . . . . . . . . . . . . . 126

6.3 Trade-o entre incentivos e risk-sharing: moral hazard . . . . . . . . . . 1316.3.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1316.3.2 Moral Hazard: otimalidade em second best . . . . . . . . . . . . 132

6.4 Seleo adversa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1366.4.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1366.4.2 Um modelo discreto de discriminao de preos: Mussa-Rosen

(1978) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.4.3 First-best: discriminao perfeita . . . . . . . . . . . . . . . . . . 1396.4.4 Informao imperfeita: discriminao de segundo grau (preos

no-lineares) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1406.5 Sinalizao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

2

1 Introduo

Essas notas pretendem dar uma viso compreensiva da noo de comportamentoestratgico e de como essa noo se relaciona intimamente com as cincias sociais emgeral e com economia em particular. Na verdade, no que podemos caracterizar comouma denio cotidiana do que entende-se por um jogo, poderamos dizer que aprimeira idia que geralmente nos ocorre que um jogo uma disputa de qualquerespcie. No entanto isso apenas no basta: uma noo razovel do que seria um jogopor certo nos informaria que jogos tambm so jogados de acordo com algumas regrasparticulares associadas cada jogo ou a um conjunto deles. Isto , se observamos doisjovens trocando sopaposna rua ou em alguma casa noturna qualquer, no diramosque se caracteriza um jogo, mas to somente um destempero ou uma estupidez. Noentanto, se os levarmos para um ringue, selecionarmos oponentes com caractersticasfsicas relativamente prximas s deles, colocarmos luvas e especicarmos quanto tempoeles tm para lutar, o que vale e o que no vale, tudo isso sob o julgo de um terceiro quechamamos juz ou rbitro, ento uma boa parcela das pessoas vai concordar que aquilopode ser chamado de um jogo - no caso, um esporte. Posto isso, no exatamente umproblema pensarmos em exemplos imediatos a partir da caracterizao sugerida. Jogosincluem jogos esportivos, de cartas, de mesa, etc.

A grande maioria dos jogos denidos de acordo com essa lgica possuem um el-emento competitivo e outro interativo. Isto , um jogador deve levar em conta ocomportamento do(s) outro(s) jogador(res) envolvidos no jogo. Nesse sentido, seu graude sucesso nesse jogo depender no apenas da forma como ele prprio se comporta,mas tambm e efetivamente das aes dos demais jogadores que esto no jogo. Por ex-emplo, no tnis, no basta meramente tentar devolver a bola para o outro jogador, massim devolv-la de uma maneira tal que o adversrio no consiga retorn-la. Portanto,notemos, no tnis, a questo aonde jogar a bola?depender, dentre vrios fatores, deaonde o outro jogador est localizado. Da mesma forma ocorre no War, quando nodevemos apenas atacar as regies em funo do nosso objetivo sorteado (e lembre-se, avitria de um jogador nesse jogo signica a derrota de todos os demais participantes),mas tambm em funo do poder de fogo do(s) adversrio(s), que pode(m) retaliar umataque qualquer. Esse elemento de interao a principal caracterstica das situaesque estudamos em teoria dos jogos e o que a distingue das outras reas cujo elementoobjeto de anlise algum tipo de processo de tomada de deciso por parte de agentesracionais, em um sentido que car claro no decorrer do texto.

H vrias caractersticas que so comuns a um grande leque de jogos. Primeiro, osjogos possuem regras, mas exatamente o qu essas regras iro especicar? Sabemosque as regras de uma situao de interao estratgica podem ser as mais diversaspossvies, mais ou menos pormenorizadas e tambm mais ou menos complexas. Noentanto podemos sugerir algumas caractersticas mais gerais que vo estar incorporadas

3

pela quase totalidade dos jogos tais quais a gente os conhece. Primeiro, quais so osjogadores. Em todo jogo h dois ou mais jogadores1, cada um deles consciente do que melhor para si prprio. Logo, para a gente, um jogador to somente um agenteinserido em um processo de tomada de deciso, de escolha, no qual o comportamentoalheio importa. Segundo, as regras especicam a ordem nas quais as aes so tomadas,assim como que aes so essas, que aes que cada jogador pode escolher. Ns vamoschamar essas aes passveis de escolha por um jogador de estratgia. E terceiro, asregras denem qual(is) (so) o(s) resultado(s) do jogo em funo das escolhas tomadaspor cada um dos jogadores. Observe ento que o resultado que um jogador (ou umgrupo de jogadores com o mesmo objetivo, uma equipe) qualquer obter depende noapenas de seu comportamento como tambm das escolhas (aes) feitas pelos demaisjogadores. Cada jogador sabe disso, e sabe que escolher a sua melhor ao possvelrequer uma previsoeciente do que ele acha que os outros jogadores iro escolher.

Essas caractersticas gerais de jogos tipicam vrias situaes do mundo real que noso jogos no sentido esportivo ou de diverso. Por exemplo, quando um representantepatronal e um lder sindical se engajam em um processo de barganha sobre a formaode um novo contrato, pode-se caracterizar facilmente uma situao de jogo. As regras,nesse ambiente, no so to detalhadas e formais como um Scotland Yard, por ex-emplo, mas h regras: ofertas e contra-ofertas so feitas pelas partes interessadas, quebuscam um acordo nal o mais favorvel possvel para o seu lado. E mais, a formulaoda oferta por um dos lados da negociao deve considerar qual ser a reao do outrolado em funo dessa oferta que ele recebeu. Outros exemplos de barganha podemser extrados no nosso dia-a-dia, como o caso quando compramos ou vendemos umautomvel, fazemos um contrato de aluguel etc. Obviamente cada situao tem suasespecicidades, mas h vrios elementos comuns em todos esses tipos de negociao.

A moderna teoria dos jogos iniciou sua evoluo j h algum tempo. Um primeiromarco terico da sua fase moderna constituiu-se na contribuio de Von Neumann eMorgenstern (1944). Entretanto, seu conceito mais difundido surgiu de um artigo deJohn Nash - um dos trs2 agraciados com o Prmio Nobel de economia em 1994, de-vido aos trabalhos na rea de teoria dos jogos -, em 1951. Depois disso, muito j sefez, embora a teoria dos jogos tenha alcanado a importncia que hoje detm apenasem perodos mais recentes, especialmente a partir da dcada de 1980. Atualmente,o arcabouo de jogos ganha valor crescente, medida em que aumentam suas possi-bilidades de aplicao. Ele hoje amplamente utilizado em economia - em anlisesde consistncias intertemporais de polticas econmicas, em organizao industrial,poltica antitruste e regulao, em teoria de leiles, em estrutura penal tima e em

1Se voc estiver pensando em algum jogo no qual no h outros jogadores em carne e ossocomovoc, como o caso de diversos vdeo-games, lembre-se que voc est jogando contra a mquina. Damesma forma, algum que est jogando pacinciaest jogando contra o baralho.

2Os outros dois foram John Harsany e Reinhard Selten.

4

muitos outros casos -, mas no se restringe a ela: envereda-se tambm por outras readas cincias sociais, como a sociologia, cincia poltica e direito, por exemplo. Um mo-tivo para no estud-la no pode ser, portanto, alguma eventual falta de abrangnciae aplicabilidade.

Outro ponto relevante a se ressaltar aqui nessa introduo diz respeito taxanomiada disciplina. Podemos dividir o estudo de teoria dos jogos em dois grandes gruposditos jogos cooperativos e os no-cooperativos, cuja distino formal foge do escopodo nosso estudo. Apenas o segundo grupo ser estudado. Essa escolha baseia-se nofato de que so sobre os jogos no-cooperativos que a teoria mais desenvolvida etem maior aplicabilidade de interesse especco economia. Alm disso, pode-se, comalgumas hipteses adicionais, tratar os jogos cooperativos como se tambm fossemno-cooperativos. Por trs desses, a idia bsica que cada indivduo eminentementeegosta, ou seja, procura sempre agir de modo a obter o maior benefcio possvel parasi mesmo, independente do que possa acontecer s outras pessoas. Evidentemente nemsempre se vericam situaes como essas. Pode ocorrer de um indivduo preocupar-secom o que acontecer com outros indivduos, alterando por isso a sua forma de agir emfuno de algum tipo deliberado de altrusmo - pense, por exemplo, em situaes queenvolvam familiares prximos. Todavia, essas possibilidades podem ser abordadas tam-bm pela tica individualista. Para isso, basta supor que todos os aspectos que afetam(positiva ou negativamente) outras pessoas j estejam considerados nos nmeros refer-entes aos nveis de ganhos (ou utilidade) relacionados a cada situao (que chamaremosde payos). Essa a abordagem que utilizaremos em todo o texto: cada jogadorescolher suas aes de modo a ter o maior benefcio para si mesmo em cada situao,sendo que esse termo maior benefcio considerar todos os aspectos da realidaderelacionados prpria pessoa e s outras pessoas que o indivduo leva em consideraode alguma forma. Agindo assim, esse indivduo poder ser chamado de racional,hiptese que adotaremos indiscriminadamente.

Uma vez que esteja claro que trataremos apenas de jogos no-cooperativos, vamosadotar um taxonomia padro nos cursos de teoria dos jogos e que decorre basicamentede duas noes associadas respectivamente dinmica (ao timing) das escolhas dojogadores e idia de informaoque adotaremos. Com relao ao timingdo jogo,classicamos os jogos como jogos estticos e jogos dinmicos. No primeiro caso as escol-has dos jogadores so simultneas (como em um jogo de par ou mpar) e no segundo sosequenciais, no sentido de que algum jogador, ao tomar sua deciso, j observou algumaescolha alheia que relevante para essa sua escolha. Por outro lado, para cada tipo dejogo que venhamos a analisar nesse curso, estar associada, explcita ou implicitamente,alguma caracterizao informacional do ambiente. Essa caracterizao fundamental epara termos uma idia inicial da explicao de sua relevncia basta focarmos mais umavez no carter de interdependncia da interao entre os agentes: se verdade que o

5

comportamento alheio importa para cada jogador em particular, ento o processamentodas informaes (ou seja, o conhecimento) que cada um tem sobre esse comportamentoalheio em si um elemento relevante de anlise. Jogos no-cooperativos so portantoclassicados de acordo com uma srie de conceitos associados cada situao, como in-formao completa ou incompleta, perfeita ou imperfeita, simtrica ou assimtrica etc.Para ns aqui nesse curso ser de fato importante entender o que signica conhecerum fato sequencialmente e trabalharmos com as idias de jogos estticos e dinmi-cos de informao completa (e perfeita/imperfeita) e jogos estticos e dinmicos deinformao incompleta, nessa ordem. Para cada uma dessas noes especicaremos umconceito de equilbrio segundo o qual faremos previses sobre o comportamento dosjogadores envolvidos de forma a inferir alguma coisa sobre o resultado daquele jogo.

Isto posto, tenha em mente que o objetivo deste texto apresentar os principais de-senvolvimentos e aplicaes da teoria dos jogos. Para tanto seus conceitos mais impor-tantes so apresentados, no sentido de possibilitar a previso dos resultados de algunsjogos, com maior ou menor acuidade. O texto procurar se ater s formalizaes apenasna medida em que as consideramos necessrias para denir precisamente o objeto em es-tudo, mas espera-se que em momento algum o aluno se veja em diculdades em funode algum tipo de formalizao. Praticamente nenhuma demonstrao matemtica desenvolvida, uma vez que a nossa meta apresentar um texto de nvel introdutrio,acessvel queles com razovel domnio dos conceitos bsicos de (micro)economia. Valeressaltar tambm que no um objetivo apresentar qualquer inovao terica, masapenas sistematizar alguns dos aspectos mais importantes e j consolidados de teoriados jogos, uma vez que ainda no existe nenhum texto satisfatrio publicado em por-tugus que tenha as caractersticas de referncia bsica e, ao mesmo tempo, trate doassunto com a profundidade mnima requerida. Obviamente, uma innidade de de-senvolvimentos recentes da teoria no sero incorporados no texto, que, pode-se dizer,tenta simplesmente cumprir o papel de um livro-textopara estudantes de graduaoem economia - e nada mais alm disso.

1.1 O Que Um Jogo?

Seguindo a denio de Mas-Collel et.al. (1995, p.219), pode-se denir um jogocomo uma representao formal de uma situao onde um nmero de indivduos in-teragem em um cenrio de interdependncia estratgica. Isto , o bem-estar de cadaum depende no apenas das prprias aes, mas tambm das aes dos demais en-volvidos. Assim, a melhor ao que cada jogador pode escolher em geral depender daexpectativa sobre o que os demais jogadores iro fazer.

Situaes como essa so, claramente, muito distintas daquelas estudadas nos cursosde microeconomia tradicional: tanto na teoria do consumidor quanto na de mercadosconcorrenciais e monopolizados, essa interdependncia no explicitamente incorpo-

6

rada. Sendo assim, naqueles casos os indivduos, as rmas ou as instituies (governo,por exemplo), ao denirem suas escolhas timas, no se preocupam com o que os out-ros agentes podero fazer. Por outro lado, se existe a interdependncia, caracteriza-seento uma situao onde h externalidades nas aes dos agentes, e por isso cadaum, ao fazer suas escolhas, preocupa-se com como os outros iro (ou podero) agir.Dessa forma o que estamos buscando em ltima instncia to somente emprestar anlise das situaes de interesse um elemento a mais de realismo que decorre do fatode que pessoas, empresas e instituies interagem entre si e que essas interaes tmimplicaes relevantes do ponto de vista individual e social.

Com essa denio, podemos perceber que praticamente todas as situaes queusualmente as pessoas chamam correntemente de jogo de fato so aqui tambmcaracterizadas como tal. Todavia, muitas outras situaes, inclusive (mas no apenas)econmicas e jurdicas, tambm se enquadram na denio.

1.2 Os Elementos Bsicos de Um Jogo

Em geral (mas nem sempre), um jogo deve fornecer ao analista algumas informaeselementares, quais sejam:

1. os jogadores (quem so os envolvidos?),

2. as regras (quem move quando? O que se sabe quando for sua vez de jogar? etc.),

3. os resultados (para cada conjunto de aes dos jogadores, quais so os resulta-dos?),

4. os payos (quais so as preferncias - representadas em suas funes de utilidade- dos jogadores em relao aos resultados possveis de forma que tenhamos umaordenao inequvoca dos resultados?).

Antes de apresentarmos exemplos que ilustraro os elementos acima, faremos umapequena digresso sobre o ponto (4), em relao aos ganhos (payos3) que cada agentetem ao se engajar em um processo de interao estratgica.

Preferncias e utilidade: Em quase toda a teoria que abordaremos nesse curso,fundamentalmente estaremos tratando de processos de escolhas feitas por agentes4

3A opo por se utilizar na maioria das vezes o termo "payo "e no "ganho"decorre do fato de quequase a totalidade dos artigos e textos em portugus que utilizam a linguagem de jogos tambm fazisso. Isso verdade para outros termos corriqueiros na linguagem de jogos, como "players"(jogadores),por exemplo.

4A partir daqui utilizaremos os termos agentes e jogadores indiscriminadamente como similares.Podem ser consumidores, rmas, governo ou qualquer outra pessoa fsica ou jurdica (mesmo informal,

7

racionais. Sem perda de generalidade, considere por enquanto que agentes racionaisso aqueles que, tendo que escolher uma opo dentre um conjunto de possibilidades,escolhe aquela que melhor lher convier - ou dito de outra forma, aquela que lhe d amaior utilidade. Vamos rapidamente qualicar esse processo de escolha5.

Considere um cidado que est sendo acusado pelo Estado de um delito qualquer.Em um depoimento autoridade legal constituda, ele pode contar trs estrias queso igualmente crveis, no importando se alguma delas ou no verdica. Chamemosessas opes de escolha de 1; 2; 3. Por algum motivo qualquer, esse cidado sabe quesua pena no caso de escolher cada uma das opes de 3,6 ou 9 meses, respectivamente.Considerando que no caso dele car preso lhe confere um custo (crescente no tempo depriso, de maneira que esse indivduo est tanto pior quanto maior for o seu tempo depriso), ento podemos dizer que a opo 1 (estritamente) prefervel opo 2, que aopo 1 (estritamente) prefervel opo 3 e que a opo 2 (estritamente) prefervel opo 36. Logo, se esse cidado escolhe a opo 1, dizemos que ele racional. Seas penas fossem de 3,3 e 6 meses , respectivamente, ento diramos que a opo 1 prefervel opo 2, que a opo 2 prefervel opo 1 (de modo que as opes 1 e2 so opes semelhantes do ponto de vista de quem est escolhendo - dizemos que oagente indiferente entre 1 e 2), que a opo 1 (estritamente) prefervel opo 3. eque a opo 2 (estritamente) prefervel opo 3. Nesse caso, se o cidado escolhessea opo 1 ou a opo 2 diramos que ele racional.

Na verdade o que estamos propondo aqui to somente uma forma de organizarteoricamente o processo de escolha de um agente qualquer. Adotamos a hiptese deque, no caso em que ele tem que fazer uma escolha dentre um leque de opes, esseagente capaz de ordenar todas essas opes de acordo com suas preferncias7. Essaspreferncias, por sua vez, so formalmente representadas por funes matemticas ditas"funes utilidade". Antes que algum se assuste com algum argumento formal, vamoslogo dizer que uma funo utilidade apenas traduz de maneira numrica o processoatravs do qual um agente, um jogador, faz a sua escolha. No exemplo acima, suponhaque essa funo fosse dada por

u (x) =1

x, onde x 2 f3; 6; 9g .

no sentido de no estar inserido em algum sistema legal constitudo, como por exemplo uma rma queopera no setor informal da economia ou um criminoso) que possa ser representada em alguma situaode comportamento estratgico.

5Essa seo uma insero muito breve de textos encontrados comumente em livros-textos demicroeconomia. Os alunos interessados devem recorrer a esses livros para uma exposio mais completado assunto.

6Dizemos que as preferncias de um agente qualquer so "transitivas"quando, por exemplo, dadastrs opes 1,2 e 3 tais que 1 prefevel a 2 e 2 prefervel a 3, podemos dizer que 1 prefervel a 3.

7Nesse caso dizemos que as preferncias so "completas": entre um conjunto de duas ou mais opesno processo de escolha, o agente sempre capaz de ordenar essas opes de acordo com um ndice indicaseu bem-estar, uma funo utilidade.

8

Isso , a utilidade do agente depende das escolhas que ele deve fazer e que, cada uma,lhe custaro algum tempo de cadeia, x = 3; 6 ou 9 meses. Ento8>:

u (3) = 13u (6) = 16u (9) = 19

tal que, observe, u (3) > u (6) > u (9)

de maneira que, por esse critrio, o agente seria racional8 se escolhesse a opo 1, namedida em que a sua utilidade seria maior do que se escolhesse qualquer das outrasduas possibilidades. importante notar que a funo acima, u (x) = 1x , no a nicafuno que pode representar as preferncias do nosso agente - na verdade h inmeraspossibilidades. Por exemplo, suponha que

u (x) =a

x, onde a > 1 uma constante e x 2 f3; 6; 9g .

Nesse caso, 8>:u (3) = a3u (6) = a6u (9) = a9

tal que, novamente, u (3) > u (6) > u (9)

Segue ento que para a gente no importa exatamente o quanto um agente prefere umaopo outra, mas to somente a ordem na qual ele estabelece essas opes. Nessesentido, ambas as funes utilidades representam as preferncias do mesmo agentedescrito acima. Faa a mesma coisa para o segundo ordedamento proposto acima, 3,3e 6 meses, e verique o que se d.

Isto posto, uma funo de ganho ("payo") to somente uma representaonumrica das preferncias dos jogadores em funo de suas possibilidades de escolha.No entanto, como se trata de situaes de interdependncia estratgica, essa funodepende tambm das possibilidades de escolha dos demais jogadores envolvidos. Masno nal o nmero associado quelas opes escolhidas na verdade reetem um conjuntode preferncias subjacentes que nos permitiro ordenar as opes de escolha de cadajogador de uma forma clara que car expressa nos exemplos abaixo.

8Nesse ponto do texto, sem considerarmos elementos de interao estratgica, dizemos que umagente racional se suas preferncias so completas e transitivas.

9

Exemplos: Denidos os elementos principais e feita essa breve explanao sobre arepresentao das preferncias dos jogadores, podemos sugerir alguns exemplos simplespara comearmos a pensar em situaes passveis de serem modeladas como jogos.

Exemplo 1 - Casamento de moedas (este usualmente um dos primeiros exemplosde jogos que os textos mais didticos sobre o tema apresentam)

1. h dois jogadores, ditos 1 e 2,

2. cada jogador joga simultaneamente uma moeda para cima,

3. se o resultado das duas moedas for o mesmo, 1 paga R$1,00 para 2; caso contrrio,a ordem do pagamento se inverte,

4. depende da especicao da funo utilidade, de como cada jogador avalia a im-portncia que tem para si ganhar ou perder R$1,00.

Exemplo 2 - Jogo da Velha

1. novamente h dois jogadores, ditos X e O;

2. como todos quase certamente conhecem o jogo, dena voc mesmo(a) como umexerccio os seus elementos bsicos.

Os exemplos acima so situaes de claro conito, uma vez que o que um jogadorganha o outro perde: so exemplos do que chamamos de jogos de soma zero. Essa uma possibilidade, mas que no necessariamente sempre ocorrer. O exemplo abaixofornece um caso diferente, onde dois jogadores ou ganham juntos ou perdem juntos.

Exemplo 3 - Encontro em BH

1. dois jogadores: Joo e Maria;

2. os dois jogadores esto separados e incomunicveis. Eles marcaram de se encon-trar em algum lugar no centro s 12:00 hs para almoar. Mas deixaram o lugarem aberto, dentre duas opes e ento perderam a comunicao. Cada um temde decidir aonde ir;

3. se eles se encontrarem, almoam juntos. Caso contrrio, sozinhos;

4. eles teriam payos iguais a uma unidade (qualquer que seja) almoando juntos,e de zero almoando sozinhos.

Como se percebe nesse ltimo caso, os jogadores tm interesses alinhados - o prob-lema a se tentar superar a falta de coordenao entre eles. Claramente, portanto,esse no um jogo de soma zero.

10

2 Jogos Estticos de Informao Completa

A primeira classe de jogos que sero apresentados so chamados jogos estticos, emcomparao com os sequenciais (ou dinmicos), que sero vistos mais frente. Essesjogos so ditos tambm jogos simultneos, uma vez que os jogadores denem suasformas de agir ao mesmo tempo. O exemplo imediato o jogo de par ou mpar,no qual os dois jogadores revelam suas estratgias ao mesmo tempo. Antes que se faaalguma restrio sobre a realidade dessa premissa, note que no necessrio que defato os jogadores faam suas escolhas literalmente ao mesmo tempo, mas to somenteque cada um dos jogadores, ao fazer a sua escolha sobre qual estratgia adotar, notenha observado as escolhas feitas pelos demais jogadores. Nesse caso poderamos terum jogo de par ou mpar, esttico, em que um dos jogadores fez a escolha, digamos,10 minutos antes do outro. Basta que o outro jogador, ao escolher o seu nmero, nosaiba qual foi a escolha daquele que jogou primeiro.

Quanto ao carter de informao completa, refere-se ao fato de que cada um dosenvolvidos conheam as funes de ganho de todos os outros. Sendo um pouco maisrigoroso, isso signica que a funo payo de cada jogador de conhecimento comum(common knowledge). Como exemplo, considere um jogo com dois jogadores, 1 e 2.Como j sabemos, esses jogadores tm um conjunto de opes dentre as quais cadaum deve escolher uma da melhor forma que lhe convier. Mas sabemos cada par deescolhas possveis associa a cada jogador uma utilidade, um nmero de acordo com oqual pode-se identicar se cada um est em melhor ou pior situao do que nas demaisopes. Nesse contexto, dizer que o jogo de informao completa signica dizer quecada jogador sabe no apenas a sua utilidade para cada combinao de escolha masconhece tambm a utilidade do outro jogador em cada situao. Mas mais do queisso: cada jogador sabe tambm que o outro conhece a sua utilidade associada a essasopes. E mais ainda: cada jogador sabe que o outro sabe que ele sabe a utilidade dooutro jogador em cada situao. E assim sucessivamente.

Sendo um pouco mais formal, dizemos que um jogo qualquer de informao com-pleta quando a funo de ganho (payo) de cada jogador de "conhecimento comum".Para entendermos o que esse termo signica, considere como exemplo uma situao comapenas dois agentes, 1 e 2. Ns dizemos que um evento X qualquer de conhecimentocomumnesse jogo se

1 sabe que X ocorreu; 2 sabe que X ocorreu.

1 sabe que 2 sabe que X ocorreu; 2 sabe que 1 sabe que X ocorreu.

1 sabe que 2 sabe que 1 sabe que X ocorreu; 2 sabe que 1 sabe que 2 sabe queX ocorreu

11

e assim innitamente. Sendo assim, um jogo esttico com dois jogadores, 1 e 2, de informao completa se, na denio acima

X = funo de ganho (payo) do outro jogador.

Ou seja,

1 conhece a funo payo de 2; 2 conhece a funo payo de 1.

1 sabe que 2 conhece a funo payo de 1; 2 sabe que 1 conhece a funo payode 2.

1 sabe que 2 sabe que 1 sabe a funo payo de 2; 2 sabe que 1 sabe que 2 sabea funo payo de 1.

e assim sequencialmente.Nesse jogos estticos de informao completa (por denio, a funo de ganho

de conhecimento comum) assumimos tambm que a racionalidade9 dos jogadores deconhecimento comum. Nesse caso,

1 sabe que 2 racional; 2 sabe que 1 racional.

1 sabe que 2 sabe que 1 racional; 2 sabe que 1 sabe que 2 racional.

1 sabe que 2 sabe que 1 sabe que 2 racional; 2 sabe que 1 sabe que 2 sabe que1 racional

e assim innitamente.Logo adiante, quando comearmos a analisar a resoluo de jogos estticos de infor-

mao completa, car claro porque a noo de conhecimento comum de um determi-nado evento relevante. Essa hiptese (informao completa) ser utilizada em quasetodo o texto, sendo exibilizada apenas no nal - isso se houver tempo hbil. O motivofundamental dessa restrio que a sua no utilizao dicultaria signicativamentea anlise, fugindo do escopo do texto e do curso - embora a teoria dos jogos de in-formao incompleta j tenha sido signicativamente desenvolvida e consolidada, masdenitivamente est em um patamar de complexidade superior ao aqui pretendido.

Vamos a partir de agora propor uma estrutura que ser seguida ao longo dessasnotas: uma vez entendido o conceito mais amplo (aqui, jogos estticos de informaocompleta), vamos fazer uma exposio sobre a forma correta de representar esse tipode jogo e posteriormente discutir como solucionar essa classe de jogos, com diversasnuances especcas associadas a cada uma das situaes. Disso tratamos agora.

9A denio de racionalidade nesse contexto de interdependncia est descrita na prxima seo dotexto.

12

2.1 Representao de Jogos Estticos de Informao Completa: FormaNormal ou Estratgica.

A forma que utilizamos para representar jogos estticos de informao completa dita forma normal (ou estratgica). De acordo com a forma normal, devemos ter asseguintes informaes sobre um jogo com n > 1 jogadores:

1. Os jogadores: 1; 2; :::; n.

2. O espao (ou conjunto) de estratgia de cada jogador. Esse conjunto vai nos dizerquais so as possibilidade de escolha de cada um dos jogadores. Por exemplo, nojogo par ou mparo espaco de cada jogador i = 1; 2

Si = fpar, mparg

Nesse ponto deve estar claro que o que chamamos de estratgia apenas umaopo, uma escolha, uma ao possvel que cada jogador pode tomar.

3. A funo de ganho (payo) para cada jogador i = 1; 2; :::; n. Essa funo, paraum jogador i qualquer, associa um nmero em funo das possibilidades de escolhade cada jogador. ela que caracteriza o elemento de comportamento estratgicodos jogos na medida em que o ganho de cada jogador afetado pela sua prpriaescolha mas tambm afetado em alguma medida pelas estratgias adotadas porcada cada um dos demais jogadores.

Nos jogos estticos, o conjunto das estratgias disponveis a cada jogador so defcil visualizao, correspondendo s opes de ao que cada jogador pode escolher.Veremos posteriormente que nem sempre elas sero to claras, como no caso dos jogosdinmicos. Sendo um pouco mais rigoroso, tome a denio abaixo:

Denio: A representao na forma normal de um jogo J com n jogadoresespecica para cada jogador i = 1; 2; :::; n um conjunto de estratgias Si e umafuno de ganho ui (s1; :::; sn), onde si 2 Si. Formalmente, escreve-se

J = (Si; ui (si; si))i=1;2;:::;n

Em suma, a representao na forma normal ou estratgica dene quais so osjogadores envolvidos, quais so as estratgias disponveis a cada um deles e ospayos para cada jogador referentes a todos os resultados possveis.

1. os jogadores 1,2,...,n.

13

2. os espaoes de estratgias,8>>>>>:S1 = fs11; s12; :::; s1k1gS2 = fs21; s22; :::; s2k2g

:::

Sn = fsn1; sn2; :::; snkngonde sij 2 Si a j-sima opo (estratgia) que o jogador i pode adotar no jogo.

3. a funo de ganhos e os payos de cada jogador,

ui : Si Si ! R| {z }ui(si;si)2R

Ou seja, uma funo especca a cada jogador que associda um nvel de utili-dade a partir da sua escolha (si 2 Si) e das escolhas dos demais n 1 jogadores(si 2 Si). Aqui o termo si denota as escolhas de todos o jogadores que no ojogador i.

Exemplo 4 - Dilema dos Prisioneiros: este constitui certamente o exemplo mais con-hecido em teoria dos jogos, em funo da sua estrutura simples e do seu resultadointrigante. H inmeras verses do jogo, que pode ser adaptado a situaes muito dis-tintas entre si. Mostraremos aqui primeiro a verso de Dixit e Nalebu (1994), umadas mais criativas. Depois analisamos a estria padro.

A idia que havia um maestro que viajava de trem na antiga URSS. Com aparnciano convencional, foi interpelado pelos policiais da KGB, que imaginaram poder tratar-se de um espio. Revistando suas bagagens, os policiais encontraram partituras, queinterpretaram como cdigos. Apesar do maestro insistir que eram apenas partiturasde msicas de Tchaikvski que ele interpretava, acabou sendo preso. Passado algumtempo na priso, chegaram os ociais ao maestro e disseram-lhe que ele teria um diapara decidir-se entre confessar ou no, mas que seria melhor confessar, uma vez queeles j haviam prendido o tal de Tchaikvski. A proposta, feita aos dois prisioneiros,era a seguinte: se ambos confessassem, cada um caria preso seis anos; se ningumconfessasse, como no haveriam provas concretas, cariam ambos presos por um ano; seum confessasse e o outro no, o primeiro seria solto imediatamente, como prmio suacolaborao com a KGB, enquanto o outro, que alm de culpado no havia colaborado,caria detido por nove anos. O jogo representado abaixo na forma normal em uma(bi)matriz, que uma matriz aonde cada entrada possui dois nmeros:

TchaiskvskiNC C

Maestro NC 1;1 9; 0C 0;9 6;6

14

Logo, se est na forma normal, devemos extrair as trs informaes: (i) os jogadores:Maestro e Tchaiskvski; (ii) para cada um dos jogadores, as estratgias possveis: con-fessar (C) e no confessar (NC) e (iii) a funo de ganho de cada jogador: os payosdo jogador 1 - Maestro - situam-se esquerda em cada clula. Por sua vez, os payosdo jogador 2 - o que teve o azar de se chamar Tchaikvski - encontram-se direita.Essa ser a regra utilizada em todo o texto e que padro na representao na formaestratgica: o jogador 1 e suas estratgias esquerda, o jogador 2 e suas estratgiasacima e, em cada clula, os payos dos jogadores 1 e 2 esquerda e direita, re-spectivamente. Aqui, portanto, o nmero de jogadores igual a dois, o conjunto deestratgias do Maestro fC;NCg, assim como o o do jogador Tchaikvski tambm esse. Os resultados possveis e os payos para cada um deles so os mostrados noquadro acima: por exemplo, se ambos no confessam, cada jogador ganha (1;1),que uma medida do bem-estar, da utilidade (ou desutilidade, no caso) dos jo-gadores Maestro e Tchaiskvski, respectivamente, caso ambos de declaram inocente. Algica que se ambos confessam, cam cada um 6 anos presos. Se ambos se declaraminocentes, no h provas sucientes mas em funo do processo cada um ca 1 anopreso. E se um jogador confessa e o outro no, ento aquele que confessou tem umprmio por ter confessado e imediatamente libertado, enquanto que aquele que noconfessou punido por sua atitude de suposta no-cooperao e ca preso por 9 anos.

Essa to somente uma primeira representao do Dilema dos Prisioneiros adaptadapara a estria acima. Outra estria, mais simples e recorrente, to somente que duaspessoas foram presas pela polcia e acusadas de cometer um delito qualquer - masns no sabemos (nem ningum, a no ser os prprios jogadores) se efetivamente eles(ou um deles) so ou no culpados. Eles esto presos em celas separadas e cada umtem a opo de confessar ou no a autoria do delito. Sendo um jogo esttico deinformao completa, quando cada jogador faz a sua escolha ele no sabe a escolhado outro jogador (jogo esttico). Alm disso, a matriz de ganhos de conhecimentocomum (jogo de informao completa), de modo que ambos os jogadores visualizam semnenhuma incerteza a matriz de ganhos, com as estratgias de cada jogador e os payosde cada um para cada combinao de estratgias possveis. Note que esses payos sorepresentaes relativas das preferncias de cada jogador e de forma alguma nico -observe que os payos no jogo acima so distintos dos payos no jogo abaixo. O queimporta que toda representao possvel dessa estria preserve o ordenamento dosganhos dos jogadores. Por exemplo, a matriz

Jogador 2No Confessa (NC) Confessa (C)

Jogador 1 No Confessa (NC) 5; 5 1; 7Confessa (C) 7; 1 4; 4

15

tambm pode ser a forma normal da mesma estria que descreve o Dilema dos Pri-sioneiros.

Esse jogo, veremos adiante, tem um resultado surpreendente: ainda que ambosos jogadores.sejam inocentes e que ambos estejam melhor quando ambos jogam noconfessar, NC, o melhor que cada um pode fazer individualmente se declarar culpado ejogar C. Esse resultado decorre em funo do elemento de interdependncia estratgicaque caracteriza o Dilema dos Prisioneiros.

Exemplo 5 - Par ou mpar. Como exerccio, descreva o jogo de par ou mpar a partirda matriz abaixo. Quais so os jogadores? E as estratgias de cada um? Quem jogoupar e quem jogou mpar?

Jogador 2Par mpar

Jogador 1 Par 1;1 1; 1mpar 1; 1 1;1

Exemplo 6 - Guerra dos sexos. Um homem e uma mulher (na verdade um casal)devem decidir o programa que faro hoje noite. Eles podem ir ao teatro ou ir aoMineiro ver um jogo de futebol. A matriz abaixo descreve o jogo:

MulherMineiro Teatro

Homem Mineiro 3; 2 1; 1Teatro 1; 1 2; 3

Descreva o jogo (jogadores, estratgias e payos) e note que o homem prefere ir aofutebol acompanhado da mulher. Mas ele prefere ir ao teatro acompanhado da mulherdo que ir sozinho ao Maracan. O mesmo acontece com a mulher, s que ela dpreferncia pelo teatro.

Exemplo 7 - O jogo do covarde ("the chicken game"). Nesse jogo dois motoristas,1 e 2, se encontram em um estrada. Naquele lugar especco, h uma ponte estreita,de modo que apenas um veculo passa de cada vez. Logo, cada um pode avanar ouesperar o outro passar primeiro. Se algum dos jogadores, 1 por exemplo, avana e ooutro espera, ele segue sua viagem e o outro espera um pouco mais - e vice-versa. Masse ele avana e o oponente tambm, ento h uma coliso e ambos perdem. O jogo representado na bimatriz abaixo:

Motorista 2Avana Espera

Motorista 1 Avana 5;5 5; 0Espera 0; 5 1; 1

16

Exemplo 8 - Pedra x Papel x Tesoura. Neste jogo (um par ou mpar mais sosticado),cada jogador escolhe simultaneamente um dos trs objetos relacionados abaixo (suasestratgias). Dependendo da combinao nal, pode-se ganhar 1, -1 ou 0 (a lgica que pedra ganha de tesoura, que vence o papel, que se sobrepe pedra; se o objeto foro mesmo, ningum ganha).

Jogador 2pedra papel tesoura

pedra 0; 0 1; 1 1;1Jogador 1 papel 1;1 0; 0 1; 1

tesoura 1; 1 1;1 0; 0Temos portanto na forma normal (ou estratgica):

1. os jogadores: 1 e 2.

2. os espaos de estratgias. Ou seja, o que cada jogador pode vir a jogar,

S1 = S2 = fpedra, papel, tesourag

3. a funo de ganho (payo) de cada jogador: qual o ganho que jogador ter paracada combinao possvel de estratgias.

H inmeros exemplos de jogos estticos de informao completa. Alguns deles nsveremos nesse texto ao discutir uma srie de questes associdas s solues de jogosestticos de informao completa. Outros no sero tratados aqui, mas o contedo dessetexto mais do que suciente para que voc entenda eventuais casos no tratados aqui.

2.2 Resoluo de Jogos Estticos de Informao Completa

Vamos a partir de agora analisar a soluo de jogos estticos de informao com-pleta. Devemos ter em mente que solucionar um jogo signica buscar determinar quaisestratgias jogadores racionais adotariam em ambientes nos quais a racionalidade dosjogadores de conhecimento comum10. Ou seja, discutir a soluo de um jogo signicaanalisar mtodos de previso dos seus resultados. Aqui, duas so as caractersticasprincipais. A primeira a preciso, que se refere ao fato de que, uma vez que sugeri-mos (previmos) um resultado, a probabilidade de que ele realmente venha a ocorrer emuma manifestao real do jogo ser tanto maior quanto mais preciso tiver sido o mtodo

10Nesse ponto j deve estar claro o que signica um evento qualquer ser de conhecimento comum.Nesse sentido, lembre-se que dizer que a racionalidade dos jogadores de conhecimento comum em umjogo com dois jogadores, 1 e 2, signica dizer que 1(2) sabe que 2(1) racional, que 1(2) sabe que 2(1)sabe que 1(2) racional e assim sucessivamente.

17

de previso utilizado. A outra refere-se abrangncia do mtodo, que diz respeito aonmero de situaes onde exista interdependncia estratgica entre os envolvidos queele consegue oferecer um resultado provvel para ele. Infelizmente, em geral os mtodosmais precisos so os menos abrangentes, e vice-versa. Procuraremos apresent-los emordem decrescente de preciso (consequentemente, em ordem crescente de abrangn-cia). Portanto, o primeiro gerar respostas a muito poucos jogos, com a vantagemde que, quando a apresentar, essa ser altamente convel. Por outro lado, o ltimopropiciar respostas a um nmero muito superior de situaes, embora seus resultadosdevam ser compreendidos com algumas ressalvas que ns iremos discutir.

2.2.1 Estratgias Estritamente Dominantes

Considere o Dilema dos Prisioneiros,

Jogador 2NC C

Jogador 1 NC 5; 5 1; 7C 7; 1 4; 4

Em um jogo como este (e em todo jogo esttico de informao completa), dizemosque uma estratgia de um jogador qualquer (do jogador 1, por exemplo) uma es-tratgia estritamente dominante se, independente da escolha do outro jogador, oganho que ele tem jogando esta estratgia estritamente maior do que o ganho que eleteria jogando a outra estratgia. Como h duas estratgias, "No Confessar"e "Con-fessar", temos que analisar essas duas possibilidades. Para vericar se h a existnciade estratgias estritamente dominantes, basta olhar, para cada jogador, se existe umaescolha que gere sempre o maior payo para ele. Em um jogo representado na formanormal, na forma de matriz, deve-se ento supor que o outro jogador escolha cada umadas suas estratgias possveis. Se a melhor alternativa for sempre a mesma, ento essase constitui em uma estratgia estritamente dominante. Indo direto ao ponto, considerea estratgia "Confessar"do jogador 1. Se o outro jogador, 2, joga "No Confessar", oganho de 1 jogando "Confessar" maior do que jogando "No Confessar", 7 > 5. E se2 joga "Confessar", o ganho de 1 jogando "Confessar"tambm maior do que jogando"No Confessar", 4 > 1. Logo dizemos que para o jogador 1 a estratgia "Confessar"uma estratgia estritamente dominante: independente das escolhas alheias (do jogador2, no caso), o ganho de 1jogando "Confessar" estritamente maior do que jogando "NoConfessar". Dito ainda de outra maneira, a estratgia "Confessar" uma estratgiaestritamente dominante para o jogador 1 porque ela gera o maior payo para este jo-gador toda vez que ele a jogar, independente das estratgias dos outros jogadores. Faaraciocnio anlogo para o jogador 2 e verique que tambm para este jogador a estrat-gia "Confessar" uma estratgia estritamente dominante. Dizemos ento que no Dilema

18

dos Prisioneiros o perl de estratgias ("Confessar", "Confessar") um equilbrio comestratgias estritamente dominantes.

Ou seja, em um jogo esttico de informao completa J com n jogadores, considereo espao de estratgias de um jogador i qualquer, dado por Si. E suponha que aestratgia que esse jogador jogou tenha sido si 2 Si. Ns dizemos que si 2 Si umaestratgia estritamente dominante para o jogador i quando, independente dasescolhas alheias, o ganho que o jogador i tem jogando si 2 Si estritamente maior doque o ganho que ele teria jogando qualquer outra estratgia disponvel no seu espao deestratgias, s0i 2 Si. Se para cada jogador i = 1; 2; :::; n h uma estratgia estritamentedominante s1 2 S1; s2 2 S2; :::; sn 2 Sn, ento (s1; s2; :::; sn) dito um equilbrio comestratgias estritamente dominantes. Formalmente,

Denio: No jogo J = fSi; ui (si; si)gni=i a estratgia si 2 Si uma estratgiaestritamente dominante para o jogador i se ui (si; si) > ui (s0i; si), 8s0i 2 Si,s0i 6= si e 8si 2 Si.

Dito ainda de outra maneira, a estratgia si uma estratgia estritamente domi-nante o jogador i se ela gera o maior payo para ele toda vez que ele a jogar, indepen-dente das estratgias dos outros jogadores.

Denio: Primeiro princpio da racionalidade: considere um jogador i qual-quer. Se existe si 2 Si tal que si uma estratgia estriamente dominante, entoi a jogar.

Observao: (si; si) um equilbrio com estratgia estritamente domi-nante no jogo J se si uma estratgia estritamente dominante para todojogador i = 1; 2; :::; n. Na verdade, como veremos abaixo, (si; si) ser umequilbrio com estratgia estritamente dominante no jogo J se si for umaestratgia estritamente dominante para pelo menos (n 1) jogadores.

Logo, se um jogador tem uma estratgia que estritamente dominante, ele, sendoracional, deve sempre jog-la, pois, por denio, no haver nada melhor a se fazer. Setodos os envolvidos em um determinado jogo possuem estratgias estritamente dom-inantes, seu resultado torna-se portanto facilmente conhecido, dada a racionalidadedos jogadores. O grau de acuidade dessa previso , de fato, extremamente potente.Anal, pouco provvel que algum no escolha fazer algo que seja reconhecidamenteprefervel a ele(a) sempre.

Observe tambm a curiosidade da seguinte nuance no Dilema dos Prisioneiros. Con-sidere que a polcia permita que os prisioneiros possam se comunicar entre si e, eventual-mente, estabelecer algum acordo no sentido de nenhum deles confessar, para caremdetidos por menos tempo. Nesse caso, qualquer acordo que emergisse do contato entre

19

eles no teria credibilidade no sentido de que ambos os jogadores teriam incentivos ano cumprir o acordo, independentemente do fato de um jogador acreditar ou no queo outro ir cumpr-lo ou no. Como resultado, ambos acabam obtendo um resultadoque pior para todos, cando ambos com um payo de 4. curioso perceber tam-bm que esse o resultado que dever prevalecer mesmo que ambos fossem inocentes,como seriam no exemplo dado o Maestro e o que teve a m sorte de possuir pais queapreciassem o nome Tchaikvski.

Caso tenhamos uma situao onde todos os jogadores, menos um, tenham estrat-gias estritamente dominantes, o resultado da interao tambm pode ser facilmenteprevisto. O que ocorrer que o jogador que no possui uma estratgia que seja estri-tamente dominante escolher a alternativa que lhe dar maior utilidade, tomando comodado11 que os outros jogadores iro jogar aquelas estratgias que forem dominantes paraeles.

jogador 2E C D

A 0; 1 4; 0 5; 3jogador 1 M 4; 0 2; 0 5; 3

B 3; 2 3; 5 6; 6

No jogo acima na forma normal (ou estratgica) temos

1. os jogadores: 1 e 2

2. os espaos de estratgias, S1 = fA;M;Bg e S2 = fE;C;Dg3. os payos, dados na matriz acima.

Nesse jogo, observe que a estratgia D estritamente dominante para o jogador.2:para qualquer escolha que o jogador.1 faa, a sua melhor resposta jogar D (pois 3 maior do que 1 e 0,.3 maior do que 0 e 0 e 6 maior do que 5 e 2). Sabendo disso(pois 1 sabe que 2 racional), o jogador.1 escolher a alternativa que mais lhe convm,dado que o jogador.2 sempre escolher D. O melhor para ele portanto jogar B (pois6 maior do que 3), o que leva ao resultado (B;D) do jogo como um equilbrio comestratgias estritamente dominantes. Desta anlise, conclumos que quando todos (oupelo menos todos menos um) jogadores possuem estratgias estritamente dominantes,a previso , como referido, extremamente acurada.

O problema que na grande maioria dos jogos no existe essa facilidade analtica,e ento outras formas de se prever os resultados tm de ser utilizadas. H um outroconceito, parecido com o oposto do visto acima, que, embora no dena o que deverocorrer, determina com muita segurana o que no dever acontecer.11Lembre-se que assumimos que a racionalidade dos jogadores de conhecimento comum.

20

2.2.2 Estratgias Estritamente Dominadas

Considere novamente o Dilema dos Prisioneiros,

Jogador 2NC C

Jogador 1 NC 5; 5 1; 7C 7; 1 4; 4

Em um jogo como este (e em todo jogo esttico de informao completa), dizemos queuma estratgia de um jogador qualquer (do jogador 1, por exemplo) uma estratgiaestritamente dominada por alguma outra estratgia desse jogador se, independenteda escolha do outro jogador, o ganho que ele tem jogando esta estratgia estrita-mente menor do que o ganho que ele teria jogando a outra estratgia. Novamente,como h duas estratgias, "No Confessar"e "Confessar", devemos analisar as duaspossibilidades. Para vericar se h a existncia de estratgias estritamente dominadas,olhamos, para cada jogador, os payos associados s estratgias comparadas duas aduas. Em um jogo representado na forma normal, na forma de matriz, deve-se entosupor que o outro jogador escolha cada uma das suas estratgias possveis. Compara-mos ento as duas estratgias (se houvessem mais as compararamos tambm), e se oganho for sempre estritamente menor, ento essa se constitui em uma estratgia estri-tamente dominada pela outra. Considere as estratgias do jogador 1, "No Confessar"e"Confessar". Se o outro jogador, 2, joga "No Confessar", o ganho de 1 jogando "NoConfessar" menor do que jogando "Confessar", 5 < 7. E se 2 joga "Confessar", oganho de 1 jogando "No Confessar"tambm menor do que jogando "Confessar",1 < 4. Logo dizemos que para o jogador 1 a estratgia "No Confessar" uma estrat-gia estritamente dominada: independente das escolhas alheias, o ganho de 1jogando"No Confessar" estritamente menor do que jogando "Confessar". Dito ainda de outramaneira, a estratgia "No Confessar" uma estratgia estritamente dominada para ojogador 1 porque ela gera um payo menor para este jogador relativamente outra al-ternativa, "Confessar", toda vez que ele a jogar, independente das estratgias do outrojogador. Faa raciocnio anlogo para o jogador 2 e verique que tambm para estejogador a estratgia "No Confessar" uma estratgia estritamente dominada. Dizemosento que no Dilema dos Prisioneiros o perl de estratgias ("No Confessar", "NoConfessar") um equilbrio com estratgias estritamente dominadas: "No con fes-sar" uma estratgia estritamente dominada por "Confessar"se ela conferir ao jogador2 um payo sempre inferior ao propiciado pela segunda, independente do que o outrojogadore possa fazer.

Ou seja, em um jogo esttico de informao completa J com n jogadores, considereo espao de estratgias de um jogador i qualquer, dado por Si. E suponha que aestratgia que esse jogador jogou tenha sido si 2 Si. Ns dizemos que si 2 Si uma

21

estratgia estritamente dominada por outra estratgia s0i 2 Si qualquer no seuespao de estratgias para o jogador i quando, independente das escolhas alheias,o ganho que o jogador i tem jogado si 2 Si estritamente menor do que o ganho queele teria jogando s0i 2 Si. Formalmente,

Denio: No jogo J = fSi; ui (si; si)gni=i a estratgia si 2 Si uma estratgiaestritamente dominada pela estratgia s0i 2 Si, s0i 6= si, para o jogador i, seui (si; si) < ui (s0i; si), 8si 2 Si.

Ou seja, si estratgia estritamente dominada s0i se ela conferir ao seu jogadorum payo sempre inferior ao propiciado pela segunda, independente do que os outrosjogadores possam fazer.

Denio - Segundo princpio da racionalidade: considere um jogador i qual-quer. Se existe si; s0i 2 Si tal que si uma estratgia estriamente dominada pors0i, ento i nunca jogar si.

Uma regra bsica de teoria dos jogos que indivduos racionais no jogam estrat-gias estritamente dominadas, pois fazendo isso eles no esto agindo da melhor formapossvel para eles mesmos. Vejamos agora as implicaes deste princpio, em particularcar claro aqui a relevncia da noo de conhecimento comum, tanto dos payos dosjogadores envolvidos como tambm da racionalidade destes12. Para isso, considere ojogo abaixo:

jogador 2C D E

jogador 1 A 2; 2 1; 5 1; 3B 1; 3 0; 1 1;2

tal que na forma normal ou estratgica temos

1. os jogadores: 1 e 2

2. os espaos de estratgias, S1 = fA;Bg e S2 = fC;D;Eg3. os payos, dados na matriz acima.

Verique inicialmente que nesse jogo no h estratgia estritamente dominante paranenhum jogador, de forma que se buscssemos fazer uma previso do resultado dojogo tendo em mente essa noo, nada poderamos dizer. Note tambm que no jogoacima, para o jogador 2, a estratgia E estritamente dominada pela estratgia D:

12Obviamente, aqui, um jogador racional se ele no joga estratgias estritamente dominadas poralguma outra.

22

comparando-se as duas temos que se o jogador.1 escolhe A, o jogador 2 estar piorjogando E do que jogando D, pois 3 < 5. Se, por outro lado, o jogador.1 escolhe aalternativa B, para o jogador.2 a estratgia E continua sendo uma estratgia pior doque D, na medida em que 2 < 1. Consequentemente, sendo o jogador 2 racional, elenunca ter incentivos a jogar E, pois ela sempre gerar payos inferiores D. Percebatambm que, apesar da dominncia de D sobre E, D no uma estratgia estritamentedominante, pois para 2 a estratgia C no estritamente dominada nem por D nempor E.

Como assumimos, 2 racional, de modo que no devemos esperar que ele nuncaescolha E Mas mais ainda, essa racionalidade de conhecimento comum, assim comoa racionalidade de 1. E como se trata de um jogo de informao completa, no apenas2 no joga E como tambm 1 tambm sabe. E 2 sabe que 1 sabe que ele nunca a jogare 1 sabe que 2 sabe... e assim sucessivamente. Isso implica que podemos eliminar osresultados do jogo que consideram essa estratgia. Procedendo assim e eliminando acoluna E do jogo, o jogo assume a seguinte forma reduzida,

jogador 2C D

jogador 1 A 2; 2 1; 5B 1; 3 0; 1

Note atentamente: repetindo o raciocnio acima, ns podemos proceder dessa formaporque no apenas trata-se de um jogo esttico de informao completa mas tambm aracionalidade dos jogadores tambm de conhecimento comum. Nesse sentido, sendo 2racional (de acordo com o segundo princpio de racionalidade), ele no jogar E. Mas(muito!!!) mais do que isso: como 1 sabe que 2 racional (de acordo com o mesmoprincpio), ele conjectura que 2 nunca a jogar. E como 2 sabe que 1 sabe que ele, 2, racional, ento 2 sabe que 1 sabe que ele nunca jogar E e assim indenidamente, demodo que a estratgia E torna-se irrelevante para o jogo, pois nenhum jogador levarem considerao a possibilidade de 2 jog-la.

Por outro lado, tendo em mente o jogo reduzido apresentado acima, observe quepara o jogador 1 a estratgia B torna-se estritamente dominada13 pela estratgia A,uma vez essa gera payo de uma unidade a mais para o jogador 1, comparando-se como que a B proveria, independente do que o jogador 2 zer. O jogador 1, portanto, nodever jogar B (e 2 sabe disso, e 1 sabe que 2 sabe e...) e podemos da mesma forma

13Aqui temos um resultado bsico interessante que o aluno um pouco mais atento j deve ter perce-bido: em um jogo 22 (dois jogadores, cada uma com duas estratgias em seus espaos de estratgias),o fato de um jogador qualquer ter uma estratgia estritamente dominada implica que a outra estratgia estritamente dominante. No jogo em questo, nesse segundo estgio, A torna-se dominante. Masapenas no jogo reduzido!

23

eliminar essa linha, reduzindo ainda mais o jogo,

jogador 2C D

jogador 1 A 2; 2 1; 5

Com o jogo dessa forma, sabemos que o jogador 1 jogar A. Consciente de tal fato, ojogador 2 far o que mais lhe dar utilidade: jogar D (pois 5 > 2). O resultado previstopara o jogo , portanto, (A;D).

O processo mostrado no exemplo acima denominado eliminao iterada deestratgias estritamente dominadas (EIEED) e o conjunto de estratgias (A;D) dito ser um equilbrio por EIEED. Esse processo de eliminao, como vimos,depende que os agentes sejam racionais, mas tambm que cada um deles saiba que osoutros tambm so racionais, e que saibam que todos sabem que todos eles so racionaisetc. Assumir tais hipteses o mesmo que assumir que existe common knowledge(conhecimento comum) de que os jogadores so racionais. No caso acima, dado quetrata-se de um jogo de informao completa, foi necessrio que:

o jogador.2 fosse racional e, assim, no jogasse E;

o jogador 1 fosse racional e soubesse que o jogador 2 tambm era racional, nojogando, por isso, B;

o jogador 2 soubesse que o jogador 1 era racional e tambm que o jogador.1soubesse que ele era racional, e ento escolhesse D.

Isto posto, verique que no Dilema dos Prisioneiros o perl de estratgias ("NoConfessar", "No Confessar") um equilbrio por EIEED.

Observe agora a relao entre estratgias estritamente dominantes e estratgiasestritamente dominadas. Se uma estratgia uma estratgia estritamente dominantepara um jogador qualquer, ento ela sobrevive ao processo de EIEED. Por outralado, se uma estratgia sobrevive ao processo de EIEED, no necessariamente seruma estratgia estritamente dominate para aquele jogador. Isso ser verdade em jogos2 x 2, onde cada jogador tem apenas duas possibilidades de escolha (como, por exemplo,o Dilema dos Prisioneiros), mas saindo dessa classe restrita de jogos, nada nos garanteque tal relao se preserva. Podemos ento generalizar e propor a seguinte relao entreas duas maneiras vistas at aqui de solucionar jogos estticos de informao completa:

Proposio 9 Se uma estratgia de um jogador qualquer uma estratgia estritamentedominante, ento ele sobrevive (no eliminada) ao processo de EIEED. Mas se umaestratgia de um jogador qualquer sobrevive ao processo de EIEED, no necessariamenteela uma estratgia estritamente dominante.

24

Observao 10 Dito de outra maneira, dizemos aqui que o primeiro princpio deracionalidade implica no segundo mas o segundo princpio no necessariamente implicano primeiro.

Uma observao importante aqui que a maior parte dos jogos no so resolvidosvia EIEED. Eventualmente isso ocorre, mas em geral apenas reduz as possibilidadesdo jogo. Considere o exemplo abaixo.

Exemplo 11jogador 2

D E FA 2; 3 3; 1 3; 2

jogador1 B 4; 1 5; 4 0; 3C 1; 1 3; 5 6; 3

Depois de descrever as informaes desse jogo na forma estratgica, observe quenesse exemplo no h nenhuma estratgia estritamente dominante e nem estratgiaestritamente dominada para ambos os jogadores. Segue o processo de EIEED nemmesmo reduz a complexidade do jogo: o equilbrio do jogo por EIEED o prprio jogo,uma informao que no nos ajuda em nada na previso do resultado do jogo.

Veja tambm o jogo de Par ou mpar. Neste jogo, o jogador chamado Par oque pediu par (P), enquanto o de nome mpar , analogamente, o que ganha se oresultado for mpar (I). Apenas para simplicar, suponha que o vencedor tem payode 1, enquanto o perdedor obtm -1.

mparP I

Par P 1;1 1; 1I 1; 1 1;1

Nota-se que, tambm no Par ou mpar, EIEED no colabora em nada com a resoluodo jogo.

Podemos relaxar um pouco a noo de estratgia estritamente dominada e tro-car a desigualdade estrita dessa denio por uma relao apenas desiguladade (noestrita). Emerge portanto a idia de estratgia fracamente dominada. Generica-mente, em um jogo esttico de informao completa qualquer, dizemos que (para umjogador qualquer) uma determinada estratgia uma estratgia fracamente dominadapor outra estratgia qualquer no seu espao de estratgias para este jogador quando,independente das escolhas alheias, o ganho que o jogador tem jogado tal estratgia menor (mas no necessariamente estritamente menor) do que o ganho que ele teriajogando a outra estratgia.

25

Considere ento um jogo esttico de informao completa J com n jogadores etome o espao de estratgias de um jogador i qualquer, dado por Si. E suponha quea estratgia que esse jogador jogou tenha sido si 2 Si. Ns dizemos que si 2 Si uma estratgia fracamente dominada por outra estratgia s0i 2 Si qualquer no seuespao de estratgias para o jogador i quando, independente das escolhas alheias,o ganho que o jogador i tem jogado si 2 Si menor (no necessariamente estritamentemenor) do que o ganho que ele teria jogando s0i 2 Si:Formalmente,

Denio: No jogo J = fSi; ui (si; si)gIi=i a estratgia si 2 Si uma estratgiafracamente dominada pela estratgia s0i 2 Si para o jogador i se ui (si; si) ui (s

0i; si), 8si 2 Si.

Uma estratgia fracamente dominada por outra portanto um conceito prximo,mas distinto, do conceito de estratgias estritamente dominadas. A diferena que oprimeiro requer que a estratgia dominada nunca seja melhor que a estratgia que adomina, enquanto o ltimo exige que a dominada seja, sempre, estritamente pior quea que a domina.

Esse conceito de estratgias fracamente dominadas possibilitaria, em princpio, queconseguissmos que se reduzisse mais (ou pelo menos da mesma forma) a complexidadedos jogos. Entretanto, a eliminao iterada deve ser feita apenas com estratgias es-tritamente dominadas: eliminar iteradamente estratgias que sejam apenas fracamentedominadas pode levar a resultados distintos do jogo. No , portanto, consequncia daracionalidade dos jogadores. Na eliminao iterada de estratgias estritamente dom-inadas, a ordem de eliminao no afeta o resultado nal, o que pode no ocorrerquando utiliza-se esse processo para estratgias fracamente dominadas. O exemploabaixo demonstra essa possibilidade.

Exemplo 12jogador 2a b

A 3; 4 4; 3jogador 1 B 5; 3 3; 5

C 5; 3 4; 3

Pode-se perceber no jogo acima que algumas estratgias podem eliminadas ao seconsiderar o conceito de dominncia fraca:

1. B fracamente dominada por C (pois nunca gera payos superiores a C): elimina-se B;

2. no jogo reduzido, b fracamente dominada por a (pelo mesmo racioccio): elimina-se b;

26

3. no jogo ainda mais reduzido, o jogador 1 escolhe C e o resultado do jogo (C; a).

Podemos, todavia, comear de outra forma:

1. A fracamente dominada por C: elimina-se A;

2. no jogo reduzido, a fracamente dominada por b: elimina-se a;

3. no jogo ainda mais reduzido, jogador 1 escolhe C e o resultado do jogo (C; b).

Conclui-se assim o enunciado acima: eliminao iterada de estratgias fracamentedominadas pode levar a resultados distintos dependendo de onde se comea o processo, eportanto no consequncia da racionalidade dos jogadores. Deve estar claro portantoa fraqueza do mtodo, na medida em que ainda que em algumas situaes a eliminaode estratgias fracamente dominadas possa nos ajudar a solucionar ou mesmo reduzir acomplexidade de um jogo qualquer, o fato do processo de interao no ser determinadopela racionalidade dos jogadores pode implicar em previses sobre o resultado do jogoque no sejam boas o sucente, que no sejam as melhores que o analista possa vir afazer.

2.2.3 Estratgias racionalizveis (anlise de "melhores respostas")

Um outro mtodo que pode ser utilizado para se prever resultados de jogos si-multneos o de eliminao de estratgias no racionalizveis. Em geral, o commonknowledgeda racionalidade dos jogadores permite eliminar outras estratgias que noaquelas eliminadas via EIEED (ou pelo menos essas). Para denir melhor tal possibil-idade, necessrio termos em mente alguns outros conceitos, abaixo apresentados.

Em um jogo esttico de informao completa, considere o espao de estratgiasde um jogador qualquer. Uma estratgia especca nesse conjunto dita a melhorresposta que ele pode dar s escolha alheias se, dadas as escolhas alheias, o ganhoque ele tem jogando tal estratgia maior (no necessariamente estritamente maior) doque jogando alguma outra estratgia qualquer. Nesse caso dizemos que esta estratgia uma estratgia racionalizvel. Mas se no existe uma combinao de escolhas dosdemais jogadores tal que o ganho desse jogador em escolher tal estratgia seja maior doque as demais estratgias, dizemos que ela no-racionalizvel. Dizemos portantoque tal estratgia no nunca a melhor resposta que este jogador pode dar sescolhas alheias. Seguem abaixo as denies de uma forma mais rigorosa.

Como foi dito, um outro mtodo que pode ser utilizado para se prever resultadosde jogos simultneos o de eliminao de estratgias no racionalizveis. Em geral, ocommon knowledgeda racionalidade dos jogadores permite eliminar outras estrat-gias que no aquelas eliminadas via EIEED (ou pelo menos essas). Para denir melhortal possibilidade, necessrio termos em mente alguns outros conceitos.

27

Denio: Em J = (Si; ui (si; si)) um jogo esttico de informao completa.Uma estratgia si 2 Si, i 2 n, a melhor resposta que i pode dar s escolhasdos demais jogadores se existe si 2 Si tal que

ui (si; si) uis0i; si

8s0i 2 SiNesse caso dizemos que si uma estratgia racionalizvel. Se no existe si 2Si tal que ui (si; si) ui (s0i; si) 8s0i 2 Si, dizemos que si uma estratgiano-racionalizvel, o que signica que si no nunca a melhor resposta quei pode dar s escolhas alheias.

Note que, em geral, existem vrias melhores respostas para cada jogador envolvido,dependendo do que os outros possam fazer (no caso especco onde existe apenas umamelhor resposta para um determinado jogador, essa seria ento uma estratgia estrita-mente dominante).

Se uma determinada estratgia no for nunca a melhor resposta para um jogador,em que circunstncias dever ele jog-la? Sendo racional, isso nunca dever acontecer,uma vez que, sempre que ele imaginar a possibilidade de escolhe-la, haver uma alter-nativa que gera um payo superior, por denio. Segue desse raciocnio que estratgiaracionalizveis so estratgias que sobrevivem eliminao iterada de estratgias quenunca so a melhor resposta que um jogador pode dar s escolhas alheias.

Como no caso de estratgias estritamente dominadas, tambm pode-se fazer elim-inao iterada de estratgias no racionalizveis (EIENR)14. Novamente, a ordem deeliminao no afeta o resultado nal. As estratgias que sobrevivem EIENR soaquelas que um jogador racional pode justicar, ou racionalizar, dada alguma conjec-tura razovel a respeito da escolha dos outros jogadores, onde razovel signica umaescolha que no contenha estratgias no racionalizveis.

Comparando com estratgias estritamente dominadas, observamos que uma estrat-gia que estritamente dominada nunca melhor resposta, mas o inverso nem sempre correto. Portanto, eliminar iteradamente estratgias que nunca so a melhor respostaelimina pelo menos tantas estratgias quanto se retiraria ao fazer EIEED, e em geralelimina-se mais. Em suma, tem-se que

(Conjunto de estratgias estratgias que sobrevivem EIEED estratgias que sobrevivem EIENR

14 Isso verdade enquanto no tratamos ainda de estratgias mistas, o que veremos logo a seguir.Quando isso ocorrer, esse resultado se altera radicalmente. A inteno aqui to somente inserir anoo de estratgias (no) racionalizveis e "preparar terreno"para inserirmos a noo de equilbrio deNash.

28

Exemplo 13 Considere o jogo abaixo, um jogo esttico de informao completa. Naforma normal (ou estratgica)

1. os jogadores: 1 e 2

2. os espaos de estratgias: S1 = fa; b; c; dg e S2 = fe; f; g; hg

3. os payos, que so os ganhos expostos na bimatriz abaixo.

jogador 2e f g h

a 2; 6 3; 3 5; 1 0; 0jogador 1 b 3; 1 6; 4 0; 2 0; 1

c 8; 1 2; 2 0; 5 0; 4d 4; 1 1; 0 0; 1 5;1

Nesse jogo, qual o conjunto de estratgias racionalizveis?Uma forma que facilita sensivelmente a visualizao das estratgias racionalizveis

(ou no) marcar as melhores respostas para cada jogador em todas as circunstnciaspossveis, sendo essas dadas pelas alternativas que o outro jogador possui. Por exemplo,quando o jogador 1 escolhe a, o melhor para o jogador 2 ser escolher e, pois lhe darum payo de 6, e no 3, 1 ou 0, que obteria se zesse outras escolhas. O mesmo deveser feito supondo escolhas de b; c e d pelo jogador 1. Por sua vez, se o jogador 2 utilizara estratgia e, o melhor para o jogador 1 ser lanar mo da estratgia c (payo de 8contra outros de 2, 3 e 4). O mesmo tambm deve ser feito supondo as escolhas de f; ge h pelo jogador 2. Se uma determinada estratgia no corresponder a uma melhorresposta em nenhuma circunstncia, ento ela no ser racionalizvel, pois signicarque, independente do que o outro jogador zer, ela nunca gerar o maior payo eportanto no corresponder ao melhor a se fazer. Uma vez que alguma estratgia foreliminada por esse critrio, pode-se novamente analisar se, no jogo reduzido, h algumaoutra que nunca ser jogada, e assim sucessivamente, at reduzir-se o jogo ao mximo.No caso acima, temos que:

h pode ser eliminado, pois nunca melhor resposta para jogador 2;

eliminado h, d tambm pode ser eliminado, pois no ser mais melhor respostapara o jogador 1 em nenhuma possibilidade do jogo reduzido.

A partir desse ponto, nenhuma outra eliminao poder ser feita, sendo que todasas estratgias sobreviventes so racionalizveis: podem ser justicadas por algumahiptese a respeito do que o outro jogador poder fazer. Portanto, nesse jogo no

29

possvel prever um resultado nal pelo mtodo de EIENR, obtendo apenas a reduoda sua complexidade:

jogador 2e f g

a 3; 1 6; 4 0; 2jogador 1 b 8; 1 2; 2 0; 5

c 4; 1 1; 0 0; 1

Em geral, portanto, EIENR (assim como, e ainda mais, EIEED) no gera previsesbem denidas para grande parte dos jogos. O mais comum que apenas dena algunsresultados que no sero jogados, caso de fato exista pleno conhecimento de racionali-dade dos jogadores por todos eles. Contudo, isso no signica que seja sempre assim.Vejamos o exemplo 8 dado na seo anterior, onde, via EIEED nada podia ser feito.

jogador 2D E F

A 2; 3 3; 1 3; 2jogador 1 B 4; 1 5; 4 0; 3

C 1; 1 3; 5 6; 3

Percebe-se que, mesmo sem possuir estratgias estitamente dominadas, no jogo acimaexistem algumas estratgias que nunca so melhores respostas, e portanto no soracionalizveis. Esse o caso da estratgia F para o jogador 2 e da A para o jogador1. Eliminando-as, o jogo se reduz a

jogador 2D E

jogador 1 B 4; 1 5; 4C 1; 1 3; 5

Nesse jogo reduzido, porm, outras estratgias passam a no constituirem-se de mel-hores respostas: a estratgia D, para o jogador.2, e a estratgia C, para o jogador1. Eliminando-as, temos ento (B;E) como resultado previsto para o jogo, que serjogado caso exista conhecimento comum de racionalidade entre os jogadores.

Por m, uma palavra de precauo necessria aqui. Ainda que tenhamos propostoe feito nesses exemplos um processo de eliminao de estratgias segundo a noo deracionalidade de jogadores associada estratgias racionalizveis, no verdade queesse processo sempre vlido quando permitimos que os jogadores aleatorizem suasescolhas. Nesse caso podemos ter estratgias no racionalizveis que sero jogadas comprobabilidades positivas, possibilidade que decorre em funo da presena do elementode interao estratgica. Por exemplo, no caso acima, pode ser que os jogadores 1 e 2

30

joguem A e F com probabilidade no nula, respectivamente. Ns veremos essa situaoabaixo, quando estudarmos estratgias mistas. Segue portanto que a anlise acima temperda signicativa de generalidade quando incorporamos estratgias mistas na anlise.

2.3 Equilbrio de Nash

Como visto acima, mesmo EIENR no em geral capaz de nos dar o resultado demuitos jogos, embora costume simplic-los. Um mtodo de soluo mais abrangenteque EIEED e EIENR o de equilbrio de Nash: se um conjunto de estratgias umequilbrio de Nash, ele sobrevive s eliminaes ..., embora o contrrio no seja,em geral, verdade. Nesse contexto um equilbrio de Nash ser determinado por umainterseo de melhores respostas, uma intersero de estratgias racionalizveis. Issosignica que um perl de estratgias (associando uma estratgia para cada jogador) serum equilbrio de Nash se, para cada jogador, a estratgia que ele adotou for a melhorresposta que ele pode dar s escolhas alheias. Podemos ainda dizer que em um jogoesttico de informao completa, um conjunto de estratgias (uma para cada jogador)constitui um equilbrio de Nash se, caso os todos os jogadores, menos um, joguem asestratgias denidas para eles no equilbrio de Nash, para aquele outro no exista nadamelhor a se fazer a no ser tambm escolher a estratgia para ele denida no equilbriode Nash. E isso deve valer para todos os jogadores tomados individualmente.

Denio: No jogo J = fSi; ui (si; si)gni=i o perl de estratgiassi ; s

icon-

stitui um equilbrio de Nash se para todo jogador i = 1; 2; :::; n a estratgiasi 2 Si for a melhor resposta que i pode dar s escolhas alheias. Isto , dadosi 2 Si, ui

si ; s

i ui s0i; si 8s0i 2 Si, s0i 6= si .

De outra forma, podemos denir as estratgias (s1; :::; sn) como um equilbrio deNash caso, para todo jogador i, a estratgia si resolva o problema de

maxsi2Si

uisi; s

i

Como usual, tome como exemplo o Dilema dos Prisioneiros,

Jogador 2NC C

Jogador 1 NC 5; 5 1; 7C 7; 1 4; 4

e analisemos inicialmente o caso do jogador 1. Se o jogador 2 jogou NC, a melhorresposta que 1 pode dar jogar C, pois 7 > 5. E se 2 jogar C, a melhor resposta queo jogador 1 pode dar jogar a estratgia C, pois 4 > 1. Analogamente para o jogador2: se 1 joga NC, a melhor resposta que ele pode dar jogar C (7 > 5) e se 1 joga

31

C a melhor resposta tambm jogar C. Logo (C;C) uma interseo de melhoresrespostas e como tal caracteriza o equilbrio de Nash no Dilema dos Prisioneiros.

Identicado o equilbrio de Nash, veja que nenhum dos jogadores tem qualquerincentivo a se desviar. Se algum dos jogadores prope ao outro que ambos joguem"No Confessar", de forma que cada um ganhe 5 (e portanto ambos estejam melhor doque no equilbrio de Nash), o melhor que cada um pode fazer no cumprir o acordo,pois na conjectura de o oponente cumpr-lo, a melhor resposta sempre no cumprir ejogar "Confessar", pois 7 > 5.

Portanto, para encontrar um equilbrio de Nash, basta ver a(s) melhor(es) re-sposta(s) de um jogador para cada estratgia do(s) outro(s) jogador(es), procedendoassim para todos eles. Quando houver coincidncia entre as melhores respostas paratodos os envolvidos, esse conjunto de estratgias ser um equilbrio de Nash.

Exemplo 14jogador 2

D E FA 2; 3 5; 1 3; 2

jogador 1 B 4; 2 1; 4 0; 3C 1; 1 0; 5 6; 8

No caso acima, no h estratgia dominante para nenhum dos jogadores nem nen-huma estratgia pode ser eliminada via EIEED ou EIENR. Mas o conceito de equilbriode Nash nos diz que o resultado do jogo ser (C;F ), o nico onde h coincidncia demelhores respostas: se o jogador 2 joga F , o melhor para o jogador 1 escolher C, evice-versa. Consequentemente, nenhum dos dois ter incentivos a desviar desse resul-tado, caso acreditem que ele deva se vericar.

2.3.1 Estabilidade, existncia e unicidade do equilbrio de Nash

Estabilidade Caso se tenha um determinado conjunto de estratgias, conhecido portodos e previsto como a soluo de um jogo esttico, ele dever constituir-se em umequilbrio de Nash. Se isso no ocorrer, ento, por denio, existir algum jogadorque poder obter um payo maior jogando outra estratgia: ele no teria, portanto,incentivos em jogar a estratgia proposta inicialmente, sendo racional. Assim, se umdeterminado conjunto de estratgias previsto como a soluo de um jogo esttico deinformao completa, ele dever ser um equilbrio de Nash. Nesse sentido dizemos queo equilbrio de Nash um resultado estrategicamente estvel (ou "self-enforcing").

Formalmente, suponha que um conjunto de estratgias (s01; :::; s0n) seja a soluoproposta para um determinado jogo esttico de informao completa com n jogadores,mas no seja um equilbrio de Nash. Ento, para ao menos um jogador i, ter-se-ia uma

32

estratgia alternativa (s00i 6= s0i) tal que o ganho desse jogador seria maior jogando-a,

uis0i; s

0i< ui

s00i ; s

0i

e o jogador i preferir jogar s00i , de onde temos que (s01; :::; s

0n) no pode ser uma soluo,

ao menos um jogador se desviaria.

Existncia Com relao existncia do equilbrio de Nash, sabemos atravs de umteorema provado pelo prprio Nash, em 1951, que sempre existir pelo menos um, desdeque o jogo em anlise seja nito15.

Teorema 15 Nash (1951). Em todo jogo nito (com o nmero de jogadores n, nitoe espao de estratgias Si, para todo i, tambm nito) existe pelo menos um equilbriode Nash (ainda que envolva apenas estratgias mistas, conceito a ser visto frente).

Exemplo 16 Par ou mpar.

jogador 2P I

jogador 1 P 1;1 1; 1I 1; 1 1;1

O jogo par ou mpar um jogo nito, uma vez que h apenas dois jogadores comduas estratgias para cada um deles. Pelo Teorema enunciado acima, ele deveria possuiralgum equilbrio de Nash, o que no se percebe na matriz acima. Obviamente noestamos mostrando uma contradio ao Teorema de Nash nem sugerindo que o Parou mpar no tenha soluo terica. Entretanto, ali est sendo mostrado apenas aspossveis estratgias puras. O par ou mpar, de fato, possui um equilbrio de Nash(anal, no consta que o Teorema tenha sido provado de maneira errada), mas emestratgias mistas, onde cada jogador joga 50% das vezes par e 50% mpar. Esseprocesso ser explicado mais adiante.

Exemplo 17 Comsidere um jogo que tenha a seguinte regra: h dois (ou mesmo umnmero maior qualquer) jogadores que tm de escrever simultaneamente em um pedaode papel um nmero qualquer. Aps terem escrito, ambos revelam seus nmeros. Oque tiver escrito o maior nmero recebe R$100, enquanto o(s) outro(s) no ganha(m)nada. Sendo igual, tambm no ganham nada. Qual o equilbrio de Nash?

Pensando um pouco, voc notar que no existe nenhum equilbrio de Nash nessejogo. Para concluir isso, veja que o perdedor sempre poder melhorar sua situao,

15Para ns aqui nesse curso, um jogo dito nito se o nmero de jogadores for nito e se o espaode estratgias de cada jogador tambm for nito.

33

dizendo um nmero maior que o vencedor; sempre havendo perdedor (ou empate),sempre algum poder melhorar e, assim, nunca se alcanar um resultado que con-stitua um equilbrio de Nash. Esse jogo uma prova contrria ao teorema de Nash?Certamente no, pois o referido teorema foi provado e no h o que discut-lo. Aquesto que neste jogo no so satisfeitas todas as hipteses necessrias validadedo teorema, uma vez que ele no nito: note que o conjunto de estratgias possveisa cada jogador possui innitos elementos, e isso que possibilita a no existncia doequilbrio neste jogo.

Unicidade Com relao unicidade, nada nos garante em um jogo esttico de in-formao completa o equilbrio de Nash seja nico. Pode existir e bastante comumencontrar jogos com mais de um equilbrioa de Nash.

Exemplo 18 Guerra dos sexos.

MulherFutebol Teatro

Homem Futebol 2; 1 0; 0Teatro 0; 0 1; 2

No jogo acima, percebe-se a existncia de dois equilbrios de Nash: ambos iremao futebol e ambos irem ao teatro. O conceito de equilbrio de Nash, portanto, nodetermina nesse caso qual ser o resultado do jogo; apenas restringe as possibilidadeselimando algumas combinaes de estratgias.

Exemplo 19 Coordenao. Esse um jogo muito comum em que dois jogadores,1e 2, combinam um jantar de negcios mas deixam o local em aberto. Posteriormenteocorre um problema de comunicao e eles perdem contato. H duas possibilidades, elespodem ir a um restaurante caro e sosticado ou a um "p-sujo". Caso se encontrem- no importa em qual local - realizam um negcio e tm payo positivo. Caso no seencontrem, voltam ambos frustrados para casa e no se o negcio entre eles.

jogador 2Antiquarius O Canto

jogador 1 Antiquarius 1; 1 0; 0O Canto 0; 0 1; 1

Novamente temos dois equilbrios de Nash, e tambm no podemos determinar qualdeles ser jogado.

Nesses jogos, ainda que haja mais de um equilbrio de Nash, ns podemos de algumaforma reduzir as possibilidades dos resultados. Mas em alguns jogos essa reduo podeser irrelevante e frustante. Considere por exemplo o jogo entre dois jogadores, 1 e 2.

34

Ambos devem escrever em um pedao de papel um nmero inteiro entre 0 e 100. Sea soma de ambos os nmeros (a escolha do jogador 1 mais a escolha do jogador 2) formenor do que 100, cada um leva o nmero que escreveu no papel. Se a soma der maisde 100, cada um perde uma quantia, R$1,00 por exemplo. Inicialmente algum poderiadizer que nesse jogo h um nico equilbrio de Nash de jogo, cada um jogar 50. Noentanto esse apenas um dos equilbrios de Nash desse jogo, provavelmente decorrentede algum critrio subjetivo de justia na cabea do aluno. Mas no isso que buscamose sim caracterizar todos os equilbrios do jogo - e nesse jogo h 101 equilbrios de Nash.

s1 s2

0 100

1 99

2 98

::: :::

50 50

::: :::

99 1

100 0

Embora nos exemplos acima no tenhamos especicado, a princpio, como apontarum ou outro equilbrios de Nash como o mais provvel a ser jogado, em alguns casos,nesses jogos com mltiplos equilbrios de Nash, existem formas de identicar qual delesdever ser jogado (ao menos com uma certaprobabilidade).

2.3.2 Equilbrio de Nash e Eliminao de Estratgias

Para relacionarmos a noo de equilbrio de Nash com eliminao iterada de es-tratgias, vamos analisar duas proposies. Como de se esperar, dada a direo queestamos tomando, ainda que estejamos perdendo em potncia com relao capacidadepreditiva, lanar mo do conceito de equilbrio de Nash nos permite atingir um graude abrangncia signicativo que nos permitir ter alguma informao sobre a resoluode um determinado jogo de informao esttica em quase todas as situaes.

As relaes que estabeleceremos abaixo dizem respeito EIEED, mas poderia serabordada atravs de estratgias no-racionalizveis. Os enunciados e as provas dasproposies so os que se seguem.

Proposio: Se o conjunto de estratgias si ; si constitui um equilbrio deNash no jogo J = fSi; ui (si; si)gni=i na forma normal, ento

si ; s

isobrevive

ao processo de EIEED.

Prova: Por contradio, suponha que no. Isto , quesi ; s

iseja um

equilbrio de Nash de J mas foi eliminada no processo de EIEED em algum

35

estgio do procedimento. Segue que para ao menos um jogador i qualquer,dadas as escolhas si 2 Si dos demais jogadores, existiria uma estratgiasi 2 Si, si 6= si , tal que ui

si ; s

i< ui

s0i; s

i. Decorre que

si ; s

ino

seria um equilbrio de Nash em J , caracterizando a contradio.

Proposio: No jogo J = fSi; ui (si; si)gni=i na forma normal, nito, sejasi ; s

io nico perl de estratgias que sobrevive EIEED. Ento

si ; s

i

o nico equilbrio de Nash em J .

Prova: (i) Pelo teorema de Nash, em J existe ao menos um equilbriode Nash. (ii) Pela proposio anterior, se um perl de estratgias umequilbrio de Nash, ento sobrevive ao processo de EIEED.

Segue que sesi ; s

i um perl de estratgias que sobrevive EIEED, nico, em

J , entosi ; s

i um equilbrio de Nash em J .

Podemos informalmente descrever e provar as proposies acima:

Proposio: Em um jogo esttico de informao completa, nito, se um conjuntode estratgias constitui um equilbrio de Nash no jogo na forma normal, entoesse conjunto de estratgias sobrevive ao processo de EIEED.

Prova: Por contradio, suponha que no. Isto , que esse conjunto sejaum equilbrio de Nash do jogo mas foi eliminada no processo de EIEED emalgum estgio do procedimento. Segue que para ao menos um jogador qual-quer, dadas as escolhas dos demais jogadores (que esto jogando o equilbriode Nash), existiria uma outra estratgia tal que o seu ganho jogando o equi-lbrio de Nash seria menor do jogando esta estratgia alternativa. Decorreportanto que o conjunto inicial no seria um equilbrio de Nash nesse jogo,caracterizando a contradio.

Proposio: Em um jogo esttico de informao completa, nito, seja um perlde estratgias qualquer (uma estratgia para cada jogador) o nico perl quesobrevive EIEED. Ento esse perl de estratgias o nico equilbrio de Nashdo jogo.

Prova: (i) Pelo teorema de Nash, nesse jogo existe ao menos um equilbriode Nash. (ii) Pela proposio anterior, se um perl de estratgias umequilbrio de Nash, ento sobrevive ao processo de EIEED. Segue que se umconjunto de estratgias um perl que sobrevive EIEED, nico, no jogo,ento tal conjunto o (nico) equilbrio de Nash no jogo.

36

O que as proposies acima mostram que todo Nash sobrevive EIEED mas quenem toda estratgia que sobrevive EIEED constitui um Nash em um jogo nito naforma estratgica. Seguindo na direo que tomamos - e como j foi dito acima - issonos sugere que a noo de equilbrio de Nash mais tnue do que a idia de equilbriopor EIEED mas no entanto extremamente mais ampla.

Analisando com relao estratgias no-racionalizveis, note que isso ocorre porqueuma estratgia que est em algum equilbrio de Nash nunca ser uma estratgia noracionalizvel, pelo menos pelas estratgias desse equilbrio de Nash dos outros jo-gadores - pela prpria denio de equilbrio de Nash. Por outro lado, suponha umresultado (a; b) qualquer, sendo a uma estratgia racionalizvel do jogador.1 e b umaoutra, racionalizvel para o jogador 2. Nada garante que a justicativa para que ojogador 1 escolha a seja a possibilidade de ocorrncia de b, assim como tambm nadagarante que a justicativa para que o jogador 2 escolha b seja a possibilidade de ocor-rncia de a. Portanto, no necessariamente o resultado (a; b) constituir um equilbriode Nash.

Sendo assim, podemos dizer que toda estratgia que compe um equilbrio de Nash racionalizvel porque pode ser justicada pelas estratgias de equilbrio de Nash dosdemais jogadores, enquanto o inverso em geral no ser verdade. Por isso, tem-se quea capacidade de predio de um jogo muito superior quando se utiliza o conceito deequilbrio de Nash, comparando-se com EIEED e EIENR.

Em suma, pode-se dizer que:

(Conjunto de estratgias estratgias que sobrevivem EIEED

estratgias que sobrevivem EIENR estratgias que so equilbrio de NashEntretanto, o grau de preciso de uma previso utilizando apenas o conceito de equi-

lbrio de Nash no to apurado quanto o dos mtodos apresentados anteriormente,como ca claro no exemplo acima em que os jogadores devem escrever um nmerointeiro de 0 a 100 em um pedao de papel. No h nenhuma dvida da alta probabili-dade de que um jogador sempre escolha uma estratgia estritamente dominante, casoa tenha. No entanto, um estratgia que constitua um equilbrio de Nash ser jogadacom alta probabilidade apenas se cada jogador realmente acreditar que o(s) outro(s)tambm escolher(o) as estratgias denidas naquele equilbrio de Nash.

Exemplo 20 Considere o exemplo (16) acima aps a EIENR:

jogador 1e f g

a 2; 6 3; 3 5; 1jogador 1 b 3; 1 6; 4 0; 2

c 8; 1 2; 2 0; 5

37

O equilbrio de Nash no jogo acima (b; f), onde existe coincidncia de melhoresrespostas e portanto nenhum jogador tem incentivos a desviar.

Embora nas denies tenhamos sempre utilizado a hiptese de existncia de njogadores, at agora todos os exemplos dados contavam com apenas dois jogadoresenvolvidos. Isso foi feito por tambm dois motivos. O primeiro que, de fato, grandeparte das situaes reais de interdependncia ocorre realmente com apenas dois jo-gadores. O outro que a anlise de jogos com apenas dois envolvidos tecnicamentemuito mais simples, embora a lgica da anlise permanea exatamente a mesma. Bus-cando mostrar os passos para se encontrar equilbrios de Nash em jogos com mais dedois jogadores, apresentaremos abaixo um exemplo com trs deles.

2.3.3 Equilbrio de Nash com trs jogadores

A representao do jogo na forma normal, via matrizes de payos, no ser maisto simples como antes. Como seria extremamente complicado desenhar uma ma-triztridimensional, deve-se construir tantas matrizes (bidimensionais) quantas foremas estratgias do jogador 3 (por exemplo). No caso abaixo so trs: S3 = fnmeroI,nmeroII, nmeroIIIg. Por sua vez, so claros o conjunto de possibilidades dos out-ros jogadores: o jogador 1 escolhe entre alto e baixo enquanto o jogador 2 entreesquerda e direitaEm relao aos payos, os apresentaremos em cada clula naseguinte ordem: o mais esquerda refere-se ao do jogador 1, o central ao do jogador2, e o direita ao payo do jogador 3. Para encontrar-se as melhores respostas decada jogador, procede-se como antes, vericando a estratgia que gera o maior payopara cada possibilidade existente. A diferena que, agora, essas possibilidades socombinaes de escolhas dos outros dois jogadores.