The Complexity of Agreement #RB22

um hello everybody this um in this session we'll discuss the complexity of agreement agreement is a problem which is tackled by many communities in social choice theory distributed computing theoretical computer science and and in this in this in this case it's it's a theoretical computer science approach on the asian agreement so it's um so based the discussion on a paper published in the symposium of the theory of computing um in 2005 by scott aronson called the complexity of agreement and it tackles the question of um two bayesian agents um trying to agree and and then you can compute how many bits of information they could share and and and and also um to reach an agreement and other problems of complexity uh theory in terms of either communication or or time uh maybe lay you want to tell us more about the paper yeah so the basic idea is that the two bayesians initially have the same prior so maybe they are born with the same file and then they collect very different data like you can imagine that one beijing is going to leave his life in one way like the other vision is going to live her life in a very different way so they call it very different data and because of this they have different uh posterior like so if you ask them for instance what is uh the probability that uh friends will win the next world cup then maybe they will disagree because they have access to different uh data so they said different probabilities like maybe one is going to say you're ten percent and the other is going to say uh 50 percent but maybe just so just so that people who are not familiar with beijing language follow with us like someone is coming from another community what do you mean by a prior so when when you say this base she has a she has a prior on the france winning the world cup or she has a prior or and then she changed her prior or uh and then she has a posterior so someone maybe like just like introduce this language to yeah uh yeah sorry about this uh so uh when you assume that an agent is beijing so an agent is beijing if uh he or she follows the laws of probability to determine what you think so it's like a fully probabilistic agent like you could win an invasion as probabilistic and uh to apply the laws of probability to know what you should think after observing some data you need to apply this equation called bezel and to apply bezel you need this prior so the prior is what you would think before looking at the data so typically initially like the two agents agreed that uh france had a like a ten percent priority for instance of winning the next world cup like the world cup in 2022 i'd say uh and uh and then as they uh as they get uh they collect more and more data for each piece of data essentially they're going to apply base rule so base rule is going to so it's an equation and it says how to compute what you should believe just after you've seen the data and so uh this posterior distribution is like an update it's a change compared to what you used to believe before looking at the data so there's this like update rule called the bayesian influence that's uh going to improve your belief in a sense now that you know the data and so you can imagine that if so let's call the two agents alice and bob so if alice uh sees uh no data or very few data or data that are unrelated to football then maybe she's not going to change her prior a lot like and so after years and years of of learning about mathematics and good stuff but not looking at football she will conclude that france has a 10 probability of winning the next world cup because that's what she used to believe uh maybe on the opposite side like bob has lived a very different life maybe he's followed the football carefully or or maybe not and he's like seen data about like uh this football player called mbappe and he's become very good and so and he sees that mbappe is like improving year after year and so now he given that uh the data that he has uh seen he's going to change his belief and he's going to say well actually uh now i believe that that france has maybe a 50 priority of winning the next world cup uh like he doesn't really decide to change like it's more like the laws of probabilities by applying the laws of probabilities he comes to this conclusion and so now imagine that alice and bob meet one another again and now they are in disagreement not because they were thinking in a bad way but just because they were exposed to different kinds of data and the question of about anson actually it's a question that came back from uh that date back to uh to allman i think it was 1981 i'm not sure like in the 80s i think uh 676. 76 in the 70s um so our man asked the question like will alice and bob agree if they get to communicate and if they uh yeah if they tried to agree on the probability that france will win the next world cup and uh arman's answer is yes they can agree and he has a very simple protocol which is like just share all of the data so alice will tell everything to bob so also i'm assuming that the the two bajans are honest like fully honest and they also trust each other fully uh and so if they share all of the data like alice knows everything that bob has seen bob knows everything that alice has seen and so uh applying the laws of probability forces both of them to conclude to the posterior distribution once all of these data the data of bob and alice are known and so they reach a conclusion so almond proved and it's actually a very straightforward theorem that two bayesians cannot agree to disagree if they had the same prior initially but what alman did not answer is what is like what if they had a huge amount of data so if you like in practice we humans uh collect huge amounts of data especially for after years and years and years and uh we cannot communicate all of these data maybe because it takes too much time if there are like a two about to be transferred maybe you cannot transfer this amount of data and so auntson's question was like suppose you have two agents that have learned from huge amounts of data maybe it's like even more than terabytes maybe it's like exabytes it's like huge amounts of data uh can they agree quickly without transferring most of or even hardly any of this data and the the like the the mind-blowing answer of anselm is that yes they can agree efficiently in fact uh the amount of bits of information they need to exchange is independent from the amount of data they collected so even if you have two agents that collected like as much data as the size of the universe as opposed to two agents that collected like 10 10 bits of data then the number of communication that you need to agree is going to be the same oh it's going to go down into the same way and this is like really mind-blowing like when i discovered this i did not believe it i had to read the proof to be convinced and then i had to re-read it to understand the proof but uh yeah it's a one of these uh very remarkable theorems uh in computer science and i think it has like like in terms of philosophy it's like a physical philosophical question if you think about this like it's like can we have communication like is communication can communication be made efficient to agree on things and here you have a very straightforward answer like a very competing answer uh orbital caveats of course because applying baseball is complicated in practice but it's still a strong indication that if we at least try to be bajan then we can quickly agree yeah maybe it deserves some more explanation on what what it means exactly to agree to disagree it's something that uh humans often do uh during a during debate like someone believes x some some other debater believes not x and then they they will discuss for some time and uh the the outcome uh often ends up being oh so you beat it x i believe not x let's agree that we disagree on the on that question but for for for bayesian agents uh it it won't stop there if uh beijing agent will not uh stop at you believe excited if not x and uh and let's agree that we'll be on that question because they do uh the thing called meta updating if you observe that a bayesian agent believes something different than what you believe it will update your beliefs because and it's something that we can also do in a in in real life with humans if you see a human that believes something different than you you push you to ask questions about what you what you actually believe are you correct is that person more correct than me so if it's a my professor at the university i will most likely update my belief towards what he or she thinks but if it's a something that has someone that has absolutely no credential or that i don't know at all i might decide to a lot less update what i believe based on based on this yeah so when when two bayesian agents interact and and know that both of them are high quality bayesian agents then they they are forced to to update towards one another that's why they it's it's not a regular according to bayesian agents to agree that uh to to be in a uh agreed to disagree with another asian agent yeah yeah and one thing that usually you can discuss as well is that the protocol the debating protocol between two patients who try to agree uh because it's like not what you would uh recommend to uh debate in general like uh you tend to think or debate something very sophisticated you have to push arguments and everything and reasons to believe and for the key data but the protocol proposed by by anson is like uh it's like it's funny how different it is from all of this essentially alice is going to say what she believes bob is going to listen to alice and say oh i i know that she believe now i know that she believes this and he's going and he's going to to do the meta updating you talking about he's going to apply baseball to update his belief and then he's going to say what he believes is going to listen update and and have a new religion she just says what she believes now and you have this back and forth where everyone is just saying what they believe and it sounds like a very bad advice for debating like you don't just say what you believe that the problem has been stated uh in like in a formal enough way so that you can compute probabilities and then you state like you just send a sequence of bits about what's the the the the object is and then you can choose the probability in a specific number so you just give me your believe in a precise sequence again and then number five computation and then i update my yeah but it is a good one because usually we debate about things and and sometimes the dividers don't even know what they're debating about uh anymore because like it's gone into all sorts of directions and it's useful to to just like make a concrete question i guess can we at least agree on what we debating about and uh choosing a probability uh i think is a very good way to just like remove all the the do like function the semantic debates or the things that are not really uh that important or that are confusing and just say well let's bet on what's going to happen in two years or something like this and what what what are the probabilities that the two of you are going to put and i think it can help to clarify a lot of the debates um yeah but then i'm not uh would recommend to do exactly well i would i think it's useful like you to just like everyone says what he believes uh but uh because we humans are not uh very good visions and not very honest and not very fully trusting on one another anselm's algorithm communication protocol may not be very efficient for humans in practice unfortunately yeah maybe another thing i can discuss is the proof uh of the of the of the or the fact that the tubasians will quickly agree in this case so like the exact proof like it's quite technical and the paper is a bit hard to read but the idea of the proof is actually very simple uh so the reason why this works is you can imagine um a third observer uh like uh eve for instance who's like listening to the debate and all she hears is like ali saying your number and then bob seeing another number and ali saying another number and so on and uh let's assume that eve knows nothing like oh all right let's consider like so he can be a fictitious just for the sake of the proof and eve has the same prior and she has no data and she just observed the debate now it turns out that there's a theorem in invasionism uh probability theory that says that if um if alice knows strictly more than eve then whatever ali says eve has to believe alice like that that's a very again it's very weird theorem if you think about it because like it's uh the argument from authority you could say and uh i guess it's a version of this uh it does require a few assumptions like constants alice and eve in this case must be bajan they must be honest and they may fully trust one another which are put on x in partic in practice but you have this theorem that says that uh from the laws of probability if alice has strictly more data than than eve and if they had the same prior and if they know that they know all of this like they then like at least knows that eve knows that uh ice has more data than uh than eve and and so on like he has to know that alice knows that you know this one and if you have all of this then it's a theorem that whatever alice says eve has to believe it and in the case of the debate between alice and bob when ali says well i believe it's 10 percent uh eve knows strictly less than alice at this point uh because we're assuming that she has strictly less data and so alice and so eve must believe what alice just said so he must say okay so now i believe it's ten percent and now bob comes in and bob says uh no actually i believe it's fifty percent consent uh it turns out that at this point eve knows strictly less than bob because what eve knows is no data and all the the first message that was communicated so eve only knows that alice thinks initially that it's absent but bob also also knows it because bob is listening to alice as well so uh eve knows strictly less than bob so now she should believe whatever bob says so if the debate was like ali said ten percent then bob say uh 50 then eve first should believe ten percent and then fifty percent and so on so then if ali says twenty percent then he should believe twenty percent if bob says forty percent then uh eve should believe forty percent and so on and so if you look at uh eve's beliefs now they're going to to go back and forth they're going to ping pong and there's another theorem that you can prove that says that a belief cannot oscillates too much uh so like the the sum of the the squared of the variations of the belief uh must be smaller than the balance of the prior like you have this theorem that you can prove and this shows that eve cannot oscillate forever like she she was more like the expectation of her but anyways uh she cannot oscillate forever so at some point she has to settle somewhere and if eve settles somewhere it means that because she she believes whatever alice and bob says it means that alice and bob are essentially saying the same thing and that's how you prove that alice and bob will agree yeah that was clear enough but i think it's really cool that it's also like a relatively simple proof i could explain it more or less it's very insightful i think it's very very deep yeah one point to note also about this uh this is that they they don't talk about uh exact agreement like having exactly the same beliefs because uh these could in some situations still require an exponential amount of time referring to when we talked about complexity but the data in the paper talks about uh slightly changed the definition of an agreement so it considers what's denta accident agreement which means agreeing with uh distance of epsilon so if if the two bayesian agents still disagree they at least that segment is within a very small difference of below epsilon and also the the the delta in there is that the protocol for agreement is not uh always sure to succeed and there is a small delta probability that the agreement won't succeed agreement that you want to agree up to epsilon with very high poverty but this probability of agreement can be made arbitrary high and the epsilon can be made arbitrary small so it's uh it's like a new agreement as close as you can get you to agreement without being guaranteed to achieve it um i don't know if you want to add more things on the paper but before wrapping up i wanted to go to how other communities talk about agreements because they were close to to know yeah and i also think it would be uh worth it to talk about uh federated learning and uh byzantine resilience and a distributed system in germany yeah so maybe before going through this we can mention another result uh of the paper uh which is uh what happens if you have multiple agents or elizabeth charlie and so on uh so if you have n agents and they get to communicate in some way like maybe alice can never talk directly to to today that she has to go to football or whatever uh then uh on and some prove that um in this case you still can still achieve agreement but it's going to take longer essentially it's well like i'm skipping a few details so it's not exactly what i'm going to say but essentially you need to have 10 times more uh exchange of communication rounds uh than uh than for the the the case for the only two agents and i don't know if you mentioned it but like essentially the when there are two agents the number of communication rounds you need to agree up to epsilon is going to be one over epsilon square so if you're disagreeing about the world cup uh french winning the world cup and you say okay it's fine if you disagree up to two to five to one percent for instance then it means that the number of communication rounds that you need is roughly of the order of uh uh 100 squared which is a bit more than that but essentially it's this uh so that's ten thousand and it means also that uh it's not going to be immediate either you still need to go back and forth so uh like communicate like agreement between patients still takes a little bit of time uh and um yeah it's not immediate however one thing that the paper does not answer it's left as an open poem is the question of whether there could be a more effective more efficient uh communication scheme uh than the one of our onsen or maybe you can even prove that onsen's key i think he proved that he could not be uh better than something but yeah so so right now there's a gap like in in our knowledge like we know that to get fcn agreement you need to communicate at most one over epsilon squared times but uh we know that it's going to take at least log of one of epsilon that's the number of decimals you want to agree up but we don't know the minimum number of communication rounds to reach agreement and maybe you see you can still have an exponential speed up compared to arlington's result we don't know yes louis so agreement in distributed computing yeah so it's interesting that the so the paper mentioned this agreement when uh there are multiple agents and not all agent can communicate with other agents and this is some uh some cases that is very useful in practice when we have a distributed system uh with each part of the system making observations about the world for example we can think of the recommender systems in a in today's world with uh social medias that they they are not controlled by one central server but they are they are absolutely distributed and this uh early servers have to to implement some algorithms to to make decisions in a coherent way with one another so so somehow this sort of agreement problems have to be uh to be solved and one thing we often discussed uh in this in this channel is also the the concept of byzantine resilience which is when you are a distributed system and you can't trust fully all the other parts of the system how do you continue to to do exactly what you want to do and you don't fail because of parts of the system that are working against you and so this is not mentioned at all in the paper and i i expect that the solutions from this paper won't succeed at all in in the case of byzantines malicious decisions malicious and delusion is maybe not well yeah so i think there's an interesting research to be done about uh byzantine beijing agreement or byzantine beijing learning in general maybe the last point is that so there is the distributed community approach to consensus and agreements and here there is like no no inference no updating of priors it's propositions and we want to agree on a value that was proposed so typically the consensus statement is that at the end the value that was decided is a value that was proposed so rarely you see like there are protocols where people update what they propose but it's mostly about having a quorum or a quota or like a majority proposing the same thing and then reaching agreements because they propose the same thing now the the third community that is also tackling agreement a lot uh is the community of game theory uh so social choice uh theory uh aggregation preferences voting systems you can think of voting systems as an approach that humanity invented to solve the problem of reaching consensus and the green and also this is maybe another direction where uh the toolbox of the asian agreement can bring new new interesting problems people could work on i don't know if they want to add this or something on this yeah i think yeah there's uh a lot uh to uh like these are three different ways but uh with different uh constraints to to to tackle the prime of agreement and all of them have interesting features and also like maybe you should combine the different features like some ideas from one side are like should be command because uh like there's a more overarching problem and so for instance if you take the case for for social choice that were voting uh in general one thing that we usually don't take into account when you're designing uh voting uh systems uh i've done research into this uh i know a little bit uh is that uh we usually usually assume for instance that the different agents know what they want and if you enter like if you combine this with more of a bayesian approach but the problem in invasionism is that people have guesses about what they want or what they think about the world let's say but they have uncertainty about this and this incentivity can can friction can change depending on the amounts of data that they have so for instance i think uh voting with uncertainty is an interesting research era uh another interesting research area would be like to combine a bayesian agreement with uh our bayesian like agreement uh with uh distributed computing uh in the presence of byzantines for instance and and uh and this is close to machine learning to distributing machine learning or things like federated learning for instance and also also you can try to combine all three together from often okay uh maybe you can wrap up the hopefully uh someone listening to this from either of the three communities could consider working on a problem in the intersection between strategy proveness in game theory or byzantine for tolerance and distributed computing and of course the asian agreement yep yeah okay see you next week see you bye