3
$\begingroup$

This is the question asked 10 years before.

Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years?

The game dealing with is $n$ player, finite actions, general sum.

$\endgroup$
1
$\begingroup$

The problem of computing Nash equilibria in general games is PPAD complete (which is believed to be hard), even for 2-player games. This was proven for 3-player games by Daskalakis et al. for 3-player games in this paper and extended to 2-player games by Chen et al. in this paper. See the Wikipedia article on the PPAD class for more details.

There are nonetheless many approaches to finding equilibria if you have further game structure, from convexity of the payoff functions to potential and zero-sum games.

Having said that, even finding local min-max equilibria in two-player zero-sum games with nonconvex-nonconcave objectives was recently proven to be PPAD complete (as hard as finding Nash equilibria in general games) by Daskalakis et al., see this video link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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