Games as computations or computations as games?

Compositional game theory is a new mathematical formulation of game theory. For the most part, it is a new way of looking at things we already know.

What is there to learn from compositional game theory? It offers a seamless switch of perspective between strategic interactions as computations and computations as strategic interactions.

Let me first give some background.

Compositional game theory is based on category theory, an abstract branch of mathematics initially conceived as a language to formalize meta-mathematical problems. Category theory also plays an important role in Theoretical Computer Science, specifically its formal semantics branch. There, one of the central questions is what does a computer actually compute? How can we model the behavior of a program?

As it happens, the nature of the computations we run has changed dramatically. While for a long time computation by a machine meant what happens on a single physical machine, this is not true anymore. Just consider the type of computations we run on the internet. How do you represent that behavior? What kind of computations do happen there? ¹

Category theory has turned out to be a flexible tool, it has accompanied the changing nature of computations and has provided various new insights. In parallel with the evolving domain it helps to study, by now category theory has emerged as a language which transcends computer based computations. It offers a language to represent process-based phenomena and is now used as such in various domains.

One commonality that recent applications of category theory share is their modeling as composable “open systems”. Open, because they are defined relative to some environment; composable, because larger systems are modelled as subsystems glued together by some set of composition rules.

Compositional game theory very much follows this line. In essence, it defines an atomic building block, an “open game”, and composition rules – simultaneous and sequential composition. The modelling process of representing a strategic interaction then works by plumbing together the information flow involved in a strategic interaction.

Each piece involved is modelled as a computation. What does this computation compute? It requires a strategy for the players and it evaluates for each element involved whether that strategy is “good” (more on that in a minute). What is key: The computation is stitched together while the modeller only needs to supply the local pieces. It is therefore well-formed by construction.

Hence, modelling via compositional game theory can be seen as generating a game-theoretic handler from composed elements which can then be called to evaluate a given strategy profile.

I said before, if we evaluate this global object, each individual component will check whether the supplied strategy is “good” from their perspective. But what does that mean?

Here, we have some degrees of freedom. In the classical game theory setting, “good” actually means optimal: Every agent chooses the strategy which maximizes his expected utility (assuming all other players stick to the supplied strategy profile). If there is no profitable deviation for any agent, then this constitutes a Nash equilibrium (or some variant of it).

Now, we are by no means limited to this perspective. We can consider alternative decision criteria for each agent. Most importantly, as each player is a computation, we can model players as (possibly very) complicated learning agents. For instance, we can model two interacting reinforcement learners (work in progress).

But we can take that further: So far I have emphasized the perspective on games as modelled as computations. Yet, the opposite view is also possible. We can view certain computations as games.² Why would we want this? Well, in the case of machine learning, for instance, this perspective is very important and has lead to critical new insights.

The framework of open game suggests we can do this in a very principled and systematic way. Thus, we can develop a dual view on strategic interactions and computations of learners.

May, 2021