Skip to main content
11 votes

PPAD and Quantum

Two answers that I learnt while writing a blog post about this question No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. ...
Aviad Rubinstein's user avatar
9 votes

PPAD and Quantum

I will attempt to elaborate a bit on why CHKPRR shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers. At a high level, CHKPRR builds a distribution over end-of-line instances where ...
Geoffroy Couteau's user avatar
5 votes

Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs): ...
usul's user avatar
  • 7,615
1 vote

Is there a fundamental link between Nash's equilibrium and Turing's halting problem?

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 ...
domotorp's user avatar
  • 14k
1 vote

How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

It depends on what your usecase is. If you are interested in getting close to an actual Nash equilibrium, then the quality measure you want will be the distance to the nearest Nash equilibrium (which ...
Arno's user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible