I’ve been wondering for several years how selection functions and lenses relate to each other, I felt intuitively that there should be some connection – and not just because they both show up in the foundations of game theory. Last night I came up with an answer, which isn’t a complete answer but looks like the starting point for a complete answer.
Continue reading “Selection functions and lenses”Category: game theory
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”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.
Slides on Breaking the Rules
I gave a talk last year at Duskofest in Oxford (a workshop celebrating the nth birthday of Dusko Pavlovic, where n is sufficiently large), based on my blog post Breaking the rules.
I have finally remembred to upload my slides here.
This is the only time I can remember enjoying creating slides.
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.
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.
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.
Jules Hedges 