12

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. As Ron points out, this extends to computational complexity under plausible assumptions. Maybe: Nash equilibrium is arguably the flagship problem of "Christos ...


9

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 finding a solution requires to either: break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or ...


5

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): D E A 1 0 B 0 1 C 0.6 0.6 I think that in any equilibrium, the row player plays only C. But now if the column player uses a no-regret algorithm, every sample will either be action D or E, and the ...


4

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) is to do a parameter sweep and solve a bunch of individual instantiations and see what the resulting sets of equilibria say about $EQ()$. Gambit is very ...


1

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 situation where they get $1$ point to one where they get $0$, a net decrease since at $\texttt{State 4}$ they are both defecting. Similarly for player $B$. The ...


1

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 effort from the employee, but, by the revelation principal, that's equivalent to having him reveal his private information.


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