Algorithms for fair, manipulation-robust, and transparent sortition with Bailey Flanigan

Transcript

we're going to uh continue governance week I promised we would get uh increasing specificity on governance as we went and we couldn't be more delighted to have biley Flanigan here who will be uh joining the MIT political science department as well as the MIT CS Department next year uh Bailey please take it away awesome thank you okay hello everyone my name is Bailey um I'm a post at Harvard right now and I'll be at MIT next year my email is here um feel free to reach out to me if you have any questions okay so today I'm going to be talking about sortition um which is a way of kind of choosing political Representatives who will then make decisions on behalf of a larger population and uh my PhD is in computer science so a lot of this work is going to be pretty algorithmic in nature

despite the fact that a lot of the ideas the motivated are very governance related and founded in in politics okay so this talk is going to cover four papers I'm not going to cite them during the talk because it would be way too cluttered so if you're curious about where the stuff is coming from these are the papers where you can find the results um but here are my lovely co-authors um who some of them are on many of these papers these are all lovely people I encourage you to meet them at some point so just to give you like a little bit of flavor of what's in here these papers are like generally based in theoretical computer science so most of the results that I'm going to talk about even when I don't prove them are based on things that we've proven um a lot of the claims that I'll tell you

are also uh verified empirically in real data from citizens assembly so just to open the box a little bit on the foundations of what I'm going to tell you um because I won't have time to be specific about every single claim so the premise of sortition is very old it's just the idea that maybe in some cases we want to randomly select a subset of the population to be decision makers um for that population so what this looks like you're going to see a lot of diagrams like this you have a set of willing participants in the standard conception of sortition the Willing participants are just the entire population um and what you do is a uniform Lottery over the population just like choose every person independently with equal probability and whoever gets chosen winds up on what we're going to

call the panel which is the group of decision makers and what happens in a governance context when we use sortition is that this panel will then convene for like several days and they're going to learn from experts they're going to deliberate with each other and maybe at the end they vote or they come up with some kind of policy proposal this is not just like a theore iCal idea this model is being used right now uh around the world in things like citizens assemblies citizens juries deliberative polls I'm happy to talk to you about the Democratic applications of this more at the end if you want I'm trying to focus this talk a little bit more on the method of sortition though because I think it might be useful for the context of um blockchain applications to give you a little flavor of maybe how this

can be used I have some examples which Andy so kindly provided to me about how sortition is already being used in the blockchain in a similar way to how it's been used in practice so the optimism collective in 2024 ran a deliberative process that looked a lot like a citizen's assembly and it was actually run by people who typically organize citizens assemblies for governance applications so the connection is actually somewhat close I don't know a lot about the details of this process um but the question that they were answering I think is a good example what they were trying to determine together is how they should define basically a measure as a formula profit and so kind of the the high level takeaway here is like these kinds of processes can be

pretty useful for cases where you have to make subjective judgments that affect the whole Community it was also used in 2023 by Cosmos in a cicis assembly and this case they were thinking about what process and principles should drive um handling like chain changes to the atom economic zone just to kind of give you someone else's much more perhaps informed perspective on how sortition might be useful on the blockchain this is a quote from uh the Discord discussion on the optimism Collective about their process and they say that we think a deliberative process could be useful in setting Collective definitions and shared values preventing gridlock and coming to a collective consensus on complex topics so maybe this gives you a perspective on how it can be used I

think the use cases are perhaps broader than this um but that's something that we can talk about together so this was a little for into the blockchain but back into the world of theoretical sortition why do we even like randomly selecting a subset of people let's start there and from here we're going to talk about kind of the ideas of a lot of political scientists who have been thinking about this for decades in the context of governance so one reason that this is pretty attractive um here's a quote that reflects this idea is that when you do a uniform Lottery your panel ends up reflecting in expectation at least a cross-section really any cross-section of this population proportionally and we're going to call this ideal okay I have a little picture you're going to see this throughout the talk um showing that the composition of the group of

willing participant ANS which you know ideally is the whole population will very closely resemble that of the panel and we're going to call this representation it's the idea that the panel is like proportionally representative on key attributes but these asterisks here kind of indicate a catch which is that if your willing participants don't actually look like your overall population then representation you're really just representing your willing participants you're not actually representing the underlying population this will be like a motivating problem that will appear throughout the talk um so when we say representation we mean representation in kind of like a normative sense like there's some notion of representation that you kind of really care about and we're going to say that the process is

representative if it achieves that notion of representation not just like whatever arbitrary representation exists among the people who participate another idea is based in this like theory of allocative Justice it's the idea that everybody is kind of entitled to a fair chance to make decisions on behalf of the collective um and so we're going to refer to this ideal as individual fairness idea that people should all have an equal chance to be chosen and whether equality is really the right thing in the context of the blockchain it's unclear right because there's this idea that if you have more stake maybe you're entitled to more power and we can talk about that throughout the talk um but for now we're going to talk about individual fairness as giving people an equal chance to be chosen and throughout

the talk we're going to represent these equal chances using a diagram that looks like this so these here are selection probabilities and what that really is is for every person in the pool of willing participants each person has some probability of being chosen represented by the height of their Dot and the dotted line across the middle shows the average probability and you can see of course why a uniform Lottery will also give you this kind of trivially my favorite reason that sortition is cool is that the randomness can prevent manipulation or at least it can make it harder to manipulate this is like an idea that appears in a lot of areas of computer science kind of random makes it harder for a manipulator to really manipulate a system this is a quote from political science by Oliver Doan talking

about protecting the process from subversion um to unpack this a little bit into formal ideals we're going to break this down into kind of who can actually subvert the process because there's actually like two kind of parties that might be interested in doing that there's the people themselves who might get chosen you can imagine them paying each other to try to like you know impersonate other people and try to increase their chance of being chosen or you can imagine any manner of manipulation and you can also imagine that the organizers running the lottery could try to cook The Lottery by for example choosing a bunch of their friends and then saying this was random and so we're going to define the first ideal to address the first issue which is we're going to call it manipulation resistance it's the idea

that individuals who might be chosen can't influence anyone's chance of selection by misrepresenting themselves and you're going to see why misrepresenting themselves is for the Govern context kind of the relevant um kind of strategy space Bailey there's like I guess is it there's like another kind of manipulation which is like after you've been selected some outside force influences your vote and I guess I guess like historically I've heard of anonymity is like the potential solution to that like keeping the membership secret yeah that's what's done in practice in citizens assemblies typically but then you can't verify that it's representative right oh well okay actually that's not entirely true so if you care about verifying representation

on like the fine grain level of like vectors of attributes like or covariates then yeah anonymity is like ruined but if you just want to verify you know that half the panel is women half was you they actually do release that information in practice so you can at least kind of verify that it was balanced on marginal attributes there is I think in several ways attention um between kind of verification and other things that you might want so we can talk about that and then finally to make sure that that you know the organizers are not just cooking the books we want transparency and we Define this to mean that constituents can observe their chances of selection and other people's chances of selection we're going to kind of ignore this ideal until the very end so we should really just be kind of

thinking of the first three for now I mentioned this problem before um what if the Willing participants don't satisfy representation so maybe we have some kind of underlying reference population that's 50/50 dark green light green and the Willing participants are very very skewed I think this is like a very like scenario um and it doesn't have to be the case that we want perfect representation of the underlying population but we're just going to assume that that's what we want for now so what we would do in this case is we would try to enforce better representation so maybe we kind of use some sampling procedure you can use rejection sampling or stratified sampling whatever you want depending on the level of kind of complexity of your representation characteristics that you're trying to satisfy um and you can kind of force

that the panel has more of these dark green people but what's going to happen if you do that perhaps unsurprisingly is that you can no longer randomize equally over everyone it's just not possible no matter what algorithm you use because on average the light green people have to get a below average number of seats and the dark green people have to get above average and this gets worse the more you try to correct the representation away from what's available among those who are currently participating so here's our fundamental trade-off um and this little symbol here represents the fact that this trade-off gets worse and worse the more skewed your willing participants are in comparison to who you actually want all right so this is just like a fundamental trade-off and why is this bad well it turns out that

Lottery equality is kind of like a very important determinant of our other ideals that I originally laid out for you so if you remember individual fairness we wanted to give everyone like a fair chance but clearly we cannot do that right and I think one of the biggest concerns here are these really low probabilities because if we think that everybody is entitled to some share of the chance we're just really worried about people getting short changed yeah this is obviously correct um I don't love this expost definition of representation like it seems to me like um I if I know all the covariates that matter it's fine to say that there's

this Expos notion of representation but I think one of the reasons we think that we like um this kind of system is that we actually think we don't know all the characteristics that matter for for opinions and we don't want to have to pick and choose which covarius we want representation because that has all sorts of problems um and that we that we want something more like an Exane notion of representation where we don't have to commit to to expose characteristics that we want balance on and then we want random selection and then of course if the pool of willing participants is not is not a random sample of the pool of the like that's just a fundamental problem we can't fix but this exact trade-off really rests I guess like on this expost notion of representation

which feels to me like it does a little bit of violence to the motivation for lrac in the first place okay that is like an absolutely excellent point so okay right so let's say that we just if we say you know what we're just going to accept that our representation is just going to be as good as it is among the Willing participants then you're totally right you basically replicate the perfect intersectional representation of everything you know and everything you don't among the Willing participants the reason that that doesn't work in practice and the whole motivation for this work is that if you actually ran a Citizens assembly like that based on Who currently participates it would be so incredibly skewed toward people who are Highly Educated people who have more liberal opinions that people wouldn't

really trust the outcome and so for now for the current practical purposes we kind of need to do something to correct the selection bias now there's a few like pieces of good news Maybe which is that if you have some understanding of how the observable covariates correlate with the unobservable covariates in your will set of willing participants and there's reason to believe that you might there tends to be patterns and who signs up you can try to design your exanti or exost expose probably requirements um to try to kind of drag along the representation at least to some degree uh to whatever extent is possible so we are actually working on that right now because we're super concerned about the unobservables um but I'm not not sure if it's possible in practice right now to just throw

representation out the window you kind of have to face this trade-off to some degree I think does that make sense yeah I'm sure that's true yeah you don't have to be satisfied it's all it's your call but I think that this is kind of what the what practitioners have told us is is important to them yeah so I I'm I'm not following what's the end goal the end goal is to have a panel that represents the actual population is that the end goal or is the end goal is to have in the willing participants everybody gets a fair CH these two seems to be very different yeah in fact they're exactly intention so what you're describing is kind of like two ends of of a tradeoff right maybe the goal should be to just get perfect representation to the best degree you can and say whatever about the

probabilities or maybe you might want to just care about only the probabilities and just ignore representation and why would any anybody care about the squl probability well we are just about to talk about that right now okay okay so the first reason um has to do with kind of this entitlement to a fair chance right it's kind of if you think about like the really extreme case where you set such tight quotas that like most people didn't even get a chance to participate at all like you just couldn't you couldn't accept them then it wouldn't really be like a random process at all right because if you if there's maybe only like one subset of the entire population that fulfills all of your requirements it's barely random and that would be considered undesirable

by some people who do sortition so that's one reason that you care but I think there's a much more important reason that you should care which I'm about to tell you right now okay so in Practical processes like this in order to actually enforce representation we need to ask people to report their attributes so if you want to you know enforce representation on gender race age whatever you have to you have to ask people those things because in practice practitioners do not have access to kind of like individual level Census Data where they can just say your person number 708 whatever here's a letter come participate it's more like they just send out a bunch of letters and whoever shows up they have to ask them who they are and you can verify some things like geographic location probably age to some extent but it's pretty difficult to

verify a lot of attributes that you care about at least in the Democratic context where you might want to stratify for example on beliefs about the issue right if you're a person who is skeptical of climate change you probably aren't going to trust a panel on climate change unless it actually con contains some climate Skeptics there's attributes that are pretty difficult to verify and you have to ask and so what can happen is that people can misreport who they are so in this example suppose you're one of these light green people and you think to yourself you know I bet taking the climate change example if the light green people are um people who are really like they really care about climate change right they would be super over represented then among those who participate makees sense they might say you know what I bet people who are not

concerned are not going to show up I'm just going to pretend to be one of those people and now you have a new instance with a slightly different pool of willing participants and this person has gained a pretty significant amount of chance of participation and I think even more concerning than that this probability if it's pretty high means there's a pretty high chance of actually choosing this person and if you choose this person they've stolen a seat from the dark green group right because they're not truly in that group so there's like multiple incentives to manipulate to try to steal seats maybe someone pays you to try to get on the panel there's all kinds of kind of schemes that could be cooked up um as soon as you can fudge your characteristics does that make sense all right so this is why you also have to

worry about determinism in selection right because as soon as there's some people who are being selected as deterministic other people might try to impersonate those people and I don't know if that's possible in the contexts that you study right there's so much more verification going on there that's the idea so this is why in the practice of governance you really care about the selection probabilities in addition to the representation does that answer question okay any more questions all this is just a quick question on like it seems like there is one other margin here for trying to avoid this tradeoff which is if you have the ability like making it worth people's time to do this paying people to participate which was a key part of meta's community forums like the pay was pretty generous if you could

pay everyone infinitely dot dot um then presumably you would get willing participation from a very broad set of people in then you wouldn't have to um go down these other roads right you're 100% right and the algorithms that we're going to talk about will just like improve optimally as the representation of your willing participants gets better so they'll take advantage of improvements but the other thing that you have to be kind of careful of is if you increase the payment somewhat but you don't increase it far enough to get rid of self-selection bias completely you have now really increased the incentives to manipulate right because if you're going to get paid a lot it just strengthens people's desire and

this has actually happened in practice there was like some Sweet incentive for participating I can't tell you too many details um because the practitioners like don't like don't want the details like public but there were like documented cases of people just kind of trying to impersonate other groups as much as they possibly could to get these incentives so it's a it is a good solution but you have to be careful and you probably have to have a lot of money okay so we're facing this fundamental trade-off between the ideals that we originally wanted and a very natural question which is kind of getting at what you were just saying is how should we make this tradeoff but that's actually not the question that we're going to answer today because that is really hard question so we're going to answer a different question how can we

design algorithmic tools that allow us to achieve any trade-off optimally and this is useful because different contexts will probably require different trade-offs so that's going to be part one of our talk is I'm going to introduce an algorithmic framework um that basically tries to perform panel selection in a way that strikes any trade-off between between these two things optimally and then in part two we're going to talk about how do we actually deploy this framework which is going to be like very general um to its full potential where we will talk about how to actually use it to achieve these two ideals that we cared about in addition to representation and then I will revisit um some potentially useful extensions for the blockchain context all right so at a high level the algorithmic framework intakes a set of willing participants and it's going to

Output a panel it's going to enforce representation which I will formally Define in a second um as a constraint so that's going to be like exp poost guaranteed whatever you input as your representation requirements it will be 100% chance the panel will satisfy them and subject to those constraints we're going to optimize the equality of the lottery which means we're going to make people's selection probabilities as equal as possible to formally specify this framework I have to tell you what I mean technically by both of those things so when we talk about representation we're going to permit practitioners and users to set quotas which can be any inequality or equality requirements on any group that whose attributes you can observe so to give you an example maybe

we're selecting a panel of size 20 and there's two categories of attributes the region that you're from north or south and your political leaning left or right so if you were to impose like the kind of representation that you would impose with actual stratified sampling you would do this you would look at every disjoints like combination of these ATT attributes and you would set precise representation Targets on all of them for now we're just going to say that the ideal case is that they're all equally split okay this might be good and you can do this with our framework but this can be very tight right this can be super restrictive and you can't really add that many attributes until maybe your panel just even isn't big enough to satisfy all of them and so sometimes and

what practitioners often do is they'll set like looser and more complicated characteristics that try to loosen up the problem a little bit while still maintaining like substantive representation so you might for example say okay I needed to be 50/50 north south and I'm really concerned about the combination of people from the South and people on the right and for people on the North and the left I'm just going to make sure there aren't none so you can choose any configuration of requirements that you want of this form okay so then when we talk about what we mean by optimizing Lottery equality we're really talking about something about the selection probability and specifically what we're talking about is we want them to be as equal as possible According to some function f

which is any convex mapping between these selection probabilities and some real number telling you how equal they are okay so f is like an equality measurement and a simple example of this would be like the L2 Norm so you would take like the L2 Norm distance between all of the selection probabilities and the average that would be an example of a valid equality measure so manipulation resistance went away from this discussion totally the framework is basically just thinking right now about representation and Lottery equality broadly then we're going to talk about how to use our definition specifically of f right because remember manipulation resistance and fairness were properties

conferred by the how kind of the selection probabilities look so we're going to think in the next part about our choice of F and how that impacts those other two ideals does that make sense yeah it's not obvious that that's the same as optimizing them together right so you're going to you're going to first like you're going to sort of lexicographically care about equality and then you're going to say within you're you're like going to first lexor graphically care about representation then lexor graphically care about uh selection problem about equal probability and then care about yes exactly so we are kind of in some sense privileging quotas that it's more of like a practical Choice than anything else

because like it's it's basically related to kind of how practitioners were already doing things but you could in principle think about doing it the other way and kind of choosing some measurement of representation on the quotas and then fixing some level of equality as a or something in between I mean there you're you're making very Stark assumptions about like kind of what the loss function you're optimizing of right you you could like you're imposing what the what a very Stark trade-off between these two things by the order in which you're doing it and you could choose another trade-off between them that's in between the doing it one the two lexographic options absolutely and actually the framework will kind of allow you to do something like that so

the I'm sort of presenting the framework as it is first and then we can kind of talk about the ways you can use it to flexibly demote or promote the importance of quotas like they are a hard constraint but because you can set them any way you want they're ways to kind of explore the space of possible constraints and see at least what equality you get in a smart way so you're totally right to point that out but I don't think it's the framework is so flexible that you can use it in a way that's similar to what you want um but yeah it's it's also for technical reasons um that that we do this okay so now I'm going to give you like a little bit of insight into how the framework actually works I won't go into this too much because I suspect that in your

applications the quotas that you're going to probably want to use would not be over that complicated of attributes and this framework is really designed to handle pretty complicated representational con like constraints and so it's possible that you might be able to use like a simpler algorithm um some of the considerations like for fairness and manipulation or whatever might still be useful but I won't go too much into how we handle like this pretty nasty combinatorial structure because it might not be that useful for you but I'm happy to take questions about it okay so the goal here is to control the selection probabilities and we're going to control that by controlling something called a panel distribution um and so here I'm just going to ask you for now to suppose

that you could write down every single panel in the whole world that satisfies your quotas you can't but just suppose that you could so that's any subset of participants that satisfies the requirements a panel distribution will be a distribution over those panels okay and we're going to sample that distrib to choose our final panel so we're going to compute a distribution and then we're going to sample it and you can see why that will immediately guarantee the satisfaction of the quos because everything in the support already satisfies them there's the little symbol saying that we're going to sample it okay so a very good first guess is that why wouldn't you just want to uniformly randomize over all the panels in the world let's see what might go wrong suppose we're looking at two people in our willing participants our blue guy

and our yellow guy the blue person here is only on the first panel and the yellow person is on all the rest if we use this panel distribution the selection probabilities that we get are going to give the blue person almost no chance of selection and the yellow person almost one right because they're on almost every single panel and so what we can do to fix this is we can design like a slightly smarter panel distribution we can just tune it a little bit better so that it balances the selection probabilities of these two people and this is really the intuition we're going to tune the panel distribution and recognizing that each person's chance of selection is just the probability of drawing a panel that contains them this allows us to control the selection probabilities yeah is there an intuition for how you would get

to a scenario where the the blue person was way less likely to be on a panel that satisfied all the quotas is it cuz they're like they don't count toward any of the quotas so it's hard to meet all the quotas with them involved that would be like a very simple case where it' be a problem I actually think the more interesting and like the more practical case is where there's pretty nasty correlations between attributes that you're controlling so you know maybe you have some like upper quota on some attribute and an upper quota on some other attribute and or maybe a lower one and there's just like only a very very specific combination of people who can satisfy all of those constraints at the same time and so then everybody else who might be used there wouldn't be able to

be included or something like that so it's more about the correlations between the constraints rather than just like individual constraints at a time does that make sense it's it's like actually kind of hard to think about when I started this project I found it really difficult to think about so this is the idea we're going to this is how the algorithm works it finds an optimal panel distribution in the sense that the panel distribution Tunes the probabilities to be as equal as they can be for the choice of convex equality notion that we're using but of course the actual problem happens here because we can't actually compute the entire support of this distribution now I'll give you like a one- slide description of how we address that problem so why can't we compute all of them first constructing even one of them is NP hard

um so finding any panel that satisfies your overlapping demographic requirements um it's kind of like set cover um so it ends up being NP hard but the good thing is that we can use general purpose computation tools to like find individual panels pretty fast um and these tools in particular are integer linear programming so what we're going to do just to give you like a sense of what this integer program is is we're going to have this Oracle and we're going to say to it okay find me a panel that satisfies the quotas and it's going to give me back some integer indicators one for every person in the Willing participants encoding whether or not they're on the panel that it CHS all right so these these constraints here are basically just going to enforce that

I get a valid panel back we can also because we're doing optimization we can tell it to find like a specific kind of panel it doesn't just have to be any valid panel and we're going to use that very specifically in the framework I'm not going to explain um exactly how though but this is the integer programming Oracle that we're going to use to call and find our next valid panel so just to be clear the the ILP objective function is not your approximate equality objective function right that just something you tune to generate like more panels as you yeah okay you'll see the framework all together and you'll see kind of what it's doing so the problem as thus far described is like super similar to the problem like an experimentalist or a

sech survey researcher would face and they would just do come some sort of really simple Block randomization M what are they missing can you can I ask what you mean by block randomization do you mean like stratified sample yeah they like they they' stratify their sample with covariant and then they'd randomize within them and then they done so back in the example before when I showed you those toy example of the quotas the first example I gave you was exactly that you basically Define disjoint groups the problem is that in practice practitioners want to Force representation on like 35 attributes at once and their panels are only like a 100 people so if you had to Define disjoint groups from which to sample you would have so many disjoint

groups that you wouldn't actually be able to like you wouldn't even be able to divide up the available people you're saying they'd have a bunch of empty cells they would have a bunch of empty cells well let me think about the empty cells you're saying no that's not what I'm saying I'm saying that if you have a hundred people and you're enforcing representation on combinations of covariates which is what you get when you divide people up into disjoint you basically won't be able to be representative on all of the combinations of covariates at the same time because you just don't have enough seats available on the panel so you might do something like what they do in matching where they Corson okay but as soon as you're cooning right you're

losing the representation that the practitioners actually would want in practice and so what this problem you you can't have the representation they want in practice right because you've only got 100 seats and you've got more sub subgroups than that okay so in practice what they care about is just something a little bit different than what is achievable with stratified sampling they want representation on gender and they want it on age but they don't always care about having it on gender and age at the like on every combination of gender and age and so in some sense what this allows you to do is Define like more flexible overlapping attributes um but the problems are actually not totally unrelated because sometimes in survey sampling you do impose quotas like these um and theistic that they're using I'm guessing look

like theistic that people were using for sortition and they tend to have pretty bad properties um so anyway I'm actually working on that right now so I'd be happy to talk about that more um when you say impossible is it just exponential I mean is it is it possible with infinite time no I don't mean computationally impossible I mean that if care about representation on every combination of like let's say you've got five categories each of them are binary and you care about every possible combination of those attributes right you're going to need a lot of people on your final panel to ensure proportional representation of every combination of

attributes because there's just a lot of combinations maybe you have a lot of empty cells in which case you're okay but if you don't then but what what goes wrong wrong with the trivial algorithm of just enumerating every subset of people and putting it into a bin either like it it's a valid panel or it's not is there not a function to determine if it's valid or not oh here you're you're asking about this yeah Oh I thought you asking an extension of this question sorry unrelated question good oh yes this is computationally yeah if you had infinite compute you could do this for sure oh yeah okay sorry got it that must have been a very confusing answer to your question the first time yeah yeah totally okay good I'm just happy to discover the computer scientists

distinguish between impossible and possible with infinite computation I wasn't that's new to me I like that a lot yeah yeah it's totally totally um yeah that would have but it still wouldn't have saved us a lot of time all right so all right so you can't find all of them so what do you do right because a priority you might need to find all of them in order to Define an optimal distribution right you may need to place non-zero probability Mass on every panel to achieve optimality but the good news is that actually that's not true that's like kind of the first Insight that allows us to do anything here um using kodor theorem which is like a theorem from geometry and you're happy to talk about the intuition here after the talk um it

turns out that there exist an optimal panel distribution over only very few panels so we can find an optimal randomization in other words that assigns zero probability to almost every panel that could ever exist where and sorry I should clarify n here is the number of willing participants and that's in practice like about a thousand or something and this is like billions and billions and billions okay good and optimal here you're back to your L2 objective functionally about optimal yeah exactly or any other objective function yeah any that you choose that's right okay and the reason for this at a very high level is that even though there might be a lot of panels you have this like really nice special structure in this problem where the objective

function that you're actually wanting the distribution you define to optimize is over a much lower dimensional object of length only n right it's the vector of selection probabilities that you're giving to people so it turns out that you don't really need that many panels to randomize over in order to achieve an optimal randomization with respect to individuals probabilities and that's kind of the essence of like kodor theorem so now we know that there exists an optimal distribution over a findable number of panels but we still don't actually know how to find them because kodor theorem it just tells us they must exist they it doesn't tell us how to find them this is actually the technical contribution of our algorithmic framework and this is the part where you actually use this linear objective in finding panels in basically a smart

order and also deciding when to stop when you've achieved an optimal distribution to give you an overview of the actual framework you start with some support these little squares right here are panels you can just sort of arbitrarily generate an initial set of panels and you're going to compute the best possible panel distribution over the current support which might not be optimal and then you're going to ask for a new panel and you're specifically going to ask from that from the ILP Oracle and the way that you're going to use this objective is to basically say find me the panel that adds the most equality to this distribution it allows me to increase the equality by the most then we Define a technical condition which I won't go into here um but if this

technical condition holds then the algorithm terminates and we can prove that if the termination condition is met then the set of panels you've found so far is sufficient to be optimal and this is this is what really requires a proof in the framework and if it's not met we add the panel to our current support and we repeat the process until we need the condition this is how the framework works this is basically column generation if you're familiar with um optimization so like in principle you could do ellipsoid method to do this I would think in theory right but I don't I don't think so because they tend to be duels col generation yes it they are duels but the the challenge here really in using off the shelf column generation methods is that the the program is convex it's not linear and so we ended

up using like kkt conditions to define the stopping condition I don't think the ellipsoid method would work if condition holds terminate that's where convexity gets used is in that statement yeah exactly you're so you're basically solving the Dual and in the Dual program each constraint corresponds to a valid panel so you're adding a con you're adding a valid panel which corresponds to adding a constraint and then you're checking some condition and if the condition holds then you can be certain that the kkt condition I which are sufficient for optimality are satisfied and then you can just basically infer the rest of the values of the Dual variable or the Primal variables yeah that's my guess is you could do with a lip soory but this is much more practical yeah very POS I mean right that might have been why we didn't ultimately go with that um yeah I don't

remember exactly okay the bad thing about this algorithm is that it has absolutely no guarantees in the worst case on how many panels you have to generate because it's using a heuristic to find the next panel but the good thing is empirically you only have to find about n plus like 150 panels and so and it's a thousand it's like 1,150 not too bad and do you think is that is is that because there is a theorem that says it's always good and you have improved it or is you think there's a big difference between worst case and average case behavior of the algorithm I think there's a huge difference between worst case and average case so you think in the worst case it could be really bad yeah okay I'm not sure though okay um but I yeah I have no reason to believe

that it's good in the worst case yeah um Okay so that is the framework the idea of the framework is that it allows us to make kind of pretty generic trade-offs between representation and Lottery equality and representation we now know is defined according to quotas which are imposed as hard constraints and Lottery equality which is measured by some convex function it's not any possible trade-off as you pointed out because we are sort of privileging quotas as expost constraints then the question is how do we actually use this framework to its full potential so the first question is how should we choose F and this is what will determine the extent to which we can achieve our other two ideals how should we design the quotas this is like a huge question right because the looser we

make them the better we can achieve Lottery equality and we can just move along that trade-off in that way and then finally I had mentioned before transparency the ability for people to understand that the process is really random um so I'll briefly touch upon that also our choice of f is really going to determine the selection probabilities which determines the extent to which we can achieve these ideals so the first choice of F that was investigated um was presented in the original paper that proposed the framework and it's really its main priority is fairness so if you recall when we think about fairness we're worried about short changing People chance of selection and so we in this paper defined F to just be the minimum of all the selection probabilities and we just use the framework to maximize

the minimum this does great unfairness if you think about defining fairness as the minimum like pretty trivially that's like the definition um but we found out kind of several years later um after defining a game theoretic model and thinking about how people might manipulate it that it's like super super manipulable and the reason is kind of simple it doesn't really care about controlling High selection probabilities and so if you can guess what combination of attributes is going to allow the algorithm to increase the minimum and you report those attributes the algorithm will just drive your selection probability all the way up in order to increase the minimum further and so you can empirically even in real data gain probability one like pretty reliably by

just misreporting um like really simple combinations of attributes that you'd kind of guess okay so that's not so good but it still like was better than the state-of-the-art this is deployed um and you can actually use it if you're interested on panel out.org so it's open source feel free to check it out to address the manipulation resistance problem first in theory um we tried a different objective which was just minimizing the maximum probability which kind of makes sense right you're worried about high probabilities so just drop them as low as you possibly can this turns out to actually optimally mitigate manipulation but the problem is that it's just super unfair right it doesn't care about low probabilities it just drops them to zero so it's not practical it was never deployed um because yeah

when you defi when you talk about manipulation resistance this means you're measuring this as the size of increase in probability I the worst off person can get from we consider three definitions that's one of them the very standard game theoretic definition another definition describes utility instead of as the amount of probability you gain just as the amount of probability you have after manipulation so instead of post minus pre it's just post and the reason that that matters qualitatively is because that's the chance of you stealing a seat from the group that you've impersonated so that's a different utility function and then we consider a third utility function which is how much you can decrease anybody

else's chance of selection so that would be anybody else's is pre minus post okay and this optimally mitigates all of them so I think like a game theoretic definition is a little tricky like a question you might ask is assuming people can report whatever they want what is the equilibrium under the algorithm that seems like the natural game theoretic way of thinking about this we originally thought about that I think there's a few reasons that that ultimately was not what we went with the first one is that in practice you wouldn't expect most people to manipulate I think typically based on anecdotal evidence from practitioners it's like a small fraction of people are willing to manipulate you could still

consider some kind of equilibrium definition though but the other thing that happens is if you've got for example everybody is misreporting even if you kind of characterize an equilibrium as like what will they end up misreporting how much will they end up gaining my suspicion is that everybody will end up getting about equal probability because as long as there are gaps people will exploit them but then your guarantees are basically meaningless because everybody has misreported your rep yeah and that so I think that that is a very damning negative theoretical result but it's also probably not that practically relevant because it will not be the case that most people are manipulating and So based on our discussions with practitioners about their impression of how people manipulate we consider them

more of like a I won't use the term I'll just describe it basically if you think everybody else will be truthful and you have some basic information about who's going to show up how much can you gain by manipulating the Strategic types are small in the population relative to the almost everybody's a truthful we basically just we we characterize the um our bounds handle like coalitions of varied size but we just basically assume that the Coalition or the individual assumes that they're the only people manipulating that's the idea but I agree that the equilibrium is the most natural thing to characterize um in from a theoretical perspective okay okay so the obvious question then is like to what extent can you get both of these things

can you control the bottom and the top at the same time um and this is a recent paper at EC this year that introduces a new choice of f which kind of does maybe one of the first things you would try it just tries to optimize a combination of the objective of the maximum and in this case one over the minimum probability so it penalizes both low Minima and high Maxima at the same time it turns out the functional form one over here is kind of important if you combine them linearly or you use the log the gradient is like isn't strong enough and you can't achieve as good of tradeoffs I'm not going to go into the details on that um but it turns out that this trade-off here so this basically strikes an optimal trade-off

we prove and this tradeoff is actually very weak empirically it's pretty strong theoretically like you can have cases where there's just a fundamental gap between the minimum and the maximum but empirically you can actually achieve almost exactly the fairness of this algorithm and the manipulation and resistance of this algorithm at the same time using this objective at least in the data that we have so that's kind of cool and this one actually has been deployed it was just deployed for the first time in Canada I will briefly talk about this all right so how should you design the quotas it's kind of simple you have to choose the groups and you have to choose the constraints sounds easy enough um but it has a kind of like a lot of complicated implications that we still don't really understand and

this is what we're working on right now the most obvious one is that there are like Downstream impacts on the quality of the process that depend on who is in the room this is like a much more qualitative question there's also like technical implications on the quality of the lottery if you loosen the quota the lottery can be more equal some options here would be to try to flag like particularly costly quotas it's pretty hard to see kind of from the outside if you look at a really complicated quota system which of these quotas is like really causing the problems mostly and then Computing constraints at different trade-off points so this gets to your question about modulating the tightness of the quotas in like a more systematic way and seeing what you can get out of the lottery and that kind of allows you to move along the tradeoff inclusion of

protected groups basically the worry is that even if you protect groups with quotas very tightly if your quotas are too tight they permit manipulation which can then corrupt the representation of the groups that you were originally trying to protect so using really really tight quotas is not necessarily the right way to get to really good represent presentation okay so that's another kind of weird difficult consideration maybe a constructive suggestion would be to flag attributes for targeting misreporting and then there's also the worry about unprotected groups if you tighten the cotus too much maybe you're short changing a lot of groups um or maybe it's really actually improving the representation of unobservables so there's a lot of Statistics uh to do

there okay I'll skip the transparency stuff for the sake of time but if you're curious you can ask me about it it's like an algorithmic add-on and then I have one slide on extensions to uh blockchain applications maybe but you can tell me if you think these are useful so one thing I was thinking about yesterday when we were talking about this like um security breach if you want to call it that um is how sortition based committees can be used to mitigate security risks so one reason that these are really nice is that you can kind of depending on the information that you have control who is on the panel and then ultimately who votes right so there isn't this Reliance on people just opting in at any given time to vote so maybe if there's like a controversial decision or some condition is triggered

you need to actually assemble a panel and have a more dedicated discussion and decision process than is typically happening in the wild what kinds of security are needed so the security required in this process for the Democratic context probably is very different than you would need on the blockchain because the adversaries are like totally different people in the real world do not understand probability they don't have computational power Etc another kind of interesting thing which you can't really do in the real world in Dem I would argue but might be able to do in the blockchain setting is that you actually can just reweight votes kind of based on you know stake or whatever and now this process gives you kind of two options to reweight power you can reweight votes in the decision process and or you can reweight the

probabilities um of actually being Chosen and so it gives you kind of two Spectra here to play with on how to determine power in these processes what kind of manipulation is even possible very different things are probably checkable and uncheckable and what can you even know about people right you probably have a lot less information so it might mean that you need to worry a lot more about unobservable characteristics and then also what kinds of representation are actually substantively useful for this application and then finally kind of an interesting um extension of this work this original process was conceived of to kind of just run once in any given setting but if you're constantly choosing from the same pool of willing participants and this maybe this willing participants group is like slowly

evolving you kind of want to think about how much chance of selection people are getting over time not just in each event individually because if you've got someone who's just like always getting short changed or like always getting selected um that might also be a conserving even if you're doing everything you can in each individual time step to make things as equal as possible [Applause]