Deterministic calibration and Nash equilibrium

摘要

We provide a natural learning process in which the joint frequency of (time-averaged) empirical play converges into the set of convex combinations of Nash equilibria. Furthermore, the actual distribution of players' actions is close to some (approximate) Nash equilibria on most rounds (on all but a vanishing fraction of the rounds). In this process, all players rationally choose their actions using a public prediction made by a deterministic, weakly calibrated algorithm. For this to be possible, we show that such a deterministic (weakly) calibrated learning algorithm exists.