Counter
0 2 4 0 7
Announcement

FAQs (research)

Arrow's Impossibility Theorem

Watch the following ten-minute vide for an introduction to this topic:




"Arrow’s impossibility theorem: One-shot proof made accessible" gives a precise statement of the theorem and a brief proof (based on a new proof published in 2012).


Q [Meaning of possibility].  What do you say to results proving the existence of (preference aggregation) rules satisfying all Arrow's conditions?  In other words, what is your opinion about assertions claiming that Arrow's Impossibility Theorem is wrong?

A. It's not that Arrow's Theorem is wrong.  It's just that their frameworks or assumptions are different from Arrow's.  Such possibility results (asserting all of Arrow's conditions can be satisfied) are not surprising, though you need to examine the paper in detail.  The bad news is that such a result is not useful for actual (centralized) social decision making, unless the rule is explicitly given in a concrete manner (see Remark 1 below).  Most likely, I bet, the rule is not explicitly described/constructed.

For example, when there are infinitely many voters, there does exist a voting rule satisfying all of Arrow's conditions.  But such a rule cannot be described in a concrete way nor executed algorithmically, as I showed in my paper (Mihara, 1997, Economic Theory [abstract; pdf]).  This is because all such rules are based on non-principal ultrafilters.  Generally, these are a highly non-constructive mathematical object, whose existence can be shown from the Axiom of Choice or the equivalent Zorn's Lemma in set theory.  (Mathematicians generally accept the Ultrafilter Existence Theorem and Axiom of Choice, which assert existence of certain mathematical objects.  But they are not able to describe/construct such an object in a concrete manner.  I suppose that relying on such a non-constructive mathematical object is problematic, as far as centralized social decision-making is concerned.)

Even though it is not always true (See Remark 2) to say the construction of a (non-principal) ultrafilter needs something close to Axiom of Choice, my argument in the above paper is that even the "simplest" ultrafilters are non-computable: they cannot be executed by a digital computer (algorithm, Turing machine).

Remark 1.  Michel Balinski and Rida Laraki explicitly give a notable example of an aggregation rule (a related article available in Japanese), but their framework is radically different from Arrow's.  What they aggregate is not individual preferences (ranking of alternatives) but grades assigned to each alternative.  Arrow's conditions are modified accordingly.

Remark 2.  I should separate the general argument and the specific one.  Recall that an ultrafilter is a collection of sets ("coalitions") belonging to a (Boolean) algebra (a nonempty set closed with respect to union, intersection and complementation).
Generally, finding an ultrafilter over an arbitrary algebra of coalitions is a complex problem.  You need something close to the Axiom of Choice to do that.  Ultrafilters obtained in this way are generally rather complex.On the other hand, finding an ultrafilter over a particular, fixed algebra of coalitions can be simpler---sometimes you do not need the Axiom of Choice to do that.  Considering the algebra of recursive (algorithmically decidable) coalitions (where the set of voters is {0, 1, 2, 3, ...}), I was able to construct a fairly simple ultrafilter (2001, Social Choice and Welfare [abstract; pdf]; 1999, JME [abstract; pdf]).
Q [Easy construction].  Is there an elementary way to understand why the Arrow theorem would be violated for infinitely many voters?

A.  As soon as an ultrafilter is available, it is easy to give an example of a rule satisfying Arrow's conditions.

In our voting context, an ultrafilter (just glance at the formal definition in Wikipedia) is a collection of "large" (or "decisive") coalitions (subsets of voters).  Any coalition belonging to an ultrafilter is "large" and the complements are not.  An example of an ultrafilter is the collection {S: i in S} of the coalitions that contain some fixed voter i ("dictator").  Any coalition that i belongs to is deemed "large" here.  These are called principal ultrafilters.  Assuming the Axiom of Choice (for example), one can generally show the existence of non-principal ultrafilters if the set N of all voters is infinite.  Unlike the dictator for a principal ultrafilter, no voter belongs to all coalitions in a non-principal ultrafilter.

Let U be a non-principal ultrafilter.  We "construct" a rule as follows (x and y are alternatives/candidates):
  • x is socially preferred to y if and only if the coalition {i: i prefers x to y} of voters that prefer x to y belongs to U.
In other words, we say that the society prefers x to y if a "large" number of voters prefer x to y.

To show that this rule satisfies all Arrow's conditions is fairly straightforward:
  • IIA (Independence of Irrelevant alternatives) is trivially satisfied, since social preference between x and y depends on individual preferences between x and y only, as one can see from the absence of another alternative z in the definition of the rule.
  • Unanimity (Pareto condition) is straightforward, since if everybody prefers x to y then the coalition {i: i prefers x to y} equals the set N of all voters, and one can show that N belongs to U from the definition of an ultrafilter.
  • Nondicatorship is also straightforward, since if there were a dictator i, then U would be principal.
  • You also need to show, for example, that social preference is transitive.
Q [Meaning of constructivness].  I can understand that mathematicians might not know how to construct a rule satisfying all of Arrow's conditions, but isn't it stronger to say that the rule cannot be constructed.

A.  You are absolutely right.  It is stronger to say that the rule cannot be constructed.  My position seems that any "constructible" rule had better be algorithmically computable: if your rule is not computable, then I cannot say you have a constructed a usable rule.  Fortunately (unlike the notion of constructibility) algorithmic computability is a well-accepted notion in mathematical logic and theory of computation.  Using that notion, I can define a computable rule.

In the infinite-voter framework, any rule satisfying all Arrow's conditions is based on a non-principal ultrafilter.  If the rule were computable, then there would be an algorithm that can decide, given a description (numeric code) of a coalition, whether the coalition belongs to the ultrafilter (i.e., whether the coalition is "large").  Since an ultrafilter is fairly complex mathematical object, it is not difficult to show that such an algorithm actually does not exist.  Roughly, my argument (Mihara, 1997, Economic Theory) is that if there were such an algorithm, one could use it to solve a computability problem that is known to be unsolvable.

Q [Noncomputability of ultrafilters].  Why are the voting rules based on an ultrafilter non-algorithmic, then?  What makes ultrafilters non-computable?  

A.  Well, it is easy to show that non-principal ("nondictatorial") ultrafilters do not contain any finite coalitions.  (This is intuitive since ultrafilters are supposed to consist of "large" coalitions.)  It follows that they are not computable, since computable ultrafilters always contain finite coalitions (Proposition 10, Kumabe and Mihara, 2008 JME [abstract; pdf])!

Why?  Recall that input to an algorithm (Turing machine; digital computer) is an integer or something describable by an integer.  In order to algorithmically decide whether a coalition belongs to a given ultrafilter, you first have to describe each coalition S by a code (natural number) e.  During the computation for determining whether S belongs to the ultrafilter, the number e is "decoded" to obtain information about the coalition S.  But according to our definition of a computable ultrafilter, it turns out (Theorem 4, Kumabe and Mihara, 2008 JME) that all information relevant for deciding whether S belongs to the ultrafilter is the status of only finitely many voters---up to the voter k (whether voter 0 belongs to S, whether 1 belongs to S, whether 2 belongs to S, ..., whether k belongs to S)  without loss of generality.  (The number k depends on the coalition and the code describing it.  This is analogous to a court deciding whether a particular clause applies to the case in question after asking finitely many yes/no questions.  An easy case requires just a few questions, but a complex one requires a lot.)  The computation process cannot tell whether S is finite or infinite, since all voters except 0 through k are ignored during the process.  This explains why some coalition belonging to a computable ultrafilter is finite.

Remark.  There are several ways of describing coalitions and defining computability for ultrafilters, but we think ours is the most natural. We describe each coalition S by the code (Godel) number of an algorithm that can determine the membership status of each voter.  (Such an algorithm must decide whether i belongs to S, given a voter's name i.  There are only countably many subsets of voters that can be described in this fashion, which we call "coalitions."  This is inevitable since we are applying the classical notion of algorithmic computability, where inputs into an algorithm are natural numbers.)  Our notion of a computable ultrafilter requires existence of an algorithm that can answer whether the coalition described by the code number belongs to it.  Note that there are two kinds of algorithms here: (i) those for describing coalitions and (ii) that for deciding whether the coalition belongs to the ultrafilter.  Roughly speaking, (i) describes the inputs and (ii) describes the rule.

Q [Vetoers].  I have noticed that the intersection of all "decisive" coalitions (those belonging to the non-principal ultrafilter) is empty if a rule satisfies Arrow's conditions.  Does this have anything to do with the resolution of Arrow's impossibility?

A.  If there are several voters belonging to all decisive coalitions, they are called vetoers.  The resulting rule satisfies Arrow's non-dictatorship, but (when the number of vetoers is small) it is only slightly more democratic than dictatorship.  So the emptiness of the intersection does have something to do with the resolution.  It is true that the intersection of all decisive coalitions is empty if the ultrafilter is non-principal.

In fact, you typically need just a few of them to make the intersection empty.  The minimum number of decisive coalitions whose intersection is empty is referred to the Nakamura number of the ultrafilter (more generally, that of a simple game).  For example, the Nakamura number of simple majority rule (where the number of voters is not four) is three, since you can pick three majority coalitions and make their intersection empty.

Nakamura's Theorem (an expository article available in Japanese) states that if the number of alternatives is less than the Nakamura number of a simple game, then the rule (based on the simple game) can pick an alternative without a problem.

For example, simple majority rule is okay if there are only two alternatives, since 2 < 3, where 3 is its Nakamura number.  Note that Arrow's theorem points out the problem of choosing from three or more alternatives (not two).

On the other hand, the Nakamura number of a rule satisfying all Arrow's conditions is infinite.  That is, a non-principal ultrafilter has an infinite Nakamura number.  So, you can choose from any finite number of alternatives if you use such an ultrafilter.  The infinite-voter resolution of Arrow's theorem is valid for any finite number of alternatives.

Imposing just some of Arrow's conditions forces the Nakamura number to be equal to two or three, if computability is imposed on the rule (Lemma 7 & Remark 2, Kumabe and Mihara, 2008, Social Choice and Welfare [abstract; pdf]).

Kumabe and MIhara generalize Nakamura's Theorem in several directions (Kumabe and Mihara, 2011, GEB [abstract; pdf]).

H. Reiju Mihara