On the Absence of Predictive Complexity for Some Games
Abstract
This paper shows that if the curvature of the boundary of the set of superpredictions for a game vanishes in a nontrivial way, then there is no predictive complexity for the game. This is the first result concerning the absence of complexity for games with convex sets of superpredictions. The proof is further employed to show that for some games there are no certain variants of weak predictive complexity. In the case of the absolute-loss game we reach a tight demarcation between the existing and non-existing variants of weak predictive complexity.
Cite
Text
Kalnishkan and Vyugin. "On the Absence of Predictive Complexity for Some Games." International Conference on Algorithmic Learning Theory, 2002. doi:10.1007/3-540-36169-3_15Markdown
[Kalnishkan and Vyugin. "On the Absence of Predictive Complexity for Some Games." International Conference on Algorithmic Learning Theory, 2002.](https://mlanthology.org/alt/2002/kalnishkan2002alt-absence/) doi:10.1007/3-540-36169-3_15BibTeX
@inproceedings{kalnishkan2002alt-absence,
title = {{On the Absence of Predictive Complexity for Some Games}},
author = {Kalnishkan, Yuri and Vyugin, Michael V.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2002},
pages = {164-172},
doi = {10.1007/3-540-36169-3_15},
url = {https://mlanthology.org/alt/2002/kalnishkan2002alt-absence/}
}