Question théorique liée à l'informatique et à la théorie des jeux
Il y a une justification philosophique souvent citée pour croire que P! = NP même sans preuve. D'autres classes de complexité ont la preuve qu'elles sont distinctes, car sinon, il y aurait des conséquences "surprenantes" (comme l'effondrement de la hiérarchie polynomiale). Ma question est, quelle...
Décider si une formule booléenne quantifiée telle que ∀ x1∃ x2∀ x3⋯ ∃ xnφ ( x1, x2, … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), évalue toujours à true est un problème classique PSPACE-complete. Cela peut être considéré...
J'étais (et je suis toujours) vraiment intéressé par la réponse à cette question, car il s'agit d'une variation intéressante sur la complexité des jeux qui n'a pas été résolue, alors j'ai offert une prime. Je pensais que la question d'origine était très probablement trop difficile, alors j'ai posté...
Ces derniers mois, j'ai commencé à m'exprimer sur le choix social, le théorème de la flèche et les résultats associés. Après avoir lu les résultats séminaux, je me suis demandé ce qui se passe avec les préférences d'ordre partiel, la réponse est dans l'article de Pini et al. : Agrégation de...
Il s'agit d'une reformulation d'une question antérieure . Considérez le jeu d' information parfait et impartial suivant entre deux joueurs, Alice et Bob. Les joueurs reçoivent une permutation des nombres entiers 1 à n. A chaque tour, si la permutation actuelle augmente, le joueur actuel perd et...
Cette récente question sur la théorie des jeux m'a fait réfléchir (c'est une tangente, bien sûr): est-il possible d'optimiser efficacement une stratégie personnelle pour choisir des questions de recherche sur lesquelles travailler en utilisant la théorie des jeux? Afin d'avancer vers une...
Mafia est un jeu de rôle populaire lors des fêtes, une description détaillée est disponible sur wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Fondamentalement, cela fonctionne comme suit: Au début, chacun des joueurs se voit secrètement assigner un rôle, soit aligné avec la mafia soit...
Je cherche des exemples de techniques pour prouver le prix des bornes de l'anarchie qui ont le pouvoir de séparer le prix de l'anarchie sur les équilibres corrélés grossiers (l'ensemble limitatif de la dynamique sans regret externe) du prix de l'anarchie sur les équilibres corrélés (la limite...
J'utilise le terme de titre dans un sens très vague. Il y a une quantité importante de travail sur la théorie des jeux évolutifs, y compris ses fondements mathématiques. On m'a recommandé "Jeux évolutionnaires et dynamique des populations", mais je n'y suis pas encore allé. Il y a également une...
L' échange de cadeaux d'éléphants blancs est un jeu populaire lors des fêtes de Noël en Amérique du Nord . En bref (en ignorant les variations), cela fonctionne comme suit: Il y a personnes et n cadeaux emballés. Les joueurs sont ordonnés arbitrairement. Au i ème tour, le joueur i...
Quels types de conjectures et de grands problèmes ouverts sont les plus importants dans la théorie des jeux algorithmiques (ou la théorie des jeux en général en ce qui concerne CS)? Par exemple, la résolution de NASH comme PPAD-complete aurait, je pense, été la plus importante jusqu'à ce qu'elle...
En tant qu'étudiant en informatique, j'ai été initié à la théorie des jeux, mais je n'ai pas vu beaucoup de détails sur le sujet. J'ai cherché sur Google et j'ai regardé quelques livres sur la théorie des jeux et ils ont confirmé leur utilisation en informatique. J'ai commencé une étude formelle de...
Je me demande s'il existe une version limitée du calcul du concept d'équilibre de Nash, quelque chose dans le sens suivant. Imaginez une sorte de jeu d'information parfait à deux joueurs qui se joue sur un plateau , et qui est complexe dans le sens où un jeu optimal est dur-EXPTIME. Supposons...
J'ai rencontré le jeu suivant. Je migrerai cela comme demandé. Un bug est en train de visiter les cercles, et un adversaire souhaite maximiser son temps de voyage. L'adversaire place un cercle à chaque tour. Le bug part de sa position actuelle directement vers le centre du cercle le plus récent,...
Considérons le jeu suivant sur un graphique pondéré dirigé avec une puce à un nœud.GGG Tous les nœuds de sont marqués par A ou B.GGG Il y a deux joueurs Alice et Bob. Le but d'Alice (Bob) est de déplacer la puce vers un nœud marqué par A (B). Initialement, Alice et Bob ont respectivement et...
Étant donné un jeu déterministe à somme partielle et à informations partielles avec seulement un nombre fini d'états, dont les résultats possibles sont [perdre, dessiner, gagner] avec des valeurs [-1,0, + 1] respectivement, quelle est la complexité de l'approximation de la valeur de tels un jeu...
Il y a une très belle construction par Conway de nombres surréalistes. Ce sont des "nombres" qui contiennent à la fois des nombres réels et des ordinaux, sont totalement ordonnés et ont toutes les propriétés d'un champ (sauf qu'ils ne forment pas un ensemble mais une classe). Voir par exemple ce...
Pour un problème de recherche locale polynomiale , on sait qu'au moins une solution (optimum local) doit exister. Cependant, de nombreuses autres solutions pourraient exister, est-il difficile de compter le nombre de solutions pour un problème PLS complet? Je suis particulièrement intéressé par le...
Je commence mes études de théorie des jeux algorithmiques, et il semble que le concept d'équilibre généralement utilisé est celui d'un point fixe dans un graphe. Cependant, les gens ont-ils envisagé d'autres concepts d'équilibre, tels que les cycles limites? Je peux imaginer qu'un cycle limite...
Comme @Marzio l'a mentionné, le jeu suivant est connu sous le nom de Géographie généralisée . Étant donné un graphique et un sommet de départ , le jeu est défini comme suit:G = ( V, E)g=(V,E)G=(V,E)v ∈ Vv∈Vv \in V A chaque tour (alternance de deux joueurs), un joueur choisit u ∈ N( v )u∈N(v)u\in...