Departamento de Matemtica

O TEOREMA DE EQUILBRIO DE NASH

Introduo Estudamos, ao longo do segundo semestre de 2006, tpicos em anlise real na reta. Com as ferramentas adquiridas, nos dedicamos desde janeiro de 2007 ao estudo dos conceitos matemticos presentes na teoria dos jogos e, principalmente, naqueles em que se baseia o conceito de equilbrio de Nash. Com o exemplo simples (mas altamente esclarecedor e de fcil extenso para n jogadores) de dois jogadores, mostramos primeiramente as condies que devem ser atendidas por domnios, estratgias e pelas funes de utilidade para que exista um equilbrio de Nash. Finalmente, utilizando o teorema do ponto fixo de Brouwer, provamos a existncia de tal equilbrio. Teoria dos Jogos A teoria dos jogos uma teoria matemtica utilizada para modelar fenmenos que se manifestam quando dois ou mais agentes de deciso interagem entre si. Ao utilizar esses modelos, podemos formular uma linguagem comum aos mais diferentes tipos de jogos, o que facilita o estudo e anlise dos resultados dessas interaes. Apesar de ser um campo de estudo intimamente ligado matemtica, o escopo das reas onde se aplica a teoria dos jogos to extenso quanto diversificado. O resultado de eleies, a dominncia de uns genes sobre outros na evoluo gentica, a dinmica dos leiles, a filosofia, a antropologia, as fontes de informaes do jornalismo e importantes conceitos econmicos so exemplos dessas reas. Mas, afinal, o que um jogo? Formalmente falando, um jogo tem alguns elementos bsicos: um conjunto finito de jogadores definido por G = {g1, g2, ... , gn}. Cada jogador gi G possui um conjunto finito de estratgias Si = {si1, si2, ... , simi}. O conjunto de todos os conjuntos de estratgia forma, assim, o produto cartesiano S = ni=1 Si = S1 S2 ... Sn, chamado de espao de estratgia do jogo. Para cada jogador gi G existe uma funo de utilidade Ui: S s Ui (s) que nos d o bem estar ou payoff Ui (s) imagem de um vetor s S para o jogador gi associado a esse perfil de estratgia. Dados esses elementos, podemos notar que o resultado do jogo para cada um dos jogadores gi no depende apenas de suas escolhas individuais, simi, e sim do encontro das escolhas de todos os jogadores de G. Representamos esse encontro pelo vetor s. O jogo que acabamos de definir possui estratgias discretas e finitas. No entanto, mais importante para este projeto trabalhar com jogos em que as opes de estratgia de cada jogador estejam em conjuntos contnuos e, portanto, todos os jogadores tenham a sua disposio infinitas estratgias dentro de um intervalo. Em uma definio mais formal,

Departamento de Matemtica

continuamos com um conjunto finito de jogadores definido por G = {g1, g2, ... , gn}. Cada jogador gi G possui agora um intervalo compacto de estratgias Ii = [ai, bi]. O conjunto de todos os intervalos forma, portanto, o produto cartesiano I = ni=1 Ii = I1 I2 ... In, que podemos chamar de espao de estratgia contnua do jogo. Vale ressaltar que o espao gerado compacto e convexo, pois produto de intervalos tambm compactos e convexos. Para cada jogador gi G existe uma funo de utilidade Ui: I x Ui (x) que nos d o bem estar ou payoff Ui (x) imagem de um vetor x I para o jogador gi associado a esse perfil de estratgia, em que x = (x1, x2, ... , xn) com xi Ii. Um Breve Histrico As primeiras referncias conhecidas teoria dos jogos datam do ano de 1713, na correspondncia de James Waldegrave a Nicolas Bernoulli. Em carta, ele apresenta sua anlise do jogo de cartas Le Her, para o qual prope uma soluo estratgica. Waldegrave, porm, no se aprofunda em uma anlise terica mais geral de suas concluses.

Figura 1: James Waldegrave

O primeiro estudo mais formal em teoria dos jogos um trabalho sobre o duoplio de Antoine Augustin Cournot, publicado em 1838. No entanto, apenas em 1913 foi publicado o primeiro teorema matemtico sobre o tema, de autoria de Ernst Zermelo, que define o jogo de xadrez como estritamente dominado, isto , um jogo em que a cada etapa da partida pelo menos um dos jogadores possui uma estratgia que lhe trar a vitria ou conduzir o jogo ao empate. Emile Borel foi outro grande matemtico que se interessou pelos jogos. Publicou quatro artigos sobre jogos estratgicos e acreditava que a guerra e a economia podiam ser estudadas de forma semelhante. Apesar de todos estes avanos, a teoria dos jogos foi encarada como uma rea menor da matemtica ainda por muitos anos. Foi apenas com o matemtico hngaro John Von Neumann que a situao comeou a mudar. Com a publicao de uma srie de trabalhos em 1928, ele provou, utilizando topologia e anlise, a existncia de soluo em estratgias mistas (quando se leva em considerao a distribuio probabilstica sobre as estratgias puras) para jogos finitos de soma-zero com dois jogadores. Em 1937, ele divulgou uma nova demonstrao com o mesmo resultado, considerada mais clara, usando o teorema do ponto fixo de Brouwer.

Departamento de Matemtica

Figura 2: John Von Neumann

Von Neumann dividiu com o economista Oscar Morgenstern a autoria do clssico The Theory of Games and Economic Behavior, publicado em 1944. A obra considerada um marco na histria da teoria dos jogos, devido ao enorme impacto no estudo da matemtica aplicada e na teoria das decises econmicas. John Forbes Nash Jr., em uma srie de estudos publicados ao longo do ano de 1950, realizou avanos enormes e definitivos. Dentre esses estudos, os de maior relevncia para nossa anlise so Equilibrium Points in n-Person Games e Non-cooperative Games, nos quais Nash provou a existncia de equilbrio para jogos no-cooperativos de estratgia mista. justamente este equilbrio que convencionamos chamar de equilbrio de Nash.

Figura 3: John F. Nash Jr.

Por suas contribuies teoria dos jogos, John Nash, John Harsanyi, e Reinhard Selten receberam o prmio Nobel de economia em 1994. Desenvolvimento Antes de tudo, cabe uma definio. Um equilbrio de Nash uma situao na qual, dadas as decises tomadas pelos outros competidores, nenhum jogador pode melhorar sua situao mudando sua prpria deciso. Em outras palavras, no h incentivos para tal mudana. Utilizando a definio formal de um jogo j apresentada, podemos dizer: Um vetor x = ( x 1, x 2, ... , x n) In um equilbrio de Nash se, para todo i, ocorre que Ui ( x i, x - i) Ui (xi, x - i) xi Ii,

Departamento de Matemtica

em que i representa todos os jogadores, exceto i. O clebre dilema dos prisioneiros, formulado por Albert W. Tucker em 1950, oferece uma boa ilustrao deste conceito. O dilema surge na seguinte situao: dois suspeitos, A e B, so acusados de um mesmo crime. Presos em celas separadas e sem possibilidade de se comunicarem, uma proposta lhes feita: cada um deles pode escolher entre confessar ou negar o crime. Se ambos negarem, sero presos por um ano. Se os dois confessarem, sero presos por trs anos. Mas, se um deles confessar e o outro negar, o que confessou ser libertado imediatamente enquanto o que negou ser submetido pena de 10 anos de priso. Temos assim os seguintes resultados: Prisioneiro B Confessar Confessar Negar Prisioneiro A
Tabela 1: Matriz de payoffs do Dilema dos Prisioneiros

Negar (0, -10) (-1, -1)

(-3, -3) (-10, 0)

Vemos na matriz de payoffs acima que, atendida a hiptese de ausncia de um acordo prvio entre os prisioneiros, tenha o outro confessado ou negado, sempre melhor confessar. Assim, o ponto (Confessar, Confessar) representa um exemplo de equilbrio de Nash. Isso fica mais claro analisando a questo do ponto de vista de cada jogador. Eles raciocinam da seguinte maneira: O outro prisioneiro pode, assim como eu, negar ou confessar. Se ele confessar, o melhor que posso fazer confessar tambm, j que ficarei preso por trs anos no lugar de 10 anos. Se ele negar, o melhor para mim ainda confessar, pois assim estarei livre em vez de condenado a um ano. Nos dois casos, o melhor confessar, portanto, eu confessarei. Como ambos os prisioneiros, se forem racionais, pensaro dessa maneira, ficaro presos por trs anos. O resultado do dilema dos prisioneiros nos permite fazer observaes bastante interessantes. No difcil perceber que o ponto de equilbrio de Nash no eficiente no sentido de Pareto, isto , existe uma maneira de melhorar a situao de um dos jogadores sem piorar a situao do outro. De fato, o equilbrio o nico que no timo de Pareto! Na verdade, nesse jogo existe uma forma de melhorar a situao de ambos os jogadores concomitantemente. Se ambos cooperarem se deslocando para o ponto (Negar, Negar) tero dois anos a menos de pena. Mas por que isso no ocorre? A resposta reside no fato de que o ponto (Negar, Negar) no obedece racionalidade. Estando nesse ponto, os dois tero um incentivo enorme a confessar o crime: sua liberdade. A desconfiana os leva a confessar o crime. Vejamos agora outros exemplos de jogos. H aqueles em que h mais de um equilbrio de Nash e outros em que eles no existem para estratgias discretas, ou puras. A batalha dos sexos descreve a seguinte situao: um casal deseja sair. Ele gosta mais de futebol e ela gosta mais de ir ao cinema. Se eles vo juntos ao futebol, ele tem satisfao maior que ela. Se forem ao cinema, ela tem satisfao maior que ele. Finalmente, se ambos sarem sozinhos, ficaro igualmente insatisfeitos. Podemos representar a situao na matriz de payoffs, em que os nmeros representam uma ordenao de utilidades, a saber, Uele: S e Uela: S ..

Departamento de Matemtica

Ela Futebol Futebol Cinema Ele

Cinema (0, 0) (5, 10)

(10, 5) (0, 0)

Observe que, nesse jogo, temos dois equilbrios de Nash. Os pontos (Futebol, Futebol) e (Cinema, Cinema) satisfazem a definio formal discutida anteriormente. O que mais importa para este casal estar junto. Se for no programa de sua preferncia, tanto melhor. Vejamos ainda o jogo combinando moedas. Nesse jogo os competidores exibem, simultaneamente, as moedas que cada um tem em sua mo. Se ambas as moedas apresentam cara ou coroa, o jogador 2 d sua moeda para o jogador 1. Se uma moeda apresenta cara e a outra apresenta coroa, o jogador 1 que deve dar sua moeda para o jogador 2. Temos a seguinte matriz de payoffs: Jogador 2 Cara Cara Jogador 1
Tabela 3: Matriz de payoffs para Combinado Moedas

Coroa

(1, -1) (-1, 1)

Coroa (-1, 1) (1, -1)

Note que, nesse jogo, os interesses dos jogadores so completamente opostos. O ganho de um , sempre e na mesma medida, a perda do outro. Isso dificulta a existncia de um equilbrio, ao menos em estratgias discretas, como veremos mais adiante. Assim, o combinando moedas com estratgias puras um jogo em que no h um equilbrio de Nash. A Demonstrao Todos os jogos apresentados at agora tm estratgias discretas (Confessar ou Negar), (Cinema ou Futebol), (Cara ou Coroa). Mais interessante e til para nosso trabalho ter estratgias contnuas que podem representar preos, decises de produo ou qualquer outra situao em que os resultados individuais dependam das decises de outros agentes. Suponha um jogo com dois participantes, 1 e 2, que escolhem estratgias no intervalo [0,1]. Temos assim I1 = [0,1] e I2 = [0,1] e o domnio I1 I2 ser o quadrado compacto de lado 1. O bem-estar ou utilidade de cada jogador dado pelas funes U1: I1 I2 e U2: I1 I2 .

Como vimos anteriormente na definio de um jogo, o bem-estar de cada jogador no depende somente da escolha que ele prprio faz, mas tambm da escolha feita pelo outro jogador.

Departamento de Matemtica

A partir destas funes-utilidade, definimos agora 1: I2 I1 e 2: I1 I2 como sendo funes tais que, dada a deciso de um dos jogadores, i leva o outro a tomar uma deciso que maximize sua utilidade. Por exemplo: 1 leva x*2 no nico x 1 que maximize a utilidade do jogador 1, ou seja, o ponto (1 (x*2), x*2) ser tal que U1 ( x 1, x*2) U1 (x1, x*2) x1 I1 e, equivalentemente, o ponto (x*1, 2 (x*1)) ser tal que U2 (x*1, x 2) U2 (x*1, x2) x2 I2. fcil notar que x i melhor que qualquer outra estratgia disposio do jogador i dado que o outro jogador escolheu a estratgia x*j. Se considerarmos o produto 1 2 obteremos uma aplicao : I1 I2 I1 I2, que leva o par (x*1, x*2) no par (1 (x*2),2 (x*1)); os pontos fixos desta aplicao sero equilbrios de Nash no jogo. Logo a demonstrao da existncia de um equilbrio de Nash se resume a obter um ponto fixo da aplicao 1 2. De fato, o teorema de Nash nos d a seguinte informao: Teorema de Nash: Todo jogo finito, isto , com finitos jogadores e um conjunto compacto e convexo de estratgias, tem uma soluo em estratgias mistas. A prova deste teorema utiliza conceitos que exigem matemtica relativamente avanada. Em nossa demonstrao, faremos uma hiptese adicional (a concavidade na prpria estratgia) que facilitar enormemente a compreenso dos passos da demonstrao, mas compromete em muito pouco a fora do resultado final, que a prova da existncia do equilbrio de Nash. Algumas condies devem ser atendidas para que as i sejam realmente funes bemdefinidas. Para garantir a boa-definio de i, as funes-utilidade U1 e U2 devem ser contnuas, pois segue ento pelo teorema de Weierstrass que existem pontos que maximizam U1 ( ,x*2) e U2 (x*1, ), j que I1 e I2 so compactos. No entanto, por si s a continuidade das funes-utilidade no o bastante para afirmar que cada i funo bem-definida, pois podem existir vrios pontos que maximizem i nos dados intervalos. Queremos, portanto, uma condio que garanta a unicidade do ponto maximizante de utilidade. Essa condio a concavidade das funes-utilidade em cada estratgia. Como foi mencionado, a demonstrao de Nash no tem essa condio como pr-requisito, pois qualquer jogo finito em estratgias mistas tem soluo. No entanto, para nossos objetivos, ela altamente vlida e simplificadora. Nos termos formais de um jogo definidos anteriormente, isso quer dizer que, uma vez fixadas as escolhas de todos os outros jogadores i, a funo Ui (xi, x - i): I1 que relaciona unicamente as escolhas do jogador i com sua utilidade deve ser cncava em I1. Observe dois casos extremos:

Departamento de Matemtica

Figura 4: exemplo de infinitos mximos

Figura 5: concavidade - um nico mximo

Podemos provar que a concavidade implica na unicidade do ponto mximo demonstrando que se existissem dois mximos, por exemplo, em dado intervalo, a funo no poderia ser cncava nesse mesmo intervalo. Tome x e y I tal que x y, ambos pontos de mximo de f: em I, portanto, f (x) = f (y) f (z) z I. Dado 0 < t < 1, da definio de concavidade estrita afirmamos que f (t.x + (1 - t).y) > t.f (x) + (1 - t).f (y), temos por hiptese que f (x) = f (y) e x e y so mximos, um absurdo, j que esta ltima equao nos informa que uma mdia ponderada qualquer de x e y possui imagem de valor maior que f (x) = f(y). Tal fato mostra que f s pode ter um mximo em I se f for cncava. Para garantir a concavidade, bastar para nossos objetivos supor que a segunda derivada de Ui seja negativa no intervalo [0, 1], uma vez fixada a escolha do outro jogador. Utilizaremos o teorema do valor mdio para provar que f(x) < 0 implica em concavidade. Suponha f: Sabemos que f cncava se f (x) f (a) + f (a).(x - a), ou seja, f cncava se est localizada abaixo da reta que tangencia f no ponto a, fato ilustrado no seguinte grfico de uma f qualquer:

tal que f (x) < 0 x [a, b].

Departamento de Matemtica

Figura 6

O teorema do valor mdio garante que z (a, b) tal que f (z) = f (b) f (a) / b - a. Considere f | (a,x] . Pelo teorema do valor mdio z (a, x) tal que f (z) = f (x) f (a) / x - a . Remanejando a equao obtemos f (x) = f (a) + f(z).(x - a). Como, por hiptese, f < 0 e z > a, podemos afirmar que f (z) < f (a). Temos assim f (x) = f (a) + f (z).(x - a) < f (a) + f (a).(x - a), f, portanto, cncava. Estabelecidas as condies para a existncia de 1 e 2, devemos nos voltar agora para a necessidade de sua continuidade. Para tanto, demonstramos que, com as hipteses sobre as quais construmos as funes i, elas sero sempre contnuas. Utilizando agora a notao x I1 e y I2, no caso de 1, teremos: 1 (y*) = x I1 / U1 ( x , y*) U1 (x, y*) x I1. Afirmamos que 1: I2 I1 contnua. Suponha agora que a afirmao falsa, ou seja, 1: I2 I1 no contnua e, portanto, existe uma seqncia yn I2 tal que yn mas 1 (yn) 1 ( ). Tomando uma subseqncia yk de yn temos 1 (yk) Conclumos que em que no maximizante.

Departamento de Matemtica

U1 (1 ( ), ) U1 ( j que U1: I1 I2

) e tambm que U1 (1 ( ), yn) U1 (1 ( ), ),

contnua. Logo vemos que, para n grande o suficiente:

U1 (1 ( ), yn) U1 (1 ( ), ) e U1 (1 (yk), yk) U1 ( , ), com U1 (1 ( ), ) U1 ( , ), o que um absurdo j que 1 foi construda como uma funo maximizadora. O mesmo se pode afirmar a respeito de 2. i so, portanto, funes contnuas. Uma vez que a existncia e a continuidade de 1 e 2 estejam garantidas, precisamos de um argumento para garantir a existncia de um ponto fixo de 1 2, ou seja, de um equilbrio de Nash. Utilizamos para tanto o seguinte teorema: Teorema do Ponto Fixo de Brouwer: Seja B conjunto compacto e convexo. Se f: B B uma aplicao contnua. Ento existe x B tal que f (x) = x. Parte final da demonstrao do Teorema de Brouwer. Provaremos o teorema no caso em que B uma bola fechada, e tomando como fato a seguinte (e difcil) proposio: se B compacto ento no existe nenhuma aplicao contnua f: B B tal que f | B = id| B. A Figura 7 ilustra essa impossibilidade:

B
Figura 7

Supomos, por contradio, que existe aplicao contnua f: B B tal que f no possui nenhum ponto fixo, ou seja, f (x) x para todo x B. Definimos ento g: B B da seguinte maneira: g (x) = interseo com B do segmento de reta que comea em f(x) e passa por x. Intuitivamente vemos que g contnua e, se x B, vale que g (x) = x. Ento g contnua e g | B = id| B, o que contradiz o fato citado cima.

Departamento de Matemtica

Figura 8: A funo g: B

Como no contexto de nosso jogo o domnio I1 I2 compacto e convexo e a aplicao : I1 I2 I1 I2 contnua, pois o produto de duas funes contnuas 1 e 2, podemos, pelo teorema do ponto fixo de Brouwer, afirmar que existe um ponto x I1 I2 tal que ( x ) = x , ou seja, que existe um equilbrio de Nash. Com um software de otimizao, podemos encontrar e calcular os equilbrios de Nash dos jogos citados ao longo do trabalho em estratgias mistas.

Figura 9: Representao grfica do Dilema dos Prisioneiros

Departamento de Matemtica

Figura 10: Representao grfica da Guerra dos Sexos

Figura 11: Representao grfica do Combinando Moedas

Departamento de Matemtica

Referncias [1] J. P. Torres-Martnez, Jogos Sociais e Equilbrio Walrasiano, notas de minicurso SEMAP/UFF online (http://www.semap.labma.ufrj.br/arquivos), 2006. [2] H. J. Bortolossi, G. Garbugio, e B. A. Sartini, Uma Introduo Teoria dos Jogos, notas de minicurso SEMAP/UFF online (http://www.semap.labma.ufrj.br/arquivos), 2006. [3] E. L. Lima, Anlise Real, Volume 1, Coleo Matemtica Universitria/IMPA, 2004. [4] M. Shubik, Teora de Juegos en las Ciencias Sociales Conceptos y Soluciones, Textos de Economia do Fondo de Cultura Econmica/Mexico, 1996.