<p>No, these two problems are quite unrelated. The halting problem is based on an argument that is similar to Russell's paradox, while the existance of the Nash equilibrium follows from Borsuk-Ulam. For some complexity results about computing an approximate Nash equilibrium, see, e.g., <a href="https://arxiv.org/abs/1103.2709" rel="nofollow noreferrer">Goldberg: A Survey of PPAD-Completeness for Computing Nash Equilibria</a>.</p>

CC BY-SA 4.0
2021-09-21T18:55:46.800Z
2021-09-21T18:55:46.800Z
domotorp
<p>Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point has some fundamental correspondence with the theory of computation.</p>

CC BY-SA 4.0
2021-09-21T19:12:29.817Z
The best computational analogue of Nash equilibrium is probably the class PPAD.  See [https://en.wikipedia.org/wiki/PPAD_(complexity)](https://en.wikipedia.org/wiki/PPAD_(complexity)) and look specifically for "Nash equilibrium".  Roughly, given a 2-player non-zero sum game, the problem of finding a Nash equilibrium is in NP.  It's probably not NP-complete. Papadimitriou created PPAD to capture the complexity of problems such as this, which involve finding a fixed point of a given function (for which a fixed point is known to exist).  For more, see the paper domotorp links to in his answer.
Neal Young
<lo.logic><computability><nash-equilibrium>
Is there a fundamental link between Nash's equilibrium and Turing's halting problem?
Ajax
# Is there a fundamental link between Nash's equilibrium and Turing's halting problem?

(Asked by: username_0 on 2021-09-21)

Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point has some fundamental correspondence with the theory of computation.

**Tags:** lo.logic, computability, nash-equilibrium
> **Comments:**
> **username_1**: The best computational analogue of Nash equilibrium is probably the class PPAD.  See [https://en.wikipedia.org/wiki/PPAD_(complexity)](https://en.wikipedia.org/wiki/PPAD_(complexity)) and look specifically for "Nash equilibrium".  Roughly, given a 2-player non-zero sum game, the problem of finding a Nash equilibrium is in NP.  It's probably not NP-complete. Papadimitriou created PPAD to capture the complexity of problems such as this, which involve finding a fixed point of a given function (for which a fixed point is known to exist).  For more, see the paper domotorp links to in his answer.  

---

## 1 answers

### Answer by username_2 on 2021-09-21. Score: 1

No, these two problems are quite unrelated. The halting problem is based on an argument that is similar to Russell's paradox, while the existance of the Nash equilibrium follows from Borsuk-Ulam. For some complexity results about computing an approximate Nash equilibrium, see, e.g., [Goldberg: A Survey of PPAD-Completeness for Computing Nash Equilibria](https://arxiv.org/abs/1103.2709).


---

