Probability and Nondeterminism in Compositional Game Theory

Abstract

We substantially extend previous work in the emerging field of compositional game theory. We generalise work by Escardó and Oliva relating the selection monad to game theory. Escardó and Oliva showed that the tensor operation of selection functions computes a subgame perfect equilibirium of a sequential game. We investigate game theoretic interpretations of selection functions generalised over a monad. In particular we focus on the finite non-empty powerset monad which we use to model nondeterministic games. We prove a negative result: that nondeterministic selection functions do not com- pute the collection of all subgame perfect plays of a sequential game. We then define a solution concept related to the iterated removal of strongly dominated strategies, and then show that the tensor of nondeterministic selection functions computes the plays of strategy profiles satisfying this solution concept. In the second part of this thesis we greatly expand the expressive power of open games, first introduced by Jules Hedges [Hed16]. In the current literature, open games are defined using the category of sets and func- tions as an ambient category. We define a category of open games that can use any symmetric monoidal category as an ambient category. This is accomplished using coend lenses which can be used to model certain bidirectional processes. Generalising open games to arbitrary symmetric monoidal categories allows us to, in particular, model probablistic games involving Bayesian agents in an open games formalism.