GTP 2010: Third Workshop on Game-Theoretic Probability and Related Topics

21 - 23 June 2010, Royal Holloway, University of London, Egham, Surrey, UK


ProgrammeOrganizersObjectivesGame-theoretic probabilityRelated topicsLinks

General information and programme

Participation is by invitation. Please contact Glenn Shafer or Vladimir Vovk if you would like to participate. There is no registration fee. The workshop will provide lunches and the conference dinner on Tuesday, but participants will pay for their own accommodation, breakfasts, and dinners (except on Tuesday).

For accommodation and other local information, please click here.

For the programme and slides for many of the talks, please click here.

Organizers

Scientific Organizers:

Local Organization: Computer Learning Research Centre, Department of Computer Science, Royal Holloway, University of London.


Department of Computer Science, Royal Holloway, University of London EPSRC

Objectives of the workshop

This workshop will bring together researchers studying game-theoretic probability with others who have also been studying topics and frameworks that do not assume or require a fully probabilized framework. These topics include imprecise probabilities (which in turn include Walley's upper and lower previsions and Dempster-Shafer theory), prequential statistics, on-line prediction (including prediction with expert advice, well-calibrated prediction, and defensive forecasting), and algorithmic randomness. Previous workshops with the same title, Game-Theoretic Probability and Related Topics, were held in 2006 and 2008 in Tokyo.

The objective of the workshop will be to make researchers in each of the different fields more aware of related work and to help them take advantage of it. Many commonalities have not yet been exploited. The workshop is important because the fields are developing the next generation of methods for sequential prediction. It is timely because there is increasing awareness about advances in game-theoretic probability and an increasing interest in using it as a general framework for communication among the different fields.

Game-theoretic probability

What is game-theoretic probability? Like the better known measure-theoretic framework, the game-theoretic framework for probability can be traced back to the 1654 correspondence between Blaise Pascal and Pierre Fermat, often said to be the origin of mathematical probability. In their correspondence, Pascal and Fermat explained their different methods for solving probability problems. Fermat's combinatorial method is a precursor of the measure-theoretic framework, now almost universally accepted by mathematicians as the result of work by Borel, Kolmogorov, Doob, Martin-Lof, and others. Pascal's method of backward recursion, using prices at each step in a game to derive global prices, can be seen as the precursor of the game-theoretic framework, to which von Mises, Ville, Kolmogorov, Schnorr, and Dawid contributed further ingredients.

The game-theoretic framework was presented in a comprehensive way, as an alternative to the measure-theoretic framework, by Shafer and Vovk in 2001 and Takeuchi in 2004 (see www.probabilityandfinance.com). As these authors explain, a classical probability theorem tells us that some event is very likely or even certain to happen. In the measure-theoretic framework, such a theorem becomes a statement about the measure of a set: the set has measure near or equal to one. In the game-theoretic framework, it is instead a statement about a game: a player has a strategy that multiplies the capital it risks by a large or infinite factor if the event fails to happen. The mere fact that we can translate theorems from measure theory into game theory in this way is of limited interest, but the translation opens up new ways of using probability theory and provides new insights into the meaning of probability and into many existing applications and related fields.

Some of the new insights come from the greater generality of the game-theoretic picture. Many classical theorems hold in generalized form even in games where relatively few payoffs are priced. In classical probability, all payoffs are priced (we call them random variables, and we call their prices expected values). This is not necessary in the game-theoretic picture. An investor in a financial market, for example, plays a game in which he can buy some payoffs (corresponding to various securities traded in the market) but not others. Because probabilities (or upper and lower probabilities) for global events are defined even in these situations, we see these probabilities as features that emerge from the structure of the game, not as features of objective reality or subjective belief external to the game.

One of the most active recent topics in game-theoretic probability, not adequately treated in the monographs by Shafer, Vovk, and Takeuchi, is continuous-time processes. The mathematical idea underlying recent work has been described by Takeuchi as high-frequency limit order trading. A player divides his capital among many different strategies, all of which rebalance a portfolio of bets when a continuous function reaches various discrete levels, but some of which operate at a much higher frequency than others. Various classical properties of stochastic processes emerge merely from the basic assumption that a strategy will not multiply the capital it risks by a very large factor.

Related topics

The related topics that are represented in this workshop can be divided into four categories: (1) imprecise probabilities, (2) prequential statistics, (3) on-line prediction, and (4) algorithmic randomness.

  1. Imprecise probabilities (see www.sipta.org) is now a fairly broad field, which includes Walley's upper and lower probabilities, Dempster-Shafer theory, and other approaches to loosening the classical axioms of probability. The imprecise-probabilities community has accumulated expertise in studying various classes of set functions, including several important classes of Choquet capacities. Inasmuch as game-theoretic probability leads to upper and lower probabilities for events, it can be considered a topic within imprecise probabilities, and the extent to which other work on imprecise probabilities can be understood game-theoretically is an interesting and sometimes open question. There is already a literature on the connection between game-theoretic probability and Walley's imprecise probabilities, and similar work is underway on connections with Dempster-Shafer theory.
  2. Philip Dawid introduced prequential ("predictive sequential") statistics in the 1980s. It helped inspire the development of game-theoretic probability in the 1990s, because it re-conceptualized the notion of a probability distribution for a sequence of events as a strategy for a forecaster in a sequential forecasting game, which the forecaster can also play without thinking through a complete strategy. It has recently attracted renewed attention, because it brings statistics closer to the spirit of machine learning, shifting emphasis from parameter estimation and model selection to predictive performance. We hope to use the workshop to explore the possibility of using martingale-based game-theoretic probability, which automatically satisfies the prequential principle, as a foundation for rebuilding prequential statistics. For example, precise versions of Jeffreys's law (two successful forecasting systems should output similar predictions) have been formulated in game-theoretic probability. Participants from the imprecise probabilities community may have the tools to contribute to further clarification of the relation between measure-theoretic and game-theoretic probability in the prequential framework.
  3. On-line prediction is a computer-science counterpart of prequential statistics. Performance of prediction strategies is measured either by evaluating a loss function or by measuring calibration and resolution. There are three important recent threads in on-line prediction: (i) prediction with expert advice, (ii) well-calibrated prediction, and (iii) defensive forecasting. All three are related to game-theoretic probability, and an elucidation of the relation may help the three learn from each other. In prediction with expert advice, no probabilistic assumptions are made about the way the data is generated; in particular, no statistical models are assumed. The role of statistical models is played by benchmark classes of prediction strategies with which the predictor competes. The recently developed game-theoretic technique of defensive forecasting leads to new prediction algorithms and new kinds of loss bounds in prediction with expert advice. It is also a technique in well-calibrated prediction. A popular proof technique in prediction with expert advice is the method of potentials (widely used in, for example, the 2006 book by Cesa-Bianchi and Lugosi), and it seems likely that many widely used potentials are in fact supermartingales; this would shed new light on known results and perhaps lead to new results. Besides the martingale-based game-theoretic probability of defensive forecasting, well-calibrated prediction has also used measure-theoretic probability and the older von Mises-style of game-theoretic probability. The organizers believe that the von Mises-type game-theoretic approach will be strengthened by the Ville-type game-theoretic approach underlying defensive forecasting, and this strengthening will enable the Ville-type game-theoretic approach to benefit topics in game theory to which only the von Mises approach has been applied so far.
  4. The algorithmic theory of randomness, which continues to develop, shares with game-theoretic probability roots in the pioneering work by Ville in the 1930s and Schnorr in the 1970s. It still provides a theoretical underpinning and a convenient testbed for game-theoretic probability and its applications. It also contributes to prequential statistics and on-line prediction. This workshop will help the number of connections, already significant, to grow further.
  5. Some links

    This list reproduces some of the links given above and gives some new ones:

    This page is maintained by Vladimir Vovk.   Last modified on 25 June 2010