Computer Laboratory

Course pages 2014–15

A Mathematical Theory of Distributed Games and Strategies

Principal lecturer: Prof Glynn Winskel
Taken by: MPhil ACS, Part III
Code: M22
Hours: 6 (Three two-hour sessions)
Prerequisites:

Aims

This module will give a rapid introduction to ongoing research in developing a mathematical theory of distributed games in which a Player (or a team of players) can interact and compete against an Opponent (or a team of opponents) in a highly distributed fashion, without, for instance, enforcing that their moves occur in a sequential fashion, or need to alternate. Although phrased in terms of `Player' and `Opponent' the dichotomy Player vs. Opponent can stand for Process vs. Environment, Prover vs. Disprover, or Ally vs. Enemy. These alternatives indicate the wide range of potential applications in computer science, logic, and beyond.

Strategies are potentially as fundamental as relations and functions. It is surely because of our limited mental capacity, and not because of its unimportance, that the mathematical concept of strategy has been uncovered relatively late. It is hard to think about the successive contingencies involved in playing a game in the same way that is hard to think about interacting processes. Developing strategies in the extra generality demanded by distributed interaction enables us to harness computer-science expertise in structure and distributed computation in their understanding and formalisation.

Because distributed games share both a mathematical and operational nature, specific motivations come from: computer science, to repair the divide between operational and denotational semantics, and the big divide between algorithmics and semantics; logic, in giving an operational/process reading of logic and proof, in which assertions denote games and proofs strategies; game theory, in providing a structural game theory in which games and (optimal) strategies are specified compositionally.

Syllabus

• Distributed games and strategies, and how to model them. Event structures and families of configurations.
• Distributed games with imperfect information.
• Winning and losing in distributed games. Determinacy.
• Probabilistic strategies. Optimal strategies and value theorems.
• Probabilistic event structures. Quantum games.
• Limitations. Backtracking and games with symmetry. Disjunctive causality, a limitation of traditional event structures and how to fix it.

Objectives

On completion of this module, students should:

• * be introduced to a variety of games, related concepts, and the underlying mathematics;
• be aware of several challenging open problems.

Coursework

None. This course is optional and is not for credit.

None.

None.