# (weak) Calibration is Computationally Hard

[edit]

Elad Hazan,
Sham M. Kakade
;

Proceedings of the 25th Annual Conference on Learning Theory, PMLR 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 \emphPPAD is solvable in polynomial time.

#### Related Material