Game Theoretic Probability | ILLC 2016

Probabilities arising from Backward Induction

Description

In 1654 Pascal and Fermat corresponded on the fair division of the stakes in gambling games that got interrupted mid-way. Fermat reasoned measure-theoretically, counting the proportion of wins in imagined continued play. Pascal argued game-theoretically, establishing fair prices for all intermediate states. Pascal and Fermat arrived at the same answer, yet their methods make different assumptions and generalise in different ways.

Today, game-theoretic probability is an alternative foundation for probability theory. It goes beyond Kolmogorov's axiomatic (measure-theoretic) framework by considering an underlying strategic dimension. We will start with various classical laws of probability and re-prove them in the following form. In an infinite game where we are allowed to bet on the outcomes sequentially, we have a strategy that accumulates infinite wealth unless the sequence of outcomes satisfies the probability law. This will be the sense in which we can force the law, no matter how the outcomes arise.

We will study the (intricate) strategies underlying such theorems. Throughout the course we will see how the generality of the framework allows us to reduce assumptions, clarify interpretation, and open up applications to other areas of science. In particular we will look at one application in machine learning in the form of defensive forecasting.

Organisation

The first two weeks are devoted to six lectures with associated homework. The last two weeks will be individual projects with one progress meeting midway.

Preliminary Schedule

Prerequisites

An introductory probability course is indispensable. Familiarity with two-player zero-sum games will be an advantage. A good level of mathematical maturity is required, the strategies that will be considered are not simple.

Assessment

Students will be assessed on the basis of six homeworks and a final report. The written report should provide either some (small) original result or a survey of some of the literature with a new perspective.

Material

Book

Slot	Topic	Notes	Homework
30 May L016	Lecture 1 (chapters 1 and 2) Introduction. Historical perspective. Kolmogorov axioms. Binomial pricing.	Chapter 1 Definitions Video	Set 1
1 June L016	Lecture 2 (chapters 3 and 4) Bounded strong law of large numbers. Unbounded strong law of large numbers.	Chapter 3 Definitions Video	Set 2
3 June L017	Lecture 3 (chapter 5) Strong laws: law of the iterated logarithm	Definitions	Set 3
6 June L016	Lecture 4 (chapter 6 and 7) Weak laws: law of large numbers Weak laws: central limit theorem	Definitions	Set 4
8 June L017	Lecture 5 (chapter 8) Game-theoretic and measure-theoretic probability	Definitions	Set 5
10 June L120	Lecture 6 (not in book) Application: On-line prediction and defensive forecasting
17 June	Progress meeting

The course will cover the first half of the the book Probability and Finance: It's Only a Game! by Glenn Shafer and Vladimir Vovk. I will lecture from the book but do my best to keep the course self-contained. In particular I will post lecture notes.

On-line prediction Wiki

The on-line prediction wiki has a section about Game-Theoretic Probability here.

Project ideas

To get inspiration and ideas for your project topic, you can browse the list of working papers on the book website. A broader selection of related topics can be found in the archives of the Workshop on GTP and related topics below.

It is perfectly fine to do a project on one of the related topics, including imprecise probabilities, prequential statistics, on-line prediction, algorithmic randomness and conformal prediction.