Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: subgame perfect equilibrium for open games

Robin Piedeleu (May 08 2021 at 21:08):

I have a basic question about open games and I'd be grateful if some of the local experts could help me out.

Is it correct that sequential composition of open games (say, for concreteness, in the classical setting of utility-maximising players with real-valued payoffs) does not restrict the solution concept to be subgame perfect equilibrium? I read this in the LiCS'18 reference paper but wanted to check. If this is the case, then what is the role of sequential composition, when the equilibrium reduces to that of the version of the game where players play simultaneously? I do not see what part the directedness of composition plays if it is not reflected in the semantics (the equilibrium). What is interesting about sequential composition is that it is directed: one player plays knowing that the next will see their move before making theirs and so the solution concept should reflect that, shouldn't it?

Of course, the strength of open games is that they are much more general and maybe by restricting myself to classical games I'm missing the point. Because the best-response is a component of the definition of an open game, maybe there's a way of tuning it so that subgame perfect equilibrium falls out of the sequential composition of two players. Has someone done this?

Jules Hedges (May 08 2021 at 21:14):

I'll list all the approaches there are. It's kind of embarrassing how difficult this turns out to be, but it's more or less solved now

Jules Hedges (May 08 2021 at 21:25):

• What you're describing, directly defining the sequential composition in the category to do subgame perfect equilibrium, goes horribly wrong for slightly mysterious reasons. Namely, the tensor product then fails to be a bifunctor. This is all in my thesis (http://www.cs.ox.ac.uk/people/julian.hedges/papers/Thesis.pdf), with the goriest details around section 2.2.8-2.2.9
• Probably the most straightforward thing that works is in section 3 of "A compositional treatment of iterated open games" (https://arxiv.org/abs/1711.07968). They define an operator that transforms an open game into another one whose solution concept is SPE, with some caveats
• In Morphisms of Open Games (https://arxiv.org/abs/1711.07059) I did an approach that I like involving 2-categorical structure. I set things up so that Nash equilibria are states in the vertical direction, and in section 7 I show that SPEs coincide with states that are $\otimes$-separable
• My current favourite approach, which involves a lot of theoretical overkill but works extremely nicely, is detailed in my blog post "Subgame perfection made difficult": https://julesh.com/2020/05/26/subgame-perfection-made-difficult/

Robin Piedeleu (May 08 2021 at 21:48):

Thanks @Jules Hedges! I'll start with the blog post to get a sense of what's going on.

Robin Piedeleu (May 08 2021 at 22:12):

One thing I still find confusing about the standard formalism (not those in the list above) is that you represent a 2-stage sequential game using a first player $1\rightarrow (X, \mathbb R)$ and $X\rightarrow (Y, \mathbb R)$ but the equivalent (from the point of view of their equilibria) simultaneous game would have two players of the form $1\rightarrow (X, \mathbb R)$ and $1\rightarrow (Y, \mathbb R)$ in parallel. In some sense, the representation of the second player in the sequential game contains information that is not really used and I'm struggling to understand what it does (except highlight at a syntactic level that the intended structure is different).

Robin Piedeleu (May 08 2021 at 22:16):

I guess at some level this is not too surprising: two different syntactic objects can of course have the same semantics. But at another level, because the semantics of the sequential game is different from what I expected, this confuses me.

Jules Hedges (May 08 2021 at 23:12):

The $X$ in the domain is what allows the second player to observe a value of $X$, or more specifically allows their strategy to be a function on $X$

Robin Piedeleu (May 09 2021 at 13:51):

Yes, but the way that their strategy depends on $X$ is the same as if the move in $X$ was played simultaneously, since the first player acts as if their move was not going to be observed, right?

Jules Hedges (May 10 2021 at 10:08):

No...... your strategy can only be contingent on things in your causal past, you can't be contingent on something that happens simultaneously

Robin Piedeleu (May 11 2021 at 11:24):

Sure, but there is a counterfactual dependence on what simultaneous moves are available to other players and what everyone's payoff would be should they adopt a given strategy. So what I was saying is that the counterfactual reasoning of the players in the sequential game (in its open game version) is not really different from the associated simultaneous game---if it were, the first player would consider the fact that they are playing first and that the other player will observe their move and adopt a subgame perfect equilibrium strategy. So, at the syntactic/type level, open games allow for a dependence on past moves, but this dependence does not matter semantically because the second player might as well have played simultaneously and the same equilibria would be found.

Robin Piedeleu (May 11 2021 at 11:25):

But, ultimately, I think we're probably thinking the same thing but expressing them differently because I am confused about what constitutes compositionality for open games.