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. ...
- 111
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 ...
- 818
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):
...
- 7,595
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 ...
- 13.9k
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 ...
- 111
1
vote
Accepted
Understanding Prisoner's dilemma
If you look at the definition for Nash equilibrium, you can see that if both $A$ and $B$ are in $\texttt{State 4}$, then if $A$ changes their mind that would mean that they would be defecting from a ...
- 26
Only top scored, non community-wiki answers of a minimum length are eligible