Aims

This module will give an 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.

An original motivation in developing distributed games was to provide a replacement for traditional denotational semantics and its mathematical foundation of domain theory; in the light of computation today domain theory is seen to have abstracted away from operational concerns too early.

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 games and 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

• Models for concurrent computation, in particular event structures and families of configurations
• Distributed games and strategies, and how to model them
• Distributed games with imperfect information
• Strategies as concurrent processes. Strategies with neutral events. A syntax and operational semantics for strategies. Equivalences on strategies.
• Winning and losing in distributed games. Determinacy.
• Probabilistic event structures. Probabilistic strategies. Optimal strategies and value theorems. Quantum games.
• Backtracking and games with symmetry. Disjunctive causality; limitations of traditional event structures and how to fix them.

Objectives

On completion of this module, students should:

• know about event structures, families of configurations and have an idea of how they relate to other models of concurrency such as Petri nets;
• have some technical proficiency in reasoning within such models;
• be introduced to a variety of games, related concepts, and the underlying mathematics;
• be aware of several challenging open problems.

Coursework

Exercises will be provided.

Practical work

None

Assessment

Assessment will be by take-home test.

Recommended reading

Full notes and copies of slides will be provided.