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 Machine Learning and Mathematics & Optimization
📈
Trend Setter
— Game AI
🧭
Keyword Pioneer
— approximate equilibrium
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Deep Learning, Healthcare & Medicine, Interdisciplinary, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Speech & Audio
🐣
Hot Topic Early Bird
— game theory
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