Open Games with external choice in Markov Fibrations › Introduction [efr-7EHV]

Game theory is a field of economics which studies mathematical models of human decisionmaking. Classically, game theory is particularly interested in the behavior resulting from individual agents optimizing simple objectives (such as the expected value of some real-valued function of each players' decision) when multiple such players interact. Although the analysis of games, obviously, has a long prehistory, the field was put on its modern theoretical footing by Von Neumann in 1928 (Reference [neumann-games], see also Reference [neumann-morgenstern-games] for a more thorough treatment from this era). The basic problem studied here is this: given two finite sets \Sigma _1, \Sigma _2 of strategies---that is, the choices available to the two players---and a function f: \Sigma _1 \times \Sigma _2 \to \mathbb {R} which assigns to a pair of such choices a score, which player 1 seeks to maximize and player 2 seeks to minimize, what can be said about the rational decisionmaking of each player?

Suppose each player has access to some source of randomness, so that they may each choose a distribution on their respective strategy set to play. This is called a mixed strategy. Suppose player 2 has the opportunity to move knowing the distribution chosen by player 1 (but not the value drawn from it), and suppose he prefers to minimize the expected outcome of the game. Writing f(\mu _1,\mu _2) for E_{x \sim \mu _1, y \sim \mu _2}f(x,y) for brevity, if player 1 selects the distribution \mu _1, clearly player 2 must select the distribution \mathrm {argmin}_{\mu _2} f(\mu _1,\mu _2). Knowing this, player 1 will select the distribution \mathrm {argmax}_{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2), and the expected score of the game will be \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2).

If the selection happens in the other order, of course, the result will be \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2). Clearly choosing knowing your opponent's (mixed) strategy can not be a disadvantage compared to choosing with no information, and so we have \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2) \leq \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2). Von Neumann's great minimax theorem is that these values agree, and this implies that by choosing as if your opponent would know your (mixed) strategy, you obtain a result as good as you could have obtained if you knew your opponents' strategy---hence neither player could improve their outcome, even if they had the advantage of greater information.

This is a strong argument for the optimality of such decisions. The key assumption is that the players are perfectly opposed, that is, player 2 seeks to minimize precisely the value that player 1 seeks to maximize. Nash in Reference [nash-noncoop-games] extended the theory to the more general class of games where players simply each have their own utility function, although it should be noted that Nash merely proved the existence of equilibria---that is, strategy sets where no player can improve their situation by switching strategies. It is computationally intractable (Reference [nash-complexity]) to identify Nash equilibria in an arbitrary game, and so to apply the theory we're forced to analyze each game in an ad hoc way.

We will not go intro a serious review of game theory here, we mention the above details mainly to contextualize our future definitions. For a modern reference on game theory see eg Reference [game-theory-maschler-textbook], or Reference [osborne-intro-gametheory] for a textbook treatment.

In his thesis (Reference [hedges-towards-compositional-thesis]), Hedges introduced a novel approach to game theory which he named compositional game theory, studying objects called open games. The idea of open games is to describe a type of "partial" game which has an interface to the world---some part of the payoff function being dependent on an undetermined environment, into which hole can be inserted another game. This is the sense in which they are open. Based on these, one can build a complex game up out of simpler subparts, as well as leverage a string diagramattical syntax to analyze games.

The original definition of open game cannot help but seem somewhat ad hoc. It was quickly realized that a large part of the definition can be understood to say that a game is a function \Sigma \to \mathsf {Lens}({S \choose X},{R \choose Y}) from a strategy set into a set of lenses, and this part of the game composes by lens composition.

The additional data of an open game is a so-called equilibrium relation, which determines which strategies are equilibria in a given situation (each strategy really represents a set of strategies, one for each player). In Reference [towards-cybercat], the author, Capucci, Gavranovic and Hedges demonstrated that this can be further simplified by realizing an open game as a parametrized map in lenses---a morphism in \mathsf {Para}(\mathsf {Lens}(\mathcal {C})) (in fact, one often wants to consider \mathsf {Optic}(\mathcal {C}) for, for example, Markov categories \mathcal {C}, to account for mixed strategies) along with a notion of equilibrium relation defined on the parameter object {\Omega \choose \Sigma }. We will begin this chapter by recapping this idea.

On a conceptual level, there is a natural operation on games, called external choice, which assigns to two open games {A_1 \choose X_1} \to {B_1 \choose Y_1}, {A_2 \choose X_2} \to {B_2 \choose Y_2} a new game, whose environment begins by making a choice between one of these games, lets that one happen, then provides some payoff for it at the end. The natural type for the interface of this operation is {A_1 \choose X_1} + {A_2 \choose X_2} \to {B_1 \choose Y_1} + {B_2 \choose Y_2}, but unfortunately the category of optics doesn't have coproducts. The category of lenses can be extended with coproducts (into dependent lenses), but the analysis of mixed strategies makes probability an absolute necessity for a useful theory of games.

The introduction of Markov fibrations provides a solution to this problem, and in the second half of this chapter, we provide such an external choice operation on open games. Although the approach based on Markov fibrations is novel, the approach to defining the external choice operator is otherwise very similar to one appearing in presently unpublished work by the author, Braithwaite, Hedges and Videla (this paper used a more specialized approach to adding coproducts to \mathsf {Optic}).