# Tag Info

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. ...

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 ...

### 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,185
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.8k
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
1 vote

### Seeking for a game for modelling a problem using game thoery

The game you're describing is a continuous-time principal-agent problem. See A continuous-time version of the principal-agent problem (Sannikov 2008). Technically the goal there is to induce optimal ...
• 111

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