Compositional Game Theory

Transcript

foreign my name is Fabrizio and here's Daniela from 20 squares and today we are going to talk about compositional game theory that is basically you know the kind of bread and butter we use tiny squares to do mechanism design based analysis of protocols and stuff like that so um basically uh the kind of flavor of mechanism design we do is heavily based on this theory that has been developed by a bunch of people one of them is Jules that is over there

and other partners of us academics it took a long time eight ten years but now this thing is basically up to a point when it can be used profitably in in production so I just wanted to use this time to give you a sense of you know what is that we do and how it works so I will start with the digression that is uh to really understand what's going on here one needs to learn to think in terms of systems and processes so the idea is a system is something we can transform and act upon and processes are things that act on systems and transform

them um so for instance uh in here we have a very simple system that is the system number you can see this as a state that can be I don't know like any integer and you have this process called add one that just takes any number on the left and spits out that number plus one on the right so looking at it like this it looks like okay super simple perfect the funny thing about processes is that you know when you start thinking about this about it this way you can basically compose them so this is a very simple example you can see that basically add one spits out something of type

number and it also takes something of time number as input so you can concatenate them and basically combine them together and the idea is that you can compose things when their types match so when the type of the input matches with the type of the output uh there is also a very interesting process in for basically any system that is the do nothing process so this is what we call in the mathematical theory that we use an identity morphism so basically this means that for each system you require to have a process that leaves the system unchanged and obviously you see that if this process does nothing which is by the way why we

don't draw it at all when you compose any process with the do nothing process is just like getting the process you started with if I say take a number add one and then do nothing it's just saying add one to the number okay so another example uh this is um basically gravitation so the idea here is that you have a process that is you know a physical system a bunch of velocities and positions in this case you know about the Sun and the Earth relative to it and then you have this process that is evolved so it basically says okay given some initial

parameters of this dynamical system what happens if I let one second pass and you it this thing will spit out some other numbers and again you know this these things can be composed obviously I can basically do evolve for any time by concatenating you know a discrete steps of evolution if I want to and obviously I have the you know do nothing process that is evolved for zero time so basically if you are here and you have all for zero time you stay here you don't have all you don't go anywhere as I said before you can compose things when types match so for instance with the add one we could compose them with

itself because the types match at one spits out something of type number and take something of time number as input but like this composition here is clearly unlawful because the idea is this thing was expecting a bunch of positions and velocities and I'm feeding it with just a number and obviously like this thing says okay what do I have to do with it it's like you are not giving me an input that I understand uh so you can compose things when types match now the idea of matching types is super important and really somehow change the face of programming languages in the

last years uh I don't know how many of you are familiar with a functional programming languages but the whole name of the game there is that you create a complicated but expressive type system that basically doesn't allow you to do things that do not make sense so if you ever try to program in askal or Idris or agda or you know this typed programming languages in the beginning programming feels much harder because everything you do the compiler just like keeps bitching say sorry I can't compile I can't do this I can do that but actually the flip side of it is that you are taking these extra constraints that somehow force you

to produce more well-behaved code so um an idea of you know where you can use type driven programming in the right way is imagine that you have a car and you know this car needs some gas to run but in principle nothing forbids you to just you know pour water in the gas tank like physically you can do it this means you know in programming language terms that probably the type of the gas tank is too loose for the kind of task that that that thing should perform so basically you can feed conceptually incorrect

input to that type to to the process and basically make a mess so the take a message of this is that having refine type is important and when you know you play this game correctly you can have code that is more reliable okay so where does all these systems and processes stuff live the underlying mathematical theory that we use is something called category theory that is I'm not going to dive into it by all means but the idea is that category tier is exactly the super glue of mathematics it's basically the

mathematics of how things compose and interact relative to each other uh and since a few years ago officially since 2018 but actually goes a bit more far back um people started getting aware of the fact that category Theory could be applied in the beginning this thing was just used in the realm of algebraic geometry and you know hyper complicated mathematics stuff but now you know in the last years people realize that hey we can use these ideas in engineering we can use these ideas in computer science we can basically instantiate categorical examples of systems and processes and the idea is that again when you do

it properly when you define a relevant category of processes and systems you care about the idea is that when you compose things the semantic value of the things you are composing is preserved so basically you cannot compose Apple apples and pears together the reason why I'm telling you all this the reason why this is important is because what we do is Game Theory in an open way where games are conceived as processes that can be composed with each other and a fundamental question that we have to be very careful about is if I compose two games do I still obtain a game do I still obtain something that

semantically makes sense as a game and if the answer is no then there is no hope that this approach is viable because you could Define one little game Lego brick then you define another then you put them together and you don't know what you have so the reason why you know this took a long time to develop is that we needed exactly to get the mathematical details right so that we could be sure that you know what we were doing made sense conceptually Okay so now that I talked very briefly about you know this kind of preview of conceptual excursors of what we are doing what we

rely upon we can start looking at compositional Game Theory proper so compositional game theory in a nutshell is a formal language for a game theoretic reasoning is based on these ideas of systems and processes and ultimately category Theory and has been implemented into a software stack so you can actually use this thing it's not just a theoretical Gadget you can actually write code using this stuff okay so the idea is that uh the implementation is useful to model strategic interaction and allows you to analyze models in various ways it can be interactively it could be automated

tests it can be integrated with machine learning Frameworks and all this kind of stuff we can probably talk a bit more about that in question time afterwards uh again the idea the key innovation of this is compositionality this idea that you can plug games together you can compose games together into a bigger game the reason why this is very important for us is that uh basically one of the things we do is economic auditing so someone comes to us with maybe a spec not even code and they ask does my protocol make sense economically or I don't know can you provide me in

you know the market boundaries within which the market is interesting I don't know like defending the peg of my stable coin and then the problem is that when you work with a project so early in the product development cycle their spec changes a lot so having you know little game Lego bricks allows us to do quick participation because if you change one thing in your protocol I can hopefully only change that little game break in the whole complex game provided that the types around it stay the same and I don't have to redo the whole thing from scratch so that saves time and it allows

us to you know follow along with the project developing thing a team as they go uh and then the idea is you know when you go so early in the product cycle development cycle is that as you basically economically test a spec they can refine the spec and actually commit to turning it into code only when the spec makes sense so instead of doing you know a trillion interactions with developers that are probably more expensive you just get the step the spec right and after you know your shirt it makes economically sense you develop it and you implement it uh okay so as I said quick prototyping capacity

speeds up stuff and can be used into larger software Stacks okay so what is the main idea in compositional Game Theory we have some Atomic building blocks these are basically usually three things and these are decision decision is strategic decision so it means I observe something and I have to apply some strategy to do something then you have computation computation is like a non-strategic decision it means you see something and you just compute something without doing anything else without thinking basically strategically simple example is a function and draw from nature is basically random

parameters so if I have to model for instance a game where at some point you need to flip a coin that's where draw from nature comes in you can basically you know spit out a probability distribution of some sort to model these um uh yeah non-deterministic behavior and then you have two composition operations that are called sequential and parallel so this is the main idea this is our main building block uh the open game uh is that thing there on the right so the idea is that we have a process that as you can see looks a bit weird because it has like a forward direction from X to Y and a backward direction from R to S so

what is the idea the idea is this game G observes something from the past this is like the past and this is the Future IT observes an X from the past so someone the context provides an x to the game at this point the game has to decide how to act on this acts again this can be strategic can be deterministic but the idea is that the game says okay I saw X I'm going to give you a y now the idea is that when you are giving the Y you are sending the Y quote unquote into the future your why will have some consequences the standard example that I'll show in the next slide is in prisoner dilemma if

I decide to I don't know like rot out my um partner or not this will have different consequences determined by a payout Matrix so the idea is you act on the environment with a Y and then what in the environment will reply with an R saying R is the type of what happens how the context reacts to what you are doing Ms which is the quote unquote magical wire that allows for the compositionality secret sauce we were talking about before is basically you can see it as the consequences like imagine that you have some context here that is giving

you consequences to your actions you itself you yourself could be the context providing consequences for another game so this is where s comes uh from the area is you you do something the context tells you something in return and maybe you yourself have to you know piggyback to someone else's before you uh I will make an example in a bit but the idea is that you can compose these things so this is a standard composition when Y and R match you can glue these two games together again the idea is G observes X does y now age

observes y does Z some consequence Q comes to age age in turn basically sends back some consequence Type R which becomes you know R is basically the type of payoffs for instance so it becomes what G sees as a consequence of Y so again in this example age is the context for G uh G is acting doing why now age absurds Y and replies with r okay so let me yeah basically the idea is that you can compose these things and when you do you can obscure details in the middle and just represent this as a composite game

then you have another kind of composition which it's uh probably weird when you call it composition but it's uh the parallel composition so the idea now is these two games are not sharing anything they are happening in parallel and you are considering them at the same time so when you do that we say the composite game for instance observes something of type X1 and X2 imagine that we are just drawing a box around these two things you have two observation types two inbound types from the past X1 and X2 and that's why you know you bundle them together when you compose okay so example this is a prisoner dilemma in compositional Game

Theory you have two players these two players do not observe anything they just have to decide what they need to do uh betray or you know do not confess and then you have a payoff Matrix right the payoff Matrix basically observes the player's decision and spits out the payoffs in compositional Game Theory the whole prisoner dilemma can be captured by the composition of these three games these two players are acting you observes the actions and spits out the payoffs so as I was saying before you know the player one

payoff is actually the magic wire into the past of the payoff Matrix and in this example you can see that these two players will have strategic reasoning they will have a set of things that they can do and they will have to decide what to do you will be fully deterministic you will be a function it will just observe the actions and deterministically spit out the payoffs but then again what if I want to change this what if you you know I want to make you into a player itself that can strategically decide what to do and would pay us to distribute to the two

players well in this case I can just change this piece by and keeping these two pieces as they are or what if I want to represent the idea that uh actually player one observes what player 2 does before doing its action well I will just have to change player one and copy this wire and fit it there and now I have player two two acts player one observes this action and then acts itself so you see I can basically change things very modularly and compositionally without having to you know level up my projects and project and start again okay so let me show you how all this

stuff is actually implemented so we have a DSL embedded in Haskell uh the reason why we use ascal is because as I say this thing was based on a kind of mathematical theory that is very deeply connected with type Theory and so using functional programming and you know programming language with a strong type system was mainly mandatory for us to to be able to implement this thing without going completely crazy I think Jules can tell you a lot about this um it's pretty available if you go on our website that is 20 squares.xyz you

can just follow the GitHub link to the GitHub page you can download this thing and play with it and yeah we used it for sticking protocols token design order flow auctions Mev related business and all this kind of stuff so the idea is that in rdsl we represent a game a game in this way uh literally what you see here you have inputs feedback output returns which correspond to the wires in the picture and then you feel the game with some internals so uh okay these are the internals of the game so if you expand the internals of G here you will see this thing

so the first thing that you notice is that the inputs feedback output and returns wires are duplicated the reason why we do so will be evident in a bit it's because as I showed you here this thing can be for instance bundled up into a unique box right so the idea is that this is exactly what's happening here this is the outside box view where I only see the wires but in the internals I can have more boxes interacting with each other so this is why we duplicate the inputs so that we can represent the wiring and then we have the operation that is basically the

actual power a horse of of the thing so operation again can be a dependent decision so a strategic Choice it can be a function it can be a draw from nature or it can also be just another game so I can basically fill this thing with the box that I defined somewhere else so again this is the example of the prisoner dilemma as you can see when you compose things what you get is a box with no wires that's basically a theorem that says that when your composition has no wires whatsoever that's equivalent to a game in normal form that is basically a game in the traditional Game Theory sense

so that's why you have no inputs feedback outputs and returns wired this this pull block is representing this thing now inside you have these two things that are the two players again they do not observe anything and they have no feedback but they have an operation that is dependent decision and these two players have to choose between corporate and the fact and they output this decision y1 and Y2 and their returns are their payoffs uh and then you have the U-Box which is this one this one takes the two decisions output by the players it applies a function pay your speed

that is basically your payoff Matrix and Returns the payoffs as outgoing wires basically you can see that actually this thing is returning it as outputs so it's spitting them up into the future and not into the past the reason why we can do that is a technicality that means we can always bend a wire a wire that goes forward can always be bent into a u-shape and be sent backwards so that's why basically in a situation like that like this one the open games engine will automatically take care of the fact that these outputs must be piped into the corresponding

returns so there is some hidden magic that allows you to use this syntactic sugar uh okay that's basically it so um now some of the things we are working on is we're working with the robust incentive and the promo verification team from the ethereum foundation to actually interface this stuff with the ethereum virtual machine in particular with the agvm that is the implementation of the ethereum virtual machine in Asco that has been used by dub tools that is basically the I would say 0.1 version of Foundry for whoever uses that

and the idea is by using this interfacing as I told you right these boxes can be filled by strategic decisions but also by just by functions for instance in this case this thing here we say is a function the idea is with this integration we will be able to take smart contracts on chain State and all this kind of stuff and plug it into a box it will be a stupid box with no strategic content whatsoever which is exactly what you expect from the ethereum virtual machine like you provide some input and the ethereum virtual machine spits some output deterministically

and then around it you put strategic actors so imagine that you want to model some kind of Mev situation the idea is in here you will have some smart contracts you care about you feed it with a list of transactions that be have to be executed in order but now you can have another box before it and you call it mempool for instance or you call it coordinator and then after that you provide the players and now coordinator can strategically decide The Ordering of these transactions to be fed to the evm box so again the idea is that I can take contracts and that are non-strategic by definition they're just

stupid functions but now I can embed them into a framework that allows me to reason strategically about them so that's one of the things we are working on we are also working on extending the analytics uh in a way that is let's say more intelligible because at the moment like when you look at the analytics basically the analytics of our framework you know spit out other simulations or equilibrium conditions or stuff like that but the output sometimes is very complicated and we want to make it more manageable and yeah then we are also working on the some extensions of the theory itself of

the engine itself because there are things that are difficult that we can somehow do but it's not clear yet how to do them in full generality one example is repeated games repeated games are not super easy to to do um you can simulate them using like Markov processes or stuff like that sometimes but on always um other things that we can do I failed to mention uh is that our engine is by default Bayesian so you by default reason probabilistically you can do mixed strategies uh and you know basically there are an example of mixed strategy

is play this thing option a 50 of the time option b fifty percent of the time for instance and in that case your expected outcome will be itself probabilistic in nature basically uh this is very useful in order flow auction simulations which is one of the things that we are actively doing and we will talk about them later on in another Workshop where the idea is we are not focusing on equilibria because there are too complicated to calculate they are computationally unfeasible but we are focusing on simulation so the idea is I have some actors that are at some level in the Mev Foods chain and they ask how should I position myself in these order

flow market and you know what we are simulating is the expected outcome depending on what they do uh so yeah that's basically it uh um yeah I mean we have seven minutes but we can show some code but probably it's better to take some questions if someone has any uh um this may be a stupid question um but from the point of view of if you have a conversational composite com composition compositional uh modules and you keep adding compositional modules is there any idea in the model of like attention degradation so like if you

obviously you can have a game theory atletically perfect game but actually it's too complex for people to care about okay that is a really interesting question um so if I understand it correctly I think that one of the kind of axioms of game theory that is somehow not so obvious is that players are rational right and if I understand correctly what you're saying is that it's very difficult to stay rational when you are overwhelmed by information or maybe there is an equilibrium to the game there is some optimal strategy well it takes a trillionaire to calculate so you won't expect anyone to

do so yeah there are uh various ways to tackle this uh one of them is by using modified utility functions for instance or modified observations but by the way I think this is exactly one of the reasons why we are focusing as of late way more on simulations than on equilibria so I think order flow auctions are really a good example because auctions have been studied extensively in the literature so basically when you have a flavor of auction you go in the literature and you know if equilibria for that auction uh been worked out probably you will find it in the

literature is I think very difficult to find I mean there are but it a lot of auctions procedure have been worked out and if they aren't haven't been worked out it's because it's invisible it's there are some niches but that's a state overall but in order flow auctions you have these uh recursive thing where you know you have multiple actions taking place at the same time it's a mess basically and I don't think it's um to be expected to have a simple way of calculating equilibria there sometimes you can be lucky enough you can maybe apply like the revenue theorem or stuff like that and get away with it but there will be cases where that's not possible

and that's why simulations are useful in simulations I'm not telling you if your strategy is optimal I'm just telling you the expected outcome so you could have a strategy worked out with some heuristics and then you can basically see how much you stand to gain with that strategy um another small point about your question is that you have to assume you're not playing against people I mean there's tons of bots out there that run similar calculations to what we're modeling so yeah I mean attention is relevant when you consider a game in which people

play but yeah if you're running Analytics that's thank you very much for the interesting presentation here on the right on your left actually yeah hey here on the left on the left thank you so much for the interesting presentation the introduction to compensational Game Theory and I just wanted to ask what is the Assumption about the informational structure of the game do we have uh perfect information in order to compose those games even backwards and the feedback mechanisms to work what does the system or the game or one instance of the system need to know about the other instances so um basically uh the types here the types of these wires can be anything you want so in theory you they can really be

anything you want uh the way you model perfect or imperfect information is a by hacking on the structure of the types and B hacking on the wiring of the diagram itself so for instance if I want to model as I was saying before a situation where player one knows player two's action in this game before the siding itself the way I would do it is by copying this wire plugging it back as an observation to player one and you know taking this into account in in the strategy because now the strategy for player one dependent

decision will have an input that can be discarded so player one can say I don't really care but can also be used so in this sense you can model games where you know some players of asymmetric information they are aware of what our other players do they can actually lie so you could also have that you know player two has two different wires one goes into you the other one goes into P1 and basically this player's D is doing a but is telling player one I did B so you can model all these kind of things dynamically by changing the type structure and the wiring of the game sure yeah it's uh very unfortunate we didn't

see a demo but uh but generally it does this formalism then actually uh suggest or even generate strategies for the players because I mean of course if it's more like that you have a template such as a mixed strategy with two options and then it's more like find me the parameters that maximize expected value and and that's cool but uh like when you have a system that has a lot of players then then of course it's more like a Monte Carlo search in in some yeah parameter space type of thing okay there are there are basically three different modes in which you can use this thing the first one is simulate you give me a strategy and I tell you the payoffs the second one is

equilibrium verification you give me a bunch of strategies and I tell you if that's the Strategic Tuple is an equilibrium or not and a third one is equilibrium search that is I don't know anything find an optimal strategy for me now these things are ordered in how computational intensive they are equilibrium verification I think is linear uh equilibrium searching is like super exponential and horrible and simulations are quite fast uh now uh if you want to do equilibrium searching which is just give me the strategies uh the optimal strategies uh that's where you know we are studying Integrations with machine learning

protocols with machine learning techniques I mean you cannot Escape mathematics there are some theorems that tell you that there are Corner cases with games that are horrible and you can't do anything about it it will take the life of the universe to compute anything but maybe you can have a very clever AI that tries to guess heuristically uh you can use relaxed notion of equilibria like Epsilon Nash equilibria where you are satisfied when you are absent close to an equilibrium but another thing that you can do and that's also very interesting and then I think I'll wrap it up because we are going slightly out of time is I can have a game with a parameter okay and I have an equilibrium strategy that is usually

a protocol designer as an idea of what is the equilibrium strategy with this parameter fantastic we verify that that holds then we can start incrementing decrementing and tweaking that parameter until the equilibrium breaks and what that does it gives you the Bound in which that strategy is optimal so standard example will be stable coin some parameters related to the peg when everything is as intended optimal strategy for the player should be defend the peg if it goes down by if he goes upsell but then you start tweaking these parameters and you can observe that domino effect when you say okay Luna is like usdt USD is like 95 said I will go

up I'll buy 93 cents probably I'll buy 85 cents like this thing is drop everything and then you have you know this domino effect so in this sense you can try to quantify how solid an equilibrium is and this is also computationally quite easy to do when you start with an unknown equilibrium strategy so that's another way to use this stuff okay cheers [Applause] yeah yeah sure sure you already started answering um my question there so this is a lot of very powerful higher order sort of like um um Solutions capabilities

um and what about at the lower level because I'm looking at this obviously to explain it you have to use a very simple example that we all get but this looks like something I could script in Python so at a lower level are you just sort of like providing people with like a clear framework for defining what each of these modules are okay so uh like our workflow is the following as I said everything is freely available so you can just use it yourself when we do uh we call it economic audit because we don't have a better term for it basically what we always provide is a report but also the model so you get all the code of everything and you know this is very important especially for projects like in medland they have

sensitive information and like the fact they are giving you their real probability distributions or stuff like that their secret sauce so what we do is give us bogus data no worries uh as long as it seems sensible we make up the model for you and then you can run the analysis with the real data in-house we don't have to do anything you save your secret sauce and everyone is happy so yeah you will always get the model code uh when when we work absolutely 100 percent thank you very much I think it's the lunch break so bon appetit [Applause] so now the next one is 45 minutes right

125 yes okay so see you around 1 20 I don't know