(weak) Calibration is Computationally Hard

Elad Hazan and Sham M. Kakade JMLR W&CP 23: 3.1 - 3.10, 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.