<p>Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than one or you could use it to solve the halting problem. But you can achieve any value less than one by the strategy that for some fixed sufficiently large $t$, simulates nature's program $j$ for $t$ steps and outputs the number of steps it takes program $j$ to halt if $j$ halts in $t$ steps, infinity otherwise. </p>

CC BY-SA 3.0
2017-10-17T17:48:21.520Z
I like this construction - it establishes that any Nash equilibrium must play correctly for all programs.

There's an additional step needed to establish that it solves the halting problem, since the distributions only need to converge to perfect performance in the limit of high precision (and thus infinite computation). Since we know the output must put unit weight on one integer, I think it suffices to compute the strategy probabilities to within 1/4 and then take whichever integer has weight greater than 1/2.
John Wentworth
CC BY-SA 3.0
2017-10-17T16:20:36.067Z
2017-10-17T16:20:36.067Z
Lance Fortnow
<p>Consider the following 2-player game:</p>

<ul>
<li>Nature randomly picks a program</li>
<li>Each player plays a number in [0, infinity] inclusive in response to nature's move</li>
<li>Take the minimum of the players’ numbers, and run the program for (up to) that many steps (unless both players chose infinity)</li>
<li>If the program halts, the player who played the minimum number gains 1 point. If the program does not halt, that player loses 1 point. Any player who played a non-minimum number receives 0 points, and both players receive 0 if they both play infinity.</li>
</ul>

<p>(Corner cases may be handled in whatever way best preserves the spirit of the problem - e.g. upper semicontinuity may be helpful.)</p>

<p>The question: <strong>does this game possess a computable Nash equilibrium?</strong></p>

<p>Without the computability requirement, each player just plays the exact number of steps in which the program halts (or infinity, if it does not halt). </p>

<p>If you try the usual diagonalization argument for the halting problem, you'll find that an equilibrium exists in mixed strategies, so the obvious approach does not immediately work. Maybe there's some way to tweak it?</p>

<p>On the other hand, the equivalence of real closed fields means that <a href="https://theoryclass.wordpress.com/2011/01/04/computability-of-nash-equilibrium/" rel="noreferrer">finite games with computable payoffs have computable equilibria</a>. This game is not finite, but the strategy space is closed and the payoffs computable, so maybe the same trick could be applied with Glicksberg's Theorem or something in that vein? The problem is, without the computability requirement, the equilibrium is in pure strategies, so any attempt to prove existence of a computable equilibrium using existence of a maybe-computable equilibrium has to explain why the equilibrium is downgraded from pure to mixed.</p>

<p>This seems like the sort of problem where people may not have addressed this exact question before, but might have looked at something similar. I haven't been able to turn up much, but if anyone knows of something in spirit, please let me know!</p>

<p>Motivation: there's a common intuition that self-reference is the main block to computability - i.e., that any uncomputable problem somehow embeds self-reference. If a game roughly like this has a computable Nash equilibrium, it would provide evidence for that intuition.</p>

<p>UPDATE: To clarify, the equilibrium should be "computable" in the sense of computable real numbers: the probabilities describing the mixed strategy distribution should be computable to arbitrary precision. (Note that only finitely many probabilities will be above any particular precision cutoff.) This also means that we can sample from an arbitrarily close approximation of the equilibrium strategy.</p>

CC BY-SA 3.0
2017-10-17T06:27:33.403Z
Are we allowed to know the opponent's distribution?
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-17T07:32:40.467Z
Ricky: the plays could be regarded as computable reals, but truncating to an integer should dominate any non-integer finite play, since a program will only run for an integer number of steps (or infinity). I'm not sure I understand your parenthesized example though, so I may be misunderstanding your question.
John Wentworth
CC BY-SA 3.0
2017-10-17T07:34:34.157Z
Bjørn: Yes. Assume nature's distribution is known and places nonzero weight on all valid programs. Also assume that each player knows the other player's strategy (i.e. distribution).
John Wentworth
CC BY-SA 3.0
2017-10-17T09:20:29.623Z
@johnwentworth, use @ or they can't see your responce.
rus9384
<lo.logic><computability><gt.game-theory>
Equilibrium in a Halting Game
John Wentworth
# Equilibrium in a Halting Game

(Asked by: username_0 on 2017-10-17)

Consider the following 2-player game:

* Nature randomly picks a program
* Each player plays a number in [0, infinity] inclusive in response to nature's move
* Take the minimum of the players’ numbers, and run the program for (up to) that many steps (unless both players chose infinity)
* If the program halts, the player who played the minimum number gains 1 point. If the program does not halt, that player loses 1 point. Any player who played a non-minimum number receives 0 points, and both players receive 0 if they both play infinity.

(Corner cases may be handled in whatever way best preserves the spirit of the problem - e.g. upper semicontinuity may be helpful.)

The question: **does this game possess a computable Nash equilibrium?**

Without the computability requirement, each player just plays the exact number of steps in which the program halts (or infinity, if it does not halt).

If you try the usual diagonalization argument for the halting problem, you'll find that an equilibrium exists in mixed strategies, so the obvious approach does not immediately work. Maybe there's some way to tweak it?

On the other hand, the equivalence of real closed fields means that [finite games with computable payoffs have computable equilibria](https://theoryclass.wordpress.com/2011/01/04/computability-of-nash-equilibrium/). This game is not finite, but the strategy space is closed and the payoffs computable, so maybe the same trick could be applied with Glicksberg's Theorem or something in that vein? The problem is, without the computability requirement, the equilibrium is in pure strategies, so any attempt to prove existence of a computable equilibrium using existence of a maybe-computable equilibrium has to explain why the equilibrium is downgraded from pure to mixed.

This seems like the sort of problem where people may not have addressed this exact question before, but might have looked at something similar. I haven't been able to turn up much, but if anyone knows of something in spirit, please let me know!

Motivation: there's a common intuition that self-reference is the main block to computability - i.e., that any uncomputable problem somehow embeds self-reference. If a game roughly like this has a computable Nash equilibrium, it would provide evidence for that intuition.

UPDATE: To clarify, the equilibrium should be "computable" in the sense of computable real numbers: the probabilities describing the mixed strategy distribution should be computable to arbitrary precision. (Note that only finitely many probabilities will be above any particular precision cutoff.) This also means that we can sample from an arbitrarily close approximation of the equilibrium strategy.

**Tags:** lo.logic, computability, gt.game-theory
> **Comments:**
> **username_1**: Are we allowed to know the opponent's distribution?  
> **username_0**: Ricky: the plays could be regarded as computable reals, but truncating to an integer should dominate any non-integer finite play, since a program will only run for an integer number of steps (or infinity). I'm not sure I understand your parenthesized example though, so I may be misunderstanding your question.  
> **username_0**: Bjørn: Yes. Assume nature's distribution is known and places nonzero weight on all valid programs. Also assume that each player knows the other player's strategy (i.e. distribution).  
> **username_2**: @johnwentworth, use @ or they can't see your responce.  

---

## 1 answers

### Answer by username_3 on 2017-10-17. Score: 11 | Accepted answer

Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than one or you could use it to solve the halting problem. But you can achieve any value less than one by the strategy that for some fixed sufficiently large $t$, simulates nature's program $j$ for $t$ steps and outputs the number of steps it takes program $j$ to halt if $j$ halts in $t$ steps, infinity otherwise.

> **Comments:**
> **username_0**: I like this construction - it establishes that any Nash equilibrium must play correctly for all programs.  There's an additional step needed to establish that it solves the halting problem, since the distributions only need to converge to perfect performance in the limit of high precision (and thus infinite computation). Since we know the output must put unit weight on one integer, I think it suffices to compute the strategy probabilities to within 1/4 and then take whichever integer has weight greater than 1/2.  

---

