Glossário de teoria dos jogos - Glossary of game theory

A teoria dos jogos é o ramo da matemática em que os jogos são estudados: isto é, modelos que descrevem o comportamento humano. Este é um glossário de alguns termos do assunto.

Definições de um jogo

Convenções de notação

Numeros reais

${\ displaystyle \ mathbb {R}}$ .

O conjunto de jogadores

${\ displaystyle \ mathrm {N}}$ .

Espaço de estratégia

${\ displaystyle \ Sigma \ = \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i}}$ , Onde

Espaço de estratégia do jogador i

${\ displaystyle \ Sigma \ ^ {i}}$ é o espaço de todas as maneiras possíveis em que jogador i pode jogar o jogo.

Uma estratégia para o jogador i

${\ displaystyle \ sigma \ _ {i}}$ é um elemento de . ${\ displaystyle \ Sigma \ ^ {i}}$

Complementos

${\ displaystyle \ sigma \ _ {- i}}$ um elemento de , é uma tupla de estratégias para todos os jogadores, exceto i . ${\ displaystyle \ Sigma \ ^ {- i} = \ prod _ {j \ in \ mathrm {N}, j \ neq i} \ Sigma \ ^ {j}}$

Espaço de saída

${\ displaystyle \ Gamma}$ é, na maioria dos livros didáticos, idêntico a -

Recompensas

${\ displaystyle \ mathbb {R} ^ {\ mathrm {N}}}$ , descrevendo quanto ganho (dinheiro, prazer, etc.) os jogadores recebem no final do jogo.

Jogo de forma normal

Um jogo na forma normal é uma função:

${\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Dada a tupla de estratégias escolhidas pelos jogadores, é dada uma alocação de pagamentos (dados como números reais).

Uma generalização adicional pode ser alcançada dividindo o jogo em uma composição de duas funções:

${\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ Gamma}$

a função de resultado do jogo (alguns autores chamam essa função de "a forma do jogo") e:

${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

a atribuição de payoffs (ou preferências ) aos jogadores, para cada resultado do jogo.

Jogo extenso de forma

Isso é dado por uma árvore , onde em cada vértice da árvore um jogador diferente tem a opção de escolher uma aresta . O conjunto de resultados de um jogo de formulário extenso é geralmente o conjunto de folhas de árvore.

Jogo cooperativo

Um jogo no qual os jogadores podem formar coalizões (e aplicar a disciplina de coalizão). Um jogo cooperativo é dado estabelecendo um valor para cada coalizão:

${\ displaystyle \ nu \: 2 ^ {\ mathbb {P} (N)} \ to \ mathbb {R}}$

Sempre se presume que a coalizão vazia ganha zero. Os conceitos de solução para jogos cooperativos geralmente assumem que os jogadores estão formando a grande coalizão , cujo valor é então dividido entre os jogadores para dar uma alocação. ${\ displaystyle N}$${\ displaystyle \ nu (N)}$

Jogo simples

Um jogo simples é uma forma simplificada de um jogo cooperativo, onde o ganho possível é considerado '0' ou '1'. Um jogo simples é o par ( N , W ), onde W é a lista de coalizões "vencedoras" , capazes de ganhar o loot ('1'), e N é o conjunto de jogadores.

Glossário

Jogo aceitável

é uma forma de jogo tal que para todos os perfis de preferência possíveis , o jogo tem equilíbrios nash puros , todos os quais são pareto eficientes .

Alocação de mercadorias

é uma função . A alocação é uma abordagem fundamental para determinar o bem (por exemplo, dinheiro) que os jogadores recebem de acordo com os diferentes resultados do jogo. ${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Melhor resposta

a melhor resposta a um dado complemento é uma estratégia que maximize o pagamento do jogador i . Formalmente, nós queremos: . ${\ displaystyle \ sigma \ _ {- i}}$${\ displaystyle \ tau \ _ {i}}$
${\ displaystyle \ forall \ sigma \ _ {i} \ in \ \ Sigma \ ^ {i} \ quad \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) \ leq \ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$

aliança

é qualquer subconjunto do conjunto de jogadores: . ${\ displaystyle \ mathrm {S} \ subseteq \ mathrm {N}}$

Vencedor Condorcet

Dada uma preferência ν no espaço de resultado , um resultado a é um vencedor do condorcet se todos os jogadores não falsos preferirem a a todos os outros resultados.

Decidibilidade

Em relação à teoria dos jogos, refere-se à questão da existência de um algoritmo que pode e irá retornar uma resposta se um jogo pode ser resolvido ou não.

Determinação

Um subcampo da teoria dos conjuntos que examina as condições sob as quais um ou outro jogador de um jogo tem uma estratégia vencedora e as consequências da existência de tais estratégias. Os jogos estudados na teoria dos conjuntos são os jogos de Gale-Stewart - jogos para dois jogadores com informações perfeitas em que os jogadores fazem uma sequência infinita de movimentos e não há empates.

Jogo determinado (ou jogo estritamente determinado )

Na teoria dos jogos, um jogo estritamente determinado é um jogo de soma zero para dois jogadores que tem pelo menos um equilíbrio de Nash com ambos os jogadores usando estratégias puras .

Ditador

Um jogador é um ditador forte se pode garantir qualquer resultado independentemente dos outros jogadores. é um ditador fraco se puder garantir qualquer resultado, mas suas estratégias para fazer isso podem depender do vetor de estratégia do complemento. Naturalmente, todo ditador forte é um ditador fraco. Formalmente: m é um ditador forte se: m é um ditador fraco se: ${\ displaystyle m \ in \ mathbb {N}}$

${\ displaystyle \ forall a \ in \ mathrm {A}, \; \ exists \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ forall \ sigma \ _ {- n} \ em \ Sigma \ ^ {- n}: \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}$

${\ displaystyle \ forall a \ in \ mathrm {A}, \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n} \; \ exists \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}$

Outra maneira de colocar isso é:

um ditador fraco é eficaz para todos os resultados possíveis. ${\ displaystyle \ alpha}$

Um ditador forte é eficaz para todos os resultados possíveis. ${\ displaystyle \ beta}$

Um jogo não pode ter mais do que um ditador forte . Alguns jogos têm vários ditadores fracos (em pedra-papel-tesoura, ambos os jogadores são ditadores fracos, mas nenhum é um ditador forte ).

Veja também Eficácia . Antônimo: manequim .

Resultado dominado

Dada uma preferência ν no espaço de resultado , dizemos que um resultado a é dominado pelo resultado b (portanto, b é a estratégia dominante ) se for preferido por todos os jogadores. Se, além disso, algum jogador preferir estritamente b em vez de a , então dizemos que a é estritamente dominado . Formalmente: para dominação e para dominação estrita. Um resultado a é (estritamente) dominado se for (estritamente) dominado por algum outro resultado . Um resultado um é dominado por uma coalizão S se todos os jogadores em S preferem algum outro resultado para um . Veja também o vencedor Condorcet .
${\ displaystyle \ forall j \ in \ mathrm {N} \; \ quad \ nu \ _ {j} (a) \ leq \ \ nu \ _ {j} (b)}$
${\ displaystyle \ exists i \ in \ mathrm {N} \; st \; \ nu \ _ {i} (a) <\ nu \ _ {i} (b)}$

Estratégia dominada

dizemos que a estratégia é (fortemente) dominada pela estratégia se, para qualquer tupla de estratégias de complemento , o jogador i se beneficia jogando . Falando formalmente: e . Uma estratégia σ é (estritamente) dominada se for (estritamente) dominada por alguma outra estratégia . ${\ displaystyle \ tau \ _ {i}}$${\ displaystyle \ sigma \ _ {- i}}$${\ displaystyle \ tau \ _ {i}}$
${\ displaystyle \ forall \ sigma \ _ {- i} \ in \ \ Sigma \ ^ {- i} \ quad \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) \ leq \ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$
${\ displaystyle \ exists \ sigma \ _ {- i} \ in \ \ Sigma \ ^ {- i} \ quad st \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) <\ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$

Fictício

Um jogador i é um manequim se não tiver efeito no resultado do jogo. Ou seja, se o resultado do jogo for insensível à estratégia do jogador i .

Antônimos: digamos , veto , ditador .

Eficácia

Uma coalizão (ou um único jogador) S é eficaz para a se puder forçar a a ser o resultado do jogo. S é α-eficaz se os membros de S têm estratégias st não importa o que o complemento de S faça, o resultado será a .

S é β-eficaz se para quaisquer estratégias do complemento de S , os membros de S podem responder com estratégias que garantam o resultado a .

Jogo finito

é um jogo com um número finito de jogadores, cada um com um conjunto finito de estratégias .

Grande coalizão

refere-se à coalizão que contém todos os jogadores. Em jogos cooperativos, muitas vezes assume-se que a grande coalizão se forma e o objetivo do jogo é encontrar imputações estáveis.

Estratégia mista

para o jogador i é uma distribuição de probabilidade P on . Entende-se que o jogador i escolhe uma estratégia aleatoriamente de acordo com a P . ${\ displaystyle \ Sigma \ ^ {i}}$

Equilíbrio de Nash misto

Igual ao Pure Nash Equilibrium , definido no espaço de estratégias mistas . Cada jogo finito tem Mixed Nash Equilibria .

Eficiência de Pareto

Um resultado a da forma de jogo π é (fortemente) pareto eficiente se não for dominado em todos os perfis de preferência .

Perfil de preferência

é uma função . Esta é a abordagem ordinal para descrever o resultado do jogo. A preferência descreve o quão 'satisfeitos' os jogadores estão com os resultados possíveis do jogo. Veja alocação de mercadorias . ${\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Equilíbrio de Nash Puro

Um elemento do espaço de estratégia de um jogo é um ponto de equilíbrio de Nash puro se nenhum jogador i pode se beneficiar por se desviar da sua estratégia , uma vez que os outros jogadores estão jogando na . Formalmente: . Nenhum ponto de equilíbrio é dominado. ${\ displaystyle \ sigma \ = (\ sigma \ _ {i}) _ {i \ in \ mathrm {N}}}$${\ displaystyle \ sigma \ _ {i}}$${\ displaystyle \ sigma}$
${\ displaystyle \ forall i \ in \ mathrm {N} \ quad \ forall \ tau \ _ {i} \ in \ \ Sigma \ ^ {i} \ quad \ pi \ (\ tau \, \ sigma \ _ {- i}) \ leq \ pi \ (\ sigma \)}$

Dizer

Um jogador i tem um Say se não for um Dummy , ou seja, se houver alguma tupla de estratégias de complemento st π (σ_i) não é uma função constante.

Antônimo: Dummy .

Número Shannon

Um limite inferior conservador da complexidade da árvore de jogo do xadrez (10 ¹²⁰ ).

Jogo resolvido

Um jogo cujo resultado (vitória, derrota ou empate) pode ser previsto corretamente assumindo um jogo perfeito de todos os jogadores.

Valor

O valor de um jogo é um resultado racionalmente esperado . Existem mais do que algumas definições de valor , descrevendo diferentes métodos de obtenção de uma solução para o jogo.

Veto

Um veto denota a habilidade (ou direito) de algum jogador de impedir que uma alternativa específica seja o resultado do jogo. Um jogador que possui essa habilidade é chamado de jogador com direito a veto .

Antônimo: Dummy .

Jogo pouco aceitável

é um jogo que tem puro equilíbrio nash, alguns dos quais são pareto-eficientes .

Jogo de soma zero

é um jogo em que a alocação é constante ao longo de diferentes resultados . Formalmente: wlg, podemos assumir que essa constante é zero. Em um jogo de soma zero, o ganho de um jogador é a perda de outro jogador. A maioria dos jogos de tabuleiro clássicos (por exemplo , xadrez , damas ) têm soma zero .
${\ displaystyle \ forall \ gamma \ \ in \ Gamma \ \ sum _ {i \ in \ mathrm {N}} \ nu \ _ {i} (\ gamma \) = const.}$

Referências