Predictive Complexity for Games with Finite Outcome Spaces

Yuri Kalnishkan

doi:10.1007/978-3-319-21852-6_8

Predictive Complexity for Games with Finite Outcome Spaces

Yuri Kalnishkan

Research output: Chapter in Book/Report/Conference proceeding › Chapter

1216 Downloads (Pure)

Abstract

Predictive complexity is a generalization of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies the “unpredictability” of a sequence in a particular prediction environment. This chapter 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 language	English
Title of host publication	Measures of Complexity
Subtitle of host publication	Festschrift for Alexey Chervonenkis
Editors	Vladimir Vovk, Harris Papadopoulos, Alexander Gammerman
Publisher	Springer
Chapter	8
Pages	117-139
Number of pages	23
ISBN (Electronic)	978-3-319-21852-6
ISBN (Print)	978-3-319-21851-9
DOIs	https://doi.org/10.1007/978-3-319-21852-6_8
Publication status	E-pub ahead of print - 4 Sept 2015

Access to Document

10.1007/978-3-319-21852-6_8

Accepted ManuscriptAccepted author manuscript, 382 KB

https://link.springer.com/chapter/10.1007%2F978-3-319-21852-6_8

Cite this

@inbook{19d62e3dc42d4671a8687b2b4c8c4173,

title = "Predictive Complexity for Games with Finite Outcome Spaces",

abstract = "Predictive complexity is a generalization of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies the {\textquotedblleft}unpredictability{\textquotedblright} of a sequence in a particular prediction environment. This chapter surveys key results on predictive complexity for games with finitely many outcomes. The issues of existence, non-existence, uniqueness, and linear inequalities are covered.",

author = "Yuri Kalnishkan",

year = "2015",

month = sep,

day = "4",

doi = "10.1007/978-3-319-21852-6\_8",

language = "English",

isbn = "978-3-319-21851-9",

pages = "117--139",

editor = "Vladimir Vovk and Harris Papadopoulos and Alexander Gammerman",

booktitle = "Measures of Complexity",

publisher = "Springer",

}

TY - CHAP

T1 - Predictive Complexity for Games with Finite Outcome Spaces

AU - Kalnishkan, Yuri

PY - 2015/9/4

Y1 - 2015/9/4

N2 - Predictive complexity is a generalization of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies the “unpredictability” of a sequence in a particular prediction environment. This chapter surveys key results on predictive complexity for games with finitely many outcomes. The issues of existence, non-existence, uniqueness, and linear inequalities are covered.

AB - Predictive complexity is a generalization of Kolmogorov complexity motivated by an on-line prediction scenario. It quantifies the “unpredictability” of a sequence in a particular prediction environment. This chapter surveys key results on predictive complexity for games with finitely many outcomes. The issues of existence, non-existence, uniqueness, and linear inequalities are covered.

U2 - 10.1007/978-3-319-21852-6_8

DO - 10.1007/978-3-319-21852-6_8

M3 - Chapter

SN - 978-3-319-21851-9

SP - 117

EP - 139

BT - Measures of Complexity

A2 - Vovk, Vladimir

A2 - Papadopoulos, Harris

A2 - Gammerman, Alexander

PB - Springer

ER -