Select text to annotate, Click play in YouTube to begin
00:00:06
uh Benedict will speak of social choice in infinite societies and these two Leicester talks will be on uh well in English I guess at least this one and uh and on social Choice Theory or
00:00:20
computational aspects in Social Choice Theory thanks Alberto um Okay so I suppose I'm going to be talking about computation but also non-computation or
00:00:33
non-computability um I'm going to start out just giving the basic sort of framework here um for social Choice Theory and we'll start with condos say of
00:00:46
course and the famous condos say Paradox so this is a paradox concerning majority rule which is kind of obvious way of making decisions you have a group of people let's call them voters and they
00:00:58
want to make some kind of choice out of some set of Alternatives um so majority rule just says okay if we have Alternatives X and Y then if a majority prefer X to Y then so should
00:01:11
the society this seems kind of reasonable um but then here's a scenario where this doesn't work so suppose we have some voter a that prefers X to Y and Y to Z and voter B who prefers white as Ed and
00:01:27
Z to X and then voter C who prefers Z to x and x to Y so fortunately there are only three so it doesn't get too complicated um but then we see a majority prefer X to Y
00:01:40
so vote array and voter C and a majority prefer y to Z A and B and a majority also prefer Z to X and we see now there's going to be some kind of
00:01:53
problem because we want to choose an alternative out of x y and z um X is preferred to y by the society by the basis of this rule
00:02:07
so and Y is preferred to Z and we think that preference is some kind of transitive relation so X should be preferable to Z but in fact Z is preferred to X by by
00:02:19
this majority rule so we have some kind of contradiction at least a contradiction with the notion of preference right we think the preference is a notion that should be transitive if I prefer X to y
00:02:31
and I prefer why it is that then I should prefer X to Z but then notice that these voters individually are not violating that condition their preferences can be transitive it's
00:02:45
just that the rule is inducing a social preference ordering that is non-transitive so that's the condo say paradox so even if the voters are individually
00:02:59
rational this majority rule can lead to socially irrational outcomes so an obvious suggestion here as well we need to impose some conditions on what our aggregation functions should be if
00:03:12
we're going to rule out scenarios like this so for example we want our social preference ordering to be transitive and we also want that any two Alternatives should be comparable
00:03:29
um we might not have a preference between them but they should be they should be comparable they should both appear in the ordering and yeah tires should be permitted to express indifference and this leads to a
00:03:42
certain notion of ordering called a weak order we Circle various different things in the literature but I'm going to stick with this term okay so here's just the definition of a weak order but just think of it like this it's like a linear order that
00:03:56
allows ties that's all that's really necessary okay so some notation I'm afraid we're going to have some notation in this talk uh so we have this
00:04:07
X less than with a subscript with a squiggle underneath y just means X is at least as good an alternative as y maybe more or maybe they're tied
00:04:21
and then the strict less than just means that X is strictly preferred to y in this order wherever this order comes from it might come from a voter it might come from the social ordering
00:04:34
and then we also have this version of equivalence X is equivalent to Y just in case X is at least as good as Y and Y is at least as good as X
00:04:46
and then we set this capital W to be just the set of all we call orderings on some set of Alternatives so we have these Alternatives these could be economic policies or perhaps candidates
00:04:59
in some hiring committee whatever it is W is just the set of all of these weak orders right so they're like the possible ways we could order these alternatives
00:05:16
okay so let's talk about societies so a society in this framework of Kenneth arrow is something like the following so we have a set of Voters and typically we're going to think of
00:05:30
these as individual people agents but there can be other things too we have a finite set of Alternatives so again these could be candidates in an election they could be economic policies
00:05:43
they could be you know candidates in for a job all these kinds of things and then W will be just the set of all week order it was on x and then we have this set a which I'll
00:05:58
explain more about later of coalitions of Voters and we can think of this as being to begin with just any set of Voters can be a coalition but typically we'll think of these as
00:06:11
being perhaps economic groups like classes or people affiliated with certain political parties in general we're going to think of any set of photos as being a coalition at
00:06:23
least to begin with okay and then we have this set F of profiles possible voting scenarios so what's a voting scenario well it's like an election we have these voters and in
00:06:35
different scenarios they might have different preferences well in this election I prefer counter debt X to Y but in some other election it's a different time it's a different context maybe I prefer y to X
00:06:48
so a profile is just a function from voters to weak orders right it just says okay given voter number one voter number one's preferences this ordering
00:07:02
and then in Arrow's original setting we have this condition called unrestricted domain or Universal domain it just says well the coalitions are just all of the possible sets of Voters and the profiles
00:07:16
are just all of those functions all of those possible ways that people could have um could have preferences all of the logically conceivable ones okay so as I said this is called the
00:07:30
unrestricted domain condition and then a social welfare function is a function that Maps profiles to weak orders so you can think of it intuitively as say in this electoral context the social welfare function is
00:07:45
going to take people's votes where we think of a vote as preference ordering and it outputs another preference ordering so it takes in all of the preferences of that Society at that election that profile and produces a
00:07:59
social ordering so something in w and arrow in trying to analyze problems like the condo say Paradox and trying to lay down these conditions that would guarantee that we had
00:08:16
fair and consistent ways of making these social decisions set down a number of axioms so the first one is kind of intuitive
00:08:28
it's called unanimity or the Pareto condition it just says well if everybody in the society all voters prefers alternative X to Alternative y
00:08:39
then so should the society so should the social welfare function this is pretty intuitive the second condition independence of irrelevant Alternatives which mostly I'm
00:08:53
just going to call Independence uh is a bit more complicated and a bit more controversial so roughly the idea is if we have two profiles call them f and g so it may
00:09:06
be different elections and if they agree on two Alternatives call them X and Y then the outputs of the social welfare
00:09:18
function for those two elections should also agree so if everyone in profile f has some particular ordering of X and Y
00:09:31
and they have you know person by person the same ordering of X and Y in this profile G then the output should be the same in both cases because
00:09:45
it shouldn't matter is Arrow's idea what we think about some third alternative Zed what matters is the relative position in our orderings of X and Y so
00:10:00
if you know I prefer X to Y in some election and Alberto prefers y to X and I prefer Z to both Alternatives and
00:10:12
so does the Alberto in the first scenario but in the second scenario perhaps we both disprofer Z and put X and Y first the social welfare function should in
00:10:24
both scenarios output a weak ordering but um is the same with respect to X and Y so if it puts X before y in the first
00:10:37
scenario it should put X before y in the second one as well and then finally non-dictatoriality this is also relatively intuitive the idea is just there shouldn't be some one
00:10:50
individual person in the society whose preferences are always carried out by social welfare functions so you know it shouldn't be the case that if I
00:11:01
prefer X to Y in some election the social welfare function does in all cases it shouldn't be that I always get my way or anybody no one should always get that way
00:11:16
and on the basis of these conditions Arrow proved this famous impossibility theorem so suppose we have a society which satisfies unrestricted domain and there's a finite set of Voters it seems
00:11:28
pretty natural you know we could be voting on something in here right now it seems like a reasonable notion of society and suppose that there are at least three Alternatives it only works there of course if you only have two Alternatives
00:11:41
then majority rule will work just fine because we're not going to get this problem of non-transitivity because we only have two alternatives so if those conditions are satisfied
00:11:54
then there's just not going to be any social welfare function that satisfies unanimity and Independence and non-dictatoriality the conditions are inconsistent so here's a quote from a political
00:12:10
scientists Riker from 1982 and this is not exactly a representative quote of the reaction to Arrow's theorem it's maybe the extreme end but nonetheless it does give
00:12:22
you a flavor of you know what people thought the upshot at least might be uh so Riker says the main thrust of arrows theorem and all the associated literature is that there's an unresolvable tension between logicality
00:12:34
and fairness independent Choice requires concentration of power in sharp conflict with democratic ideals so there's this idea that we can't have both democracy meaning populist democracy and
00:12:48
consistency and transitivity but can we Maybe if we have infinitely many voters we can so infinite societies offer a kind of
00:13:03
Escape I'm going to be a bit guarded about exactly what kind of Escape they offer so in 1970 Peter Fishburn proved this very nice theorem this possibility theorem
00:13:15
um he said well suppose you've got a society that satisfies unrestricted domain and suppose you've got infinitely many voters and you also have you know
00:13:26
three or more alternatives then there is a social welfare function that satisfies unanimity and Independence and non-dictatoriality so this seems great if you care about
00:13:42
infinite societies I mean it doesn't seem like this is going to be directly applicable to a lot of everyday electoral scenarios or you know usually if you're hiring somebody the hiring committee is probably going to be
00:13:54
finally many people but there are maybe some scenarios where this is interesting um I'm just going to mention two basic qualms about this Escape Route first group the first one is obviously you
00:14:07
know our infinite Society is realistic in any way are they useful as some kind of idealization or abstraction of a political or economic situation are they helpful to people in the social sciences
00:14:20
as some kind of modeling tool or as some you know some way of understanding normative questions for example about societies which extend into the future
00:14:34
and then secondly okay fishburn's possibility theorem says yes you get this social welfare function you can satisfy all of these conditions simultaneously but how do we do it does it do it in a way that's actually at all
00:14:47
useful so I'm going to start with the first um so I'm going to present three different models on which infinite societies can potentially be useful uh
00:14:59
the first is just this notion of a continuous Society or a continuous economy so economists sometimes work with models where you have a Continuum of Agents um and the idea here is that we're
00:15:11
really treating this as a kind of limit case of just having more and more agents um this has typically been applied not really so much primarily in the social
00:15:23
Choice context although there is work on this but more to do with the Notions of economies related to Game Theory Etc um so you know we set the set of Voters
00:15:36
to be say set of real numbers uh or you know you can always think when we talk about the voters being real numbers or being natural numbers or something we're not necessarily talking about actual voters being those things but
00:15:50
those things being labels so just as we're all labeled perhaps by our social security numbers or by our University ID number we have some kind of convenient labeling system that allows us to
00:16:04
differentiate and enumerate voters in our collection V so Primo fascia this doesn't seem a great fit for the arrow style social Choice theory in which we really treat
00:16:20
this set of Voters discreetly rather than continuously I won't say too much about this but if you have a kind of continuous treatment of v in fact you recover Arrow's theorem or something
00:16:33
rather like it um okay so a second one is societies that are infinite through time so in population ethics and intergenerational social Choice Theory
00:16:47
we might think about scenarios where new voters keep being born and if the universe extends far enough and we want to consider a wide enough notion of society or what a voter might be you
00:16:59
know they might not be from Earth they might be somewhere outside our light cone nonetheless you know we might want to consider them as having views about how things should be
00:17:11
and people do and in these kinds of scenarios we typically don't assume that there are a Continuum of photos but just that there are countably infinitely many individuals so as many individuals as
00:17:24
there are integers right whole numbers natural numbers um it's not immediately clear whether social decision making of the sort described by arrow is applicable to such scenarios there is a literature on it
00:17:38
but I'm I wouldn't commit to the plausibility of this kind of thoughts experiment I mean for one thing that if we want to actually carry out some kind of decision even if we have some way of taking into
00:17:51
account the views of future people perhaps we compute what we think they might want um still any kind of action will have to be taken before they can really make
00:18:04
their views known and then finally in in some ways perhaps most plausibly is is a third type of infinite Society so it's one where there's only finitely many agents just thinking about a more normal electoral
00:18:19
Society so we only have finitely many say human beings making decisions but they're conditioning their preferences on possible states of the world so they're saying well if things are like this then these are my preferences but
00:18:32
if things are like that and my preferences are like this and then it's easy to get infinitely many quote unquote voters so each voter consists of a pair of an agent and a state
00:18:45
um and when the set of states is infinite so it will be the voters okay so that's three types of infinite society that might be of interest either
00:18:56
for modeling or for kind of more normative purposes so now turning to the second question uh what kind of social welfare functions do we get out of this Fishburne possibility
00:19:13
theorem so normally when we think of social welfare functions we think of them as applications of rules right so the function is a kind of a mathematical operation it's mapping one thing to
00:19:25
another but how does it do it well it does it through a rule and this is kind of naturally conceived also as an algorithm so if you think of majority rule what do you do well you just count up how many people
00:19:38
want option A versus option b and in fact sen refers to the more General class functions that include social welfare functions as collective Choice rules the very use of this terminology demonstrates the way in
00:19:55
which these things are being thought about as rules and thus in some sense as algorithms uh and here we have a problem because fishburn's proof
00:20:07
doesn't produce something that looks like a rule or like it could be operationalized by a rule uh uses these very non-constructive methods in fact and this suggests a kind of obvious
00:20:21
worry well Fishburn shows that there are mathematically speaking these non-dictatorial social welfare functions but do any of them correspond to rules are there any that we could actually even potentially use
00:20:37
so as I've already said in this context a natural way of understanding the notion of a rule is as an algorithm or as a computable function okay so with all of this sitting there
00:20:52
we can we can go sort of more to the mathematics and to the modeling of all of this um so I first need to talk a bit about this notion of a decisive Coalition and this was introduced by our own you can
00:21:05
think of it as a kind of generalization of the notion of a dictator so decisive Coalition is one that always gets its way and of course the set of all voters is a decisive Coalition by the unanimity
00:21:18
Axiom so yeah just some more notation given some Coalition we write we have this um square bracket C after the profile F to
00:21:30
mean everyone in that Coalition refers X to Y possibly non-strictly and then a coalition C is Sigma decisive where Sigma is a social welfare function
00:21:43
just in case for any profile F and any pair of Alternatives X and Y if everyone in the Coalition prefers X to Y strictly then so does the social welfare function right so it's just a straightforward
00:21:57
generalization of the notion of a dictator or of unanimity and this notion was used by Kerman and Sunderman in the 70s
00:22:10
to basically reprove Arrow's theorem on the basis of this analysis of these decisive coalitions so here's the theorem they proved so suppose we have a society that's going to satisfy our usual conditions and
00:22:26
restricted domain it's got at least three Alternatives and we have a social welfare function which we assume satisfies unanimity and satisfies Independence
00:22:37
then there exists an ultra filter on the set of coalitions consisting of exactly those coalitions which are Sigma decisive so you might say okay but
00:22:50
what's an ultra filter well an ultra filter is a kind of notion of a you know collection of large sets so anything small and a thing finite will be
00:23:03
um in one partition no not in the algebra anything big will be in the ultra filter one way of thinking about this and the ultra filter will be principle
00:23:16
just in case the social welfare function is dictatorial so a principal Ultra filter is one generated by a single element so a coalition will be in the ultra filter just in case it contains
00:23:30
that element which is of course the dictator now this theorem applies not just to finite sets of Voters but also to infinite sets of Voters and you can prove this in a you know the standard
00:23:45
formal theory for formalizing for pretty much all of mathematics zamelo Frankel set theory ZF um and this shows by an argument that I won't give that
00:23:57
Fishburne's possibility theorem is not provable within that system it's genuinely non-constructive in the sense that it goes outside this system um because it implies the existence of what's called a non-principle Ultra
00:24:10
filter one that's not generated by a single element um okay so this gives us a kind of starting point it says well Fishbones possibility theorem it seems like it's not going to
00:24:23
give us anything computable anything tractable so here are some questions that I will attempt to provide more fine-grained answers to so the first is are there non-dictatorial social welfare
00:24:38
functions that do correspond to rules ones that we can compute this was previously examined in the 80s by Alan Lewis and in the 90s By Radio mahara
00:24:51
and in general the answer is no but the answer will be a bit more subtle than this so here's the more subtle version how non-computable are these functions and thus are there
00:25:04
electoral scenarios or so infinite societies where it might make sense to think about non-compute non-computable but not very non-computable social welfare functions perhaps some of these
00:25:19
not three scenarios that I proposed at the beginning might be more amenable to this than others and then the second question which looks like it's a very different question but in fact is intimately related to the first is are non-constructive axioms
00:25:33
like the Axiom of choice necessary to prove fish Burn's possibility theorem and again the answer is going to be yes but also no so I hope to provide something more
00:25:45
satisfying towards the end of the talk but roughly the answer is going to be non-constructive principles are necessary where not by non-constructive by now mean non-computable but these principles are much less
00:26:01
non-constructive than one might imagine so you're going to get non-computable sets but not that high up in the hierarchy of non-computable sets okay
00:26:13
so having done all the setup we now proceed to talk about some logic so I will try to just give a sort of sketch of how this goes
00:26:28
so just some sort of background here so the framework I'm going to be looking at is called reverse mathematics and the idea of reverse mathematics is to say well we've got all these mathematical theorems like for example Fishbones
00:26:42
possibility theorem or the Kerman Sunderman theorem what do we need to prove that what's actually necessary and this turns out to be intimately connected to the question of what kind
00:26:55
of solutions are there to the problems posed by theorems right so a problem might be something like an infinite society and a solution would be a non-dictatorial social welfare
00:27:07
function for that Society so what do we mean for an axiom to be necessary for proving a theorem and one obvious and basic idea is just well if the theorem employs the Axiom if
00:27:20
you can prove the Axiom from the theorem hence the reverse part of reverse mathematics and reverse mathematics is just a subfield of mathematical logic connected to computability Theory and proof Theory
00:27:35
that's really dedicated to answering questions of this form and there have been hundreds and hundreds of ordinary mathematical theorems analyzed in this way using this framework so in working
00:27:47
with this we're going to be able to place things like the Fishburne possibility theorem the kermen zonderman theorem arrows theorem into this well-understood universe of results and say exactly where in this hierarchy of
00:27:59
principles these things work out to be so the formal setting is a language called L2 of second order arithmetic and Axiom systems called systems of second order arithmetic so second order
00:28:13
arithmetic is a language in which we can talk about natural numbers 0 1 2 3 Etc and addition multiplication less than but also about sets of natural numbers
00:28:27
so the set of primes or the set of odd numbers set of even numbers the set of numbers or which are the indexes of Turing machines that halt when given their own code as an input this kind of
00:28:40
thing okay so it's a quite expressive language it's a two-sorted language in the signature and then the structures are like this I
00:28:51
won't belabor this too much um but roughly the idea is that we have this um two-part domain one part with numbers in and one part with sets of numbers more or less
00:29:03
and using this framework you can formalize a lot of analysis accountable algebra topology of complete separable metric spaces infinitely combinatorics like Ramsay's theorem mathematical logic
00:29:17
and so on and so forth and now also it turns out social Choice Theory okay and then the hierarchy that I talked about of these subsystems of second order arithmetic
00:29:31
consists of systems that extend this basic system called rca0 and the way to think about RCA 0 is well we've got some arithmetic you can do addition multiplication you can do a bit
00:29:44
of induction but it also posits the existence of computable sets of natural numbers so if you have a set of natural numbers that can be computed by a turing machine computed by an algorithm
00:29:56
then RCA 0 can prove that set exists and then we extend that with this increasing list of setting system principles that are
00:30:09
stronger and stronger I'm only going to talk about one of them so don't worry about what the others are this one aca0 Okay so yeah in case you're interested these are
00:30:28
the axioms for RCA 0. I couldn't even really fit them all on because number one is kind of long but this the sketch I gave you before is all that you really need you know that we have some arithmetic some induction and
00:30:41
comprehension for computable sets so how does reverse mathematics work well it works like this you formalize a mathematical theorem as a statement in this language of second order arithmetic
00:30:56
so if I want to prove an equivalent say between arithmetical comprehension and the Bolton or via stress theorem that every convergent sequence of real numbers has sorry every bounded sequence
00:31:09
of real numbers has a convergent subsequence I have to find a way to formalize the notion of real number and sequence and convergence and once I've done all that then I can express it as a
00:31:21
statement in this formal language and then the work starts then you prove it you prove that statement in some subsystem of second order arithmetic in my example
00:31:35
aca0 and then you go back right you do the reversal you add your formal statement to the base Theory and you prove the axioms of the theory that you're proving
00:31:48
it equivalent to right so in my example you formalized the balsano Via stress theorem you prove the formalized version of this theorem in aca0
00:31:59
and then you do the reversal by taking your formalized version of the boltonovius theorem adding it as an axiom to the axioms of RCA 0 and proving
00:32:10
arithmetical comprehension and there's a kind of deep connection between reverse mathematics and computability theory in particular this
00:32:26
idea called recursive counter example so recursive counter example is when you have a some theorem it's asking a question you know is there say
00:32:38
given us an infinite Society is there a non-dictatorial social welfare function um and if it's the case that you can construct
00:32:51
a society that's computable that has no computable Solutions that's a recursive counter example because it shows that theorem is false when you interpret its set quantifiers as ranging over the
00:33:05
computable sets so when we do these reversals from theorems to axioms very often the way it works is that we will do exactly this but within RCA 0 so we formalize this
00:33:24
construction of a recursive counter example um so you you construct the recursive counter example as a set in RCA 0 so it's a as a computable instance of your theorem
00:33:39
and then the theorem says well given say any infinite Society there exists a non-dictatorial social welfare function for that Society but then it turns out that that thing is
00:33:54
very complicated and that allows you to prove this set existence Axiom for example arithmetical comprehension okay so what is this arithmetical comprehension Axiom well it just says
00:34:10
that every set definable by a formula in the language of first order arithmetic exists this might seem kind of innocuous but in fact you can define a lot of stuff in this
00:34:27
way so we can Define limits of convergent sequences of real numbers paths through infinite but finitely branching trees so kernig's Lemma
00:34:39
the sets of codes of Turing machines that halt on all inputs so you can see at least with this last one that this is an axiom that allows us to prove the existence of non-computable
00:34:51
sets so go beyond the computable which lca0 doesn't do rca0 is computably true all of its axioms can be made True when we just look at the computable sets
00:35:04
but aca0 is not like this okay okay so that's the formal framework so let's use this methodology use this formal framework to develop a notion of social Choice theory for countable
00:35:22
societies and when you do that it turns out there are really two principal challenges the first is cardinality um so if you've got an infinite
00:35:36
set of Voters and you have arrows unrestricted domain condition then you're going to have an uncountable set of coalitions right and this won't work in second order
00:35:49
arithmetic because it's expressively very limited you can't talk about uncountable sets you can only talk about sets of natural numbers all of which are countable um
00:36:02
so that's one problem and of course the social welfare functions are also going to be uncountable objects and thus at least Primal fascia they're not going to be candidates for the kind of thing that could even be computable in principle
00:36:17
so we need to find a way to cut this down somehow in particular we need to find a way to relax this unrestricted domain condition but presumably we want to do it in a way that allows us to
00:36:29
still prove Arrow's theorem in the finite case right we don't want to relax it in a way that means that our you know Fishburne's possibility theorem is trivially true we want it to be true in a kind of substantial way so we need to
00:36:42
make sure that for example Arrow's theorem is still true in this setting and the Second Challenge is effectiveness um so roughly here the idea is just
00:36:54
we're working in this base theory that only admits the existence of computable things only has a limited amount of induction and so we need to have definitions that are tractable within
00:37:05
this weak Theory okay so how do we do it then well voters that's easy just take some infinite or possibly even finite set V of natural numbers so the natural
00:37:21
numbers are just being used to label our voters let me label them zero one two Etc um in the finite case we'll only have finitely many in the infinite case it could be all of
00:37:34
the natural numbers or it could just be a infinite subset so you know we could just have the odd numbers or the even numbers or the prime numbers doesn't matter and then the Alternatives will just be a
00:37:47
finite set of natural numbers so alternative zero alternative one alternative two and so on as long as you've got at least three and W again will be the set of all week orders
00:38:00
um on x and in this setting you have to do some coding so that you can represent these weak orders which themselves will be finite objects right because they're just like a an ordering of some finite
00:38:11
set of Alternatives so it turns out that we can code these up also by natural numbers okay so then we have to actually start doing some work and address this cardinality issue by
00:38:24
weakening the unrestricted domain condition so we are only going to look at societies with countable sets of profiles
00:38:37
so that's already one big weakening of of arrows conditions um and in fact we're going to code them up as sequences so you'll have some
00:38:49
countable sequence of profiles which can then itself be coded as a single set because of arithmetic and again with our algebra of coalitions we're going to restrict from the algebra
00:39:06
of all sets of subsets of a set of Voters to some countable algebra so it's going to contain the empty set it's going to contain the set of all voters it's going to be closed under
00:39:21
unions closed under intersections closed under relative complements but we don't put any other restrictions on except that it's also going to contain all Singletons and this is important
00:39:34
because we want to make sure that the social welfare function has the possibility of being dictatorial and if you don't have any Singletons you can't can't get that uh this kind of move was already
00:39:47
anticipated in the aces by Thomas Armstrong he generalized permanent zonderman's results to algebra of coalitions um Okay so we've got voters alternatives
00:40:04
week orderings on those Alternatives we've got countable sequences of profiles and we've got countable algebra it's also coded as sequences
00:40:15
but then once we've got this not every such collection will determine a society because we need to impose some further conditions so we have a kind of problem of richness
00:40:27
we need to make sure that the algebra and the set of profiles mostly the set of profiles are sufficiently rich to allow the proofs to go through and in particular they need to be sufficiently
00:40:39
closely related to one another so Armstrong's solution was to just say okay I'm going to take some arbitrary algebra and then I'm going to take all of the profiles that are measurable by
00:40:55
some set in that algebra but this doesn't work very well in a more effective setting because it turns out that being
00:41:08
measurable is itself kind of complicated as a property so we need to assume that we have something stronger kind of baked into our society namely uh but for every
00:41:20
profile it's going to be measurable via some uniformizing function so here's the definition suppose we've got a non-empty set of Voters and a finite set of alternatives accountable algebra of sets and
00:41:34
accountable sequence of profiles then we say that f is uniformly a measurable via Theta if Theta is a function from
00:41:45
indexes of profiles so that every profile they're coded in a sequence they're going to have an index think of it as the name of the profile and pairs of Alternatives X and Y the
00:42:00
idea is okay you give me the index of a profile all right some election and a pair of alternatives for that election and then I hand you back the index of
00:42:12
the Coalition of Voters who prefer X to y that's all there is to it okay so that's one condition the other side of this richness problem is that the set of profiles needs to be
00:42:29
sufficiently combinatorially rich with respect to the setup of coalitions um in particular and in some sense this is just to make proofs go through
00:42:42
uh our set F needs to contain profiles that encode membership not just in individual coalitions but in finite sequences of coalitions finite partitions of v in fact in fact they
00:42:56
don't need to be very large at least for the proofs related to arrows theorem to go through you need like uh partitions of length four or something in other contacts you might need more but but for this it's really pretty
00:43:09
straightforward so here's this definition it's a kind of horrible definition so don't worry too much about trying to follow the details roughly the idea is
00:43:21
that if we have any sequence of indexes of coalitions then what we need is for there to exist a
00:43:35
single profile that will give us back um different week orderings depending on
00:43:46
whether the voter is in a particular one of the coalitions we started with so here's the definition roughly yeah I guess usually I do this with a board
00:44:04
but uh okay so imagine that we have you know this room as the set of Voters and this is going to be coalition one Coalition two Coalition three and this quasi-partition embedding
00:44:18
condition is going to say something like okay there's going to exist for any three week orders a profile in which this coalition
00:44:31
as week order one this Coalition has weak order two and this Coalition has weak order three so for any three so obviously we're going to have several um different profiles depending on how
00:44:45
we choose those weak orderings okay that's that's the essential idea and this just ensures that f is Rich enough that these proofs will go through okay so that that was the hard bit
00:45:00
uh and combining these definitions we finally have the definition of a society so a society accountable Society is just a set of Voters a set of natural numbers a finite set of alternatives
00:45:13
an atomic countable algebra of coalitions and accountable sequence of profiles such that these two conditions are satisfied one f is uniformly a measurable
00:45:25
and two a is quasi-partition embedded into f and then we just say accountable Society is finite if the set of voices is finite and otherwise it's infinite so so far so straightforward
00:45:39
so in some sense this is where all the real work is in getting the right definition and this is true of a lot of reverse mathematics okay so from this point on things get easier
00:45:52
so suppose we have a countable Society then a social welfare function is going to be a function from natural numbers to weak orders why from natural numbers
00:46:04
before we had the social welfare function was a function from profiles well here the uh social welfare function is going to map indexes of profiles right the names of profiles
00:46:16
rather than the sets themselves okay um and it's going to need to satisfy the following conditions this is just unanimity formalized this is just Independence and then it's non-dictatorial if it
00:46:32
satisfies the non-dictatoriality condition as it appropriately expressed within this framework but you know really these just look exactly like the arrow conditions
00:46:44
um once it's all formalized okay so then we can formalize our three statements as follows so the Kerman Sunderman theorem for accountable societies just says okay if you've got a accountable society and a social welfare
00:47:00
function for that society and from now on we always consider social welfare functions that satisfy unanimity and Independence then the set of Sigma decisive
00:47:14
coalitions exists and it forms an ultra filter on the algebra of coalitions and its principle if and only if this social welfare function is dictatorial Arrow's theorem just says well if you've
00:47:30
got a finite Society and a social welfare function for that Society then it's dictatorial and then finally Fishbones possibility theorem for countable societies uh just says well if you have accountable
00:47:42
accountably infinite Society then there's a non-dictatorial social welfare function Sigma 4S so in some sense having done all of this work we've packaged it all up in the
00:47:55
notion of countable Society and the statements of the theorems are simple and just mirror those that we find in the classical social Choice literature
00:48:12
okay so I said that a kind of adequacy condition on this whole Enterprise was that we could prove Arrow's theorem in this setting otherwise maybe we're just going to get fishburn's theorem for free and it's not really a good modeling of
00:48:25
the original classical mathematical results so let's prove Arrow's theorem um Okay so an almost decisive Coalition is one that
00:48:39
is in some sense strictly decisive so if we Define the set of Voters into two perhaps the people on this side of the room and the people on this side of the room and all of you over here prefer X to Y
00:48:52
and all of you over here prefer y to X strictly then this Coalition is almost Sigma decisive if
00:49:03
your preference prevails in these scenarios where we can exactly Define the set of Voters in two as those who have a strict preference one way and a strict preference the
00:49:16
other way okay there's nobody havering in the middle saying oh I'm not sure maybe X maybe y okay and we then get this kind of version of a
00:49:30
classical result uh it's called various things in the literature like the contagion Lemma or the spread of decisiveness so suppose we've got accountable Society
00:49:43
then the following conditions on a coalition are equivalent uh it's decisive it's almost decisive it's almost decisive add a single
00:49:56
profile and finally it's almost uh decisive at this one particular profile that we can compute so it's like Forest just giving us a computable
00:50:08
witness for three okay and this is really the heart of the proof um it's the heart of permanent zonderman's proof of arrows theorem and of their theorem and it also allows us to prove the
00:50:24
kerman's theorem in RCA zero because if you look at this you'd see that condition four doesn't have any quantifiers in so we can prove that the set of indexes for coalitions that satisfy this
00:50:38
condition exists in RCA zero so this lets us prove the Kerman Sunderman theorem in RCA zero and because all of the ultra filters on a pro on a finite set are principle are
00:50:53
all generated by a single element and you can prove this in RCA zero just requires a bit of induction then we have the following corollary that arrows theorem is approvable in RCA 0 which is
00:51:05
what we wanted so so far so good okay so this puts us in a position to look at this Fishburne possibility theorem and it's non-constructive status and finally get
00:51:19
some kind of answers about that so here's the result so the following statements are equivalent over RCA zero and I'm going to give a number of them just for illustrative purposes
00:51:30
but only the first one and the last one are in some sense essential so fishburn's possibility theorem for countable societies is equivalent to all of the following
00:51:43
firstly the statement that for every countable Atomic algebra a over infinite set V there exists a non-principle Ultra filter U on a
00:51:55
so this is important because of course it shows us that in some sense non-principle Ultra filters are essential to proving Fishburne's possibility theorem so we had them in this setting in set
00:52:07
theory where they were these very complex big non-constructive objects down here in the countable world they're much less complex but they're still in essential for proving this
00:52:19
result the third one in the list is that for every set X the Turing jump of X exists I'll explain what this means in a sec but roughly it means the halting problem relative wise to X so a
00:52:36
non-computable set a kind of canonical non-computable cell and finally arithmetical comprehension so we have an equivalence to one of these big five subsystems of second
00:52:47
order arithmetic okay so yeah the Turing jump of a set X or X jump a little tick that's just the halting problem for Turing machines with Oracle
00:53:01
X so you have you know some enumeration of all of your Turing machines and they can appeal to this set X whatever it is and then there's a question well do they halt or not when given their own index
00:53:13
as an input um and if you assume RCA 0 and fishburn's possibility theorem then you can prove that whatever set X you have
00:53:24
the jump of that set exists so you can always prove that these non-computable sets exist so this shows that really fishburn's possibility theorem not only relies on Ultra filters but is essentially
00:53:38
non-constructive in the sense that it um relies on and implies the existence of non-computable sets okay and maybe we'll just skip the actual proofs of these
00:53:59
um okay and maybe I I'll just pause at this point and wrap up so we started with this question about whether there are non-dictatorial social welfare functions that correspond to rules so ones we can compute
00:54:13
um the answer is actually yes but only when the algebra is very impoverished so if you have an extremely simple algebra of coalitions it's possible to have a
00:54:24
computable but non-dictatorial social welfare function but it does have to be very simple indeed and in particular it can't contain a set of this form
00:54:37
I won't explain in too much detail but roughly just says um that it's like a yeah maybe I won't go into too much
00:54:54
detail on this we can cover it in the questions that people are interested um but this equivalence between Fishburne's possibility theorem and arithmetical comprehension shows that in general the answer to this question is
00:55:05
no we can't have social welfare functions that we can compute that are not dictatorial and then the second question was well our non-constructive axioms like the
00:55:18
action of choice necessary to prove Fishburne's possibility theorem and here the answer is well if we only look at countable societies such as those we might use in intergenerational Social
00:55:30
Choice Theory population ethics this kind of thing then much weaker axioms are in fact sufficient so ACA zero you know this is not just
00:55:42
approval in in ZF it's far far weaker um it's conservative over first order PA um so at least if we look at some restricted range of scenarios no you
00:55:56
don't need some incredibly powerful Axiom to prove the existence of these things but nonetheless it's still non-constructive it still involves non-computability
00:56:08
because it guarantees the existence of non-computable sets like the Turing jump okay so maybe I'll stop there thank you [Applause]
00:56:25
there are immediately some questions yes thank you uh I don't really understand the meaning you put to this or the goal you want to achieve because I see that
00:56:43
you have some nice mathematical results but are you really looking for a way to implement like what for a democratic
00:56:53
decision making system would look like because I feel like from the beginning you define like for instance a dictatorial system where someone is always satisfied but in fact
00:57:07
I could both completely randomly and be extremely lucky but we we wouldn't call this dictatorship so for instance you when you put a sedation some at the
00:57:24
beginning it was said that uh the democracy and fairness was not compatible but I don't feel like it was the the conceptual definition of
00:57:37
democracy and the dictatorship and uh and uh even though you you achieve you could achieve to find a computable function I would feel like it would be
00:57:50
more democratic to have something that we could understand that then an obscure NP complete algorithm that no one can understand yeah so in fact I share your concerns
00:58:08
about the interpretation of the non-dictatoriality Axiom um I mean I think one way of thinking about it is that the point is that there will always be a
00:58:21
dictator in the sense that even if you vote randomly and you turn out to be the dictator in that particular society for that social welfare function the point is that no matter what social
00:58:36
welfare function is chosen there will always be somebody who perhaps through Dent of uh just voting in a random way or through dint of you know enforcing their
00:58:49
will on the society whatever it is there's always going to be somebody who will always get their way obviously in the mathematical framework you can't have any kind of causal link between
00:59:01
that person voting a certain way and the social welfare function having a certain output I mean the you know that kind of thing just isn't there in the formalism of course but nonetheless I think you
00:59:15
know there is something to the name just because it's you know that there for all social welfare functions you get this result this impossibility result
00:59:27
that that there will always be somebody of this nature who uh you know whenever they prefer X to y the social preference is exactly the
00:59:39
same um yeah so that's that's the first point the second I mean yeah I I think this is all very idealized and we should worry about the
00:59:51
extent to which it's idealized I suppose part of the point of some of the slides I had towards the beginning about different Notions of infinite society that are considered in different bits of
01:00:01
uh academic research in economics and philosophy and political science is that at least this is something that people are working on I don't know if we should take it too seriously that you
01:00:15
know there might be some as you say random uh NP complete uh function that will do this um I don't think this is something that's about to have any kind of
01:00:27
application to elections in the immediate future it's more I suppose in the vein of a sort of normative project right in the sense that I mean
01:00:40
when I have my philosopher hat on I think of it like this um we want to think about possibility in a fairly broad sense it seems like computability it gives us a quite clear
01:00:53
demarcation between things that could in principle if given access to sufficient computational resources be carried out um you know thought processes or decision mechanisms that could be
01:01:08
carried out um versus those that can't be and so we have this kind of bright dividing line and there's a strength to the results in that sense right so if we show that something is non-computable then we show
01:01:20
in a certain sense that it's impossible modular any kind of discussion about hyper computation Etc and then you know
01:01:34
if it's possible then I agree that there's a big discussion to be had about whether it's feasible and whether it's open to some kind of introspection Etc and that that's all perfectly
01:01:46
reasonable I I agree completely with that but uh I think the value of these kinds of results is just that you know they contribute to this kind of more general question about possibility not necessarily in you know something that's
01:01:59
going to be implemented by us that you know can in general be possible or not be possible so I'm not sure that really answers your question but but I'm very sympathetic to the point
01:02:17
question so uh when you gave motivations about uh justifying infinite societies of Voters in media so there was one motivation with the future generations and another uh another one with the
01:02:32
states of Nature and decided okay so I see that you have infinite set of states of Nature and but then if you apply a social issues
01:02:45
mechanism to that I mean you're going to Output a pair consisting of an alternative and a state of nature but you cannot choose states of nature so how do you cope with that oh I mean the output is just going to be a
01:03:04
weak ordering of the Alternatives right it's not going to have this data in it um the the example so the example that example comes from this paper by mihara
01:03:16
and he talks about various scenarios like where we have um experts recommending uh the adoption or not of various drugs this kind of
01:03:30
thing depending on whether or not certain conditions are met um I'm not sure that in that specific example I find it super plausible that there are going to be infinitely many outcomes but infinitely many states that
01:03:43
we might want to index on but maybe we can come up with some more natural example along those lines yeah maybe we should stop here have a break and think again oh you had the question
01:03:57
what yes so okay the there's also of course all of these famous results about manipulability and strategy proofness of voting systems
01:04:18
and impossibility results like the Gibbard sassathway theorems kind of corresponds to Arrow's theorem in that setting these results also have possibility theorems in the infinite case and you
01:04:32
can do a similar kind of analysis there and get pretty similar results a similar kind of equivalence to arithmetical comprehension um so I don't know if that's what you wanted but okay
01:04:45
yes so hence non-constructive non-computable Etc yeah thank you again uh benedicta
End of transcript