2012
COLT
COLT 2012
(weak) Calibration is Computationally Hard
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.
🌉
Interdisciplinary Bridge
- Artificial Intelligence and Computer Science and Mathematics & Optimization
📈
Trend Setter
- Game Theory
🐣
Hot Topic Early Bird
- nash equilibrium
Authors
Topics
Artificial Intelligence > Core AI > Game AI
Machine Learning > Optimization & Theory > Theory
Computer Science > Foundations > Algorithms
Mathematics & Optimization > Optimization > Discrete Optimization
Mathematics & Optimization > Optimization > Game Theory
Artificial Intelligence > Core AI > Game Theory