Compositional game theory reading list

The best starting point, for a reader who knows a little about both game theory and category theory, is the paper Compositional game theory.

Additional background and motivation is provided by the blog post A first look at open games and the preprint Compositionality and string diagrams for game theory.

By far the most complete exposition is my PhD thesis Towards compositional game theory. It is fully self-contained for readers who know category theory but not game theory.

If you don’t have background in category theory, my current recommendation is Seven sketches in compositionality by Brendan Fong and David Spivak.

A first look at open games

Even I think open games are hard to understand, and I invented them.

(Perhaps this is just me though. Grothendieck wrote “The very idea of scheme is of infantile simplicity — so simple, so humble, that no one before me thought of stooping so low.” [Grothendieck, Récoltes et Samailles, translated by Colin McLarty] So simple, in fact, that it took me years before I understood the definition of a scheme.)

Here I will give the best starting-out intuition I can give for open games, based on a few years of giving research talks consisting of three-quarters introduction. I’ll make no attempt to explain how they work — for that, section 2 of my thesis is still the best thing.

Continue reading “A first look at open games”

Breaking the rules

As might be expected, the rules of the game are an important concept in game theory. But the way that game theory treats its all-important rules is very un-subtle: it is firmly built into the epistemic foundations that the rules are common knowledge, which makes it extremely difficult to talk about breaking the rules. If any player breaks the rules, or even if any player suspects another player of breaking the rules (up to any level of epistemic reasoning), you are simply outside the scope of your model. Of course the possibility of breaking any individual rule, and the consequences for doing so, can be manually built into your game, but then it is unclear whether it can reasonably be called a ‘rule’ any more.

Continue reading “Breaking the rules”

Abusing the continuation monad

(Recall that monads are not a good topic for your first blog post.)

I intend to bootstrap a blog by writing about 2 of my old papers, Monad Transformers for Backtracking Search and The Selection Monad as a CPS Transformation. (Wall Street will be spared for the time being.)

I’m going to write about this little bit of Haskell code:

import Control.Monad.Cont
sat n = runCont $ sequence $ replicate n $ cont $ \k -> k $ k True

It’s a SAT solver: you give it a boolean function, and the number of variables to search, and it decides whether that function will ever return true for any values of those variables.

How does this work? Haven’t the foggiest. If anyone can explain what it does at runtime, there’s probably a research paper in it for you. If you can also predict how long it takes, that’s a big deal.

Continue reading “Abusing the continuation monad”