Towards dependent optics

There are two different generalises of lenses that are important in my research. One is optics, which are a non-obvious generalisation of lenses that work over a monoidal category (whereas lenses only work over a finite product category). We use optics in Bayesian open games, over the category of Markov kernels (kleisli category of probability). The other is dependent lenses, also known as containers and equivalent to polynomial functors. These haven’t appeared in a game theory paper yet, but I use them privately to handle external choice of games better than lenses do.

An interesting and probably-hard question is to find a common generalisation of optics and dependent lenses. In this post I’ll outline the problem and explain a (probable) partial solution that might be useful for somebody, but doesn’t appear useful in game theory. This post will be heavy on category theory: I assume knowledge of fibred categories and the Grothendieck construction.

Continue reading “Towards dependent optics”

Subgame perfection made difficult

This is the second post in catching up on aspects of open-games-hs that are ahead of my papers, following open games with stateful payoffs. Subgame perfection has been an embarrassing thorn in my side since 2016 when I had to do major surgery on my PhD thesis because the category of “open games with subgame perfect equilibria” turned out to not be monoidal. Currently there are two approaches: One in iterated open games which is quite pragmatic and requires the “user” specifying an open game to manually mark where the subgames are by applying a functor; and one in morphisms of open games which I find very elegant but requires both an extra categorical dimension and an equivalent amount of effort by the “user”.

I always wanted an “automatic” approach to subgame perfection in open games, like I failed to do in my thesis – just draw the usual string diagram, and get subgame perfect equilibria out. I now have a way to do it, implemented in OpenGames.Engine.SubgamePerfect, which I’ll document here.

Continue reading “Subgame perfection made difficult”

Open games with stateful payoffs

I’m starting to worry that my open games implementation is getting ahead of what I’ve written in papers in a few ways, and I should correct that with documentation blog posts. This one is about the module OpenGames.Engine.StatefulPayoffs, which is a pragmatic solution to a fundamental conceptual problem with open games: the identity of agents is not well-defined. Rather the fundamental unit is a decision, and if two decisions are made by the same agent then it is the user’s responsibility to make sure that those decisions have the same payoff, or at least game-theoretically “coherent” payoffs.

For a long time I thought this was a conceptual problem but not a practical one. But recent work with my collaborators Philipp Zahn, Seth Frey and Joshua Tan has stress-tested open games in new ways and revealed it to a problem after all. Specifically, if one agent makes 2 decisions on different sides of an abstraction boundary, then the programmer must explicitly design the boundary to accommodate that agent’s payoff. This feels like an abstraction leak.

Continue reading “Open games with stateful payoffs”

Lax functors describe emergent effects

In this post I’ll describe something that’s kind of common knowledge among applied category theorists, that when you describe behaviour via a (pseudo)functor to the category of relations, emergent effects are described by the failure of that functor to be strong, ie. to be an actual functor. This is more or less in Seven Sketches (Fong and Spivak say “generative effects”, which as far as I can tell is an exact synonym for emergent effects), but I’ll write it in one place and in my own words.

Suppose we have a domain-specific category \mathcal C. It’s hopefully monoidal and most likely a hypergraph category, but the basic idea of what I’m saying applies just to the category structure. The morphisms of \mathcal C are open systems of some sort, the objects describe the open boundaries that a system can have, and composition describes coupling two systems together along a common boundary. The standard sledgehammer for building categories like this is decorated cospans, with structured cospans as a closely related new alternative.

Continue reading “Lax functors describe emergent effects”

Categorical cybernetics: A manifesto

(Image credit: H.R. Grant / SaurianDandy)

I suddenly became obsessed with cybernetics (exactly) 2 weeks ago when I learned what the word actually means, closely followed by this tweet bring my attention to the following line from the beginning of Kenneth Boulding’s classic (1956) paper General Systems Theory: “The developments of a mathematics of quality and structure is already on the way, even though it is not as far advanced as the “classical” mathematics of quantity and number.” Which sounds like category theory to me. (I think it’s extremely unlikely Boulding had category theory in mind – Eilenberg and Mac Lane’s General Theory of Natural Equivalences was published in 1945; for comparison the first textbook on graph theory was published in 1936.)

Continue reading “Categorical cybernetics: A manifesto”

Symmetric polymorphic lenses (maybe)

Whereas ordinary directed lenses go from a source to a view, symmetric lenses relate two different views of an internal source. I’ve been thinking about how to smoosh together symmetric lenses with polymorphic lenses, which are the sort used in functional programming. My actual goal is to invent “symmetric open games” (without relying on non-well-founded recursion like I did in this paper). But with the right definition, I think symmetric polymorphic lenses could be a useful tool to programmers as well.

Normally when I’m playing with an idea like this I mock it up in Haskell and play around with it to check it works, before committing to too much hard work on the proofs. But this would be very difficult (and maybe impossible) to write in Haskell, so the idea of this post is to give enough detail that some folks could try it in Agda or Idris, and give me feedback on whether it feels like something useful. (In the meantime, I will try an extremely fast and loose Haskell version by pretending that pullbacks and pushouts are products and coproducts, and see what happens.)

Continue reading “Symmetric polymorphic lenses (maybe)”

Are open games useful for my problem?

Recently open games have reached a state where they realistically might start becoming useful to some people (see this demo). I want to write down the current state of the art, what I believe is possible and what I believe are the limitations of compositional methods. This guides which sorts of situations I believe open games will be applicable to.

First I will say what open games can already do (at least in theory). Then I will say what is awkward and what I think is probably possible with future work, and finally when I think you shouldn’t use open games. This post is written for a hypothetical reader who wants to use game theory as a modelling paradigm.

Continue reading “Are open games useful for my problem?”

Folklore: Monoidal kleisli categories

I’ve been threatening a few times recently to blog about bits of mathematical folklore that I use, i.e. important things that aren’t easy to find in the literature. I’m going to start with an easy one that won’t take me long to write.

Theorem: Given a commutative strong monad on a symmetric monoidal category, the kleisli category is symmetric monoidal in a canonical way.

Continue reading “Folklore: Monoidal kleisli categories”

Lenses for philosophers

Lens tutorials are the new monad tutorials, I hear. (This is neat, since monads and lenses were both discovered in the year 1958.) The thing is, after independently rediscovering lenses and working on them for a year and a half before Jeremy Gibbons made the connection, I have a very different perspective on them. This post is based on a talk I gave at the 7th international workshop on bidirectional transformations in Nice. My aim is to move fast and break things, where the things in question are your preconceptions about what lenses are and what they can be used for. Much of this will be a history of lenses, which includes at least 9 independent rediscoveries.

Continue reading “Lenses for philosophers”

The pre-history of open games

I feel that having Compositional game theory accepted for publication marks the end of the first chapter for me, and marks open games as a proper research topic. I want to record how open games came to be, told through the story of this paper, which took almost 3 years from writing to acceptance. (That’s roughly the same amount of time as the Higher Order Decisions/Games duo, although they definitely felt longer. Their story can wait for another blog post.)

Continue reading “The pre-history of open games”