Video: Jerôme LANG, Computational Social Choice (DocDrop)

00:00:10

from AI to computational social choice okay thanks a lot Alberto and and thanks for the invention and I'm very I I love Purity Singularity so interrogative narrative I think so so I I'm really

00:00:24

pleased to be here uh so I hope that the other ones are going to join from outside okay um so

00:00:37

um I'm I'm going to so I'm I have a background in computer science a little bit of mathematics and a little bit of Economics so it's a mixture between the three and I would say I will also come

00:00:49

from engineering so the the talk we also have an engineering flavor okay so again social stress Theory so you know what that is but still I mean because it's the end of

00:01:01

the day maybe it's let me show a few slides about some instances of social shows problems so you know that social choice is the

00:01:13

science of Designing and analyzing mechanisms for collective decision making so here is in the I mean here is an instance which you uh I've heard about I

00:01:28

hope okay uh here is another instance I mean with the I mean with the stake that is maybe lower than the previous one okay uh so I don't need to explain uh here is

00:01:41

another example I mean who knows what that is yes yes to have agreement okay okay so that's again a collective decision making problem maybe there is a significant difference between this one and the other two I mean can anybody say

00:01:56

I mean not about the techniques that would be used but about the kind of information that is going to be aggregated is there a difference between this one and and the other two who has an idea but maybe there could be

00:02:14

many differences but a key difference about the kind of information the nature of the information that we deal with yes yes addictions are about preferences not only addictions but yeah many many

00:02:30

problems in Social shows are about aggregating preferences and this is not about aggregating preferences this is about aggregating opinions beliefs yeah about the ground truth

00:02:41

and this is important because I mean uh for instance strategic issues are crucial in aggregating preferences they are for instance less crucial in aggregating beliefs and there are many other differences okay

00:02:55

so a very rough history of social choice I mean in social just in one minute so usually we say there are three three periods sometimes four I mean if we include an ancient Greece I mean if I

00:03:09

give a talk in Greece or or or in Rome so I mean I I would I would consider Antiquity but I mean here we I'm in Paris so I start with condos and Border okay so some of you might remember in

00:03:23

the Euro days in 1789 when you're I mean most of you are too young for that but I was there okay so then in the the second period is the the birth of the of modern social choice I mean or mathematicians

00:03:37

economists it's coming to play and and so what they did at the time is related to the the previous talk I mean the proved impossibility theorems sometimes possibility theorems

00:03:49

uh such as Arrow theorem or gibad and certificate and then um the the turn of the I mean late 80s early 90s and even more in the 2000s

00:04:01

then um researchers from computer science and AI came into play and considered uh I mean that was a computational turn I

00:04:12

mean those researchers considered uh not only conditions that could prevent the existence of mechanisms or that could or that could allow the existence of mechanisms but how these functions these

00:04:27

rules could be implemented for real how they could be computed or they could be implemented in the real world okay so the the rest of the talk is a collection of simple examples about I mean it's like uh you

00:04:41

know a small ghost board if you know the word of problems that we deal about in the community and so that will not be very technical I

00:04:52

mean and you can interrupt me when you want it's the last Talk of the day I mean you need to be awake so you can interrupt me when you want okay uh okay yeah before yeah this is not exactly the steroid but so in the rest of the talk I

00:05:06

mean I will use different kinds of uh of inputs so sometimes so suppose here that okay first of all yeah so uh so um

00:05:19

so we have agents finite set of Agents okay uh uh and we have also find that several set of candidates and uh the output is of course I mean if we

00:05:33

want to to consider a social welfare function the output would be a collective preference relation but very often I consider a voting rule that will output simply an alternative sometimes a

00:05:45

set of tied Alternatives okay so a very simple example is I mean choosing the temperature in the room supposing that we have control over it okay so there could be various input formats that will of course influence the kind of

00:05:59

functions that we use okay so we could have uniniminal ballots where everybody would name their top temperature their ideal temperature we could have ordinal ballots where you see

00:06:12

that everybody gives a ranking over a temperature of course I mean this this these rankings are not uh arbitrary you see that the the the satisfied property that is called single peakiness for those you

00:06:25

you know I mean for instance I mean it would be strange to have someone who prefers 17 then 20 then 18 okay you see what I mean [Music] um

00:06:36

that it could be approvals so approvals means that any voter will be asked to say for which I mean which of the candidates which of the Alternatives she approves and which

00:06:50

she doesn't and also evaluations you could ask you could specify a numerical evaluation for each of the of the candidates okay so depending on which input we have we will have different

00:07:01

kinds of methods okay now ai and computer science and social choice so initially computer scientists helped

00:07:16

solving hard computationally hard problems that stemmed from social choice but then after 20 10 20 years I mean it

00:07:29

became something else I mean the the AI and computer science communities contributed to reshape social choice so not only by using new techniques but also by creating by by launching new

00:07:44

paradigms and by focusing on new objects of study and new applications okay so and my talk will be more in these two and not much on new techniques which you probably don't care much about again so

00:07:59

uh this talk will be a quick guided tour of computational social Choice via a non-existive and biased I mean towards the problems I like a selection of problems

00:08:12

uh okay okay so topic number one there will be uh I think 10 topics but depending on the time that I have I mean there will be a few topics I won't talk about okay

00:08:24

so again remember you can interact me when you want so uh uh who has heard about liquid democracy Ariana don't answer okay okay who else has heard about liquid democracy okay

00:08:37

okay so of course I mean you know the two extremes that are representative democracy where citizen citizens choose their delegates like members of parliaments for instance and direct

00:08:50

democracy where citizens vote directly over issues like in referenda and so liquid or fluid democracy is a Continuum between these two extremes

00:09:02

okay uh so citizens can choose either to vote on an issue like in direct democracy or to delegate their vote to someone else as in representative democracy so it's much more flexible

00:09:16

um first example so committee election the question is who should be elected the new steering board okay uh so maybe so

00:09:27

that then you ask voters I mean do you want to vote yourself or delegate your vote to a trusted peer so maybe you don't want to devote too much energy thinking about the candidates looking at their programs okay so maybe I'm going

00:09:41

to delegate my vote to someone who knows better okay so in that case this is about aggregating preferences as in addictions okay there is no ground truth this is classical social shows preference

00:09:53

aggregation right another question now in the where we don't aggregate preferences but beliefs which is called epistemic social Choice okay so two examples I mean first

00:10:07

example uh questions about English you say idioms or idiom idioms okay so uh you know I mean before being asked the question you know that the question will

00:10:19

be about English idioms okay and then uh I ask you you want to vote yourself or delegate to a peer okay a trusted peer so maybe I would dedicate to this man who's I believe much more competent for

00:10:33

me about English English idioms maybe not about everything but about English Indians for sure okay and and but then if the question is about landmarks I mean you're shown landmarks of uh

00:10:47

well-known places and you you have to say in which country they are I wouldn't I wouldn't trust Baris Johnson for that yeah so I would loads again so and so this is about epistemic social shows

00:10:59

such as in the the 12 increment movie this is about aggregating beliefs about the grand truth okay so uh actually this uh this so what's

00:11:11

nice with the epistemic social shows is that it it gives a way of evaluating liquid democracy and there were experiments actually about uh whether

00:11:23

allowing people to delegate to people they believe are more competent than them helps finding the right decision and it does it does help okay so your experiments done by

00:11:35

manoloville at MIT so the here is the dedication graph here you see that again and this is uh actually this is about the the competence measured by the fraction of uh correct answers they gave

00:11:49

so you see that people tend to delegate to someone more competent than them not always actually because also we we also ask people who delegate to to to give answers I mean to to measure whether

00:12:01

people tend to delegate to more competent people and here is here's the outcome when you aggregate the votes uh weighted by the number of delegations that you get you see that using liquid

00:12:15

democracy you get a better outcome you get more you have more chances to to get the right answer okay uh more accurate answering them but then I mean there are also algorithmic problems uh with liquid

00:12:28

democracy so look at these two examples okay so here you have four voters okay and here you have so A and B delegate to C is C

00:12:40

that it gets to D and D abstains okay so you see first I mean in liquid democracy I should have said that but you have transitivity if a dedicates to C and C delicates to B then by transitivity a dedicates to d but then I mean

00:12:54

everybody's vote is lost because the abstains okay so that's not good okay so we have to find something and also there is another issue here okay e direct gets to H that it gets to F that it gets to e

00:13:06

there is a cycle okay so what do we do with that okay uh and uh and also you see that H uh may also delegate to G

00:13:19

so I I I'm going to explain in a few seconds what it means to to delegate to to to to agents okay but uh uh then it's okay because G dedicates to

00:13:32

to herself yeah g votes so that's okay uh so a way of uh of so many these two these two issues I mean cycles and delegations that lead

00:13:44

nowhere is to allow for ranked irrigations okay uh uh so um for instance you can say A dedicates

00:13:55

to B and B delegates to C but B is also willing to delegate to G if delegating to C leads nowhere and and similarly here okay so using these so these rank

00:14:09

dedications means preferences preferences about whom you dedicate to okay uh but of course you you it it's it leads to non-trivial problems I mean uh is it uh

00:14:22

[Music] for instance is it better to delegate here I mean to take this for f to take the second preferred delegation I mean to age who actually uh prefers to

00:14:38

negate to G but the second choice would vote or is it better to to take a longer path uh that leads for sure to to an answer I mean the these are tricky questions which actually Ariana here has

00:14:51

worked on that but these uh these three questions are not being served yet I mean they're it's still the uh a very hot topic about it I mean knowing what to do in such cases okay so that was

00:15:06

about liquid democracy questions about that or should I continue okay continue so um let's stay in epistemic voting so aggregating beliefs and let me

00:15:18

let me say a few words about why and how to apply to crowdsourcing okay so epistemic social Choice once again so there is a ground truth to be uncovered okay so we are we are asking

00:15:33

questions about the real world and we want to infer to aggregate beliefs about this real world actual World votes are noisy report about the grand truth about the real world okay

00:15:46

um and voting rules are usually seen as maximum likelihood estimators okay actually this trend starts it right with Contour C okay in 1785 with the condos injury theorem which I I won't talk

00:16:00

about okay and it's also highly related to statistical machine learning which is an extremely hot topic now as you know so let me give an example of what we can do with the epistemic voting

00:16:13

so um instead of just asking so we could ask of course I mean people to give a ranking over Alternatives I mean which one do you believe is most plausible and

00:16:25

which one is the second most possible but sometimes for actually at least two reasons it might be better to ask them to report simply approvers okay so here are the the

00:16:39

um so for instance suppose that the question is which okay I show you this picture and the question is in which of the 20 districts around the small of Paris was this picture taken okay so I

00:16:51

mean ranking the 20 districts will be uh quite uh difficult and long but it makes more sense to allow people to say I believe it's in this one or that one or

00:17:03

that one okay and actually it's quite convenient because look look at that okay suppose that the answer are this okay so I consider Only The District 12 to 20 okay

00:17:18

so uh uh you see what can we say and we ain't into about about about about that so you you know what that means what that means Anne says that she believes it's 18 and that's it

00:17:32

okay nothing else and Bob says he believes it's 14 or 16 or 19 and 20 and so on okay what can we say about Eva for instance Eva she sees almost everything's possible so

00:17:47

what can we infer about Eva she's not sure but she's not very competent okay she considered that almost everything is possible so she has no idea probably she doesn't live in Paris right and um

00:18:00

so what can we say about Anne and about Fred I mean they're very sure okay they give only one possibility each so so they believe they know okay so we can't say that they know because no

00:18:14

knowing means that uh the beliefs are are true okay and at least one of them has a wrong belief but uh at least they're very confident but which which of both do we want to trust more than

00:18:28

the other what do you think Ann or Fred or no one or we don't know what do you think yes and why

00:18:39

sorry exactly okay okay because Fred you know I mean he he is giving an answer that no he is voting for 12 no one else votes

00:18:51

for 12. so it's like it's likely that Fred is just uh pretending he knows and he doesn't okay so you know I mean there are lots of things we can infer about these votes and and so we can uh use

00:19:05

these intuitions actually to weigh the the voters by some measure of confidence okay so uh using what we have said we said and we should give a high

00:19:18

confidence and and Fred a low confidence and and Eva as well for very different reasons and so on and we would probably aggregate you see that 18 as a year for

00:19:30

approvals uh but 19 is for approvals as well but uh uh 18 is approved by uh someone with

00:19:40

the high expertise I it was a presumed expertise and uh one with the rather good expertise too okay so we should pre using this intuition I mean we should

00:19:53

prefer 18 to 19 and this is actually the correct answer so the and this has been tested on in on huge data sets and this works well uh these are also this was also applied to aggregating linguistic annotations

00:20:06

yeah yes okay so there are two arguments for that uh exactly but we have no way to know this we have absolutely no way to know if

00:20:30

uh we can we statistically suppose that we have we have thousands of Voters statistically people will give only one answer the 10 to be correct more often I

00:20:43

mean the the 10 I mean if I ask you about in which year Napoleon when apart was born okay if you tell me does anybody know Make It Sick

00:20:56

17 76 he was very young at the 1765 something like that okay if you give me a date like that it's likely that you know okay I'm ready to believe you of course there is a probability that

00:21:10

you're mistaken but statistically I mean people were given me one day they would know but then the second reason is that Anne gives an

00:21:24

answer that is also approved by many other people so it looks like it's a non-stupid answer of course I mean there is absolutely no proof I agree with you but statistically it works because it gives a

00:21:41

no no he's continent I said is confident that is not reliable it doesn't look reliable but he's very confident of course yeah confidence is not enough but I'm an engineer so what counts is

00:21:57

that it works I mean yes more likely more likely statistically yes of course of course yeah yeah for sure I totally agree with

00:22:19

you yeah but for that I mean no for that we didn't we did that I mean I had the PHD student who did that on uh a few he reused data sets about uh detecting

00:22:32

languages I mean in which I mean you you can hear language some text uh and uh spoken text and you have to to identify the language there was also labeling pictures of soccer matches and things

00:22:45

like that and it works yeah but of course I'm I'm pretty sure that you can find domains where it won't work okay next topic the topics are rather disconnected yeah next topic this would

00:22:58

be very quick iterated voting so um plurality I have to explain what plurality is plurality is the extremely simple voting rule I mean the simplest

00:23:11

rule maybe after dictatorship where everybody just name names one candidate and the con the candidate with the higher the highest count the highest number of votes wins this is the the voting rule that is used

00:23:24

for instance for electing members of parliament in in Britain in the UK uh so suppose we have uh 11 voters okay so the

00:23:37

the first force a a I prefer a then B then C and then d and e and and so on okay so if we use plurality okay and if the voters actually uh vote sincerely so these these uh these four they would

00:23:51

vote for a and these three for e and so on so the winner would be a of course you could someone who's a specialist of strategy manipulation in voting would say yeah but they are going

00:24:04

to to manipulate maybe yeah but in order to manipulate so there are two things first I mean so you everybody knows what manipulating and voting means if you don't know you're going to see very quickly so

00:24:17

manipulating assumes that you know about voters preferences you know at least something and this is not necessarily the case initially but uh if I tell you now uh

00:24:31

well look I mean if we stop the votes here the winner is a because a has for votes and E and so I make this public I make public the counts I mean the the

00:24:43

count of votes I mean I'm not I am not saying Wu is voting for a and who is voting for e and so on I am telling everyone a is for votes and uh e as

00:24:56

three votes and so on okay this is made public so you're going to ask me why are you making that public you give people the the the the possibility to manipulate and perhaps they wouldn't they would

00:25:10

have been unable to manipulate before because they didn't have this information I say yes but why should manipulation be always something negative it could be also positive because maybe

00:25:22

if you use a voting rule that is too simple to and that sometimes give a very bad outcome actually a is not a very good outcome here you see I mean there are so many people who hate a so if you manipulate I mean so maybe

00:25:36

these these two voters you know I mean they see they voted for C but they see they can observe that c is far from willing so maybe they are going to switch to e because if the switch to E I

00:25:50

mean e is closer to to beating eight and then C so they won't maybe they want to switch to E and if they switch to e then the current winner is e but we're not stopping here

00:26:02

then seeing that the current winner is e then uh well these four uh so they don't they don't want e they hate e so they are

00:26:15

going now to vote for B because I mean a they understand that a will not win anymore so none that would vote for B and once we are here so we continue but it looks like it won't change okay yes

00:26:33

I'm giving you two answers so either you you fix a number of iterations from the beginning you say five times maximum or you just just I mean in practice what you would do is that you would let uh

00:26:46

this would be on a website you would say the website will be open until tomorrow noon okay so you can change your vote as as much as you want okay so there is no fixed number of iterations but there

00:26:59

will be a I mean sometimes most of the times not always most of the times convergence will be reached here I mean once once the once we have this configuration we'd be within there

00:27:12

is little chance that that it can change maybe some voters will chase them but probably I mean it things won't change much and um so if you reach Con in in most

00:27:25

practical cases you will reach convergence and uh and then we get an outcome which is in many cases not all in many cases

00:27:35

better than a sincere outcome that I mean if you compare ear B and the initial outcome a I mean there are many reasons to prefer e to prefer B right yes how would you okay uh why why would I

00:28:02

say that that b that's B is better than a Nick okay so you want to decide where we're going to have a dinner uh tonight okay

00:28:23

and there are five different restaurants okay uh there are I mean four of you are love Burgers okay they love Burgers you know this with the ostek Tata or you

00:28:36

know these raw beef meat okay there are always a fraction of people who love that I hate that and most people I mean many people don't like that okay so the weather initially would be a the burger

00:28:48

okay but then I mean uh if you if you let people uh if you give people a chance to to to to to uh coordinate you actually you give

00:29:01

people the opportunity to coordinate to it's a to coordinate implicitly to coordinate without communication and and then you can you can reach an outcome which is arguably better I can explain

00:29:14

why I believe it's better it's more consensual Erb B is much more consensual than than a okay so you give people the ability to

00:29:25

coordinate without communication but I mean I don't work on that so you can you can I mean um I can understand why you're skeptical but I would be rather positive about

00:29:43

this kind of thing in cases where it improves social welfare and and and so I didn't want to show any theorems but actually there are people who showed that under certain

00:30:04

assumptions about voters preferences I mean this kind of iterative voting those improve social welfare so it leads to a socially better outcome uh so I mean this example is is not an

00:30:17

exception I mean it's it's something typical it converts to something more consensual yeah exactly yeah for instance if you have a conversation winner the probability of of obtaining controversy

00:30:30

winner after convergence is much higher than that initially for instance yeah so which is another I mean so another argument towards using this kind of thing

00:30:47

yeah actually this is yeah at least exactly the answer to your question four you you can you can stop me when uh but for

00:30:58

let me think maybe I will skip four for now but I can I can come back because it's a it's a little bit long so but if you're interested in participatory budgeting I can't come back on it I will talk a little bit about participatory

00:31:11

visiting anyway here okay um or no maybe maybe let me change my I'll change my mind let me talk about participatory imagining so

00:31:24

who has heard about participatory budgeting okay who lives in Paris among those who would who live in Paris who has ever voted for the Vijay

00:31:36

participative okay uh so participator Beijing is the following Collective decision-making problem you have a set of uh projects

00:31:49

candidate projects which are usually suggested by by citizens each of these has a cost okay there is a maximal budget for I mean to be spent over this project

00:32:02

so we cannot we cannot fund all projects okay and voters vote on projects and yeah the goal is to to select a set of projects to to be fun funded but I mean

00:32:15

uh how are going voters to vote on projects and how are we going to select projects so this was Paris actually until I mean the change a little bit the system this

00:32:27

was Paris until uh 2020 I think or 2021 so they used approval voting approve voting is actually used in most cities who have participatory budgeting so in

00:32:40

Paris until 2020 each season could vote for at most four projects of their aroundismo district and at most far projects concerning all of Paris because there were 21 sets of projects I mean

00:32:53

all of Paris and and then the 20 districts um and so the way the the deed is the way that is used in most cities that have a

00:33:05

participatory budgeting process so um each district that is as its maximal budget and then you rank

00:33:16

projects by the number of votes okay and given that each voter has four votes yeah and then you you you you take them in in that list by decreasing order of

00:33:31

votes and you decide to fund the project uh provided that it does not exceed the budget so here if the so suppose I mean you you so you you start with this project

00:33:44

is the budget exceeded no okay so you take it then you take it then you take it and then maybe you will find that taking this one would go over the budget so you would stop yes yes

00:34:01

it's important they do um and um so is it good is it a good a good uh output well maybe not yeah so let me give a stylized

00:34:16

example I mean to show you why it's not good okay and I will come back to the the Katrina this morning in 2018 after all okay so suppose that we have a new file sorry 100 voters here and and four

00:34:29

possible projects and the costs are here and so you see I mean you have 17 voters who vote for A and B and so on okay so if we order the projects by number of votes we get 51

00:34:42

for a and uh 50 for B 50 for 49 the costs are here so if you if you use this greedy method then you would start by a the maximum budget is 60 so you you a is within budget you you take it and

00:34:57

then you cannot take any other project okay so you you take only a is it good can't you do better here can't you do better than that of course of course you can do better

00:35:08

okay if you take BCD okay it's much better for many reasons I mean you have more projects you satisfy you satisfy more voters because for any of these voters there is at least one project

00:35:21

that they like which is funded why if you take a I mean half of the voters they are not satisfied okay so these are this is already a difference between the greedy uh algorithm versus the global mechanism

00:35:35

where you have to find a selection of projects that maximizes the sum of scores where the score of a project is the number of Voters who vote for it this is a in computer science this is

00:35:47

called the knapsack problem it's an NP hard problem but that's that's fine I mean some NP hard programs are not so difficult to solve including this one the global algorithm

00:36:00

on on this example would actually found all projects except this one you see this one is very expensive okay and so and it would be more fair uh also to to

00:36:14

the people okay is it good I mean this Global algorithm well it looks better than the greedy one okay here is another example it's uh it's the 18th District in 2018.

00:36:27

so you see the difference between the greedy and the and the global I mean the the global tends to to fund more projects and also including a cheaper projects okay but it's not perfect

00:36:39

either the global one because you see so these are actually uh uh so the the implemented outcome was this one because Paris was using the the this is greedy I mean yeah

00:36:52

and without this one down here again but the global is not perfect either because you see I mean uh uh 53 percent of the budget would be would go to two projects that are very similar that are concerned

00:37:06

with the same Sports Center plus if you add this one I mean you get you get 59 of the budget that goes to to sports projects okay so this is still not not perfect and there are actually

00:37:19

improvements to make the to make the the selection fairer fairer I mean more fair more proportional but I I won't have time to to to to to give details about

00:37:31

it but it's a very hot topic right now Fair methods for participatory budgeting Alberto can you tell me how much time I still have while you're checking I'm going okay so five

00:38:03

um let me skip five maybe I will come back diversity six um so um do I mean those of you who are academics uh working in in a French Department in

00:38:20

French research department they were probably they were members of committed selection right who was ever a member of a committed Resurrection okay so so you know when you make a committed selection a hiring committee you have

00:38:33

lots of constraints I mean you so you have to find this number of people there are continuity constraints but you you must have an equilibrium between a Junior and senior you have a cream between men and women between local and

00:38:47

local local and non-local plus if if you have several groups who are concerned I mean you have must have a topic-wise equilibrium it's very hard okay and so this is this is uh the problem of

00:39:04

a multi-winner election so so not that it's not an addiction here I mean it will become an election later in the slides but so far there is no addiction because there are no votes okay it's a selection of a of a group of people of

00:39:17

committee uh given some diversity constraints okay um so constraints could be thought either as uh

00:39:28

Target a Target that we should try to I mean these proportions can be considered as a Target that is ideal and then we should get as close as possible or we can also consider them as constraints so I will do both so first let's consider

00:39:42

that as a Target so we try to get as close as possible to to these Target proportions and these are the candidates we have a database of of candidates and each candidates come with a three three uh

00:39:56

three values for each of the of the features okay so here we have a woman in area one Junior and so on so here I mean if we take uh if we take and we want four

00:40:07

members okay if we take C2 C3 C6 C7 it's okay for the gender equilibrium and and the area representation but it's not okay for the Junior and senior uh Target representation but this is the best we

00:40:20

can do I mean it's not possible to do better given this database and these targets proportions or we can consider them as constrained so in that case we will even interverse the the the

00:40:32

parameters which is exactly exactly what we do for a Community selection we we have intervals for instance for a male and female it will be between 40 and 60 for each

00:40:46

um and so then [Music] so then then you can do better also because if we have constraints it could be that uh

00:41:00

not only there will be one uh hopefully one solution that will work but maybe we have several ones and then how are we going to choose between several committees that satisfy the constraint

00:41:12

maybe we have votes okay so you could ask the question among the Committees that satisfy these constraints which is the one who has the more votes okay and so this this is the kind of questions

00:41:24

that some people are looking at in the community uh of course I mean this so there is also an online variant okay uh suppose that you you're going to ask the people

00:41:37

in a sequence you are going to ask the people in sequence you're going to to send them an email we are you willing to participate to this committee and they are going to I mean this is

00:41:50

what people do in reality here in in real life this is how they do they do it sequentially uh and then uh so how does it happen so maybe I I let me give another example where this

00:42:03

happens I mean these online selection you know the the citizens convention such as in France the the convention situation or in in in the UK there was a I mean there are many countries there

00:42:15

were also like such conventions citizens assemblies so what you can do is I mean because you want in the end you want a a good representation for each of many

00:42:26

parameters like gender age and so on so initially you will you you contact people by phone for instance and the first ones you would take them in any case but after some time you're okay oh I have a state I mean I have

00:42:40

significantly more young and educated people and living in Paris so so you're going to exclude the new ones that even even is the constraints the cons even if the quota for Paris and for educated

00:42:52

people is not rich you're going to to exclude them more often Okay so to to maximize the chance of of get getting to a perfect committee sooner

00:43:06

okay so maybe the first one you selected in any case but then uh the second one I mean you know we we have a senior already we have someone in area three already so even though the the the

00:43:18

second candidate would be good for gender representation it would not be good for the other to uh parameters so that's not good so the third one we're going to maybe to to to take him either if it's not good fortune

00:43:31

the representation and so on okay and um so depending whether we have a probability distribution that we know on the the arrivals of candidates or not I mean we have one kind of methods or

00:43:46

another yeah which I won't talk about so that was six let me hesitate okay let me say I'm going to talk about

00:44:02

one more so you have the choice between long-term fairness or voting with memory Fair division of indivisible items or stable matchings who votes for long-term fairness

00:44:16

okay who votes for uh Fair division no no it's okay cutting would be for divisible goods and this is about indivisible Goods and and who votes for stable matchings

00:44:33

okay stable matchings Okay so [Music] um you know I mean uh some of you may have children who are uh the the the the age

00:44:51

of applying to universities okay so they use parkour soup you know but I mean in every country you have different systems but I guess in most places now you use such uh systems for matching students with universities okay so

00:45:04

here it's an example with doctors and hospitals but I mean it's the same so assume we have four doctors I mean and Bob kaholen France okay and three hospitals okay now CMS and Strasbourg I

00:45:18

come from the contest region yeah so um Anne says that she prefers Nancy to mess and she doesn't rank which means that she doesn't want to go there if she's

00:45:30

she if she's she prefers not to be assigned at all then to be assigned to Strasbourg he prefers to be unemployed and going to strasbour um I don't know why because a really

00:45:41

nice city but anyway I mean um Bob has preferenced nursing okay Nancy has only one position and not see as I mean they have their

00:45:54

criteria and they would prefer kahul to Bob to run to France okay and mess has two positions and this is their preferences and strasbord was only one position I would prefer Bob to Carol but they don't want and they

00:46:06

don't want France for some reason so consider this solution okay the solution sending Bob to Nancy and Carol to mess and France to mess so this is okay for

00:46:21

the the the capacity constraints because mess has two two available positions okay and no cs1 and we don't send anyone to Strasbourg is this solution acceptable what do you think

00:46:35

is it acceptable don't tell me it's not acceptable because uh stress board doesn't feel its position this is not enough reason yeah well it is not acceptable why isn't it

00:46:49

acceptable because Ann would prefer and is not assigned here but she would prefer Miss to nothing okay you see I mean uh yeah

00:47:00

okay she would like to go to mess and mess would prefer an to France who is currently assigned to to the hospital illness okay so this matching

00:47:14

is not stable okay so it's not acceptable we can do better okay question is there a stable matching what do you think who thinks there is a stable matching here well you should say yes because there is

00:47:26

always a stable machine okay there is always a stable matching okay so he he's here is one you see it's not complete I mean there is still nobody in Strasburg um

00:47:39

and uh so why is it stable so this is quite a little bit long to to no that not that long but yeah we should have to consider all possible pairs that are not in the matching and show that the you

00:47:51

cannot object with such a pair for instance if you object with an and Nancy and would indeed prefer no C okay but no C does not agree I mean not see

00:48:03

the the the they prefer to have Bob uh sorry Nancy they prefer to have Bob than an okay and you can do that with any pair and you will see that there is no acceptable objection because so this uh

00:48:17

this matching is stable okay uh well in general like so there is always a stable matching okay this is a well-known result by uh gaelish and

00:48:28

chaplains 71 I believe actually got even the got the Nobel prize in economics for that I mean it was in 2012 so David Guetta was no longer here um

00:48:42

I mean it's also known that I mean whether you you start with the hospitals whether you give priority to hospitals or priority to to doctors uh you you you you you you you can get different

00:48:55

matchings sometimes it will give the same matching but sometimes you give different matchings okay so it is well and there are hundreds of papers about that in economics in computer science in mathematics maybe in philosophy I don't

00:49:08

know you know better than me Lisa will skip I mean the people working exporting data I mean large data sets about about collective decision making

00:49:20

engineering so social engineering in my University so I am in five years of construction works and reassigning people's offices I mean in in different phases I mean for the next five years so the this is this is going to be for real

00:49:34

I mean this is not just a game yeah okay yeah and so let me uh sees I skip so maybe so when I give this

00:49:47

talk first I mean the um I I I wanted uh the the attendees to tell me which of these topics they had preferred uh so they could vote on on on

00:49:59

their preferred topics and I I just want to to to to to is there a is the computer connected to the internet we're going to see soon okay anyway

00:50:11

yeah uh yes no yes okay so you see so this is the whale platform so you know you all know doodle everybody knows doodle who does not know

00:50:25

doodle okay so doodle is uh is developed by a profit making company you have ads and okay whale is developed by people in the University of grand emblem

00:50:40

there is no no advertising it's totally for free it's a it's used for research and it's much more the variety of things that you can do is it's much wider than we do that so please use whale next time

00:50:53

I mean I I will send you the the the the link to the whale platform it's really cool sometimes it could I mean if you use the the very latest version sometimes it will fail so you should use

00:51:06

the second uh yeah the stable version yeah uh that's it uh if there is still time for questions I would be very happy yeah

00:51:22

yes I think there is still sometimes so Walter great so thank you very much um I learned a lot very quickly um about subjects that are on the sort of cusp of my interest in complexity

00:51:35

Theory um so with regard to um uh participary budgeting um which I take it was the first three examples um uh liquid democracy epistemic voting

00:51:47

and iterated voting um in a way I take it you were positive about as good social mechanisms for various reasons but then we get to particularly budgeting and it ends up being bad but it ends up being bad to a

00:51:59

reason that's certainly familiar to a complexity theorist because it seems that then what the Marie is asking us to do is essentially solve the knapsack problem um okay okay that's enough of a but question um

00:52:12

incentives so that people Converge on an efficient approximation algorithm okay so let me so um because I mean I didn't have much time so I mean I I couldn't go until the end so there would be two two

00:52:26

um I mean two important criteria for for having a I would say three three important criteria for having a good participatory budgeting mechanism first good axiomatic properties such as being fair to the voters okay so

00:52:40

proportionality for instance okay being simple to compute which was your question and being understandable by the people okay so and also which includes uh that the input also should be simple

00:52:52

to to fill in and so the question is is there are there rules that satisfy these three uh positive properties the answer is yes

00:53:04

yes but I didn't have time to yeah but yeah actually there was a rule that does everything it was found in 2021 uh by two researchers one of one of which works in my lab

00:53:18

it's called the methods of equal shares and yeah yeah but still I mean if you have to get I mean if only if one of the three part properties has to be given up I would be I would give up uh polynomial

00:53:33

computability I prefer to have NP hard methods that has good properties and that is simple to understand even if it's NP hard because yeah

00:53:45

I can approximate it yeah yeah is there any other question or yeah I I just learn about uh epistemic voting and it's fascinating I take it this is the kind of thing that has

00:54:07

actually been tried out as a some kind of decision or detection mechanism like for I mean the the where was this picture taken oh it turns out to be taken from a Matra and we should believe Fred

00:54:20

um that actually could be trialed but then my question is if it actually does work in the field how sensitive is it to the payoff parameters there is not a way to always a payoff in

00:54:35

the sense that I mean um in Amazon you know Amazon Mechanical Turk okay who knows who doesn't know Amazon Mechanical Turk okay who knows who knows them as a Mechanical Turk okay

00:54:47

so you know it's it's like you you can you can you can volunteer to to to to do simple tasks on on the on the internet you are paid indeed but you are paid independently of of the answer you're

00:54:58

giving okay so the it's not an incentive to be okay you can but on on some other experiments especially if you do lab experiments indeed you can pay people uh uh what they're paid varies

00:55:12

according to what the toward the answer so for this approval voting schemes so there would there was one experiment in the U.S that indeed paid

00:55:27

voters so they they had so you had a reward for finding the right answer and you have a penalty that in increases with the number of answers that you give a Batista

00:55:49

um so I feel like your methods are useful to know the answer to a question but to know what is the true answer like

00:56:04

to know about something whether there is well there is a result to know and uh but does it work when we try to

00:56:15

know what we should do like what is right or what is a public politically right like we try like when we try to make a decision but the decision has no

00:56:28

like true or false answer for instance to be sure I understand your question you're all about the moral machine who knows about the machine experiment yeah yeah if you don't know I mean you have to go and look because this is

00:56:44

amazing in the maroon machine experiment you you have people give being given scenarios where I mean they have to they have to choose so there is a car we we

00:56:56

that is going to crash against a set of people and whether it goes right or left is going to to to to kill a different sets of people and you have to you have to choose when there are very many

00:57:10

parameters the numbers of number of people whether you have to do an action or not and of course and you can see that as a collective decision making problem and then of course I mean so

00:57:24

um this is about building uh Collective ethics Collective ethical Norms so is is your question about that because I'm not sure

00:57:36

no okay about politics like for instance we uh how should we address this problem in the world or

00:57:53

should we implement this solution or this solution it's not necessarily about ethics okay for instance suppose that we are okay we're debating about uh

00:58:07

methods for fighting climate change okay so there will be questions such as should we have a carbon tax uh how much are these the kind of questions that you have in mind okay

00:58:20

but of course I mean this is classical social so this is a preference aggregation the the you have really this distinction between belief aggregation about I mean you have beliefs about the grand truth I mean when I show you a

00:58:41

picture that taken from Walmart it was actually taken from momarte this is true when uh I tell you I mean who would like would you prefer

00:58:53

a or b or c to become the next president of the Republic there is no true answer okay so it's about preferences and it's the same about about uh yeah

00:59:04

taking measures to fight climate change so in In classical preference aggregation there is no ground truth and you cannot you cannot evaluate the outcome of the vote according to the ground fruit

00:59:18

because there is none the last question okay no thinking about your different topics it looks to me that iterative voting is of a different kind of the others because it's in the process of

00:59:35

interaction and we could apply this model to all the other topics am I right or not because because it's about in in all the other things we could have voters look at the results and iterate

00:59:48

on it and so would it work and would it yes I'm not saying that there was there were studies for each I mean for iterative voting for each of these problems but

01:00:08

therefore there was some work on multiple referenda for instance I mean we have to have to give yes no answers on on multiple questions that are interrelated

01:00:19

uh and it gives also good results yeah maybe we should we should maybe so thanks again uh uh the very last okay thank you very much for this

01:00:41

extremely interesting talk uh so I got very interested in the iterated voting as well but I'm not sure I was able to absorb everything so I have a question maybe it's uh silly so please correct me if it's uh if it's

01:00:54

wrong but uh so you have convergence because in this case that you showed us we have ordering of preferences right now I was wondering if we didn't have ordering could we see it rated voting as

01:01:07

another case of some political systems like in Israel where we have a simple analogy I don't know what it's called in English exactly where they are not able to to have a stable government and they go again and again and again to

01:01:20

elections could we say that this could be a case of iterative and it will be so so it is not silly at all um yeah so this is a very different kind

01:01:32

of uh of of indeed dynamic dynamic collective decision making process this is about forming coalitions okay so the problem you're mentioning is that so you have you first I mean in Israel you you

01:01:44

elect the the parliament set using a purely proportional representation system without threshold I mean this is the purest proportional representation also in the Netherlands for instance okay

01:01:56

and um and then parties have to to interact with each other to find to find a coalition governing coalition and sometimes I mean the most iterate because I mean they have to do

01:02:13

trade-offs okay uh this is not the case only in Israel I mean it happened also in other I mean most countries in most democratic countries use some proportional representation in France

01:02:25

and UK and the US are three exceptions uh but all all all countries in the EU except France you you use proportional representation so this can occur in many countries and it does have occur in

01:02:38

Italy in in Germany too and indeed I mean indeed I mean this iteration in codition formation is very important problem and there are lots of worries about that yeah it depends a lot about it depends a lot

01:02:54

about I mean if you don't if you don't assume anything about the preferences of the uh of the of the different parties about the the the the other parties that are going to be the same Coalition no

01:03:06

there is no guarantee of convergence but if you start by uh imposing restrictions on the preferences that they have yes and then you have positive results you can converge here to the center

01:03:21

drinks so thanks a lot for uh this Lively talk so thank you [Applause] participants emails I will send the link

01:03:36

to the