Teoria dos jogos
Um jogo representa uma situação ou conflito entre dois ou mais oponentes. Estes oponentes são usualmente chamados de jogadores (um jogador pode ser um time composto de mais de uma pessoa). Cada jogador tem um certo número de escolhas, finito ou infinito, chamadas de estratégias.
Um jogador supostamente escolhe sua estratégia sem qualquer conhecimento prévio da estratégia escolhida pelos outros jogadores. A partir das escolhas dos jogadores, o jogo fornece o resultado/saída definindo cada jogador ganhou ou perdeu. Cada jogador faz sua escolha de modo a otimizar o resultado.
Chamamos o que se ganho de recompensa.A Teoria dos Jogos é um conjunto de procedimentos lógicos e matemáticos projetados para auxiliar na determinação de estratégias ótimas a serem seguidas em situações competitivas de tomada de decisão.
Classificação
A classificação é realizada por diversas formas.
● Pelo resultado do Jogo:
● Jogos de soma zero: São jogos de dois competidores, nos quais o ganho de um é exatamente a perda do outro, sendo que cada qual segue sempre a mesma estratégia;
● Jogos de soma não-zero: A soma dos resultados não precisa ser zero ou outro qualquer valor fixo. Classificados em relação ao grau de cooperatividade.
Como:
● Não-cooperativos: Não há comunicação prévia entre os jogadores;
● Cooperativos: Há comunicação prévia e acordos são permitidos.
Jogos de duas pessoas de soma zero
Dois jogadores de soma zero é o tipo de jogo mais estudado pela teoria dos jogos. De modo simplificado, neste tipo jogo cada um dos dois jogadores escolhe uma de suas estrategias possíveis. Uma vez que ambos os jogadores tenham tomado suas decisões, elas são anunciadas e uma tabela de pagamento é utilizada para determinar o pagamento de um jogador ao outro, ou seja, o ganho de um é exatamente a perda do outro. É possível usar estratégias puras ou mistas. Para jogos de duas pessoas de soma zero usando estrategias puras, onde se busca o equilíbrio.
Cada um dos oponentes escolherão sempre a mesma combinação de estratégias. O resultado é dado pelo ponto de sela. O ponto de sela é o cruzamento das estratégias puras dos dois jogadores, assim, o número que aparece no ponto de sela, ou ponto de cruzamento é o valor do jogo.Jogos de estratégias mistas não há ponto de sela como nas estratégias puras, e nem uma única solução de equilíbrio, são resolvidos por meios de gráficos ou por programação linear. Para a busca de equilíbrio ambos os jogadores alternem suas alternativas de decisão escolhida de forma a chegar ao equilíbrio. A solução gráfica é adequada para jogos nos quais no minimo um jogadores tenha exatamente duas estrategias puras. O método de programação linear pode ser usado para resolver qualquer tipo de jogo de soma zero com duas pessoas.
Dominância
Uma estratégia A é dominada por outra estratégia B, quando em qualquer circunstância o jogador escolhe B, porque sempre traz melhores recompensas que A. Na análise do jogo, estratégias dominadas podem ser eliminadas previamente de consideração, economizando tempo.
Posts relacionados:
- Alguns algoritmos da Regional da Maratona da ACM 2007
- Algoritmo: Boliche
- Algoritmo Quadrado Mágico em Assembler
- O desafio de chamar a atenção do consumidor
- Um contrato diferente
Tags: programacao linear