Jeux arbitrés avec pièces semi-privées non corrélées

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é trois questions connexes qui seraient également dignes de la prime. Personne n'a posté de réponse avant l'expiration de la prime. Plus tard, j'ai été en mesure de répondre à deux des questions connexes (questions 3 et 4, abordées ci-dessous dans mon message d'origine), montrant que la valeur approximative des jeux avec arbitrage avec des pièces semi-privées corrélées (définies ci-dessous) était EXPTIME-complète. La question d'origine est toujours sans réponse. Je serais également intéressé par tout résultat mettant des jeux liés entre PSPACE et EXPTIME dans des classes de complexité intéressantes.

POSTE ORIGINAL:

Cette question a été inspirée par la discussion sur la question hexagonale d'Itai . Un jeu arbitré est un jeu où deux joueurs sans limite de calcul jouent en communiquant via un vérificateur polynomial qui peut lancer des pièces privées (ainsi le nombre de tours et la quantité de communication sont également limités en temps polynomial). À la fin de la partie, l'arbitre exécute un algorithme en P pour déterminer qui gagne. Déterminer qui remporte un tel jeu (même approximativement) est EXPTIME complet. Si vous avez des pièces publiques et une communication publique, ces jeux sont dans PSPACE. ( Voir Feige et Killian, «Making Games Short». ) Ma question concerne la frontière entre ces deux résultats.

• Question: Supposons que vous ayez deux joueurs sans limite de calcul qui jouent à un jeu de longueur polynomiale. Le rôle de l'arbitre se limite, avant chaque coup, à donner à chaque joueur un certain nombre de lancers de pièces privés (non corrélés avec ceux de l'autre joueur). Tous les mouvements du joueur sont publics, et donc vus par son adversaire - la seule information privée est le lancer de pièces. À la fin du jeu, tous les lancers de pièces privés sont révélés, et l'arbitre polytemps utilise ces lancements de pièces et les mouvements du joueur pour décider qui va gagner.

  Par le résultat des jeux arbitrés, la probabilité que le premier joueur gagne soit en EXPTIME, et c'est clairement PSPACE difficile. Lequel (le cas échéant) est-ce? Connaît-on ce problème?

Notez que les joueurs peuvent avoir à utiliser des stratégies mixtes, car vous pouvez jouer à des jeux de matrice à somme nulle (à la von Neumann) de cette façon.

MATÉRIAU AJOUTÉ:

Appelons cette classe de complexité RGUSP (toutes les langues qui peuvent être réduites à un jeu arbitré avec des pièces semi-privées non corrélées comme décrit ci-dessus, de sorte que si , le joueur 1 gagne avec probabilité , et si , le joueur 1 gagne avec probabilité ). Mes trois questions connexes sont:x ∈ L ≥ 2 / 3 x ∉ L ≤ 1 /$L$$x \in L$$\geq 2/3$$x \notin L$$\leq 1/3$

• Question 2: RGUSP semble assez robuste. Par exemple, si nous changeons le jeu pour que l'arbitre n'envoie pas de messages, mais observe uniquement les messages publics des joueurs 1 et 2, et en reçoive des messages privés, alors la valeur approximative de ce jeu est toujours équivalente à RGUSP. Je voudrais démontrer que RGUSP est robuste, donc je suis prêt à donner la prime à toute personne qui trouve une classe de complexité naturelle C afin que PSPACE C RGUSP, où aucun des confinements ne semble être exact.$\subseteq$$\subseteq$

• Question 3: Je soupçonne également fortement que la classe RGCSP (jeux arbitrés avec pièces semi-privées corrélées) est EXPTIME complète, et je suis également prêt à donner la prime à quelqu'un qui prouve ce fait. Dans RGCSP, à la première étape, l'arbitre donne aux deux joueurs des variables aléatoires corrélées (par exemple, il peut donner au premier joueur un point dans un grand plan projectif, et au deuxième joueur une ligne contenant ce point). Après cela, pour un nombre polynomial de tours, les deux joueurs alternent en s'envoyant des messages publics de taille poly. Une fois le match joué, l'arbitre poly-temps décide qui a gagné. Quelle est la complexité de l'approximation de la probabilité de gagner pour le joueur 1?

• Question 4: Enfin, j'ai une question qui peut vraiment concerner la cryptographie et la distribution des probabilités: donner la possibilité d'effectuer un transfert inconscient à deux joueurs dans un jeu arbitré avec des pièces semi-privées non corrélées leur permet-il de jouer un jeu arbitré arbitré avec des pièces corrélées (ou alternativement, leur permet-il de jouer à un jeu déterminant le vainqueur dont EXPTIME est complet)?

Je ne peux pas répondre à ma question d'origine, mais je peux répondre à la question 3 (et 4), que j'ai ajoutée lorsque j'ai offert une prime parce que je pensais que la question d'origine était probablement trop difficile. En fait, j'ai deux preuves de la question 3.

Voici le réglage de la question 3: Nous avons un arbitre polynomial qui, au début du jeu, donne aux joueurs 1 et 2 variables aléatoires corrélées. Les joueurs 1 et 2 jouent alors le jeu, sans aucune interférence de l'arbitre. À la fin de la partie, l'arbitre examine la transcription et décide qui gagne. Je peux montrer que décider qui gagne un tel jeu est EXPTIME complet, même si on vous promet que le vainqueur gagne avec une probabilité d'au moins .$2/3$

======== Preuve 1 ============

La première preuve utilise le fait que le transfert inconscient est universel pour un calcul sécurisé à deux parties. Ainsi, si les joueurs 1 et 2 peuvent effectuer un transfert inconscient, ils peuvent simuler un arbitre arbitraire en temps polynomial, de sorte que les résultats précédents selon lesquels les parties arbitrées sont terminées EXPTIME peuvent être appliqués.

Maintenant, pour réaliser 1-2 transferts inconscients, au début du jeu, l'arbitre donne aux deux joueurs un grand nombre de "boîtes de transfert inconscientes". Nous décrivons l'une de ces boîtes de transfert inconscientes. P1 obtient deux nombres aléatoires, et . P2 obtient l'un de ces nombres aléatoires, et la variable ( ou ) indiquant quel nombre aléatoire de P1 il a obtenu. Pour effectuer un transfert inconscient, P1 prend les deux données qu'il veut transférer, et XOR les avec etr 2 r i i = 1 2 r 1 r $r_1$$r_2$$r_i$$i$$=1$$2$$r_1$$r_2$. P2 peut alors décoder l'un d'entre eux, mais P1 ne peut pas dire lequel P2 peut décoder. Il s'agit d'un ou deux transferts inconscients. (Évidemment, l'arbitre doit également donner aux joueurs des boîtes de transfert inconscientes dirigées dans l'autre sens, de P2 à P1.)

Lorsque j'ai posé la question 4 pour la première fois, je craignais que les résultats du calcul sécurisé à deux ne s'appliquent pas à ce type de calcul interactif avec un arbitre, mais en fait, il est assez facile de montrer qu'ils le font.

=========== Preuve 2 ===========

Maintenant, pour la deuxième preuve de la question 3. Ici, nous devons revenir en arrière et modifier la preuve de Feige-Kilian. Dans cette preuve, ils considèrent une machine de Turing T qui exécute un calcul de temps exponentiel. Feige et Kilian codent les bits de la bande au temps dans un polynôme multilinéaire x_1 x_n sur un grand champ fini GF ( ). Maintenant, l'arbitre donne un point à P1 et une ligne contenant ce point à P2, et les deux joueurs rendent l'évaluation du point et de la ligne sur à l'arbitre. L'arbitre utilise la recherche binaire pour trouver un instant où les évaluations P1 et P2 de t Q t ( , … , ) p Q t t Q t Q t + $2^n$$t$$Q_t($$, \ldots,$$)$$p$$Q_t$$t$$Q_t$d'accord, mais leurs évaluations de ne sont pas d'accord, après quoi il pose à P1 une question intelligente qui révélera si c'est elle qui ment.$Q_{t+1}$

La première chose que nous utiliserons est que, même avec des pièces aléatoires non corrélées, l'arbitre peut obliger les joueurs 1 et 2 à effectuer un engagement de bits, en leur faisant XOR les données qu'ils veulent engager avec les pièces aléatoires. Ainsi, nous pouvons parler de P1 et P2 mettre les choses dans des enveloppes scellées.

Une chose que vous pourriez essayer de simuler la preuve Feige-Kilian est la suivante: l'arbitre donne à P1 beaucoup de points différents et P2 beaucoup de lignes , de sorte que est sur . Maintenant, à chaque étape de la recherche binaire, les joueurs mettent les valeurs et dans des enveloppes scellées, puis l'arbitre en choisit une au hasard pour que les joueurs l'ouvrent. Les deux joueurs décident si les valeurs sont cohérentes et procèdent à la recherche binaire en conséquence. Maintenant, nous avons ruiné la paire , parce que les deux joueurs connaissent la valeur du point et de la ligne, mais nous avons encore beaucoup d'autres paires (point, ligne) que nous pouvons utiliser.ℓ i p i ℓ i Q t ( p i ) Q t ( ℓ i ) ( p i , ℓ i$p_i$$\ell_i$$p_i$$\ell_i$$Q_{t}(p_i)$$Q_t(\ell_i)$$(p_i, \ell_i)$

(Comment l'arbitre peut-il en choisir un au hasard s'il ne donne des instructions aux joueurs qu'au début de la partie? Il peut encoder ses instructions dans le XOR des valeurs qu'il donne aux deux joueurs au début, et le deux joueurs ne peuvent pas lire l'instruction jusqu'à ce qu'ils révèlent tous les deux les valeurs au moment approprié.)$(p_i, \ell_i)$

Cette stratégie ne fonctionne pas tout à fait, car P1 et P2 n'ont pas à être cohérents quant au moment où ils commencent à mentir avec deux points (ou lignes). Autrement dit, P1 pourrait laisser donner la bonne valeur pour et la mauvaise valeur pour . Cela gâcherait complètement la recherche binaire et rendrait le protocole non concluant. Cependant, il existe une astuce intéressante que nous pouvons utiliser pour forcer P1 à être cohérent. Ajoutez un tas de points fictifs à l'ensemble de points de P1 et ajoutez des lignes fictivesQ t ( p j ) p ′ k ℓ ′ $Q_t(p_i)$$Q_t(p_j)$${p}'_k$${\ell}'_k$à l'ensemble de lignes de P2. Laissez chaque ligne factice avoir deux points dessus. S'il se trouve que P1 donne la bonne valeur pour un point fictif sur une ligne et la mauvaise valeur pour l'autre point fictif, alors il s'est révélé comme un menteur, puisqu'il n'y a aucun moyen pour P2 de donner la valeur pour une ligne qui est corriger pour l'un des deux points de P1 sur elle et pas l'autre. Nous pouvons faire une astuce similaire pour que la réponse P2 soit cohérente. Ensuite, la seule chose qui reste est de montrer que la dernière étape de la preuve Feige-Kilian fonctionne toujours. Cela s'avère simple, bien que passer par les détails rendrait cette réponse beaucoup plus longue.