0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ The best computational analogue of Nash equilibrium is probably the class PPAD. See 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. $\endgroup$
    – Neal Young
    Sep 21, 2021 at 19:12

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.