Jeu succinct (eBook)

Un voyage à travers l'évolution et le potentiel de la technologie blockchain Cardano

Fouad Sabry (Autor)

eBook Download: EPUB

2025 | 1. Auflage
320 Seiten
Un Milliard De Personnes Informées [French] (Verlag)
978-0-00-090801-8 (ISBN)

Infos

Dans le monde de la technologie blockchain, comprendre la théorie des jeux est crucial pour les professionnels, les étudiants et les passionnés. « Succinct Game », ouvrage de la série « Cardano Blockchain Platform », propose un voyage éclairant à la croisée de la complexité computationnelle et de la prise de décision stratégique. Ce livre est une ressource essentielle pour quiconque souhaite approfondir sa compréhension des plateformes blockchain et de leurs fondements théoriques des jeux.

Succinct Game-Une exploration fondamentale des jeux succincts et de leur pertinence pour les plateformes blockchain.

Marché Fisher-Explorez les marchés Fisher et leur modélisation des économies d'échange, contribuant ainsi à la compréhension des économies décentralisées.

PPAD (complexité)-Découvrez la complexité computationnelle des problèmes PPAD et leur lien avec les mécanismes de consensus blockchain.

Théorie des jeux graphiques-Découvrez comment la théorie des jeux graphiques s'applique aux systèmes en réseau comme les plateformes blockchain.

Jeu symétrique-Explorez les jeux symétriques et leur importance dans le développement de protocoles blockchain équitables.

PLS (complexité)-Étudier la complétude des PLS et ses implications pour l'évolutivité des réseaux blockchain.

Prix de l'anarchie-Examiner le concept de prix de l'anarchie et son influence sur l'efficacité et l'équité de la blockchain.

Jeu de congestion-Comprendre les jeux de congestion et leurs applications directes à l'optimisation des systèmes blockchain.

Prix de l'anarchie dans les jeux de congestion-Approfondir l'analyse du prix de l'anarchie, notamment dans les jeux de congestion, en lien avec l'évolutivité de la blockchain.

Jeu continu-Découvrir les jeux continus et leur lien avec les opérations continues et non discrètes de la blockchain.

Équilibre concurrentiel approximatif à partir de revenus égaux-Analyser l'influence des équilibres concurrentiels sur les résultats économiques de la blockchain.

Équilibre epsilon-Étudier les équilibres epsilon et leur rôle dans les réseaux décentralisés et l'optimisation de la blockchain.

Théorème de Folk (théorie des jeux)-Approfondissez le théorème de Folk et son importance pour comprendre la coopération durable dans les systèmes blockchain.

Calcul de l'équilibre de marché-Apprenez les méthodes de calcul à la base de l'équilibre de marché, essentielles à la finance décentralisée sur les plateformes blockchain.

Équilibre corrélé-Explorez les équilibres corrélés et leurs applications à la coordination des contrats intelligents.

Équilibre de Nash fort-Étudiez les équilibres de Nash forts et leur importance pour assurer la stabilité des réseaux décentralisés.

Algorithme de Lemke-Howson-Découvrez l'algorithme de Lemke-Howson et son application à la recherche d'équilibres dans les jeux blockchain.

Théorie algorithmique des jeux-Découvrez comment la théorie algorithmique des jeux optimise les interactions stratégiques au sein des réseaux blockchain.

Poker de Kuhn-Étudiez le poker de Kuhn et son lien avec les processus décisionnels de la blockchain.

Le prix de l'anarchie dans les enchères-Comprendre le prix de l'anarchie dans les enchères et son impact sur la distribution de jetons sur les plateformes blockchain.

L'équilibre de Nash-Acquérir une compréhension approfondie de l'équilibre de Nash et de son application à la prise de décision décentralisée de la blockchain.

Textauszug

Chapitre 1 :Jeu succinct

Un jeu qui peut être représenté dans une taille nettement inférieure à sa représentation sous forme standard est appelé un jeu succinct ou un jeu qui peut être décrit de manière très concise dans le domaine de la théorie des jeux algorithmique. Pour décrire une partie dans laquelle sont impliqués des joueurs de LaTeX0, chacun d'entre eux étant confronté à des stratégies LaTeX1, il est nécessaire de spécifier les valeurs d'utilité de LaTeX2. En effet, il n'y a aucune limitation imposée aux utilitaires du lecteur. Même les algorithmes les plus basiques sont capables de localiser un équilibre de Nash dans un polynôme temporel qui est exactement de la même longueur que l'entrée considérée. Dans un jeu représenté par une chaîne de longueur n, un jeu succinct est de type polynomial si le nombre de joueurs et le nombre de stratégies employées par chaque joueur sont tous deux contraints par un polynôme en n. Une définition formelle des jeux succincts, qui les décrit comme un problème de calcul, est fournie par Papadimitriou et Roughgarden (2008).

Les jeux qui sont considérés comme des jeux graphiques sont ceux dans lesquels l'utilité de chaque joueur dépend des actions d'un petit nombre d'autres joueurs. Si LaTeX3 est le plus grand nombre de joueurs par les actions desquels un seul joueur est influencé (c'est-à-dire qu'il s'agit de l'indegré du graphique du jeu), alors le nombre de valeurs d'utilité requises pour décrire le jeu est LaTeX4, ce qui représente une augmentation significative pour un petit LaTeX5 par rapport à la valeur précédente.

Il a été prouvé qu'un jeu graphique avec tous les degrés bornés par trois et avec deux stratégies pour chaque joueur est réductible à n'importe quel jeu de forme normale. Cela a été démontré par de multiples expériences. Les jeux graphiques, contrairement aux jeux de forme normale, ont un défi NP-complet lorsqu'il s'agit d'identifier un équilibre de Nash pur, en supposant qu'une telle chose existe un jour. Le défi de trouver un équilibre de Nash dans un jeu graphique qui peut ou non être mixte entre dans la catégorie PPAD-complet. Lorsqu'il s'agit d'un graphe avec une largeur d'arbre bornée, il est possible de trouver un équilibre corrélé optimal en temps polynomial. C'est également vrai lorsqu'il s'agit de trouver un équilibre corrélé d'un jeu graphique.

Un jeu est dit clairsemé si la majorité de ses utilités sont égales à zéro. Il est possible que les jeux graphiques soient un sous-ensemble de la catégorie connue sous le nom de jeux clairsemés.

Il est possible de définir un jeu clairsemé comme un jeu dans lequel chaque ligne et colonne des deux matrices de récompense (utilité) a au plus un nombre constant d'entrées qui ne sont pas nulles. Cette définition s'applique à un jeu qui implique deux joueurs. Il a été démontré que la découverte d'un équilibre de Nash dans un jeu aussi clairsemé est difficile pour le PPAD, et il a également été démontré qu'il n'existe aucune stratégie d'approximation en temps entièrement polynomial à moins que le PPAD ne contienne l'élément P.

Lorsqu'il s'agit de juger de l'utilité d'une combinaison de tactiques, la seule chose qui compte est le nombre de joueurs de LaTeX6 qui utilisent chacune des stratégies de LaTeX7. En effet, dans les jeux symétriques, tous les joueurs sont les mêmes. Par conséquent, afin de décrire un tel jeu, il est nécessaire de ne fournir que des valeurs d'utilité LaTeX8.

Il y a toujours un équilibre de Nash pur dans un jeu symétrique avec deux stratégies ; cependant, il est possible qu'un équilibre de Nash pur symétrique n'existe en aucune circonstance. Le problème de trouver un équilibre de Nash pur dans une partie symétrique (avec peut-être plus de deux joueurs) avec un nombre constant d'actions est dans AC0. Cependant, lorsque le nombre d'actions augmente avec le nombre de joueurs (même linéairement), le problème ne peut pas être résolu puisqu'il est NP-complet. L'existence d'un équilibre symétrique est une caractéristique de tout jeu symétrique. Étant donné un jeu symétrique avec n joueurs et k stratégies, il est possible de trouver un équilibre symétrique en temps polynomial si la valeur de k est égale au logarithme du logarithme de logLaTeX9. Le processus de localisation d'un équilibre corrélé dans les jeux symétriques peut être accompli dans un temps polynomial.

Dans les jeux anonymes, les joueurs ont des utilités différentes, mais ils ne font pas la différence entre les autres joueurs. Par exemple, le fait de devoir choisir entre « aller au cinéma » et « aller au bar » tout en ne pensant qu'à l'affluence de chaque lieu, plutôt qu'à qui ils vont y rencontrer, est un exemple de situation dans laquelle les gens jouent à des jeux anonymes. Il est nécessaire d'avoir des valeurs d'utilité LaTeX10 car, dans ce type de jeu, l'utilité d'un joueur dépend non seulement de sa propre stratégie, mais aussi du nombre de ses pairs qui choisissent cette approche.

Si le nombre d'actions augmente proportionnellement au nombre de joueurs, il est extrêmement difficile d'atteindre un équilibre de Nash pur dans un jeu qui se joue anonymement. Il est possible de trouver un équilibre corrélé optimal d'un jeu anonyme dans une contrainte de temps polynomiale. Il existe un PTAS bien connu qui peut être utilisé pour localiser un équilibre de Nash ε-approximatif lorsque le nombre de techniques à considérer est de deux.

Dans le cas où le profil de stratégie (B, R, l) a été sélectionné, l'utilité du joueur I serait de 9 + 8 = 17, l'utilité du joueur II serait de 1 + 2 = 3 et l'utilité du joueur III serait de 6 + 4 = 10.

Une matrice d'utilité est une matrice qui représente un composant de l'utilité du joueur i dans un jeu polymatriciel, également appelé jeu multimatriciel. Cette matrice est présente pour chaque paire de joueurs (i,j) dans le jeu. L'utilité ultime du Joueur i est égale à la somme de tous ces composants. Afin de représenter avec précision un tel jeu, le nombre de valeurs d'utilité requises est LaTeX11.

La présence d'au moins un équilibre de Nash mixte est garantie dans les problèmes polymatriciels. Trouver un équilibre de Nash dans un jeu polymatriciel est un problème qui est PPAD-complet sans solution facile. De plus, le problème de localisation d'un équilibre de Nash approximatif constant dans un jeu polymatriciel est PPAD-complet. C'est un problème qui ne peut pas être résolu autrement. Le processus de localisation d'un équilibre corrélé dans un jeu polymatriciel peut être accompli en un temps polynomial. Il est important de garder à l'esprit que même si les parties par paires jouées entre joueurs ont des équilibres de Nash purs, l'interaction globale n'admet pas nécessairement un équilibre de Nash pur (bien qu'un équilibre de Nash mixte doive exister). Le problème de déterminer s'il existe ou non un équilibre de Nash pur est un problème qui est hautement NP-complet.

Une généralisation des jeux à somme nulle à deux joueurs est la catégorie des jeux polymatriciels compétitifs, qui n'impliquent que des interactions entre les joueurs de nature à somme nulle. Le théorème Minimax, qui a été initialement développé par von Neumann du point de vue des jeux à deux joueurs, peut être généralisé aux jeux polymatriciels à somme nulle.

De la même manière que les jeux à somme nulle à deux joueurs ont des équilibres de Nash mixtes, les jeux polymatriciels à somme nulle ont des équilibres de Nash mixtes qui peuvent être calculés en temps polynomial, et ces équilibres correspondent à des équilibres corrélés. Cependant, lorsqu'il s'agit de jeux à somme nulle à deux joueurs, il y a plusieurs aspects qui ne se généralisent pas. Il est important de noter que les joueurs n'ont pas besoin d'avoir une valeur unique du jeu, et que les tactiques d'équilibre ne sont pas des stratégies max-min dans le sens où elles ne maximisent pas les gains les plus défavorables des joueurs lorsqu'ils utilisent une stratégie d'équilibre. La simulation de jeux polymatriciels compétitifs peut être réalisée à l'aide d'un package Python open source.

Une approche de fonction potentielle peut être utilisée pour résoudre des jeux potentiels, qui sont des jeux polymatriciels qui ont des jeux de coordination sur leurs bords. Ces jeux sont des jeux potentiels par définition.

Moi, le joueur, c'est celui qui a X ∧ (Y ∨ Z).

Joueur 2 : Joueur X ⊕ Y ⊕ Z

Joueur III : X est un sous-ensemble de Y

La table d'utilité qui suit est décrite par ceux-ci.

Une machine de Turing limitée dans le temps polynomial, qui accepte comme entrée les actions de tous les joueurs et produit l'utilité du joueur, est la manière dont un jeu concis peut être représenté de la manière la plus flexible. En effet, la machine de Turing prend en compte les activités de tous les joueurs. La représentation d'une telle machine de Turing, que l'on appelle jeux de circuits, est équivalente à un circuit booléen, et c'est cette représentation que nous allons examiner.

L'approximation de la valeur d'un jeu de circuit à somme nulle à deux joueurs jusqu'à un facteur multiplicatif est connue pour être dans PSPACE. Le calcul de la valeur d'un tel jeu est un problème...

Produkt-Details

• Erscheint lt. Verlag: 20.6.2025
• Übersetzer: Nicholas Souplet
• Sprache: französisch
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• ISBN-10: 0-00-090801-0 / 0000908010
• ISBN-13: 978-0-00-090801-8 / 9780000908018