L'équilibre dans un jeu d'arrêt

Considérez le jeu à 2 joueurs suivant:

• La nature choisit au hasard un programme
• Chaque joueur joue un nombre en [0, infini] inclus en réponse au mouvement de la nature
• Prenez le minimum de numéros de joueurs et exécutez le programme pour (jusqu'à) autant d'étapes (sauf si les deux joueurs ont choisi l'infini)
• Si le programme s'arrête, le joueur qui a joué le nombre minimum gagne 1 point. Si le programme ne s'arrête pas, ce joueur perd 1 point. Tout joueur qui a joué un nombre non minimum reçoit 0 point, et les deux joueurs reçoivent 0 s'ils jouent tous les deux à l'infini.

(Les cas d'angle peuvent être traités de la manière qui préserve le mieux l'esprit du problème - par exemple, la semi-continuité supérieure peut être utile.)

La question: ce jeu possède-t-il un équilibre de Nash calculable?

Sans l'exigence de calculabilité, chaque joueur joue simplement le nombre exact d'étapes dans lesquelles le programme s'arrête (ou l'infini, s'il ne s'arrête pas).

Si vous essayez l'argument de diagonalisation habituel pour le problème d'arrêt, vous constaterez qu'un équilibre existe dans les stratégies mixtes, donc l'approche évidente ne fonctionne pas immédiatement. Peut-être qu'il y a un moyen de le modifier?

D'un autre côté, l'équivalence des champs fermés réels signifie que les jeux finis avec des gains calculables ont des équilibres calculables . Ce jeu n'est pas fini, mais l'espace de stratégie est fermé et les gains calculables, alors peut-être que la même astuce pourrait être appliquée avec le théorème de Glicksberg ou quelque chose dans ce sens? Le problème est que, sans l'exigence de calculabilité, l'équilibre est dans des stratégies pures, donc toute tentative de prouver l'existence d'un équilibre calculable en utilisant l'existence d'un équilibre peut-être calculable doit expliquer pourquoi l'équilibre est rétrogradé de pur à mixte.

Cela semble être le genre de problème où les gens n'ont peut-être pas répondu à cette question auparavant, mais ont peut-être envisagé quelque chose de similaire. Je n'ai pas pu beaucoup me présenter, mais si quelqu'un connaît quelque chose en esprit, faites-le moi savoir!

Motivation: il existe une intuition commune selon laquelle l'auto-référence est le principal obstacle à la calculabilité - c'est-à-dire que tout problème non calculable intègre d'une manière ou d'une autre l'auto-référence. Si un jeu à peu près comme celui-ci a un équilibre de Nash calculable, cela fournirait la preuve de cette intuition.

MISE À JOUR: Pour clarifier, l'équilibre doit être "calculable" au sens de nombres réels calculables: les probabilités décrivant la distribution de stratégie mixte doivent être calculables avec une précision arbitraire. (Notez que seulement un nombre fini de probabilités seront supérieures à un seuil de précision particulier.) Cela signifie également que nous pouvons échantillonner à partir d'une approximation arbitrairement proche de la stratégie d'équilibre.

$1/2^i$$i$$t$$j$$t$$j$$j$$t$