<p>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 <a href="https://people.csail.mit.edu/costis/journal_ver10.pdf" rel="nofollow noreferrer">in this paper</a> and extended to 2-player games by Chen et al. <a href="https://arxiv.org/pdf/0704.1678.pdf" rel="nofollow noreferrer">in this paper</a>. See the <a href="https://en.wikipedia.org/wiki/PPAD_(complexity)" rel="nofollow noreferrer">Wikipedia article</a> on the PPAD class for more details.</p>
<p>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.</p>
<p>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 <a href="https://www.youtube.com/watch?v=yNsrHLpjkvo&amp;t=4739s" rel="nofollow noreferrer">this video link</a>.</p>

CC BY-SA 4.0
2021-04-04T10:10:55.667Z
2021-04-04T10:30:31.967Z
2021-04-04T10:30:31.967Z
smalldog
<p>This is the question asked <a href="https://cstheory.stackexchange.com/questions/1994/algorithms-for-nash-equilibrium-computation?newreg=cd326e0785eb43068fb58936056f7b50">10 years before</a>.</p>
<p>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?</p>
<p>The game dealing with is <span class="math-container">$n$</span> player, finite actions, general sum.</p>

<ds.algorithms><gt.game-theory>
Algorithm to find $n$ player nash equilibrium
dawen
# Algorithm to find $n$ player nash equilibrium

(Asked by: username_0 on 2021-04-02)

This is the question asked [10 years before](https://cstheory.stackexchange.com/questions/1994/algorithms-for-nash-equilibrium-computation?newreg=cd326e0785eb43068fb58936056f7b50).

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.

**Tags:** ds.algorithms, gt.game-theory


---

## 1 answers

### Answer by username_1 on 2021-04-04. Score: 2

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](https://people.csail.mit.edu/costis/journal_ver10.pdf) and extended to 2-player games by Chen et al. [in this paper](https://arxiv.org/pdf/0704.1678.pdf). See the [Wikipedia article](https://en.wikipedia.org/wiki/PPAD_(complexity)) 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](https://www.youtube.com/watch?v=yNsrHLpjkvo&t=4739s).


---

