Schelling Games and the Theory of Voting Systems

Transcript

everyone so my name is William George I'm a researcher for for the Claire's cooperative so I'm also gonna be talking about voting systems today but from like a completely different angle so I'm going to specifically talk about sort of how different election systems work in combination with shelling games so as I'm going to explain in a bit klaus is a blockchain based dispute resolution system that uses something called a shelling game and how sort of like the classical theory of how like vote aggregation like works in a shelling game context okay so describing sort of like how election theory voting system theory works for us I'll briefly recall how it sort of works classically and the

simplest voting system the one you're probably all the most familiar with it's something called first past the post or the plurality voting system and this is the like like like simplest voting system where you just have every person pick one candidate they want to vote for and then once everyone's voted you look at who which candidate got the most votes and they win even if they don't have a majority because they're more than two candidates and may only have a plurality they win anyway so this voting system can be problematic for a variety of reasons that have to do with tactical voting and vote splitting and strategic voting so this political cartoon sort of illustrates this if you're not familiar with this in the

1912 u.s. presidential election a former Republican President Teddy Roosevelt ran against an incumbent president like as it ran as an independent against an incumbent Republican President Taft and the result was that a Democrat got elected so you know these are the kinds of like pathological things that can happen when when you have plurality voting with more than two candidates mmhmm yeah exactly we'll do R Wilson okay so a standard solution to this problem is to ask voters for more information instead of his ranking picking one candidate instead maybe I'll ask them to rank their candidates so here we'll make my hypothetical voter has ranked the pink angel first the

yellow angel second and then sort of down the line there are some other non ranked ballot vote systems of social choice theorists that explored approval voting Jews moment down I'm not going to go into those but they also have this property that the voters are providing more information and then what can I do with that information well there are a whole bunch of different ways that I can aggregate that into a election winner so one standard classical process is that all I've signed points based on where I rank the candidates the person in first that I wrecked will get maybe three points the person Iraq second will you get two points and down the line this is called the border system another example people another system that people use is called Instant Runoff so here i've ranked at

the candidates again and now what happens is i after everyone's voted I wait and then I check how many first-place votes each candidate gets and whoever gets the least first-place votes they're eliminated they're gone so here imagine I put the pink angel first and my pink angel he came in last he's gone he's eliminated but then there's like another round I don't vote again but they react that I already made to whoever I ranked second so now my vote is just sort of flows to the yellow angel and you keep going like this until someone gets a majority and it's called instant run off because you simulate a series of run offs where there is one fewer rounds than the number of candidates this system is used for parliamentary elections in Australia

for example it's also used for the Academy Awards however there is a somewhat like a problem with this and there's this famous theorem of arrow a kenneth arrow that's all voting systems that are based on ranked choice voting have some tactical voting there are some situations in which i would be instead of us to put a ranking of candidates that is not what I actually want not what I actually believe in order to try to game the system so that a candidate I prefer will do better than if I'd voted honestly so that's it's kind of sad but you know that that's the mathematical reality and since so as an example for how the well like a situation like this an Instant Runoff these are the results

from the burlington vermont in the US mayoral election in 2009 so there was a democrat or republican the major candidates a democrat republican in this progressive candidate who's kind of the left with the dumber and then if you look carefully the results you'll notice that if a bunch of Republicans had ranked the Democrat first then the ultimate runoff between the last two candidates Anning would have been between the Democrat and the progressive and the Democrat would have won but instead because the Republican was in the last round against the progressive than the Republican lost to the progressive and these Republican voters based on their votes they made you can see that they had preferred the Democrat to the progressive so if they had voted differently they would have gotten the Democrats as progressive and they would have preferred that so this

is an example of tactical voting in itself so this applies to all ranked voting systems according to arrow and since arrows theorem social choice theorists the scholars who study this have basically looked at the different kinds of properties one I could have hope a voting system could have the kinds of partial resistance through strategic voting and they look at different voting systems and you basically have this like table of trade-offs so it's like some voting systems have some properties and other voting systems have some other properties and not any pre voting so no voting system can have all of them but you kind of pick the ones you need based on your use case and a few examples of those kinds of properties that are considered there's a property called monotonicity which is the idea that if I vote some way and candidate a wins and I

vote some other way where I move candidate a up Canada they should still win so that's a and there's a similar property for moving somebody down not causing them to win so that's voting systems like that are called monotonic not every voting system is monotonic that's one of the good properties you might want to have another voting system is another property is clone independence or clone resistance so there's a formal definition of this but roughly it says that if I have some similar candidates they don't split the vote the fact that I have three angels here does not make the devil more likely to win than if I just had one angel the devil hat is not more or less likely to win than if I had just a single copy of the clone okay so what does this all have to do with blockchains and

cryptocurrency and Claro's so the I'm gonna change gears a bit and explain to you exactly something called a selling point and how selling point vote point voting can work so a selling point is a concept that was introduced by Thomas Schelling who's an economist won the Nobel Prize that when people are trying to coordinate but they can't indicate between each other they'll sort of gravitate towards solutions that seem natural special or relevant to them so the example that shelling like to give was that if two people are trying to meet each other in New York City but they don't then try to be tomorrow but they don't know where and they don't know what time the natural thing to do the thing that empirically most people try to do is go to Grand Central Station

at Newton the information desk at Grand Central Station at noon if they're meeting in Paris maybe they would go stand under the Eiffel Tower with the idea being that the Grand Central Station is this sort of a natural meeting place people just like think of that as a place to meet so if I don't know where else this other person might try to meet me I'll go to Grand Central Station hoping they think oh it's kind of a meeting place maybe the other person think will meet the meeting place too even though there's nothing like intrinsically special about that place and then so in kleros where a dispute resolution system that's based on a blockchain crowd-sourced and basically what we do is we take a bunch of crowdsource randomly selected participants and we incentivize them to vote on disputes based on a shelling partner to incentive system so imagine I

have a small business owner Alice that hires the freelancer Bob to build our websites and she's not happy at the quality of his work the money to pay payment for the escrow was put into escrow for the website is to put into escrow and then eventually she's unhappy so she's like I want a dispute in chlorosis like a bunch of crowdsource jurors jurors are chosen and then they are penalized if they are inconsistent with how the other jurors vote and they're rewarded if they're consistent with how the other jurors vote with the idea of klepto like the fundamental idea of Claro's being that if I built not communicate with the other jurors and I analyzed the case and I think Alice is right I'll expect the other jurors it also analyzed the case and probably also think Alice is right so I'm gonna vote

for Alice because I expect other people to also grab the tape towards Alice because honesty is kind of a selling point in the absence of communication etc so you know like this juror here in the middle is like okay I've analyzed the case I think Alice is right the other two jurors are probably also gonna vote for Al's because they probably also think alice is right and then they all vote for Alice hopefully statistically more or less this should work on average most of the time so but this this voting is fundamentally different than sort of the classical democratic elections I want my candidate when voting system begin my incentives are totally different I no longer care about who wins I don't have a dog in the fight between Alice and Bob I don't like I'm not trying to get my candidate elected president anymore however there are basically I

just want to Mize my own economic return by my coherence payment for being right but could write agreeing with the other jurors but that you find that a lot of the pathologies that exist in classical voting systems sort of manifest themselves here and may be slightly different ways so if I look at the plurality voting system again well maybe am i maybe I have more than two choices maybe in addition to pay Bob and refund Alice the other choices that are put to the jurors in clouds these choices are sort of agreed on before there's a dispute at the beginning between Alice and Bob on the side of the contract but the other choice is to put it three rows maybe their choice is to give Bob more time give Bob a chance to like fix up the web side and work out the kinks so

maybe there was a choice to give Bob seven more days and maybe those opposed to give Bob eight more days and there was a choice to get Bob nine more days and I might analyze the case I think Bob just needs more time he can work this out but if I look at this I might say my so uh the the odds at any one of these more time options winning is really low because they're gonna split the vote between each other and this worse in the short of shelling point logic this thing was this dishonest choice here just refunding Alice just just is actually like distinguished now it's an it's a dishonest choice among the see of honest choices so I might gravitate towards that just because it stands out expecting other people to gravitate towards that because it's as out so like shelling point voting needs to pay

careful attention to these kinds of phenomena in Claro's so far all of our disputes have been sort of de facto binary did the gray that hadn't been like literally binary usually they like the other choices not beyond the top sort of two plausible choices are sort of like unlikely to happen unlikely to be chosen edge cases so and then furthermore plurality also sort of decreases your attack resistance imagine you know now the vote is putting em between the Angels and I'm as trying to bribe the voters maybe I only need to bribe like a third of the voters in order to get the most of compared to the Angels whereas if there was only a binary choice I'd have to bribe half of the people I have to do is sort of 51% attack what we call a 51% attack so 51% attack resistance is

decreased by by using plurality okay so what can we do so and we've done researched study what kinds of voting systems and incentive systems can work in a multiple choice scenario and a selling point system it's important to note that the voting system instead of system sort of go hand in hand before when I was talking about the incentives I just like oh if your coherent you'll be rewarded if you're in clearing or be penalized well what if they're like a bunch of choices what does it mean to be coherent if I put the final win or a second is that coherent enough so I'll hit on what that means in a multiple choice in Aereo and we want this to work even when they're non binary choices okay so our sort of candidate incentive system so we're using a we're planning on using a slightly more complicated

version of this but this gets the idea across basically like each voter will put in a deposit of little D and if they are wrong they lose a deposit that looks given by this formula so if I say that the ultimate winner is W if I put the winners second then I'll lose a little bit of my deposit but not very much if I put the winner third I'll lose twice as much as that if I put them second for three times as much and so on the voters do not write the options they're hard coded it they're like the parties that the disputes will create the options when they set up the like bit of contract they might eventually do this bit okay well so like my example with

like you know we want Clarence in the future to be able to handle like a wide variety of disputes that might have non-binary outcomes so my sort of toy example from before was give Alice like the refund hey Bob give like more time and disappered amount of time so that's already a non binary choice you can come up with like insurance contracts or like different parties money to pay and it might not be like a binary thing okay so and then once that like Alice loses part or like the voter loses parts of her to her deposit based on her how coherent or not she is that's redistributed using a very similar sort of set of formulas basically the higher-ranked I put the the winning choice the the more of the like loss deposit some other people I got and the more of the arbitration fees which were sort of put

in by the parties to pay for this dispute resolution process that are sort of paid in equally to the jurors based on how coherent they works the more of those again and then you can prove that under that incentive system if you believe that the outcome is independent of your vote which is a little strange hold on a second then you're incentivized to just rank the choices by how likely they are so I'm like okay I think the pink angel is most likely to win on ranking first I think this yellow angel the second most likely on ranking second so this gives you like like like if I vote like this this the voters are providing like a useful signal of what honesty is you would expect be able to turn this information into a good set of outcomes if you have sort of a good voting system

yeah yes yes yes so we again this sort of shelling point principle that if you believe that the other people are going to honestly analyze the case and the systems like incentivize to convince people to put in the effort in tahno analyze the case then they inter its benefits it's sort of a statistical property based on like I think people are going to gravitate towards this choice so like honesty like which should be the on like of the results of an honest evaluation most of the time in most cases particularly this sort of like low-hanging like freelancer disputes they're sort of semi subjective

but kind of partial the objective so if you want like this this is a deep question like Federico is like like doing research on like the concept of what is fair and the con and dispute resolution this kind of diffuse evolution and it's like what is honestly is a very broad question and I don't know time to go into that but and so like the idea of Claire's is that like honesty in this framework should usually be good like maybe they'll be switch cases where was not but it should be good most of the times provide acceptable speed resolution most of the time but you know it isn't it's not like an absolute thing yeah yeah so I need if I want to finish

our always on so so this idea that the outcomes independent vote like that might mean strange but if there's lots of voters like maybe I missed little one it's more or less independent vote also Clarence is an appeal system so the outcome might literally be independent voter there's an appeal because then I'm looking at sort of the fun I'll come in around that I'm not voting it and then so okay like I have that incentive system what kind of voting system can I use well I want to be clone independent for the reasons that I subscribed before I want like there's this notion of being like voting systems being a maximum likelihood estimator this is like a part of social choice theory that's been studied extensively in the context of like normal voting systems and I don't want to go to into too much into this

but it's basically the idea of like the voting system translating the noisy information with the voters honest votes into a sort of a good collective outcome I want the voting system to be easy understand the voters are trying to simulate how the voting the voting system was like process other people's votes and I don't want voters have to spend too much time thinking about the voting system itself I want a voting system to be tap resistant this is fundamental in a blockchain world anyone can spin up a smart contract in forest attack and you like need to be able to resist that usually that's like an economic resistance it should cost more to attack then you get ideally and we talked about how plurality have low attack resistance because it like lowered the cost a 51% attacks and then you have these kinds of trade-offs where like okay well some

properties are like load independent but do I have less maximum likelihood resist access to major properties some are have better or worse attack resistance and you try to pick a voting system that sort of like is good enough based on your knees and Claro's in the medium term is planning we're planning to use and still run off because it seems to meet a sort of like on average it works out to have good enough properties on most of these points but already Instant Runoff they're they're still voting pathologies here and so this is an example of a voting paradox in this situation where like before I made this point about like I try to rank I'm incentivized by the incentive system to rank my choices based on how likely they are to win assuming I think the vote is

independent the outcomes in defending my vote if I drop this into and into my vote like assumption like maybe it's the last round maybe I think I have the key determining vote in a close election then you get crazy stuff so here I'm like okay I want to vote the first choice to be the most likely winner but if I think the other voters are going to vote like this for some reason then if I think okay I'm gonna try to vote for a then see becomes the most likely winner okay okay I'll try to probe to see that B becomes the most likely winner okay I'll try to go for B then a it becomes the most likely winner so this you know it's like weird sort of whack-a-mole voting paradox and you basically construct this out of the kinds of voting paradoxes you have

innocent runoff in sort of classical elections you just sort of port them into this framework and in fact based on our research we've seen that there's like a version of arrows theorem in this world so for a precise statement of that sort of selling point based arrows theorem and a proof of that like maybe follow me on Twitter that will come out relatively soon but already you can cite of kind of see kind of how that might go with this example so everything's about trade-offs and picking something that sort of broad leagues have the blown works most of the time and minimizing the the pathologies so much done if I have any time for questions [Applause]

okay so you want the maximum likelihood estimator thing okay so this is the idea that if the voters submit noisy information like say hey say you believe that they're incentivized to be honest they might still be wrong this based on like statistical variation so they split in this like noisy vector of votes and but imagine there's a true vector that they see with noise and then being a mic maximum likelihood estimator it says that the voting system will output most well output the most likely vote like sort of an like a Bayesian framework based on either of the inputs that people put it so your voting isn't necessarily likely to like you know there's this like I have a true vote I

go to noise I try to like aggregate based on the noise and I hope to get the to Boyd vote back and the maximum likely estimator says that you actually do that you picked the most like yeah like a problem with sort of scoring

function based voting in the context of like the attack hostile world of blockchains or Debord ago is that people can like their bearing attacks where if I'm an attacker I can bribe you not only to rank the attacker choice like first but also to like berry it's like the closest rival last and then you get into these sort of like what you expect people didn't like ideally people would put all the honest choices at the top and then maybe the scoring function would work kind of well but there's the second to the center your question or right yeah if you just look at this and you're like okay one and two are pretty close and then the other ones here you

know like that also sort of increases the intellectual effort for the for the juror yeah yeah so I mean the like the there are other sort of tactical voting systems like like tactical voting questions with with approval voting and reasonable majority it basically come with how what's my threshold for like you know as usual image or tear you you put like okay this is excellent this is good this is not so great you rank that for each candidate with the proof of voting or like I approve or I disapprove and even people have different thresholds for whether something is like

excellent or it's just sort of okay and how you incentivize people to like how you build the incentive system to incentivize people to provide honest answers that are like attack resistant what do I do if my like some attacker is trying to bribe me to say don't don't put excellent just put okay like how do you like pick out honest behavior there's a like we would need a different incentive system and there are different tactical voting questions that are involved so that this is something we've looked at not as quite as much as the the ranked choice systems that it's possible that we like a system could be built out of that but in this context of trying to incentivize people be honest and rewarding them in a shelling way for being honest it does not seem as promising to us right now yeah I mean that's completely

different so much is so like one thing so there are questions of like how do I like if I have people communicating how can I like instance incentivize them to communicate include so the appeal structure is is useful in that I didn't get into quite of how Claro's works with with other reductive Appeals that you're incentivized to be honest with respect to an ultimate outcome so if I'm including the people in my voting round and then ultimately the people pick something else because like you know I wasn't able to effectively coordinated with them like me and although the commuters might lose because we pick the wrong the wrong side so in practice so for the moment these people are

basically ethereum addresses right yeah yeah yeah so like how good of protection the appeal system is for sort of anti collusion depends on how how much you expect like wrong judgments that could be appealed so this is another segment of a research you know it's obviously relevant to this but it you know there's like a rabbit hole there so thanks everybody [Applause] [Music]

[Music]