Jogo Sucinto (eBook)

Uma jornada pela evolução e potencial da tecnologia blockchain da Cardano

Fouad Sabry (Autor)

eBook Download: EPUB

2025 | 1. Auflage
320 Seiten
Um Bilhão Bem Informado [Portuguese] (Verlag)
978-0-00-092990-7 (ISBN)

Infos

No mundo da tecnologia blockchain, compreender a teoria dos jogos é crucial para profissionais, estudantes e entusiastas. 'Succinct Game', parte da série 'Cardano Blockchain Platform', oferece uma jornada perspicaz pela interseção da complexidade computacional e da tomada de decisões estratégicas. Este livro é um recurso essencial para quem busca aprofundar sua compreensão das plataformas blockchain e seus fundamentos da teoria dos jogos.

Resumo dos Capítulos:

1: Succinct Game: Uma exploração fundamental dos jogos sucintos e sua relevância para as plataformas blockchain.

2: Fisher Market: Mergulhe nos Fisher Markets e como eles modelam economias de troca, auxiliando na compreensão de economias descentralizadas.

3: PPAD (complexidade): Descubra a complexidade computacional dos problemas de PPAD e sua conexão com os mecanismos de consenso da blockchain.

4: Teoria dos jogos gráficos: Aprenda como a teoria dos jogos gráficos se aplica a sistemas em rede, como plataformas blockchain.

5: Jogo simétrico: Explore jogos simétricos e sua importância no desenvolvimento de protocolos blockchain justos.

6: PLS (complexidade): Estude a completude do PLS e suas implicações para a escalabilidade de redes blockchain.

7: Preço da anarquia: Examine o conceito de preço da anarquia e sua influência na eficiência e justiça do blockchain.

8: Jogo de congestionamento: Entenda os jogos de congestionamento e suas aplicações diretas na otimização de sistemas blockchain.

9: Preço da anarquia em jogos de congestionamento: Mergulhe profundamente no preço da anarquia, especificamente em jogos de congestionamento, relevantes para a escalabilidade do blockchain.

10: Jogo contínuo: Descubra os jogos contínuos e como eles se relacionam com operações contínuas e não discretas do blockchain.

11: Equilíbrio Competitivo Aproximado a partir de Rendas Iguais: Analise como os equilíbrios competitivos influenciam os resultados econômicos do blockchain.

12: Equilíbrio Epsilonequílico: Estude os equilíbrios epsilonequílicos e seu papel em redes descentralizadas e na otimização do blockchain.

13: Teorema de Folk (teoria dos jogos): Mergulhe no teorema de Folk e sua importância para a compreensão da cooperação sustentada em sistemas baseados em blockchain.

14: Cálculo do equilíbrio de mercado: Aprenda os métodos computacionais por trás do equilíbrio de mercado, essenciais para finanças descentralizadas em plataformas blockchain.

15: Equilíbrio correlacionado: Explore equilíbrios correlacionados e suas aplicações na coordenação de contratos inteligentes.

16: Equilíbrio de Nash forte: Estude equilíbrios de Nash fortes e sua importância para garantir a estabilidade em redes descentralizadas.

17: Algoritmo de Lemke-Howson: Aprenda sobre o algoritmo de Lemke-Howson e sua aplicação na busca de equilíbrios em jogos blockchain.

18: Teoria dos jogos algorítmicos: Descubra como a teoria dos jogos algorítmicos otimiza as interações estratégicas em redes blockchain.

19: Pôquer de Kuhn: Investigue o pôquer de Kuhn e sua conexão com os processos de tomada de decisão em blockchain.

20: Preço da anarquia em leilões: Entenda o preço da anarquia em leilões e sua relevância para a distribuição de tokens em plataformas blockchain.

21: Equilíbrio de Nash: Obtenha uma compreensão abrangente do equilíbrio de Nash e sua aplicação à tomada de decisões descentralizada em blockchain.

Este livro é leitura obrigatória para qualquer pessoa interessada na mecânica estratégica de blockchain, oferecendo insights aprofundados sobre teoria dos jogos, complexidade e modelos econômicos que definem os sistemas descentralizados modernos. Seja você um profissional, estudante ou entusiasta, este livro fornece uma estrutura crucial para a compreensão da interseção entre a tecnologia blockchain e a teoria dos jogos.

Textauszug

Capítulo 1 :Jogo sucinto

Um jogo que pode ser representado em um tamanho que é significativamente menor do que sua representação de forma padrão é referido como um jogo sucinto ou um jogo que pode ser descrito de uma maneira muito concisa no campo da teoria algorítmica dos jogos. Para descrever um jogo em que os jogadores LaTeX0, cada um dos quais é confrontado com estratégias LaTeX1, estão envolvidos, é necessário especificar os valores de utilidade LaTeX2. Isso ocorre porque não há limitações colocadas nos utilitários do jogador. Mesmo os algoritmos mais básicos são capazes de localizar um equilíbrio de Nash em um polinômio de tempo que é exatamente o mesmo comprimento que a entrada que está sendo considerada. Em um jogo que é representado por uma sequência de comprimento n, um jogo sucinto é do tipo polinomial se o número de jogadores e o número de estratégias empregadas por cada jogador são ambos limitados por um polinômio em n. Uma definição formal de jogos sucintos, que os descreve como um problema computacional, é fornecida por Papadimitriou e Roughgarden (2008).

Jogos que são considerados jogos gráficos são aqueles em que a utilidade de cada jogador depende das ações de um pequeno número de outros jogadores. Se LaTeX3 é o maior número de jogadores por cujas ações qualquer jogador é influenciado (isto é, é o grau de ingrau do gráfico do jogo), então o número de valores de utilidade necessários para descrever o jogo é LaTeX4, o que é um aumento significativo para um pequeno LaTeX5 em comparação com o valor anterior.

Um jogo gráfico com todos os graus limitados por três e com duas estratégias para cada jogador provou ser redutível a qualquer jogo de forma normal. Isto foi demonstrado através de múltiplas experiências. Os jogos gráficos, em contraste com os jogos de forma normal, têm um desafio NP-completo quando se trata de identificar um equilíbrio de Nash puro, assumindo que tal coisa sempre existe. O desafio de localizar um equilíbrio de Nash em um jogo gráfico que pode ou não ser misturado se enquadra na categoria de PPAD-completo. Quando se trata de um grafo com uma largura de árvore limitada, é possível encontrar um equilíbrio correlacionado ideal em tempo polinomial. Isso também é verdade quando se trata de encontrar um equilíbrio correlacionado de um jogo gráfico.

Diz-se que um jogo é esparso se a maioria dos seus utilitários for igual a zero. É possível que os jogos gráficos sejam um subconjunto da categoria conhecida como jogos esparsos.

É possível definir um jogo esparso como um jogo em que cada linha e coluna das duas matrizes de recompensa (utilidade) tem no máximo um número constante de entradas que não são zero. Esta definição aplica-se a um jogo que envolve dois jogadores. A descoberta de um equilíbrio de Nash em um jogo tão esparso tem sido demonstrada como sendo PPAD-difícil, e também foi demonstrado que não existe uma estratégia de aproximação em tempo polinomial que exista a menos que a PPAD contenha o elemento P.

Quando se trata de julgar a utilidade de uma combinação de táticas, a única coisa que importa é o número de jogadores LaTeX6 que usam cada uma das estratégias LaTeX7. Isso porque, em jogos simétricos, todos os jogadores são iguais. Portanto, para descrever tal jogo, é necessário fornecer apenas valores de utilidade LaTeX8.

Há sempre um equilíbrio de Nash puro num jogo simétrico com duas estratégias; no entanto, existe a possibilidade de que um equilíbrio de Nash puro simétrico não exista em nenhuma circunstância. O problema de encontrar um equilíbrio de Nash puro em um jogo simétrico (com talvez mais de dois jogadores) com um número constante de ações está em AC0. No entanto, quando o número de ações cresce com o número de jogadores (mesmo linearmente), o problema não pode ser resolvido, uma vez que é NP-completo. A existência de um equilíbrio simétrico é uma característica de qualquer jogo simétrico. Dado um jogo simétrico com n jogadores e estratégias k, é possível encontrar um equilíbrio simétrico em tempo polinomial se o valor de k for igual ao logaritmo do logaritmo de logLaTeX9. O processo de localização de um equilíbrio correlacionado em jogos simétricos pode ser realizado em um tempo que é polinomial.

Em jogos anónimos, os jogadores têm utilidades diferentes, mas não diferenciam entre outros jogadores. Por exemplo, ter que escolher entre "ir ao cinema" e "ir ao bar" pensando apenas em quão lotado cada local estará, em vez de quem eles encontrarão lá, é um exemplo de uma situação em que as pessoas jogam jogos anônimos. Há um requisito para os valores de utilidade LaTeX10, uma vez que, neste tipo de jogo, a utilidade de um jogador depende não apenas de sua própria estratégia, mas também do número de seus colegas que escolhem essa abordagem.

Se o número de ações aumenta proporcionalmente ao número de jogadores, então é extremamente difícil alcançar um equilíbrio de Nash puro em um jogo que é jogado anonimamente. É possível encontrar um equilíbrio correlacionado ideal de um jogo anônimo em uma restrição de tempo que é polinomial. Existe um PTAS bem conhecido que pode ser utilizado para localizar um equilíbrio de Nash ε aproximado quando o número de técnicas a serem consideradas é dois.

No caso de o perfil de estratégia (B,R,l) ser selecionado, a utilidade do jogador I seria 9+8=17, a utilidade do jogador II seria 1+2=3 e a utilidade do jogador III seria 6+4=10.

Uma matriz de utilidade é uma matriz que representa um componente da utilidade do jogador i em um jogo polymatrix, que também é referido como um jogo multimatrix. Esta matriz está presente para cada par de jogadores (i,j) no jogo. A utilidade final do Player i é igual à soma de todos esses componentes. A fim de retratar com precisão tal jogo, o número de valores de utilidade que são necessários é LaTeX11.

A presença de pelo menos um equilíbrio de Nash misto é garantida em problemas de polimatriz. Encontrar um equilíbrio de Nash em um jogo de polimatriz é um problema que é PPAD-completo sem solução fácil. Além disso, o problema de localizar um equilíbrio de Nash aproximado constante em um jogo de polimatriz é PPAD-completo. Este é um problema que não pode ser resolvido de outra forma. O processo de localização de um equilíbrio correlacionado em um jogo de polimatriz pode ser realizado em um tempo que é polinomial. É importante ter em mente que, mesmo que os jogos em pares jogados entre jogadores tenham equilíbrio de Nash puro, a interação global não admite necessariamente um equilíbrio de Nash puro (embora um equilíbrio de Nash misto deva existir). O problema de determinar se existe ou não um equilíbrio de Nash puro é altamente NP-completo.

Uma generalização de jogos de soma zero para dois jogadores é a categoria de jogos competitivos de polimatriz, que envolvem apenas interações entre jogadores que são de natureza de soma zero. O teorema Minimax, que foi inicialmente desenvolvido por von Neumann a partir da perspetiva de jogos para dois jogadores, pode ser generalizado para jogos de polimatriz de soma zero.

Da mesma forma que os jogos de soma zero para dois jogadores misturaram equilíbrios de Nash, os jogos de soma zero de polimatriz misturaram equilíbrios de Nash que podem ser calculados em tempo polinomial, e esses equilíbrios correspondem a equilíbrios correlacionados. Quando se trata de jogos de soma zero para dois jogadores, no entanto, há vários aspetos que não generalizam. É importante notar que os jogadores não precisam ter um valor único do jogo, e táticas de equilíbrio não são estratégias max-min no sentido de que não maximizam os piores retornos dos jogadores enquanto eles estão utilizando uma estratégia de equilíbrio. A simulação de jogos competitivos polymatrix pode ser realizada com a ajuda de um pacote Python de código aberto.

Uma abordagem de função potencial pode ser usada para resolver jogos potenciais, que são jogos de polimatriz que têm jogos de coordenação em suas bordas. Estes jogos são jogos potenciais por definição.

Eu, o jogador, é quem tem X ∧ (Y ∨ Z).

Jogador 2: Jogador X ⊕ Y ⊕ Z

Jogador III: X é um subconjunto de Y

A tabela de utilitários a seguir é descrita por estes.

Uma máquina de Turing limitada em tempo polinomial, que aceita como entrada as ações de todos os jogadores e produz a utilidade do jogador, é a maneira pela qual um jogo conciso pode ser representado da maneira mais flexível. Isso ocorre porque a máquina de Turing leva em conta as atividades de todos os jogadores. A representação de tal máquina de Turing, que é referida como jogos de circuito, é equivalente a um circuito booleano, e é essa representação que vamos analisar.

Aproximar o valor de um jogo de circuito de soma zero para dois jogadores até um fator multiplicativo é conhecido por estar no PSPACE. Calcular o valor de tal jogo é um problema EXP-completo, o que significa que é impossível encontrar uma solução exata. Há um problema LaTeX12-completo que envolve determinar se existe ou não um equilíbrio de Nash puro (para obter mais informações, consulte Hierarquia polinomial).

Há um grande número de tipos adicionais de jogos concisos, muitos dos quais estão...

Produkt-Details

• Erscheint lt. Verlag: 24.6.2025
• Übersetzer: Felipe Azevedo
• Sprache: portugiesisch
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• ISBN-10: 0-00-092990-5 / 0000929905
• ISBN-13: 978-0-00-092990-7 / 9780000929907