Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL FLUMINENSEJUSCILEI CARLOS HENRIQUE
UMA INTRODUÇÃO À TEORIA DOS JOGOS E SUAS APLICAÇÕES
Niterói2010
JUSCILEI CARLOS HENRIQUE
UMA INTRODUÇÃO À TEORIA DOS JOGOS E SUAS APLICAÇÕES
Trabalho de Conclusão de Curso subme-
tido ao Curso de Tecnologia em Siste-
mas de Computação da Universidade
Federal Fluminense como requisito par-
cial para obtenção do título de Tecnólo-
go em Sistemas de Computação.
Orientador: Uéverton dos Santos Souza
NITERÓI2010
JUSCILEI CARLOS HENRIQUE
UMA INTRODUÇÃO À TEORIA DOS JOGOS E SUAS APLICAÇÕES
Trabalho de Conclusão de Curso subme-
tido ao Curso de Tecnologia em Siste-
mas de Computação da Universidade
Federal Fluminense como requisito par-
cial para obtenção do título de Tecnólo-
go em Sistemas de Computação.
Niterói, 30 de Novembro de 2010.
Banca Examinadora:
_________________________________________
Prof. Uéverton dos Santos Souza, Msc. – Orientador
UFRJ - Universidade Federal do Rio de Janeiro
_________________________________________
Prof. Fábio Protti, Dsc. –Avaliador
UFF - Universidade Federal Fluminense
_________________________________________
Profa. Maise Dantas da Silva, Dsc. – Avaliadora
UFF - Universidade Federal Fluminense
Dedico este trabalho aos meus pais, aos
meus estimados irmãos e sobrinhos.
AGRADECIMENTOS
A Deus, que sempre iluminou a minha cami-
nhada.
Aos professores/tutores e funcionários do CE-
DERJ/Três Rios;
Aos Membros da Banca Examinadora por
suas sugestões de melhoria que contribuíram
para o enriquecimento do trabalho;
Um agradecimento especial ao Professor Ué-
verton dos Santos Souza, meu orientador,
pelo esforço e dedicação com que conduziu a
orientação do trabalho;
A todos os meus familiares e amigos pelo
apoio e colaboração.
RESUMO
A teoria dos jogos é uma teoria que estuda através de modelos matemáticos os comportamentos de um determinado grupo de indivíduos. Ela apresenta-se como uma alternativa à formulação de estratégias, onde cada indivíduo deseja encontrar sua estratégia ótima para um determinado conflito denominado jogo. Esta teoria for-nece uma linguagem para descrever processos de decisão conscientes e objetivos envolvendo mais do que um indivíduo sendo, portanto, usada para o estudo de as-suntos tais como leilões, eleições, evolução genética, modelos econômicos, tráfego em redes, etc. Este trabalho tem o objetivo de evidenciar conceitos desta teoria como suas definições, notações, exemplos, aplicabilidades, algumas aplicações des-ta teoria em problemas de otimização combinatória também são apresentadas, além de algumas estruturas de dados utilizadas para representar jogos, por exemplo, as árvores de jogos.
Palavras-chaves: Teoria dos jogos, Otimização Combinatória, Árvore de Jogos.
LISTA DE ILUSTRAÇÕES
Figura 1: Roteamento por provedores de serviço de Internet....................................23
Figura 1: Roteamento por provedores de serviço de Internet....................................23
1
LISTA DE TABELAS
Tabela 1: Dilema dos prisioneiros...............................................................................21
SUMÁRIO
RESUMO......................................................................................................................6
LISTA DE ILUSTRAÇÕES ..........................................................................................7
LISTA DE TABELAS ...................................................................................................8
SUMÁRIO ....................................................................................................................9
1 INTRODUÇÃO.........................................................................................................10
2 DEFINIÇÕES BÁSICAS E NOTAÇÕES..................................................................12
3 JOGOS CLÁSSICOS E APLICAÇÕES....................................................................20
4 OTIMIZAÇÃO COMBINATÓRIA .............................................................................38
5 A FORMA EXTENSIVA DE UM JOGO....................................................................48
CONCLUSÃO.............................................................................................................52
REFERÊNCIAS BIBLIOGRÁFICAS...........................................................................53
1 INTRODUÇÃO
Teoria dos Jogos é uma técnica que estuda através de modelos matemá-
ticos, tomadas de decisões em ambientes de conflito, denominados jogos.
Um jogo é basicamente composto por um conjunto de regras e um con-
junto de agentes denominados jogadores. Cada jogador tem um conjunto de estraté-
gias, ou seja, um conjunto de ações a ser executado ao longo do jogo, onde o objeti-
vo de cada jogador é maximizar o seu grau de satisfação após o término do jogo.
No decorrer de um jogo, cada jogador faz uso de estratégias que modifi-
cam o ambiente jogado, resultando assim em respostas dos adversários. Desta for-
ma, todo jogador possui um plano estratégico para cada ação e reação do adversá-
rio, que compõe um complexo conjunto de alternativas e uma diversidade de lances.
Quando cada jogador escolhe sua estratégia, temos então uma situação
ou perfil no espaço de todas as situações possíveis. Cada jogador tem interesse ou
preferências por cada situação no jogo. Em termos matemáticos, cada jogador tem
uma função utilidade que atribui um número real (o ganho ou payoff do jogador) a
cada situação do jogo.
A teoria dos jogos tem a finalidade de prever os movimentos dos jogado-
res, posicionando-os da melhor forma para obter o resultado desejado. O seu objeti-
vo é entender a lógica na hora da decisão e ajudar a responder se é possível haver
colaboração entre os jogadores, em quais circunstâncias o mais racional é não cola-
borar, quais estratégias devem ser adotadas para garantir a colaboração entre os jo-
gadores visando solucionar os conflitos onde o foco do estudo são as estratégias uti -
lizadas pelos jogadores.
No Capítulo 2 será introduzido as definições básicas de um jogo, bem
como as ações e estratégias tomadas por cada jogador. Os tipos de estratégias, ti-
pos de jogos cooperativos e não cooperativos e os possíveis resultados e soluções
de um jogo. Um breve histórico sobre a origem da teoria dos jogos.
No capítulo 3 será apresentado alguns jogos clássicos como o dilema dos
prisioneiros, roteamento por provedores de serviços, batalha dos sexos, jogo de con-
gestionamento, cara ou coroa, tragédia dos comuns dentre outros. Ainda nesta se-
ção será apresentado algumas aplicações da teoria dos jogos; em economia, biolo-
gia e computação.
No capítulo 4 será apresentado alguns problemas de otimização combina-
tória analisados pela teoria dos jogos. Um exemplo bem conhecido é o problema dos
casamentos estáveis, entre outros. Algoritmos para estes problemas também serão
apresentados.
No capítulo 5 será apresentada a forma extensiva de um jogo, bem como,
árvores Min/Max.
2 DEFINIÇÕES BÁSICAS E NOTAÇÕES
Neste trabalho, um jogo J será definido por um conjunto N= {1,...,n} de jo-
gadores, onde cada jogador i possui um conjunto de estratégias Si. Uma configura-
ção (resultado) deste jogo J, consiste de um ponto do jogo onde cada jogador esco-
lheu uma estratégia si ∈ Si, sendo S= S1 x S2 x ... x Sn o conjunto de resultados do
jogo, onde s ∈ S é um possível resultado do jogo.
Em um jogo J, cada jogador i possui uma ordem de preferência dos resul-
tados, dado por uma função de utilidade ui: S → R. Se ui(s) > ui(s’) então o jogador i
prefere o resultado s a s’.
Dado s = (s1,...,sn) onde s ∈ S, definimos s-i = (s1,..., si-1,si+1,...,sn), ou seja,
uma configuração parcial do jogo, onde apenas o jogador i não teve sua estratégia
escolhida. Sendo assim, (s-i,ri) é definido como uma configuração do jogo, onde a es-
tratégia ri é escolhida dado s-i.
Em relação a uma configuração final do jogo s, dizemos que o jogador i
esta satisfeito se não existe nenhuma outra configuração melhor para ele, ou seja,
ui(s-i,s’i) ≤ ui(s), para todo s’i ∈ Si..
2.1 AÇÕES E ESTRATÉGIAS
O conceito de estratégia confunde-se, erroneamente, com o de movimen-
to. Um movimento é uma ação que toma um jogador em um determinado momento
do jogo (por exemplo, no xadrez). Uma estratégia, por sua vez, é um conjunto de
ações a ser executado ao longo do jogo. Ainda usando o xadrez como exemplo, em
principio o jogador deveria saber como responder a cada movimento do adversário,
e a estratégia seria definida como o conjunto de ações a ser realizada em resposta
aos movimentos do adversário. Assim, a estratégia consiste num plano de ações
que pode se resumir a apenas uma ação, ou a um complexo conjunto de alternativas
do tipo “se ele fizer isso, eu faço aquilo, e, se ele responde A, eu respondo B, entre
outras”, como no jogo de xadrez.
Em Teoria de Jogos, a estratégia de um jogador é um plano de ação com-
pleto para qualquer situação que possa acontecer; determina a conduta do jogador.
A estratégia de um jogador determinará a ação que tomará o jogador em qualquer
momento do jogo, para qualquer sequência de acontecimentos até esse ponto.
Um perfil de estratégia é um conjunto de estratégias para cada jogador
que especifica completamente todas as ações em um jogo. Um perfil de estratégia
deve incluir somente uma estratégia para cada jogador.
2.1.1 TIPOS DE ESTRATÉGIAS
Uma estratégia pura é aquela em que cada jogador tem uma jogada que
não depende do conhecimento prévio do jogo do opositor. Em particular, define,
para cada escolha possível, a opção que toma o jogador. O espaço de estratégia de
um jogador é o conjunto de estratégias puras disponível ao jogador.
Uma estratégia mista é a distribuição de probabilidade sobre suas estraté-
gias puras. Define uma probabilidade sobre as estratégias e reflete que, em lugar de
eleger uma estratégia pura particular, o jogador elegerá a esmo uma estratégia pura
com base à distribuição dada pela estratégia mista. Por exemplo, no jogo de cara ou
coroa, o jogador A ganha se faces são iguais e B ganha se diferentes: A poderia es-
colher jogar Cara 50% do tempo e Corroa os 50% restantes e vice e versa.
2.2 JOGOS COOPERATIVOS E NÃO-COOPERATIVOS
Em um jogo, devem estar definidas as ações possíveis de ser realizadas
por parte dos jogadores, como a possibilidade ou não de cooperação, acordos ou
coalizões entre eles. Os jogos em que os acordos são permitidos são chamados jo-
gos cooperativos. Por exemplo, um acordo formal de cartel, como a OPEP (Organi-
zação dos Países Exportadores de Petróleo), ou uma joint venture (associação de
empresas para o desenvolvimento e execução de um projeto específico no âmbito
econômico e/ou financeiro). Quando os acordos não são possíveis, temos os jogos
não-cooperativos. Por exemplo, uma disputa na pesquisa e desenvolvimento de uma
patente. Os jogos não-cooperativos foram os mais estudados e apresentam resulta-
dos mais conhecidos.
Um jogo também deve definir que tipo de informações está disponível
para os jogadores. Chamam-se jogos de informação completa aqueles nos quais os
jogadores possuem todas as informações necessárias para a tomada de decisão.
Esses são os mais conhecidos e mais facilmente analisados. Quando parte das in-
formações não está disponível, temos um jogo de informação incompleta.
Também existem os jogos de informação perfeita ou seqüenciais e os jo-
gos de informação imperfeita ou simultâneos. Nos jogos em que a jogada é simultâ-
nea, como o “par ou impar”, a informação é imperfeita, já que um jogador não sabe o
que o outro vai fazer. Nos jogos cujas ações ocorrem em sequência, como o xadrez,
a informação é perfeita, pois o jogador sabe o que o outro fez antes de fazer sua jo-
gada.
2.3 OS RESULTADOS (PAYOFFS)
Os resultados são avaliados de acordo com as preferências dos jogado-
res. Nem sempre os resultados e sua avaliação se colocam de forma simples. Na
maior parte das vezes, os resultados são apresentados numericamente para facilitar
o entendimento do jogo. Esses números geralmente representam lucro ou nível de
satisfação do jogador ao fim do jogo (consequentemente, quanto maior o número,
maior o nível de satisfação).
Temos também os chamados jogos de soma zero, que são os jogos nos
quais o que um grupo de jogadores ganha é exatamente o que o outro perde (ou
falando mais informalmente, um jogador só lucra com base no prejuízo de outro). O
Poker exemplifica um jogo de soma zero (ignorando possíveis vantagens da mesa),
porque o vencedor recebe exatamente a soma das perdas de seus oponentes. Os
jogos de soma zero são um caso particular dos jogos de soma constante, que são
aqueles em que a soma dos resultados é sempre a mesma, independentemente das
ações dos jogadores, contrapondo-se aos jogos de soma variável no qual a soma
dos resultados é inconstante, como o dilema dos prisioneiros, que será definido na
seção 3
2.4 SOLUÇÕES
Solução de um jogo consiste em saber qual a melhor forma de jogar o jogo
(a melhor estratégia) para cada jogador, e assim até o resultado final. Existem vários
conceitos de solução ou de tomada de decisão. Aqui, analisaremos três dos mais
conhecidos:
• Dominância
• Maxmin
• Equilíbrio de Nash
De todo modo, a idéia central é sempre a de que a melhor decisão (a me-
lhor estratégia) é sempre a que garanta o melhor resultado, dadas as estratégias
dos adversários. Utilizando basicamente jogos não-cooperativos de informação com-
pleta e dois jogadores, poderemos estudar esses conceitos.
2.4.1 DOMINÂNCIA
Frequentemente, iremos discutir perfis de estratégia na qual apenas a es-
tratégia de um único jogador g i ∈ G irá variar, enquanto que as estratégias de seus
oponentes permanecerão fixas.
Denote por
s−i = (s1,...,s(i−1), s(i+1),..., sn) ∈S−i = S1 ×···× Si−1 × Si+1 ×···× Sn
uma escolha de estratégia para todos os jogadores, menos o jogador g i. Desta ma-
neira, um perfil de estratégia pode ser denotado por
s = (s−i, si,) = (s1,..., s(i−1), si, s(i+1),..., sn).
Estratégia dominante
Uma estratégia é chamada de dominante em relação a outra quando os
resultados obtidos com sua utilização são melhores em relação aos resultados obti-
dos com outra estratégia, dada uma ação dos demais jogadores. Essa estratégia é,
assim, melhor que as outras e pressupõe-se que é a que deverá ser escolhida pelo
jogador, ou seja, ui(s’i,s-i) ≤ ui(s), para todo s’i ∈ Si.
Estratégia Pura Estritamente Dominada
Uma estratégia pura sik ∈ Si do jogador gi ∈G é estritamente dominada
pela estratégia sik' ∈ Si se ui(sik’, s−i) > ui(sik, s−i), para todo s−i ∈ S−i. A estratégia sik ∈ Si
é fracamente dominada pela estratégia sik’ ∈ Si se ui(sik’, s−i) ≥ ui(sik, s−i), para todo s−i
∈ S−i.
Dominância estrita iterada nada mais é do que um processo onde se eli-
minam as estratégias que são estritamente dominadas.
2.4.2 MAXMIN
Outra forma de escolher a estratégia, quando não existe estratégia domi-
nante, é o chamado maxmin. Nesse caso, o jogador procura maximizar o mínimo
que ele pode assegurar para si, independente das estratégias dos outros jogadores.
Por exemplo, a batalha dos sexos, que será detalhada na seção 3. A estratégia max-
min é a que garante ganho mínimo para o jogador. A idéia aqui é a seguinte: não sei
o que fazer, farei aquilo que me der “o menos pior” dos piores resultados possíveis.
O conceito de maxmin é baseado na idéia de que o jogador age de ma-
neira mais prudente possível. Para muitos autores, essa idéia é muito forte, pres-
supõe-se que os jogadores vivem constantemente na retranca ou que são sempre
muito pessimistas. Além do mais, pode conduzir a resultados que geram arrependi-
mento dos jogadores: eles poderiam ter feito melhor. Tais criticas fazem com que
esse conceito seja pouco usado como forma habitual de solucionar jogos pelos teóri-
cos, que preferem outro conceito.
2.4.3 O EQUILIBRIO DE NASH
O conceito de equilíbrio (ou solução) de Nash é também conhecido como
o de não-arrependimento. A combinação de estratégias escolhidas leva a um resul-
tado no qual nenhum dos jogadores individualmente se arrepende, ou seja, esse jo-
gador não poderia melhorar a sua situação unilateralmente modificando a estratégia
escolhida. Numa situação em que se utiliza o conceito de Nash, um jogador escolhe
a melhor estratégia, dada a escolha do outro.
Dizemos que um perfil de estratégia
s* = (s*1,..., s*
(i−1), s*i, s*
(i+1),..., s*n) ∈ S
É um equilíbrio de Nash se
ui(s*i, s*
−i) ≥ ui(sji, s*−i)
para todo i =1,..., n e para todo ji =1,..., mi, com mi ≥ 2, onde n é o número de jogado-
res e mi é o número de possíveis estratégias do jogador i.
2.5 HISTÓRICO
A teoria dos jogos, especialmente em sua ligação com a economia, tem
como marco fundamental a publicação, em 1944, do livro Teoria dos jogos e com-
portamento econômico, de autoria do matemático John Von Neumann e do econo-
mista Oskar Morgenstern [5]. Porém, antes dela muitos avanços haviam sido feitos
especialmente no campo da matemática.
Em 1912, o alemão Ernst Zermelo [3] prova um importante teorema que
conduz à ideia de que jogos não-cooperativos de duas pessoas, com ações seqüen-
ciais e informação completa, são perfeitamente determinados. Desse modo, jogos
como o “jogo da velha” ou xadrez têm uma solução conhecida, ou seja, os jogadores
têm uma estratégia ótima (apesar de se saber disso, ainda não foi descoberta qual
estratégia ótima em jogos de xadrez, mas sabe-se que ela existe). Outro grande ma-
temático que se interessou em jogos foi Emile Borel, em 1924 trabalhou com os
mesmos problemas que Von Neumann, chegando mesmo a definir um jogo na sua
forma moderna.
John Von Neumann era húngaro e já em 1928 publicou um estudo sobre
o conceito de minimax para jogos não-cooperativos de duas pessoas com soma
zero. Além de escrever o livro com Morgenstern, Von Neumann deixou contribuições
em diversas áreas. Foi um brilhante matemático, tendo elaborado importantes traba-
lhos em ciências da computação, desenvolvendo autômatos e inteligência artificial,
além de trabalhar com matemática aplicada à física quântica. Participou inclusive do
grupo que desenvolveu a bomba atômica nos Estados Unidos. Oskar Morgenstern,
economista austríaco, fez parte do famoso circulo de Viena, junto com pensadores
como Albert Einstein e Bertrand Russel, dedicou-se durante vários anos a modelos
de previsão econômica e a questões epistemológicas, quando se juntou a Von Neu-
mann para se dedicar aos modelos matemáticos de teoria dos jogos e suas aplica-
ções econômicas.
Depois do livro de Von Neumann e Morgenstern, ampliaram-se os traba-
lhos nesse campo, especialmente nos jogos chamados estritamente competitivos
(jogos de duas pessoas de soma zero). No início da década de 1950, uma nova im-
portante contribuição vem com John Forbes Nash Jr. [6,7,8,9,10], ainda dentro de jo-
gos não-cooperativos, porém com mais de duas pessoas e soma variável. Nesse pe-
ríodo, o autor desenvolve os conceitos de solução chegando ao chamado equilíbrio
de Nash. Nash também inicia importantes trabalhos na ainda pouco explorada área
dos jogos cooperativos. Nessa década, a parte básica de teoria dos jogos já estava
montada. A partir de então desenvolveram-se importantes sofisticações e refinamen-
tos no arsenal montado em meados do século. Em 1994, John Forbes Nash Jr. (Uni-
versidade de Princeton), John Harsanyi (Universidade de Berkeley, California) e Rei-
nhard Selten (Universidade de Bonn, Alemanha) receberam o prêmio Nobel por suas
contribuições à teoria econômica, especialmente à teoria dos jogos.
3 JOGOS CLÁSSICOS E APLICAÇÕES
Neste capítulo, será apresentado alguns jogos clássicos estudados na te-
oria dos jogos e algumas de suas aplicações.
3.1 O DILEMA DOS PRISIONEIROS
Trata-se de uma situação formulada por Merrill Flood e Melvin Dresher [1] em
1950 onde dois indivíduos devem tomar uma decisão, e sua conseqüência
depende da interação das duas decisões. Nesse jogo duas pessoas são
aprisionadas, suspeitas de terem cometido, conjuntamente um crime. Os policiais
colocam os dois suspeitos em celas separadas, de modo que a comunicação entre
eles não seja possível; a cada um é perguntado se cometeram ou não o crime. Os
policiais para induzi-los a confessar, propõem as seguintes situações:
• Se o suspeito não confessar e o seu parceiro confessar, denuncian-
do o outro, a pena será máxima para o que não confessou: dez anos de re-
clusão, enquanto o que confessou terá a pena reduzida à zero;
• Se ambos confessarem, a pena será reduzida à metade: cinco anos
de reclusão para cada suspeito;
• Se nenhum deles confessar o crime, eles apenas continuarão pre-
sos por mais um tempo, um ano, por exemplo.
A Tabela 1 ilustra o cenário descrito acima.
BConfessa Não Confessa
A
Confessa (5,5) (0,10)Não Confessa (10,0) (1,1)
Tabela 1: Dilema dos prisioneiros.
Com base no exemplo citado, temos um jogo com dois jogadores, não-co-
operativos, simultâneo, com informação incompleta. Podemos estudar o comporta-
mento dos jogadores, as estratégias possíveis e suas conseqüências. Se um dos
suspeitos confessar o crime, poderá ficar preso cinco anos ou permanecer
livre, caso o outro não confesse. Se não confessar, poderá ficar apenas um
ano preso, se o outro não confessar, ou dez anos caso o outro não confesse. Tam-
bém é possível analisar o resultado do jogo, a chamada solução de um jogo. Nesse
caso parece melhor para ambos não confessar e permanecer preso mais um ano,
porém como eles estão incomunicáveis existe a ameaça do outro confessar e com
isso ficar dez anos preso, enquanto aquele que confessou recebe a liberdade imedi-
atamente. Considerando a hipótese de traição, ambos terão fortes motivos para con-
fessar, podendo assim reduzir sua pena ou até se ver livre dela. A conseqüência
acaba sendo a confissão de ambos, com cinco anos de cadeia para cada um, o que
não é a melhor solução para ambos.
No caso do dilema dos prisioneiros, ambos os jogadores possuem uma
estratégia dominante. Para o prisioneiro A a estratégia dominante é confessar. Essa
estratégia leva a resultados melhores que a outra, não importando o que o prisionei-
ro B fizer. Assim, se o prisioneiro B confessar, a melhor resposta para o prisioneiro A
é confessar. Por outro lado, se o prisioneiro B não confessar, continua sendo a me-
lhor resposta (dominante) confessar. De modo análogo, podemos verificar que a es-
tratégia dominante para o jogador B também é confessar.
Vimos que a solução por estratégias dominantes é ambos confessarem e,
assim, ficarem presos por cinco anos. Essa também é uma solução de Nash. O prisi-
oneiro A tem uma decisão melhor do que a de confessar, uma vez que o prisioneiro
B confessou? Não, pois a outra opção seria não confessar, e se o fizesse ficaria dez
anos preso. Assim, para o prisioneiro A, confessar é a melhor estratégia se o B con-
fessar. O mesmo ocorre para o prisioneiro B, pois confessar é a melhor resposta que
ele pode dar à estratégia de confessar escolhida por A. Nessa situação, nenhum dos
dois prisioneiros se arrepende do que fez em vista do que o outro fez. Cada um de-
les, individualmente, não poderia ter atingido de maneira melhor. Essa solução é,
portanto uma solução de Nash, que é a mesma encontrada pelo critério de dominân-
cia.
3.2 ROTEAMENTO POR PROVEDORES DE SERVIÇOS
Este é um exemplo de roteamento em provedores de serviço de Internet
(ISP- Internet Service Providers) onde a mesma situação do Dilema dos Prisioneiros
pode ocorrer. Suponha que temos dois provedores de serviços ISP-A e ISP-B, cujas
redes estão ilustradas na figura abaixo (rede ISP-A do lado esquerdo e ISP-B do
lado direito). As duas redes possuem dois pontos por onde podem transmitir dados
de uma para outra rede, chamados pontos de troca, que são os pontos C e S. Quan-
do há uma requisição de transmissão com origem em um ponto a1 (na rede ISP-A)
para um ponto b3 (que está na rede ISP-B) o provedor ISP-A deve fazer esta trans-
missão através de uma rota (caminho) necessariamente passando por um dos pon-
tos C ou S. A rota percorrida dentro de uma mesma rede é determinada pelo seu
respectivo provedor e uma vez que o pacote atinge a rede de destino, todo o trajeto
restante será feito na mesma rede. Posto isso, uma transmissão de a1 para b3 pode
seguir pela rota (a1,C,b1,b2,S,b3) ou pela rota (a1,a2,S,b3) e como é o provedor ISP-A
que define em qual ponto de troca ele chega (se primeiro em C ou em S), é a deci-
são do provedor ISP-A que define qual a rota o pacote seguirá. A Figura 1 ilustra a
situação descrita acima.
Figura 1: Roteamento por provedores de serviço de Internet.
Como os provedores têm comportamento racional, eles tentam minimizar
o tráfego em sua rede e enviam o tráfego pela rota que chegar primeiro a um ponto
de troca. Vamos supor que cada aresta da rede tem custo unitário, exceto pelas liga-
ções S–a3 e S–b3, que terão custo 0 por ligarem pontos muito próximos. Assim, se o
provedor ISP-A escolher a rota passando por C, ele terá custo 1, porém fará com
que ISP-B tenha custo 3. Caso ele escolha a outra rota, terá custo 2 e não acarreta-
rá custos para ISP-B. Para deixar esta situação igual ao do Dilema dos Prisioneiros,
suponha que haja uma requisição para transmitir do ponto b1 para o ponto a3. Com
isso, se ambos provedores se comportarem de maneira racional (fazem suas res-
pectivas transmissões passarem por C), cada provedor terá um custo total de 4. Se
ambos não enviarem o pacote por C, cada provedor terá custo 2. Quando apenas
um servidor for racional, ele terá custo 1 e o outro 5.
O equilíbrio de Nash neste exemplo é o caso de ambos os provedores
não enviarem o pacote por C, onde cada provedor terá custo 2. Como podemos ob-
servar na Tabela 2.
ISP -B
C S
ISP-A
C (4,4) (1,5)
S (5,1) (2,2)
Tabela 2: Roteamento por provedores de serviço de Internet
3.3 BATALHA DOS SEXOS
Filomena e Juvenal se amam e detestam ficar separados. No entanto, nos
fins de semana, ambos gostam de programas distintos. Juvenal gosta de ir ao
futebol, ao passo que Filomena gosta de ir ao cinema. O problema é que ambos
detestam fazer programas sozinhos. A situação, comumente chamada de bata-
lha dos sexos, pode ser representada com base na matriz da tabela 3.
Filomena
Futebol Cinema
Juvenal
Futebol (3,2) (1,1)
Cinema (-1,-1) (2,3)
Tabela 3: Roteamento por provedores de serviço de Internet
Se ambos forem ao futebol, ambos estarão felizes, porém Juvenal um
pouco mais. Se ambos forem ao cinema, também ambos ficarão felizes, mas Filo-
mena mais. Contudo, se cada um for fazer um programa diferente, não estarão tão
felizes; pior ainda se Juvenal for ao cinema e Filomena ao futebol. Se cada um tiver
de escolher individualmente (sem se comunicar com o outro, mas procurando imagi-
nar o que o outro fará), percebe-se que nenhum deles possui uma estratégia domi-
nante, assim o jogo fica sem solução pelo critério de dominância. Usando o conceito
de maxmin, temos: para Juvenal, se ele escolher a estratégia de ir ao futebol, o pior
que pode ocorrer é Filomena escolher ir ao cinema, de modo que o resultado para
Juvenal seja (1). No caso de escolher a estratégia de ir ao cinema, o pior que pode
ocorrer é Filomena ir ao futebol, cujo resultado, para Juvenal, será (-1). Procurando
obter a menor perda possível, Juvenal, então, escolherá a estratégia de ir ao futebol.
Fazendo o mesmo raciocínio para Filomena, ela acabará escolhendo ir ao cinema.
Assim, a solução do jogo por maxmin será o par de estratégias Juvenal vai ao fute-
bol e Filomena ao cinema, com resultado mediano para ambos (1,1).
Olhando agora para o exemplo da batalha dos sexos, vemos que a solu-
ção maxmin não é uma solução para Nash: se Juvenal escolher ir ao futebol, era
melhor que Filomena também o fizesse. Do mesmo modo, já que Filomena escolheu
ir ao cinema, era melhor Juvenal também ter ido. Porém, olhando para a situação
em que ambos vão ao futebol, nenhum deles se arrepende da estratégia adotada,
dado o que outro fez. Essa é uma solução de Nash.
3.4 JOGO DE CONGESTIONAMENTO
Considere um jogo de controle de congestionamento em uma rede. Supo-
nha que dois usuários A e B podem transferir seus dados por dois pontos de cone-
xão, P e Q. O ponto P permite transferir os dados com uma velocidade um pouco
maior que o ponto Q. Assim, é natural que ambos prefiram fazer suas conexões pelo
ponto P, porém se ambos transferirem os dados por um mesmo ponto de conexão
haverá um congestionamento no ponto e o tempo de transmissão para cada um será
muito maior. Para enriquecer um pouco mais este exemplo, vamos supor que o joga-
dor A tem um pouco mais de urgência que o jogador B. Uma possível matriz de ga-
nho (satisfação do jogador) neste jogo poderia ser a representada pela Tabela 4.
BP Q
AP (2,2) (7,5)Q (4,6) (1,1)
Tabela 4: Jogo de congestionamento
Note que neste jogo também há dois resultados estáveis. Em um a soma
dos ganhos é igual a 12 e no outro a soma dos ganhos é igual a 10. Com isso, se
medirmos a satisfação média dos jogadores vemos que é preferível ter o resultado
onde o jogador A está na máquina P e o jogador B está na máquina Q.
3.5 CARA OU COROA
Neste jogo, conhecido em inglês por Matching Pennies, temos dois joga-
dores, cada um controla uma moeda e pode mostrar Cara ou Coroa. O jogador A ga-
nha se os dois mostram as moedas com as mesmas faces e o jogador B ganha se
as faces das duas moedas forem diferentes.
A matriz deste jogo é dada na Tabela 5 e o valor 1 representa ganho e -1
representa derrota. Quando todos os resultados de um jogo tiverem soma das utili -
dades iguais a uma constante, temos um jogo de soma constante.
BCara Coroa
ACara (1,-1) (-1,1)Coroa (-1,1) (1,-1)
Tabela 5: Cara ou coroa
Note que a soma das utilidades de cada resultado no jogo Cara ou Coroa
é igual a zero, e neste caso temos um jogo de soma zero. Da forma como estamos
considerando até agora, este jogo não tem um resultado estável. Para ver isso, note
que em qualquer resultado há um vencedor e um perdedor, porém o perdedor pode
mudar sua alternativa para um resultado onde vence.
3.6 JOGO DE CONGESTIONAMENTO 2
O exemplo do jogo de controle de congestionamento pode ser adaptado
para uma situação parecida com o jogo Cara ou Coroa, onde não há resultado está-
vel. Considere a situação onde os jogadores A e B podem fazer suas transmissões
de dados pelos pontos P e Q. Suponha agora que ambos os pontos tem a mesma
taxa de transmissão e o preço cobrado pela empresa que controla estes pontos de-
pende do tempo que levou para transmitir os dados. Se a empresa transmitir os da-
dos em pouco tempo, ela cobra um valor fixo e se ela demora em transmitir, ela não
cobra pelo serviço. Agora, suponha que o jogador A precisa fazer a transmissão ra-
pidamente e não pode transmitir a partir de um ponto congestionado, e conseqüen-
temente quer pagar por este serviço. Já o jogador B não tem dinheiro nem pressa e,
portanto só pode se conectar por um ponto congestionado. Se considerarmos que
um ponto fica congestionado quando há dois jogadores transmitindo por ele, então
este jogo não tem um resultado estável. Como podemos observar na Tabela 6.
BP Q
AP (1,-1) (-1,1)Q (-1,1) (1,-1)
Tabela 6: Jogo de congestionamento 2
3.7 TRAGÉDIA DOS COMUNS
Neste jogo, temos vários jogadores que obtêm mais vantagens atuando
de maneira racional, mas tal comportamento levará o jogo a um resultado com bene-
fício muito aquém daquele obtido se todos fizessem um acordo para uma melhor uti-
lização dos recursos. Exemplificaremos esta situação com um problema de compar-
tilhamento de largura de banda em um canal de transmissão.
3.7.1 COMPARTILHAMENTO DE LARGURA DE BANDA
Suponha que n jogadores querem transmitir dados por um cabo de trans-
missão que tem capacidade máxima 1 (largura de banda). O fluxo de dados usados
por um jogador é a quantidade de largura de banda usada por ele durante a trans-
missão.
Denotaremos por N o conjunto de jogadores e por x i ∈ [0,1] o fluxo do joga-
dor i ∈ N. A medida que o fluxo total se aproxima da capacidade do cabo, a qualida-
de da transmissão se deteriora e com isso diminui o benefício dos jogadores. Neste
modelo, se a banda total requisitada é ( ∑∈Njxj ) > 1 então o benefício para cada jo-
gador é nulo. Caso ( ∑∈Njxj ) ≤ 1 o benefício do jogador i é dado por xi(1 – ∑
∈Njxj ).
Esta função de benefício mostra que cada jogador deve fazer um balanço entre seu
fluxo e o fluxo total de transmissão.
Agora, considere um jogador i e sua escolha por um valor para o seu fluxo
considerando que os outros jogadores já definiram seus fluxos. Vamos supor que t =
{ }∑
∈ iNjxj
/< 1 é a quantidade de fluxo total usada pelos outros jogadores. Como o in-
teresse de i é maximizar seu benefício, ele escolhe seu fluxo como o valor x que ma-
ximiza x(1 – t – x). Resolvendo isso, ele obtém o valor x i = (1 – t)/2. Por outro lado,
como todos os jogadores são racionais e deseja maximizar seu benefício, todos fa-
rão estas mesmas contas e, portanto teremos um resultado estável. Estas equações
nos levam a um sistema com solução única dada por x i = 1/(n + 1), para todo jogador
i.
Portanto, o benefício de cada jogador i é xi(1- ∑∈Njxj ) = 1/(n + 1)2 o que dá um
benefício total de n/(n + 1)2 ≈ 1/n. Por outro lado, se cada jogador definir seu fluxo
como xi = 1/(2n) temos um fluxo viável onde cada jogador tem benefício de 1/(4n) re-
sultando em um benefício total de 1/4, que são valores muito melhores que os obti-
dos no resultado estável (aproximadamente n/4 vezes maior).
3.8 JOGOS REPETIDOS
Até agora, consideramos que cada jogador faz sua escolha sem o conhe-
cimento das escolhas dos outros jogadores. Outra forma de jogo é quando os joga-
dores se alternam na escolha de suas decisões. Para exemplificar esta situação,
considere o jogo de Compartilhamento de Largura de Banda, visto anteriormente.
Suponha que, por restrições no sistema, não é possível ou fica muito custoso para o
jogador saber a quantidade de fluxo que cada jogador está enviando, mas ele sabe
apenas o fluxo total que está sendo enviado pelo canal em cada momento. Além dis-
so, suponha que um jogador possa modificar a quantidade de fluxo a cada momento
para obter um melhor benefício individual. Por simplicidade, vamos supor que as
atualizações dos jogadores são realizadas em alguma ordem (i.e., dois jogadores
não atualizam seus fluxos ao mesmo tempo).
Sabendo o valor do fluxo atual, um jogador i pode facilmente calcular o
fluxo total dos outros jogadores, dado por t = { }∑
∈ iNjxj
/. Neste momento o jogador cal-
cula o valor do fluxo x que maximiza seu benefício, de x(1 – t – x), obtendo o valor xi
= (1 – t)/2. Naturalmente, a mudança feita pelo jogador i pode ser considerada pelos
próximos jogadores, que farão também mudanças nos seus fluxos para obter um
maior benefício. Se os jogadores forem ajustando seus fluxos um após o outro, de
maneira sequencial, o fluxo final convergirá na mesma solução vista anteriormente,
com benefício global próximo de 1/n e, portanto muito aquém daquela solução de
benefício total 1/4.
3.9 JOGOS SEQUENCIAIS
Podemos também considerar jogos que são repetidos entre os jogadores
várias vezes. Isto é, há várias partidas de um mesmo jogo entre os mesmos jogado-
res. Além disso, os jogadores podem manter um histórico das partidas anteriores
que poderiam ser usadas para a tomada de suas decisões. O custo obtido neste
jogo é o custo total obtido em todas as partidas. Considere por exemplo o jogo do
Dilema dos Prisioneiros. Note que se o número de partidas é fixo, é sempre preferí-
vel para um prisioneiro confessar na última partida, pois diminuirá o número de anos
na cadeia nesta partida. Isto também pode ser aplicado à penúltima partida, assim
por diante. Com isso, se o número de partidas for repetido um número finito de ve-
zes, temos um resultado estável também onde os prisioneiros apenas confessam.
Por outro lado, se o número de partidas for infinito ou não for conhecido, pode valer
a pena aos jogadores ficar em silêncio. Isto ocorre, pois o histórico de escolhas for-
ma uma reputação do jogador que poderá ser usada pelo outro prisioneiro para de-
cisões futuras. Com isso, pode valer a pena um prisioneiro ficar em silêncio, saben-
do que se trair confessando o crime ele poderá ser retaliado nas próximas partidas.
Uma regra de escolha interessante que um jogador pode tomar é escolher cooperar
na primeira partida e para as próximas partidas escolher exatamente a escolha do
outro prisioneiro na partida imediatamente anterior. Neste caso, se ambos os prisio-
neiros escolherem inicialmente ficar em silêncio, ambos continuarão em silêncio
para sempre. Se um prisioneiro escolher confessar e o outro não, o prisioneiro que
não confessou irá retaliar na próxima partida. Esta estratégia é conhecida como
Olho por Olho, ou em inglês Tit for Tat, e foi adaptada em protocolos de redes distri-
buídas par-a-par (peer-to-peer), exemplificado a seguir.
3.9.1 TRANSFERÊNCIAS EM SISTEMAS PEER-TO-PEER
Neste tipo de sistema, um usuário pode transferir arquivos da Internet
para seu computador, mas também tem incentivo a disponibilizá-los a partir de seu
computador, minimizando o tráfego no geral, já que outros usuários terão mais alter-
nativas de onde obter este arquivo. Naturalmente um usuário pode não querer dispo-
nibilizar o arquivo de seu computador, tornando-se assim, um aproveitador do siste-
ma. Para incentivar que os usuários também disponibilizem os arquivos, muitos pro-
tocolos mantém uma reputação dos usuários que melhora quando o usuário disponi-
biliza os arquivos do seu computador e piora quando ele não disponibiliza o arquivo.
Além disso, sempre que o número de usuários chegarem ao máximo o sistema dará
preferência a um novo usuário com melhor reputação e interromperá a transmissão
de um usuário com reputação pior. Com isso, usuários tentarão cooperar, para não
sofrerem retaliações no futuro.
3.10 APLICAÇÕES DA TEORIA DOS JOGOS
Nesta seção, apresentamos algumas aplicações da teoria dos jogos.
3.10.1 ECONOMIA
A Teoria dos Jogos foi desenvolvida por John Von Neumann com o objetivo de anali -
sar a forma como agentes econômicos ou sociais definem suas estratégias no mer-
cado, para avaliar as prováveis decisões que esses agentes tomarão. Essa teoria
constituiu significativo avanço nas ciências econômicas e sociais, pois permite se
examinar a conduta do jogador, agente econômico, em interação com os demais
agentes, e não só de forma isolada.
John Nash contribuiu aprofundando os estudos de equilíbrio entre os
agentes econômicos, aplicando a teoria, também, em ambientes não cooperativos.
Os economistas têm usado a teoria dos jogos, para analisar fenômenos econômicos,
utilizando um conjunto particular de estratégias conhecida como equilíbrio de jogo,
que é baseado na racionalidade.
É uma ferramenta que se posicionou no processo de concorrência da
economia de mercado, ajudando na tomada de decisões, indicando através de es-
tratégias, aquela que indica a maximização do benefício, levando em conta todas as
reações possíveis dos concorrentes. Escolhe-se a estratégia do maxmin, maximiza-
ção do ganho mínimo, oposta pela estratégia do minimax, minimização do ganho
máximo, pela qual se deverá posicionar o adversário. O resultado de cada combina-
ção de estratégias, por dois jogadores ou empresas é chamado ganho.
A aplicação dos jogos em economia, visa a eficácia da ação das decisões
consideradas individuais, ou em grupos de interesses, para a conquista de merca-
dos com ou sem a cooperação de outros participantes sobre o mercado.
A teoria dos jogos, tal como num jogo, dispõe os seus competidores, na
lógica de situações de monopólios, ou ao contrário, naquelas de situações de oligo-
pólios, de acordo com os mecanismos da teoria econômica tradicional.
Pense na corrida armamentista entre Estados Unidos e Rússia, na déca-
da de 1950, quando cada país poderia construir mísseis nucleares ou deixar de fa-
zê-lo. Os ganhos dessas estratégias poderiam ser semelhantes aos apresentados
na Tabela 7. O melhor resultado para os dois seria abster-se de construir mísseis,
dado um ganho de (4,4). Mas se um se abstém enquanto o outro constrói, o ganho
será de 3 para o que constrói e de 1 para o que se abstém. O ganho quando os dois
constroem mísseis é (2,2).
Não é difícil verificar que são dois equilíbrios de Nash com estratégia pura
(abstém, abstém) e (constrói, constrói). Contudo, o primeiro é melhor para as duas
partes. O problema está em que nenhum dos participantes sabe que escolha fará o
outro. Antes de comprometer-se com a abstenção, cada participante deseja assegu-
rar-se da abstenção do outro.
URSSAbstém Constrói
EUAAbstém (4,4) (1,3)Constrói (3,1) (2,2)
Tabela 7: Corrida armamentista
Uma forma de alcançar essa certeza é que um dos participantes o faça
primeiro, permitindo, digamos, uma inspeção. Observe que isso pode ser feito unila-
teralmente, pelo menos enquanto se acredita nos ganhos do jogo. Se um dos partici -
pantes anuncia que se abstém de construir mísseis nucleares e dá ao outro partici-
pante evidencias suficientes de sua escolha, pode ficar certo de que o outro partici-
pante também se absterá.
3.10.2 BIOLOGIA
Todos nós evoluímos, por um processo conhecido por seleção natural, conforme
teoria proposta por Charles Darwin e aceita como a melhor explicação cientifica.
Um gene não consegue construir uma perna sozinho, para isso é necessária à
cooperação de outros genes, além do meio externo, como: fonte de alimento. Ne-
nhum gene ou agentes do meio externo pode, isoladamente, ser responsável
pela formação de um bebê.
Em cada espécie é deixado um número de descendentes, onde alguns
sobrevivem mais do que outros, pois se adaptam melhor a um determinado ambi-
ente, sendo assim têm maior êxito reprodutivo, eliminando dessa forma os des-
vantajosos para essa mesma condição.
Os jogos na Biologia são interpretados como uma medida de adaptação,
porém menos voltado para o equilíbrio e sim para aquilo que pode ser mantido
pela forças evolucionárias. Este é o equilíbrio mais bem conhecido na biologia
como Estratégia Evolucionária Estável ou (EEE), que foi criada por John May-
nard Smith [2], embora não tenha feito nenhuma relação com equilíbrio de Nash,
cada Estratégia Evolucionária Estável esta em um equilíbrio de Nash.
O conceito de equilíbrio de Nash foi elaborado para lidar com indivíduos
racionais, calculistas, cada um dos quais está tratando de formular uma estraté-
gia adequada à melhor estratégia que possa ser adotada pelo outro jogador. A
EEE foi elaborada para modelar o comportamento animal sob forças evolucionis-
tas, onde estratégias com melhores resultados em termos de aptidão de sobrevi-
vência se reproduzirão mais rapidamente. Mas o equilíbrio EEE é também um
equilíbrio de Nash, fornecendo outro argumento para a atração exercida por este
conceito especifico da teoria dos jogos.
A idéia é que há vários tipos de comportamento geneticamente programa-
dos e que a evolução seleciona combinações de população estáveis em termos
de forças evolucionarias. Em anos recentes, os biólogos passaram a considerar
a teoria dos jogos como uma ferramenta indispensável para estudar o comporta-
mento animal.
O mais famoso dos jogos de interação animal é jogo dos pombos e fal-
cões. Não se trata de um jogo entre as duas espécies (que teria um resultado
bastante previsível), mas antes de um jogo que envolve uma única espécie que
exibe dois tipos de comportamento.
Imagine um cachorro selvagem. Quando dois cachorros selvagens encon-
tram um pedaço de comida, têm de decidir se brigam ou dividem o alimento. A
briga é a estratégia do falcão: um ganha e outro perde. Dividir é a estratégia do
pombo: funciona bem se o outro jogador também tiver um comportamento man-
so, mas se o outro jogador também for agressivo, a proposta de divisão será re-
jeitada e o jogador dócil ficará sem nada. Observe a Tabela 8.
Cachorro BFalcão Pombo
Cachorro AFalcão (-2,0) (4,0)Pombo (0,4) (2,2)
Tabela 8: Jogo dos pombos e falcões
Se ambos os cachorros selvagens jogarem pombo, acabarão com (2,2).
Se um deles jogar falcão e o outro, pombo, o jogador falcão ganha tudo. Mas se
ambos jogarem falcão, os dois cachorros serão gravemente feridos.
Obviamente não pode haver equilíbrio se todos jogarem falcão, pois se al-
gum cachorro jogasse pombo, acabaria com 0 em lugar de -2. E se todos os ca-
chorros jogassem pombo, compensaria se alguém se desviasse e jogasse pom-
bo. De modo que, no equilíbrio, é necessária alguma mistura de tipos de falcão e
de tipos pombo.
Um jogo cooperativo repetitivo na biologia é o mutualismo entre espécies,
onde dois seres de espécies distintas optam por uma colaboração mútua para
suprir suas necessidades. Por exemplo, o jogo entre o jacaré e o pássaro, no
qual o jacaré pode optar por comer o pássaro (não cooperar) ou deixar o pássaro
limpar seus dentes (cooperar), enquanto o pássaro pode optar por não se aproxi-
mar do jacaré (não cooperar) ou aproximar-se para comer os restos de alimento
que se encontra entre os dentes do jacaré (cooperar). Tal cenário pode ser ob-
servado pela Tabela 9.
Pássaro Coopera Não coopera
JacaréCoopera (10,10) (1,1)
Não coopera (5,0) (1,1)
Tabela 9: Jogo do mutualismo entre jacaré e pássaro
Neste jogo conforme pode ser observado a melhor estratégia é ambos os
indivíduos cooperarem (10,10). O que pôde ser observado pelas espécies duran-
te repetições deste conflito ao longo do tempo.
3.10.3 COMPUTAÇÃO
Muitos dos jogos clássicos descritos na seção 3 são aplicados a computa-
ção como o roteamento por provedores de serviços, jogos de congestionamento, tra-
gédia dos comuns, transferências em sistemas peer-to-peer.
A Teoria dos Jogos consiste no estudo de modelos para situações onde
agentes interagem em um sistema. Cada agente possui escolhas que alteram o es-
tado do sistema, e também possuem preferências sobre cada um dos possíveis es-
tados do sistema. Cada jogador gostaria de deixar o sistema na melhor situação in-
dividual. Mas o que isto tem a ver com Sistemas Computacionais? O surgimento da
internet trouxe consigo vários novos desafios e surgiram várias áreas com aborda-
gens práticas propondo soluções para esses desafios.
Nos últimos anos áreas teóricas da computação começaram uma tentati-
va de formalizar esses aspectos como teoria e estudar melhor esses novos proble-
mas. A internet é formada por várias entidades, onde cada entidade tem um objetivo
próprio, e essas entidades se relacionam com outras de várias maneiras, às ve-
zes seus relacionamentos são cooperativos, às vezes competitivos, ou também
se relacionam de maneira egoísta, e neste caso, não se preocupam com as con-
seqüências que suas ações podem acarretar para o sistema como um todo.
Esse cenário é ideal para ser modelado formalmente na Teoria dos Jogos.
Em computação, não se tem uma definição rígida do que seria um jogo,
porem existem algoritmos e heurísticas para solucionarem jogos. Estas, em geral, ou
utilizam métodos estatísticos para previsão de jogadas, ou utilizam o algoritmo mini-
max.
Jogos que utilizam métodos estatísticos para darem soluções usam uma
grande quantidade de dados de jogos anteriores e tentam prever qual seria a melhor
jogada a ser seguida de acordo com as jogadas utilizadas em jogos anteriores. Por
exemplo, o famoso supercomputador da IBM, Deep Blue, que jogava xadrez contra
o campeão do mundo em xadrez, Kasparov, utilizava esta técnica para decidir qual
seria sua jogada. Como se sabe, o Deep Blue conseguiu vencer o campeão.
Jogos que utilizam algoritmo minimax fazem uso de uma função valora-
ção de cada estado do jogo e um mecanismo de gerar novas jogadas a partir de um
estado. O jogo parte de um estado inicial e a partir daí geram-se as possíveis próxi -
mas jogadas em vários níveis e tenta-se maximizar o ganho da jogada a ser realiza-
do para o computador e minimizar o ganho da jogada do adversário.
4 OTIMIZAÇÃO COMBINATÓRIA
Nos últimos anos, notou-se que vários problemas de otimização combina-
tória podem ser olhados sob o ponto de vista de teoria dos jogos, e isso tem trazido
resultados interessantes para tais problemas, pois permite que técnicas e observa-
ções da área de teoria dos jogos sejam usadas ou sirvam de inspiração. Ao mesmo
tempo, o crescimento da internet trouxe consigo uma variedade de problemas no-
vos, muitos deles envolvendo aspectos de teoria dos jogos. Neste projeto mostrare-
mos problemas de otimização combinatória sob o enfoque de teoria dos jogos. Al-
guns desses estudados por Oliveira e Fernandes em 2010 [11].
Problemas pertences à área de teoria dos jogos envolvem o estudo de so-
luções que garantam certas propriedades. Para entender melhor essas propriedades
podemos analisar alguns problemas desta área. Um exemplo bem conhecido é o
problema dos casamentos estáveis, entre outros.
4.1 CASAMENTO ESTÁVEIS
Considere um grupo de homens e um grupo de mulheres que se conhe-
cem, todos solteiros. Podemos imaginar que cada homem tem uma ordem de prefe-
rência para as mulheres do grupo, desde a que mais gosta até a mulher que menos
gosta, sem empates. O mesmo vale para as mulheres, de maneira análoga. O pro-
blema em que estamos interessados é chamado de problema dos casamentos está-
veis.
Supondo que os dois grupos têm o mesmo tamanho, queremos escolher
uma esposa para cada homem, levando em conta as ordens de preferência, de
modo que os casamentos sejam estáveis.
Denotamos por H o conjunto dos homens e por M o das mulheres, e con-
sideramos então que |H|= |M| = n. Todo m ∈ M tem uma ordem de preferência nos
elementos de H: para a e b ∈ H, e m ∈ M, a ≻m b denota que a mulher m prefere a
mais do que prefere b. Assim temos uma ordem de preferência estrita:
h1≻m h2≻m h3≻m ... ≻m hi≻m ... ≻m hn,
onde o elemento m tem maior preferência por h1, e menor preferência por hn.
Um grupo de casamentos entre H e M é dito instável se temos dois ho-
mens h1 e h2 ∈ H e duas mulheres m1 e m2 ∈ M onde h1 está casado com m1 e h2
está casado com m2, mas h1 prefere m2 a m1, e m2 prefere h1 a h2. Nesse caso, dize-
mos o par (h1, m2) é um par bloqueador, e temos então um grupo de casamentos
instável. Um grupo de casamentos que não possui nenhum par bloqueador é está-
vel. O pseudo código abaixo, que deve-se à Gale e Shapley [13], encontra um grupo
de casamentos estável em tempo O(n2).
Começamos com um conjunto S de homens solteiros, um conjunto de
mulheres solteiras G, e uma lista L de casais, que descreve com qual homem uma
mulher está casada. Inicialmente S = H, G = M e L = 0 . (Estamos usando o conjunto
G apenas para facilitar.) Temos também uma marcação para identificar qual será a
próxima mulher que receberá a proposta de um homem h ∈ H, e chamaremos essa
marcação de F(h). Inicialmente cada homem h irá fazer a proposta à mulher mais
bem colocada na sua ordem de preferência, ou seja, F(h) é a primeira mulher na or -
dem de preferência de h.
Então pegamos o conjunto S’ = S, e para cada homem s ∈ S’ olhamos
para a próxima mulher p = F(s) a quem ele deve fazer uma proposta (que é a mulher
mais bem colocada na sua ordem de preferência que ainda não o rejeitou).
Caso 1: p está no grupo G de mulheres solteiras. Então removemos p de G, e tam-
bém removemos s de S, além de atualizar F(h) com a próxima mulher logo abaixo
de p na sua ordem de preferência, e atualizar a lista L marcando que s está casado
com p. (Observação: este casamento pode ser desmanchado ainda nesta iteração;
veja o Caso 2 para entender.)
Caso 2: p não está em G, ou seja, a mulher p já está casada com algum outro ho-
mem. Então ela deve decidir se irá se casar com s, ou manter seu casamento, e
para isso basta ela escolher utilizando sua ordem de preferência.
Caso 2.1: p opta por manter seu casamento (rejeitando s). Basta atualizar a próxima
mulher a quem s fará sua proposta.
Caso 2.2: p decide se casar com s (rejeitando seu antigo marido). Então precisamos
remover s de S, e inserir o antigo marido da mulher p em S. (Repare que, como ele
não era solteiro, não haverá duplicações no conjunto S.) Também atualizamos a lista
L e F(s). Começamos uma nova iteração, com os novos conjuntos S e G, a lista L, e
a função F.
O algoritmo termina quando o conjunto S fica vazio, o que significa que to-
dos os homens estão casados, chegando, como veremos, a um grupo estável de ca-
samentos. Abaixo será apresentado o algoritmo de Gale e Shapley [13] que encon-
tra um casamento estável.
Algoritmo PROPOSTA MASCULINA (H, M, ≺h, ≺m)1. S ←H, L(m) ← indefinido, para cada m ∈ M2. para todo h ∈ H faça3. F(h) é a primeira mulher em ≺h
4. enquanto S ≠ 0 faça5. seja h um homem em S6. se L(F(h)) está indefinido7. então L(F(h)) ← h, S ← S\ {h}8. senão9. se h≻F(h) L(F(h))10. então S ← S ∪ {L(F(h))},11. L(F(h)) ← h,12. S ← S \ {h}13. Atualize F(h) para a próxima mulher em ≺h
14. devolva L
Além disso, esse algoritmo garante outra propriedade importante da área
de teoria dos jogos. O algoritmo acima é à prova de estratégia, ou seja, nenhum ho-
mem pode se beneficiar ao declarar uma ordem de preferência sobre as mulheres
que não seja sua real ordem de preferência. As soluções propostas para os proble-
mas apresentados a seguir também garantem a prova de estratégia. Observamos
neste trabalho que não podemos encontrar um equilíbrio de Nash para o problema
de casamentos estáveis, pois este é um jogo cooperativo. E tal equilíbrio se dá em
jogos não-cooperativos.
4.2 ALOCAÇÃO DE BENS INDIVISÍVEIS
Foi estudado o problema da alocação de casas para entender o modelo
de alocação de bens indivisíveis. Nesse problema temos um conjunto N = {1,2, ...,n}
de negociantes e cada negociante possui inicialmente uma casa. As casas são
transferíveis e os negociantes podem trocar de casa usando como moeda a sua pró-
pria casa. Cada negociante possui também uma ordem de preferência estrita sobre
as n casas em questão, ou seja, uma lista ordenada das casas, desde a casa que
mais gosta até a casa que menos gosta, sem empates. Nosso objetivo é realocar as
casas entre os negociantes, de forma a satisfazer algumas condições, chegando a
uma alocação dita estável.
A casa j denota a casa inicial do negociante j. Para descrever uma aloca-
ção de casas usaremos um vetor x de tamanho n, onde xi é o número da casa atri-
buída ao negociante i. Assim temos a alocação inicial xi = i, para i de 1 a n.
Uma alocação de casas x deve satisfazer x i ≠ xj para todo i ≠ j, ou seja,
uma casa só pode pertencer a um negociante, e será então uma alocação viável. O
contrário também deve ser válido: todo negociante só pode possuir uma única casa.
Neste problema dada duas casas a e b dizemos que a ≻i b se e somente
se, o negociante i prefere a casa a mais do que prefere b.
Dada uma alocação x, um conjunto S é bloqueador se os negociantes não
concordam com esta alocação. Em outras palavras, S é um conjunto bloqueador se
é preferível para pelo menos um dos seus elementos ficar com sua casa inicial em
vez de receber a casa da alocação x, ou se S possui um par de negociantes que
preferem trocar as casas entre si a receber as casas da alocação x.
O exemplo abaixo ilustra o problema de alocação estável. Considere as
seguintes ordens de preferência:
1: 2≻1 1 ≻1 3.2: 3 ≻2 2 ≻2 1.3: 2 ≻3 1 ≻3 3.
A alocação (1,3,2) é estável. Já a alocação t=(3,2,1) não é estável pois o
negociante 1 prefere continuar com a casa 1 que receber a casa 3 dada pela aloca-
ção t, um outro conjunto bloqueador é o par de negociantes 2 e 3 que preferem tro-
car entre si suas casas iniciais, do que receber respectivamente as casas 2 e 1 dada
pela alocação t.
Uma alocação que não possui nenhum conjunto bloqueador é uma aloca-
ção estável. O conjunto de todas as alocações estáveis é chamado núcleo.
Teorema 4.2.1 O núcleo sempre consiste de uma única alocação e o algoritmo abai-
xo encontra uma alocação estável para os negociantes e casas.
Algoritmo TTCA (N)1. enquanto N ≠ 0 faça2. G ← (N,0)3. para todo u ∈ N faça4. seja v o negociante cuja casa é de maior preferência para u
dentre os negociantes em N5. E(G) ← E(G) ∪ {uv}6. para todo ciclo C em G faça7. para todo vértice v ∈ C faça8. seja u em N tal que a aresta vu ∈ E(C)9. A(v) ← u10. N ←N \ V(C)11. devolva A
Esse algoritmo recebe um conjunto N de negociantes, e suas ordens de
preferência sobre as casas. O algoritmo chama-se Trocas em Ciclos Superiores uma
tradução livre para Top Trading Cycle Algorithm, abreviado para TTCA.
Construa um digrafo dirigido G, onde cada negociante em N é um vértice.
Para cada negociante i em N, insira um arco do vértice i para o vértice j se a casa j
for a casa preferida do negociante i dentre as casas de N. Como temos tanto |N| vér-
tices como arcos e o grau de saída de cada vértice é exatamente um, temos pelo
menos um ciclo em G, que pode ser de tamanho 1. Mais do que isso, cada ciclo é
disjunto dos outros, ou seja, os vértices que pertencem a um ciclo não pertencem a
nenhum outro ciclo de G. Ademais, cada componente conexa possui exatamente um
ciclo.
Então, podemos definir qual casa deve ser atribuída a cada negociante
(vértice) pertencente a cada ciclo, fazendo o seguinte. Para cada circuito C em G, di -
gamos de tamanho r, que é da forma i1 → i2 → ... ir, ou seja, o negociante i1 tem
como casa preferida a casa do negociante i2, e etc., basta atribuir a casa i2 ao nego-
ciante i1, e genericamente, para x ≥ 2, atribuir a casa ix ao negociante ix-1. A casa i1
deve ser atribuída ao negociante ir. Após a atribuição de casas, basta removermos
os negociantes que estão em cada ciclo C do conjunto inicial N, e recomeçamos o
algoritmo se N ≠ 0.
No pseudocódigo acima, A(v) denota a casa atribuída ao negociante v pelo al-
goritmo.
Veja um exemplo de simulação do algoritmo para uma instância com 5
negociantes que possuem as seguintes ordens de preferência:
1: 3 ≻1 4 ≻1 5 ≻1 2 ≻1 1.2: 1 ≻2 5 ≻2 4 ≻2 3 ≻2 2.3: 2 ≻3 1 ≻3 5 ≻3 4 ≻3 3.4: 3 ≻4 2 ≻4 1 ≻4 4 ≻4 5.5: 1 ≻5 3 ≻5 2 ≻5 4 ≻5 5.
Figura 2: Primeira iteração.
Nessa primeira iteração, o algoritmo aloca a casa 3 ao negociante 1, a casa 1 ao ne-
gociante 2, e a casa 2 ao negociante 3. Removendo o ciclo 1,3,2 temos a seguinte
relação de preferência:
4: 4 ≻4 5.5: 4 ≻5 5.
Figura 3: Segunda iteração.
Após alocar a casa 4 ao negociante 4, temos o grafo da última iteração do algoritmo.
5:5
Figura 4: Terceira iteração.
O algoritmo aloca a casa 5 ao negociante 5, e encontra a alocação A = (3,1,2,4,5).
4.2.1 CORRETUDE E COMPLEXIDADE DO ALGORITMO
A corretude deste algoritmo pode ser facilmente verificada, pois como no
digrafo construído todo vértice tem grau de saída 1 (um), conseqüentemente este
não possui sumidouro e contém pelo menos um ciclo direcionado. Na primeira itera-
ção deste algoritmo os vértices que se encontram no ciclo recebem a sua casa pre-
ferida (representada pelo seu vizinho de saída) e depois os vértices são removidos
do digrafo, como podemos ver esses vértices não farão parte de um conjunto blo-
queador, pois estão com suas casas de maior preferência. Descartados esses nego-
ciantes, um novo digrafo é construído através da relação de preferência dos negoci-
antes restantes, e o processo é repetido. Como em cada iteração os vértices removi-
dos não podem fazer parte de um conjunto bloqueador ao termino deste algoritmo
temos uma alocação de bens indivisíveis sem conjunto bloqueador, ou seja, temos
uma alocação estável.
Não foi encontrado nenhum estudo sobre a complexidade deste algoritmo
na literatura pesquisada. Sendo assim apresentamos esta analise neste trabalho.
Para analise da complexidade deste algoritmo devemos observar que
como os ciclos do digrafo construído são disjuntos percorrer para cada ciclo todos os
seus vértices será não mais do que percorrer todos os vértices do digrafo, ou seja,
tempo O(n). Também observamos que o número de iterações deste algoritmo (repe-
tições do laço enquanto) é no máximo n, pois no pior caso para cada iteração é re-
movido apenas um vértice.
Fazendo uma observação deste algoritmo podemos notar que existe uma
relação entre o número de iterações do laço enquanto e o número de vértices remo-
vidos em cada iteração (quanto mais vértices forem removidos de uma iteração i,
menos iterações será necessário no pior caso). Deste raciocínio obtém se a seguinte
equação:
n1*1 + n2*2 + ... + nn-1*(n-1) + nn*n = n
onde ni representa o número de iterações em que i vértices foram removidos.
Neste ponto, poderíamos pensar que a complexidade do algoritmo TTCA
seria O(n). Porém, havia sido desconsiderada a complexidade da construção dos di-
grafos, e a complexidade para identificar os ciclos deste, o que não pode ser descar-
tada a priori. Portanto, a complexidade do algoritmo TTCA será O(n²), pois nestes di-
grafos o número de vértices será igual ao número de arestas, a enumeração dos ci-
clos pode ser obtida em tempo O(n+m), e a construção do digrafo pode ser feita em
tempo O(n).
4.2.2.1 O ALGORITMO TTCA MODIFICADO
Conforme tido anteriormente, o algoritmo TTCA possui complexidade
O(n²), pois necessita em cada iteração construir um digrafo e enumerar todos ciclos
deste. Nesta subseção apresentaremos uma modificação do algoritmo fazendo com
que os ciclos sejam identificados durante a construção do digrafo, reduzindo assim
o seu número de passos. É importante observar que a complexidade do algoritmo
ainda será o O(n²) pois a cada iteração ainda será necessário construir um digrafo.
Abaixo segue o algoritmo modificado, onde em vermelho se encontram nossas mo-
dificações:
Algoritmo TTCA Modificado (N)01. enquanto N ≠ 0 faça02. G ← (N,0)
03. S ← {w}, onde w é um elemento qualquer de N04. N ← N/{w}05. para todo u ∈ S faça06. seja v o negociante cuja casa é de maior preferência para u
dentre os negociantes em N
07. E(G) ← E(G) ∪ {uv}06. colorir o vértice u com a cor preto07. se v está colorido com a cor preto então08. marcar aresta uv como aresta de um ciclo09. S ← {w}, onde w é um elemento qualquer de N10. N ← N/{w}11. senão 12. S ← {v}13. N ← N/{v}14. para todo ciclo C em G faça15. para todo vértice v ∈ C faça16. seja u em N tal que a aresta vu ∈ E(C)17. A(v) ← u18. N ←N \ V(C)19. devolva A
A modificação feita neste algoritmo baseia-se em após adicionar uma
aresta de saída em um vértice u continuar inserindo arestas a partir de seu vizinho
de saída v (repare que conforme as arestas são inseridas, um percurso em profundi-
dade está sendo feito). Como o número de vértices é finito e todo vértice terá ape-
nas uma aresta de saída, em algum momento este percurso fechará um ciclo (detec-
tado pela coloração preta), sabendo que os ciclos são disjuntos, neste ponto pode-
mos selecionar outro vértice refazendo todo esse processo de inserção de aresta e
percurso. Ao final, quando todas as arestas tiverem sido criadas, todo ciclo terá uma
de suas arestas marcadas. Para trabalhos futuros esperamos construir um algoritmo
de complexidade O(n) para o problema.
Observamos neste trabalho que não podemos encontrar um equilíbrio de
Nash para o problema de alocação de bens indivisíveis, pois este é um jogo coope-
rativo (por exemplo, dois negociantes podem preferir trocar as casa entre si).
Conforme [12,13], o algoritmo TTCA é a prova de estratégia, ou seja,
caso o negociante apresente uma ordem de preferência que não seja a sua real pre-
ferência, este não conseguirá obter uma casa melhor do que receberia caso a or-
dem fosse sua real preferência.
5 A FORMA EXTENSIVA DE UM JOGO
Como vimos, normalmente as possíveis configurações de um jogo são re-
presentadas por uma matriz, esta geralmente é usada em situações onde os jogado-
res escolhem sua estratégia simultaneamente ou o fazem sem conhecer a estratégia
dos outros jogadores.
Existem outras situações (como por exemplo, nos mundo dos negócios ou
na política e em alguns jogos de cartas) em que os jogadores tomam suas decisões
de forma sequencial, depois de observar a ação que outro jogador realizou. A forma
extensiva tem uma estrutura mais adequada para analisar jogos desta natureza, es-
pecificando assim quem se move, quando, com qual informação e o payoff ou ganho
de cada jogador. Ela contém toda informação sobre um jogo [17].
Existem varias formas de se representar um jogo da forma extensiva, to-
das elas tentando formalizar a ideia de árvore. Entre elas: (1) relações de ordem
(algo mais familiar a um matemático), (2) teoria de grafos [15] e (3) alfabetos [16]
(mais familiar a um cientista da computação).
Denotamos por árvore de jogo (game tree) a forma extensiva de um jogo
não cooperativo finito, isto é, uma representação através de árvores que descreve
formalmente como um jogo não cooperativo pode ser jogado [18], em outras pala-
vras, ela especifica os possíveis movimentos de cada jogador em cada ponto do
jogo.
Todo jogo estratégico finito pode ser convertido em um jogo na forma ex-
tensiva [17]. Por exemplo, o jogo Pedra-Papel-Tesoura com dois jogadores, que é
um jogo onde os jogadores escolhem suas estratégias simultaneamente, tem a ma-
triz de payoffs apresentada na Tabela 10:
J2Pedra Papel Tesoura
J1Pedra (0,0) (-1,1) (1,-1)Papel (1,-1) (0,0) (-1,1)
Tesoura (-1,1) (1,-1) (0,0)
Tabela 10: Jogo Pedra-Papel-Tesoura
A forma extensiva (árvore de jogo) deste jogo é apresentada a seguir:
Figura 5: Árvore do jogo Pedra-Papel-Tesoura
Nesta representação, a raiz da árvore representa o jogador 1 J1, este pos-
sui três possíveis escolhas: pedra, papel ou tesoura. Os vértices do nível 2 por sua
vez representam o Jogador 2 J2, como este não sabe qual será a escolha de J1, para
cada possível escolha de J1, ele terá três possibilidades de escolhas: pedra, papel
ou tesoura.
5.1 ÁRVORES MIN/MAX
Considere um jogo J de soma zero com informação perfeita entre dois jo-
gadores e uma configuração inicial s. Como J é um jogo de soma zero, isto significa
que a soma dos ganhos destes jogadores é igual a zero, como J também é um jogo
de informação perfeita, após um movimento inicial, cada jogador efetua seu movi-
mento somente após o movimento de seu adversário. Denotamos por Max e Min os
dois jogadores de J, sendo Max o jogador inicial sabemos que enquanto Max deseja
maximizar o seu ganho, Min deseja minimizar o ganho de Max. Uma possível árvore
de jogos que representa a forma extensiva de J é a árvore Min/Max.
Árvores Min/Max são árvores enraizadas por um vértice s que representa
a configuração inicial do jogo, nestas árvores os níveis impares representam estados
do jogo em que o jogador Max deverá fazer um movimento, enquanto os níveis pa-
res representam estados do jogo em que o jogador Min deverá fazer um movimento,
as folhas da árvore, por sua vez, representam estados finais do jogo J e possuem
valores que representam o ganho Max (o ganho de Min pode ser obtido multiplican-
do o ganho de Max por -1). A Figura 6 ilustra uma subárvore Min/Max do jogo da
velha (não foi apresentado a árvore completa, pois esta possui 26.830 nós folha.)
Figura 6: Subárvore Min/Max do jogo da velha
Embora no exemplo apresentado os ganhos possíveis são (1,0,-1) exis-
tem árvores Min/Max onde o ganho possível é maior do que um, neste caso, geral-
mente o jogador Max deseja encontrar o ganho “menos pior” possível, ou seja, uma
solução minimax para o jogo. Esta solução pode ser interpretada como: se o jogador
Min fazer sempre o seu melhor movimento possível, qual é o melhor resultado que o
jogador Max pode obter, no caso do jogo da velha, este valor é 0, ou seja, o jogador
Max conseguirá sempre garantir no mínimo um empate, se o resultado fosse 1, isto
significaria que o jogador Max possui uma estratégia vencedora.
Dado uma árvore Min/Max, um algoritmo linear no seu número de
vértices, baseado em um percurso das folhas até a raiz (Bottom-Up) calcula o ganho
mínimo do jogador Max [18]. No entanto, nem sempre o número de vértices da
árvore é polinomial à entrada do jogo (por exemplo, o jogo da velha que possui
26.830 nós folha), quando isto ocorre alguns heurísticas devem ser aplicadas.
CONCLUSÃO
Neste trabalho mostramos que a teoria dos jogos e seus conceitos são uti-
lizados nas mais diversas áreas, relacionando-se a temas da biologia, computação,
economia, política e ciência militar. Isto mostra que o campo de utilização desta teo-
ria é muito grande, tanto que, a área acadêmica e de estudos, tem apresentado di-
versos trabalhos sobre este tema.
Situações de conflito, tomada de decisão e desenvolvimento de estratégi-
as reúnem-se nesse fascinante campo de estudo que não pára de surpreender a
cada nova aplicação. Nos jogos de estratégia em geral, prever como os competido-
res reagirão aos movimentos e antecipar-se às suas próximas ações constitui uma
enorme vantagem. É sob esta ótica que a teoria dos jogos adquire especial relevân-
cia, uma vez que seu instrumental analítico visa permitir a identificação dos movi-
mentos mais adequados a se realizar, de acordo com a movimentação do adversá-
rio.
Com o desenvolver desta pesquisa, analisou-se que a aplicabilidade da te-
oria dos jogos se fazem válidas em determinadas situações: quando é mais vantajo-
so entrar em uma competição (por exemplo, na corrida armamentista), ou quando se
corre o risco de perder ou ganhar (como no cara ou coroa), ou ainda, adotar a políti -
ca de colaboração entre as partes envolvidas (como o mutualismo na biologia), e
quando em determinado momento há uma troca altruísta entre as partes, para que
haja um ganho maior para ambas (como na alocação de bens indivisíveis).
Neste trabalho também foram apresentadas algumas estruturas de dados
utilizadas para representar os jogos.
REFERÊNCIAS BIBLIOGRÁFICAS
1. MERRILL, Flood; DRESHER, Melvin. The Mathematics of Games of Strategy: Theory and Applications, 1950. Dover Publications.
2. SMITH, John Maynard. Evolution and the Theory of Games, 1982. Cam-
bridge University Press.
3. ZERMELO, E. Über eine Anwendung der Mengdenlehre auf die theor-iesdes Schachspiels, 1913. Atas do Décimo Quinto Congresso Internacional
de Matemáticos, vol. 2, p. 501–504.
4. VON NEUMANN, J. Zur Theorie der Gesellschaftsspiele. Mathematische An-
nalen, v. 100, p. 295-320. Traduzido por S. Bargmann: On the Theory of Games of Stategy em Contributions to the Theory of Games, 1959. v. 4, p.
13-42, Editores: TUCKER, A. W.; LUCE, R. D. Princeton University Press.
5. VON NEUMANN, J; MORGENSTERN, O. Theory of Games and Economic Behavior, 1944. Princeton University Press.
6. NASH JR, J. F. Equilibrium Points in n-person Games, 1950. Proceedings
of the National Academy of Sciences of the United States of America, p. 48–
49, 1950.
7. NASH JR, J. F. Non-Cooperative Games, 1950. PhD. Thesis. Princeton Uni-
versity Press
8. NASH JR, J. F. The Bargaining Problem, 1950. Econometrica, p. 155–162.
9. NASH JR, J. F. Non-Cooperative Games,1951. Annals of Mathematics, p.
286–295.
10.NASH JR, J. F. Two-person Cooperative Games, 1953. Econometrica, p.
128–140.
11.OLIVEIRA, A. F; Fernandes, C. G. Teoria dos jogos algorítmica e Otimiza-ção combinatória, 2009. Trabalho de Conclusão de Curso – Departamento
de Ciência da Computação, Instituto de Matemática e Estatística Universida-
de de São Paulo.
12.AGGARWAL, G.; MUTHUKRISHNAN, S.; PÁL, D.; PÁL, M. General Auction Mechanism for Search Advertising, 2008. Proc. of the 18th International
Conference on World Wide Web (WWW’09).
LEHMANN, D.; O’CALLAGHAN, L.I.; SHOHAM, Y. Truth revelation in rapid,
approximately efficient combinatorial auctions, 1999. Proc. ACM Conference
on Electronic Commerce (ACM-EC), Denver, p. 96–102.
13.GALE, D.; SHAPLEY, L.S. College Admissions and the Stability of Mar-riage,1962. The American Mathematical Monthly 69 , n. 1, p. 9–15.
14.ETESSAMI, K. Algorithmic Game Theory and Aplications, 2004. Lecture
Notes, School of Informatics – The University of Edinburgh, Scotland, UK.
15.HART, S. Games in Extensive and Strategic Forms, 1992. Capítulo 2 em
Handbook of Game Theory, v. 1, Editores: AUMANN, R. J.; HART, S. Elsevier
Science Publishers.
16.SARTINI, B. A.; GARBUGIO, G.; BORTOLOSSI, H. J.; SANTOS, P. A.; BAR-
RETO, L. S. Uma Introdução à Teoria dos Jogos, 2004. II Bienal da SBM -
Universidade Federal da Bahia.
17.RIVEST, R. L.; Mit R. R. Game Tree Searching By Min/Max approximation,
1988. Artificial Intelligence, v. 34, p. 77–96.
