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.)

I was a PhD student with Paulo Oliva, original tasked with extending higher order sequential games to simultaneous games. By 2014 we had achieved this using multi-valued selection functions, but this led to the question of unifying the single-valued and multi-valued approaches. This is something I still want to do, but there’s some surprisingly serious barriers.

Motivated by this, and hearing about the need for a new foundation of mathematical economics from Viktor Winschel, in late 2014 I was explicitly thinking about the question “How do you make game theory compositional?” Everybody implicitly or explicitly uses von Neumann’s models of extensive form or normal form games, which are quite bad for this purpose (although some people have tried composing them, with varying amounts of success). I was mainly looking for inspiration from concurrency theory and game semantics.

One of my ideas was to generalise extensive form games from trees to event structures. I was unaware of the paper Equilibria of concurrent games on event structures, which was published earlier in 2014. I think that paper has several problems game-theoretically such as its naive treatment of nondeterminism, but is a good place to start. If I had known about it back then, open games would probably have never existed. Fortunately I didn’t, because open games are more strongly compositional.

Another closely related thing I was thinking about was games on series-parallel (or N-free) posets. This primed me into thinking about monoidal categories. Later I would like to come back and tie up these loose ends via categorical presentations of these concurrency models, such as this paper introduced to me by Pawel Sobocinski.

Anyway, between January and April 2015 I was a visiting student in Mannheim’s department of economics, spending every day with Viktor Winschel and Philipp Zahn and sometimes Evguenia Shprits. Other than trying to push selection functions further, I was still thinking hard about compositional game theory.

There was no ‘aha!’ moment when open games sprang into being. (This is one reason that I still find it so hard to explain them.) Inspired by Dusko Pavlovic’s paper, I tried to make a category whose objects were sets and whose morphisms are pieces of games that can observe a state in and output a new state in . From the first attempt, these game-processes carried a set of strategy profiles and a play function , both of which survived unchanged into open games. This is the only part that I got right first time, and still the only part that I think is intuitive.

Beyond that, everything was very different. I was already using the Haskell interpreter GHCi to type-check and test many definitions by brute force. I wrote a report, dated February 17, 2015, called “String diagrams for game theory: a (very) preliminary report” which I have made available here. Section 14 implies that I’d been playing around in Haskell for over 2 weeks by that point, although I don’t remember it.

At this time, ‘pregames’ had a sideput that composed only by cartesian product (like strategy profiles), and what became the counit was a noticeably non-compositional operator that was only defined on pregames with domain . I also now think that the graphical language would take a lot more work to formalise properly. Despite the problems, most of the philosophical benefits of open games are already in this paper, and example 4 survived essentially unchanged all the way into the published version of Compositional game theory. It also contains the phrase ‘open games’ which later replaced ‘pregames’ as the name.

Viktor sent my report to several of his contacts in computer science departments, of which only Neil Ghani responded, and enthusiastically at that.

As far as I can remember, I had the idea the contravariant and ports, to make outcomes compositional, soon after this. As far as I can remember, there followed another week of intense wrangling with GHCi, type-checking and testing many possible definitions. At some point I started narrowing down to a few remaining possibilities, after which I would declare the problem impossible. I worked through them in decreasing order of how likely they were to work out.

At the end of one day I had narrowed down to all but the last possibility, which I thought was the least likely. (I have no way to remember other definitions I tried around this time.) At the end of the day Viktor, Philipp and me were in the Irish pub in Mannheim, where we often went after work, and I was quite depressed because I thought my idea wouldn’t work. (Clearly I already realised the significance of 4-variant open games, before having a working definition.) I still haven’t been able to live this down, because the remaining thing I tried the next morning turned out to be the correct definition of open games.

I wrote this up very quickly as String diagrams for game theory, and submitted it to MFPS 2015, where it was rejected mostly for being too preliminary. Although I still called them ‘pregames’, the full definition of open games appeared in this paper. The only difference was that the best response function was written as an ‘individual rationality relation’ equivalent to just remembering the fixpoints of best response, i.e. the Nash equilibria. This is a very minor difference, and I don’t think best response is the last word on the matter anyway.

I thought (probably correctly) that my writing style left a lot to be desired, so the next thing I did was recruit Neil as a coauthor. He mostly rewrote my paper, which became A compositional approach to economic game theory. I don’t remember clearly what happened around this time, but I think we took our time with it, and Neil submitted it as an invited publication to a special issue. I think it was under review for a long time (maybe a year) before it was rejected (technically major revisions, which is a politer way of saying the same thing) — as an invited submission this is quite a dubious achievement.

By this time it was late 2017, I was a postdoc in Oxford, and the paper had been renamed to Compositional game theory and had gained Viktor and Philipp as coauthors. I want to be clear about this, in case anybody is looking around the different versions and wondering about the changes of authorship. The mathematical definition of open games was due to me, and the first version of the paper was written solely by me. But it was directly motivated by discussions with them, and on reflection I should have understood that it was impossible to disentangle it from the context of our discussions. By 2017 they were both working on various extensions and applications of open games, and both felt that their early contributions were not recognised. I agreed, and to make everything unambiguous they both worked heavily on the rewrite for the LiCS 2018 submission, still called Compositional game theory but otherwise with no text in common with the previous version.

I have to thank Jamie Vicary for telling me in no uncertain terms that I should submit the paper to LiCS. After attending LiCS in 2014 (an earlier version of Dialectica categories and games with bidding was rejected from it, admittedly for a serious error, and somehow I missed or forgot the paper on games on event structures I mentioned earlier) I was left with the impression that such a big and powerful conference (to the point where you almost need a publication or two there) isn’t healthy for the subject, and I became determined not to play everyone’s game. This lasted until half way through my first postdoc, when the threat of job applications caught up with me and I realised that an unfavourable Nash equilibrium is still a Nash equilibrium, and I was harming myself by deviating unilaterally.