Predictive Complexity for Games with Finite Outcome Spaces. / Kalnishkan, Yuri.

Measures of Complexity: Festschrift for Alexey Chervonenkis. ed. / Vladimir Vovk; Harris Papadopoulos; Alex Gammerman. Springer-Verlag, 2015. p. 117-139 8.

Research output: Chapter in Book/Report/Conference proceedingChapter



  • pc_finite

    Accepted author manuscript, 381 KB, PDF-document

  • Festschrift_acceptance

    22 KB, PDF-document


Predictive complexity is a generalisation of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies ``unpredictability'' of a sequence in a particular prediction environment. This paper surveys key results on predictive complexity for games with finitely many outcomes. The issues of existence, non-existence, uniqueness, and linear inequalities are covered.
Original languageEnglish
Title of host publicationMeasures of Complexity
Subtitle of host publicationFestschrift for Alexey Chervonenkis
EditorsVladimir Vovk, Harris Papadopoulos, Alex Gammerman
Number of pages23
ISBN (Electronic)978-3-319-21852-6
ISBN (Print)978-3-319-21851-9
StatePublished - 2015
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 22650071