1
$\begingroup$

This question is loosely inspired by the following paper of Shelah on Arrow property in which he answered a question of Gil Kalai affirmatively.

  • Shelah, Saharon, On the Arrow property. Adv. in Appl. Math. 34 (2005), no. 2, 217–251. (MR2110551)(Arxiv link)

Arrow's Impossibility Theorem (published in 1951) is one of the most central (and controversial) theorems in the social choice theory with various applications in politics and economics. Roughly speaking, it asserts that any democratic society in which finite number of voters participate in a fair election gives rise to a dictator, an individual whose personal preference always determines the fate of the whole society! In other words, a true democracy is impossible! The following post deals with some of the set-theoretic aspects of this theorem. The terminology and notation that is being used are standard.

Before getting into technicalities let me mention that you are not alone if you think that Arrow's Impossibility Theorem is weird! In fact, the notion of election as an interpretation process which transfers individual preferences of a group of people to a conclusion (i.e. the so-called community's preference) may affect the original information included in the individual votes drastically. So the result of an election highly depends on its interpretation method. Consequently, it is not immediately clear what the community's opinion is even if every single person's opinion is known! A curious reader may take a look at Condorcet paradox and this and this episodes of PBS Infinite series show for a quick introduction to the subject. See also this related MathOverflow question: Is there a truly general voting impossibility theorem that applies to real elections?

Now, let's add a precise formulation of Arrow's theorem and his definition of a "true democracy". I omit explanations about the real-life interpretations of the formal elements in the following definitions for the sake of shortening the post. You may find further information in the corresponding links.

Notation. Let $\sf{Voters}$ and $\sf{Options}$ be arbitrary sets:

(1) The set of preference orders on options, $\sf{PO(Options)}$, is the set of those $R\subseteq \sf{Options}\times \sf{Options}$ satisfying asymmetry (i.e. $aRb\rightarrow \neg bRa$) and negative transitivity (i.e. $aRb \rightarrow aRc \vee cRb$) for any $a, b, c \in \sf{Options}$.

(2) Let $\sf{Situations}$ and $\sf{SWF}$ (i.e. Social Welfare Function) be $\sf{Voters \rightarrow PO(Options)}$ and $\sf{Situations \rightarrow PO(Options)}$ function spaces respectively.

(3) For any $a, b\in \sf{Options}$, $v\in \sf{Voters}$, $U \subseteq \sf{Voters}$, $f, g\in \sf{Situations}$ and $\sigma\in \sf{SWF}$ denote:

  • $af[U]b~~$ if $\forall v\in U ~~af(v)b$
  • $f(v) =_{a,b} g(v)~~$ if $(af(v)b \leftrightarrow ag(v)b)$ and $(bf(v)a \leftrightarrow bg(v)a)$
  • $f =_{a,b} g~~$ if $\forall v\in \sf{Voters}$$~~f(v) =_{a,b} g(v)$

Definition 1. The sets of voters, options, situations and social welfare function space belong to a democratic society if for any $\sigma\in\sf{SWF}$ the following principles hold:

(A1) There are enough options: $|\sf{Options}|$$\geq 3$.

(A2) Unanimity (aka Pareto efficiency): $\forall a, b\in \sf{Options}$, $\forall f\in \sf{Situations}$, $af[\sf{Voters}$$]b \Rightarrow a\sigma(f)b$

(A3) Independence of irrelevant alternatives: $\forall a, b\in \sf{Options}$,$\forall f, g\in \sf{Situations}$$~~~f =_{a,b}g \Rightarrow \sigma(f) =_{a,b}\sigma(g)$

(A4) Non-Dictatorship: There is no $v_0\in \sf{Voters}$ such that for any $f\in \sf{Situations}$, $a, b \in \sf{Options}$, $af(v_0)b \Rightarrow a\sigma(f)b$

Theorem. (Arrow's Impossibility)(MR0039976) If $1\leq |\sf{Voters}|$$<\aleph_0$ then the axioms (A1), (A2), (A3), (A4) are inconsistent. In other words, there is no finite democratic society!

Two decades later, in 1970, Fishburn proved that in contrary to the case of Arrow's theorem, people who live in infinitely large societies may have a chance to experience a true democracy. In fact, using the Axiom of Choice he proved that Arrow's theorem fails in the infinite case.

Remark. Not to mention that infinite societies are of some interest from political and economics perspective. They are related to the intergenerational evolution of a society in long term.

Theorem. (Fishburn's Possibility) (MR0406390) If $|\sf{Voters}|$$\geq\aleph_0$ then the axioms (A1), (A2), (A3), (A4) are consistent. So an infinite democratic society is possible!

Soon afterward, by a result of Kirman and Sondermann, it turned out that Fishburn's dream of the possibility of a true democracy in an infinitely large society is nothing more than a tempting mirage because even people who live in such a community are bound to admit certain type of dictatorship imposed by an arbitrarily small group of people (rather than a single dictator) who determine the fate of any election in that community, what Kirman and Sondermann call a hidden dictatorship (or an oligarchy in some other papers).

They used a special measure space $(\sf{Voters}$$, \Psi, \mu)$ introduced by Aumann into economics as the limiting case of a sequence of finite economies. See Aumann's paper for the precise definition of this measure space.

Definition 2. Let $(\sf{Voters}$$, \Psi, \mu)$ be Aumann's measure space such that $\Psi$ is a $\sigma$-algebra of coalitions of individuals in $\sf{Voters}$, and $\mu$ is a non-negative measure on $\Psi$, such that for every coalition $C\in \Psi$ with $\mu(C)>0$ there exists a subcoalition $C'\subseteq C$ with $0<\mu(C')<\mu(C)$. Then consider the following axiom:

(A5) Non-oligarchy:

$\neg(\forall \epsilon>0~\exists \emptyset\neq C\in \Psi;~ \mu(C)>0,~\forall f\in \sf{Situations}$$~\forall a, b \in \sf{Options}$$~~~af(C)b \Rightarrow a\sigma(f)b)$

Theorem. (Kirman-Sondermann's Hidden Dictator)(MR0449477) If $|\sf{Voters}|$$\geq\aleph_0$ then the axioms (A1), (A2), (A3), (A5) are inconsistent. So any seemingly democratic infinite society contains a hidden oligarchy which acts as the dictatorship of a small minority.

The above result revived the idea of proving a universal version of Arrow's Impossibility Theorem for socieities of arbitrarily large size. It also provoked objections towards unrestricted uses of the Axiom of Choice in social choice theory which resulted in Fishburn's Possibility Theorem.

In this direction, Litak managed to derive Arrow's Impossibility Theorem in the countably infinite case from the Axiom of Determinacy, $\sf{AD}$, a widely applicable anti-choice axiom.

Theorem. (Litak's Infinite Impossibility)(Link to the paper) If $|\sf{Voters}|$$=\aleph_0$ then $\sf{AD}$ implies that the axioms (A1), (A2), (A3), (A4) are inconsistent. Thus under assumptions more reasonable than $\sf{AC}$ such as $\sf{AD}$, democracy in countably infinite societies is also impossible!

The point about Litak's proof is that it can't be generalized to the uncountable case quite easily because the Axiom of Determinacy doesn't rule out the existence of all non-principal ultrafilters. There are uncountable sets for which $\sf{AD}$ allows the existence of free ultrafilters which may cause consistency between axioms (A1), (A2), (A3), (A4) and give rise to a possibility theorem.

On the other hand, Litak's use of $\sf{AD}$ provides a large cardinal upper bound for the consistency strength of Arrow's Impossibility Theorem in the countably infinite case because based on a result of Woodin, assuming existence of $\omega$-many Woodin cardinals and a measurable above them, one may construct a model of $\sf{ZF+AD}$ and so a model of Arrow's theorem in the countably infintie case.

Here, the following natural questions arise about the consistency of Arrow's Impossibility Theorem in other infinite cardinals beyond countability:

Question. Let $\sf{AI}_{\kappa}$ (Arrow's Impossibility for $\kappa$ voters) denote the assertation that the axioms (A1)-(A4) are inconsistent under the condition $|\sf{Voters}$$|=\kappa$. As a summary of the mentioned results by Arrow, Fishburn, Litak and Woodin, we know:

$\sf{ZF}$$~\vdash \forall n\in [1,\aleph_0) ~~~$$\sf{AI}_{n}$

$\sf{ZF+AC}$$~\vdash \neg $$\sf{AI}_{\aleph_0}$

$\sf{ZF+AD}$$~\vdash$$~\sf{AI}_{\aleph_0}$

$\sf{Con(ZFC+\text{$\omega$-many Woodin cardinals and a measurable above them})}$$\Rightarrow$$\sf{Con(ZF+\sf{AI}_{\aleph_0})}$

The questions simply are:

$\sf{Con(ZFC+\text{?})}$$\Rightarrow$$\sf{Con(ZF+\forall \kappa\in Card^{>0}~~~ \sf{AI}_{\kappa})}$

$\sf{Con(ZFC+\text{?})}$$\Rightarrow$$\sf{Con(ZF+\exists \kappa\geq \aleph_{1}~~~ \sf{AI}_{\kappa})}$

In other words:

  1. What is the consistency strength of having Arrow's Impossibility Theorem in societies of arbitrarily large size in the absence of the Axiom of Choice?

  2. Define an Arrow cardinal to be an uncountable cardinal $\kappa$ which $\sf{AI}_{\kappa}$ holds. What is the consistency strength of having at least one such cardinal in the absence of $\sf{AC}$?

$\endgroup$
  • 2
    $\begingroup$ The technical content of your question boils down to the existence of nonprincipal ultrafilters. See mathoverflow.net/questions/59157/… $\endgroup$ – Monroe Eskew Jun 9 '18 at 8:08
  • $\begingroup$ @MonroeEskew Somehow yes (though, the details need checking)! So I think it would be possible to weave an answer for the above questions using the known set-theoretic theorems. Any suggestion for the missing large cardinal assumptions in the question? $\endgroup$ – Morteza Azad Jun 9 '18 at 8:27
  • 5
    $\begingroup$ Large cardinals are not relevant. It is consistent relative to ZF that ZF holds and there are no nonprincipal ultrafilters on any set. The proof of Arrow’s theorem says that the outcome of the election is determined by what happens on ultrafilter-many ballots. So in the model with no n.p.u.f.’s there is always a dictator. $\endgroup$ – Monroe Eskew Jun 9 '18 at 8:47
  • 11
    $\begingroup$ Let me add some criticism, that when you formulate your questions in these long and elaborate prosaic ways, you end up obfuscate the mathematics. Which would have been much simpler to answer otherwise, as remarked by Monroe. $\endgroup$ – Asaf Karagila Jun 9 '18 at 9:18
  • 2
    $\begingroup$ Nitpicking about your statement that "There are uncountable sets for which AD allows the existence of free ultrafilters": This is true but it's a vast understatement. AD implies the existence of free ultrafilters on $\aleph_1$ (and on the set of Turing degrees). $\endgroup$ – Andreas Blass Jun 9 '18 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.