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. ...
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 ...
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,140
4 votes
Accepted

Is there a tool for finding Nash equilibria in parametric games?

Is there a tool which solves parametric games? Not that I am aware of (I am a co-author of GTE and help with Gambit). The best suggestion I have if you don't find such a tool (and I doubt one exists)...
  • 1,713
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