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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 3.1-3.10 |
| Journal | Journal of Machine Learning Research |
| Volume | 23 |
| State | Published - 2012 |
| Externally published | Yes |
| Event | 25th Annual Conference on Learning Theory, COLT 2012 - Edinburgh, United Kingdom Duration: Jun 25 2012 → Jun 27 2012 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence