Citation:
E. Hazan and S. M. Kakade, (weak) Calibration is Computationally Hard. Conference on Learning Theory (COLT): ArXiv Report, 2012.
Abstract:
We show that the existence of a computationally efficient calibration algorithm, with a low weak calibration rate, would imply the existence of an efficient algorithm for computing approximate Nash equilibria - thus implying the unlikely conclusion that every problem in PPAD is solvable in polynomial time.See also: 2012