<p>I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.</p>

<p>Imagine some kind of two-player perfect information game which is played on an $n\times n$ board, and which is complex in the sense that optimal play is EXPTIME-hard.  Suppose also for simplicity that draws are not possible.  Imagine a pair $(A, B)$ of randomized polynomial-time Turing machines playing this game against each other.  For each $n$, let $p_{A,B}(n)$ be the probability that $A$ beats $B$ at the order-$n$ game.  (For concreteness, let's say that $A$ gets to play first with probability 0.5.)  What I think would be cool is if one could prove the existence of a pair $(A,B)$ with the property that no randomized polynomial-time Turing machine $A'$ <i>dominates</i> $A$ (where "$A'$ dominates $A$" means $p_{A',B}(n) &gt; p_{A,B}(n)$ for all sufficiently large $n$), and similarly no randomized polynomial-time Turing machine $B'$ dominates $B$ (where "$B'$ dominates $B$" means $p_{A,B'}(n) &lt; p_{A,B}(n)$ for all sufficiently large $n$).</p>

<p>Somehow, I suspect that this is too much to hope for, but is there any hope for something like this to be true, perhaps for a restricted class of games?</p>

<p>One motivation for this question is that I am looking for a way to formalize the notion that a given chess position is "advantageous for White."  Classically, a position is either a win for White or it isn't.  However, chess players, both human and computer, have an intuitive understanding of what it means for White to have an advantage.  It seems to have something to do with the probability that White will win, given that the players are computationally bounded and have to guess at the best move.  For a specific pair of randomized algorithms one can of course talk about the probability that White will win, but what I'm wondering is if there can be, in some sense, a <i>canonical</i> pair of computationally bounded players whose winning probabilities yield a value for the position that depends only on the game itself and not the idiosyncrasies of the players.</p>

CC BY-SA 3.0
2014-12-10T15:16:27.637Z
The computationally bounded equilibrium concepts I know of have a different flavor -- thinking of Halpern, Pass, and Seeman as in [Truth Behind the Myth of the Folk Theorem](http://www.cs.cornell.edu/~lseeman/Docs/ITCS2014.pdf), 2014. There we don't assume that finding an equilibrium strategy for the given game is hard (because for a given game, it might or might not be). Rather, we allow any strategy set to be an equilibrium if it is hard for any player to compute a profitable deviation. (Note this assumes exponential strategy space, otherwise we can check all deviations.)
usul
<gt.game-theory>
Computationally bounded version of Nash equilibrium?
Timothy Chow
# Computationally bounded version of Nash equilibrium?

(Asked by: username_0 on 2014-12-10)

I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.

Imagine some kind of two-player perfect information game which is played on an $n\times n$ board, and which is complex in the sense that optimal play is EXPTIME-hard. Suppose also for simplicity that draws are not possible. Imagine a pair $(A, B)$ of randomized polynomial-time Turing machines playing this game against each other. For each $n$, let $p\_{A,B}(n)$ be the probability that $A$ beats $B$ at the order-$n$ game. (For concreteness, let's say that $A$ gets to play first with probability 0.5.) What I think would be cool is if one could prove the existence of a pair $(A,B)$ with the property that no randomized polynomial-time Turing machine $A'$ *dominates* $A$ (where "$A'$ dominates $A$" means $p\_{A',B}(n) > p\_{A,B}(n)$ for all sufficiently large $n$), and similarly no randomized polynomial-time Turing machine $B'$ dominates $B$ (where "$B'$ dominates $B$" means $p\_{A,B'}(n) < p\_{A,B}(n)$ for all sufficiently large $n$).

Somehow, I suspect that this is too much to hope for, but is there any hope for something like this to be true, perhaps for a restricted class of games?

One motivation for this question is that I am looking for a way to formalize the notion that a given chess position is "advantageous for White." Classically, a position is either a win for White or it isn't. However, chess players, both human and computer, have an intuitive understanding of what it means for White to have an advantage. It seems to have something to do with the probability that White will win, given that the players are computationally bounded and have to guess at the best move. For a specific pair of randomized algorithms one can of course talk about the probability that White will win, but what I'm wondering is if there can be, in some sense, a *canonical* pair of computationally bounded players whose winning probabilities yield a value for the position that depends only on the game itself and not the idiosyncrasies of the players.

**Tags:** gt.game-theory

> **Comments:**
> **username_1**: The computationally bounded equilibrium concepts I know of have a different flavor -- thinking of Halpern, Pass, and Seeman as in [Truth Behind the Myth of the Folk Theorem](http://www.cs.cornell.edu/~lseeman/Docs/ITCS2014.pdf), 2014. There we don't assume that finding an equilibrium strategy for the given game is hard (because for a given game, it might or might not be). Rather, we allow any strategy set to be an equilibrium if it is hard for any player to compute a profitable deviation. (Note this assumes exponential strategy space, otherwise we can check all deviations.)  

---

## 0 answers

