<p>It is <strong>NP-Hard</strong> to find a pure Nash equilibrium in a 2P0S game given in extensive form, even if one is promised to exist.</p>
<p>It is NP-Hard to decide if a pure Nash equilibrium exists in a 2P0S game given in extensive form. This is a result in &quot;<a href="https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8640.1996.tb00256.x" rel="nofollow noreferrer">Perfect Recall and Pruning in Games with Imperfect Information</a>&quot;, by Jean R. S. Blair, David Mutchler, Michael van Lent (1996).</p>
<p>Section 4.2 in that paper reduces <a href="https://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow noreferrer">3-PARTITION</a> to deciding if a pure Nash exists in a 2P0S game.<br />
Section 4.3 states the corollary &quot;Given a zero-sum, perfect-recall game in which a pure-strategy equilibrium point exists, it is NP-hard to find such an equilibrium point&quot;, but the proof is in a separate paper which doesn't seem to be on the internet.</p>

CC BY-SA 4.0
2024-09-13T17:02:52.117Z
2024-09-24T15:54:40.830Z
2024-09-24T15:54:40.830Z
Kevin Wang
<p>Say we want to find a pure Nash equilibrium of a 2-player zero-sum (2P0S) game. A pure equilibrium does not exist for all games, so let's consider the setting where we are promised that such an equilibrium exists.</p>
<p>If you are given a 2P0S game in extensive form (EFG), you can compute a Nash equilibrium using polynomial time in the size of the game tree, by constructing a linear program. However, this Nash equilibrium may not be pure.</p>
<p>If we specifically want a pure equilibrium, can we still do it in polynomial time? How?</p>
<p>(The paper <a href="https://arxiv.org/pdf/1109.2152" rel="nofollow noreferrer">&quot;Pure Nash Equilibria: Hard and Easy Games&quot; (Gottlob et al., 2005)</a> describes hardness and tractability results but doesn't seem to consider extensive form games. <a href="https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/sandholm/nash_complexity.GEB-08.pdf" rel="nofollow noreferrer">&quot;New complexity results about Nash equilibria&quot;</a> (Conitzer &amp; Sandholm) describes hardness results for Markov games and Bayesian games but doesn't seem to consider the 2P0S setting.)</p>

CC BY-SA 4.0
2024-08-17T20:09:10.747Z
Can you be more precise about the representation of the input? Is it complete information?
usul
CC BY-SA 4.0
2024-08-20T19:29:32.210Z
@usul The input is given in extensive form (EFG), which I believe means that it is complete information.
Kevin Wang
CC BY-SA 4.0
2024-08-21T03:12:20.480Z
It is straight forward to check whether a give pair of strategies for the two players constitute a pure NE.  Why not try all possible pairs of strategies? One doesn't need zero sum for this. And this works for any fixed # of players, no?
Chandra Chekuri
CC BY-SA 4.0
2024-08-22T18:37:16.907Z
@ChandraChekuri Here, I'm asking if the game is given in extensive form (EFG), i.e. it's a sequential game where the game tree is given. The number of pure strategies is thus exponential in the size of the game tree.
Kevin Wang
<gt.game-theory><two-player-games>
Given a 2-player zero-sum game in EFG, find a pure Nash equilibrium (given that one exists)
Kevin Wang
# Given a 2-player zero-sum game in EFG, find a pure Nash equilibrium (given that one exists)

(Asked by: username_0 on 2024-08-15)

Say we want to find a pure Nash equilibrium of a 2-player zero-sum (2P0S) game. A pure equilibrium does not exist for all games, so let's consider the setting where we are promised that such an equilibrium exists.

If you are given a 2P0S game in extensive form (EFG), you can compute a Nash equilibrium using polynomial time in the size of the game tree, by constructing a linear program. However, this Nash equilibrium may not be pure.

If we specifically want a pure equilibrium, can we still do it in polynomial time? How?

(The paper ["Pure Nash Equilibria: Hard and Easy Games" (Gottlob et al., 2005)](https://arxiv.org/pdf/1109.2152) describes hardness and tractability results but doesn't seem to consider extensive form games. ["New complexity results about Nash equilibria"](https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/sandholm/nash_complexity.GEB-08.pdf) (Conitzer & Sandholm) describes hardness results for Markov games and Bayesian games but doesn't seem to consider the 2P0S setting.)

**Tags:** gt.game-theory, two-player-games

> **Comments:**
> **username_1**: Can you be more precise about the representation of the input? Is it complete information?  
> **username_0**: @username_1 The input is given in extensive form (EFG), which I believe means that it is complete information.  
> **username_2**: It is straight forward to check whether a give pair of strategies for the two players constitute a pure NE.  Why not try all possible pairs of strategies? One doesn't need zero sum for this. And this works for any fixed # of players, no?  
> **username_0**: @ChandraChekuri Here, I'm asking if the game is given in extensive form (EFG), i.e. it's a sequential game where the game tree is given. The number of pure strategies is thus exponential in the size of the game tree.  

---

## 1 answers

### Answer by username_0 on 2024-09-13. Score: 3 | Accepted answer

It is **NP-Hard** to find a pure Nash equilibrium in a 2P0S game given in extensive form, even if one is promised to exist.

It is NP-Hard to decide if a pure Nash equilibrium exists in a 2P0S game given in extensive form. This is a result in "[Perfect Recall and Pruning in Games with Imperfect Information](https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8640.1996.tb00256.x)", by Jean R. S. Blair, David Mutchler, Michael van Lent (1996).

Section 4.2 in that paper reduces [3-PARTITION](https://en.wikipedia.org/wiki/3-partition_problem) to deciding if a pure Nash exists in a 2P0S game.  
Section 4.3 states the corollary "Given a zero-sum, perfect-recall game in which a pure-strategy equilibrium point exists, it is NP-hard to find such an equilibrium point", but the proof is in a separate paper which doesn't seem to be on the internet.


---

