The possibility of generalized social choice functions and Nash’s independence of irrelevant alternatives

Abstract

Social choice functions are generalized to handle Nash’s independence of irrelevant alternatives. Possibility and impossibility results are established.

1 Introduction

Consider a group of individuals. Each individual has a preference over alternatives, for instance social options or candidates to an election. An individual preference is supposed to be a ranking of all the alternatives, possibly with ties. On the basis of a list of individual rankings (a ranking for each individual), we want to obtain a social/collective preference or a social/collective choice thanks to a procedure. This procedure will have to satisfy properties which reflect ethical or/and political criteria. Among these, we might require that there is no individual who is able to impose his own ranking as the social preference or, in case of social choice, a social choice uniquely based upon his ranking. This is the essence of a condition called non-dictatorship. We might also demand that the social choice or the social preference respect unanimity: if every individual in the group ranks some alternative a before some alternative b, then a must be socially preferred to b or b must not be chosen when a is available. This property is generally associated with the name of Pareto because it is the source of the concept of the so-called Pareto-optimality. A third property, called independence of irrelevant alternatives, which is the main concept studied in this paper, says that when we have two lists of individual rankings of the alternatives which agree on some of these alternatives (these alternatives are ranked in the same way in the two lists), the social preference or the social choice over these alternatives must be identical.

Kenneth J. Arrow demonstrated in his RAND document of 1948 that if all individual rankings are possible, the number of individuals is finite and at least two, and the number of alternatives is at least three, there is no procedure that will satisfy the three properties.¹

To illustrate the property of independence of irrelevant alternatives, Arrow provided two examples of specific procedures violating the property. One of these was Borda’s rule, called rank-order method of voting by Arrow who had probably never heard of Borda at that time. The other was a kind of utilitarian rule based on normalized von Neumann-Morgenstern utility functions. In both cases, however, the created examples are not correct in the 1948 version. In Arrow (1950), we have again the rank-order method of voting example. In Arrow (1951), one can find the rank-order example and the utilitarian example. However, the utilitarian example has two parts and, in the second part, it is clear that Arrow perceived the difficulty and gave a correct version of the violation of the independence property as described above.

In the incorrect example for Borda’s rule, Arrow considered a list of individuals rankings over four alternatives and then deleted one option among the four. In this example, a chosen alternative among the four (which was not, of course, the one which was deleted) is not chosen among the three left. For obtaining this outcome, Arrow had to consider a list of individual rankings over the three left alternatives even if the individual rankings over the three alternatives agree with the restriction to these three alternatives of the individual rankings over the four alternatives. One must notice that the independence condition as described above considers two lists of individual rankings over the same set of alternatives.

The idea of having a consistency condition between a choice over a set of alternatives and the choice over a subset of this set can be found in the literature regarding individual choice behavior, in particular in revealed preference theory. It can also be found in a two-person context in a paper by John Nash (1950). It has been rather unfortunate that this consistency property has been called later (not by Nash himself) independence of irrelevant alternatives causing much confusion. Paramesh Ray called our attention to this confusion in a paper which has been largely unnoticed (Ray 1972). A historical survey of this strange story is presented in Salles (2023).

My current belief is that Arrow was persuaded that the two independence properties were formally related given an appropriate setting. The purpose of this paper is to introduce this setting, and to explore the properties described in this introduction and the so-called Nash independence of irrelevant alternatives property. One of the main outcome of the paper is a by-product: the two independence conditions are independent.

2 From Arrow’s framework to generalized functions

The basic ingredients of our framework are binary relations over a set of alternatives and choice functions. This is borrowed from the framework introduced by Arrow in his 1948 RAND document. Given a set Z of alternatives a binary relation over Z denoted $\succeq$ is a subset of the Cartesian product $Z\times Z$. In social choice theory this binary relation is interpreted as a preference and $(x,y) \in$ $\succeq$, (often) denoted $x \succeq y$, means ‘x is at least as good as y’. A strict preference, denoted $\succ$, is the asymmetric part of $\succeq$: $x \succ y$ if $x \succeq y$ and $\lnot y\succeq x$. An indifference, denoted $x \sim y$ is the symmetric part of $\succeq$: $x \sim y$ if $x \succeq y$ and $y \succeq x$. In the sequel the binary relations which will be considered are complete: for all x and y $\in Z$, $x \succeq y$ or $y \succeq x$. When the preferences are individual preferences, we will further assume that they are transitive: if $x\succeq y$ and $y\succeq z$, then $x\succeq z$ (this implies that strict preferences and indifference relations are also transitive). A transitive and reflexive ($x \succeq x$ for all $x \in Z$) binary relation is called (after Bourbaki) a preorder. Accordingly, individuals will be supposed to have preferences given by a complete preorder, which, when Z is finite, is a ranking of the alternatives with possible ties.

A choice function c related to a set Z is a function from the family of non-empty subsets of Z into this family such that for all $A \subseteq Z$, $c(A)\subseteq A$: c(A) represents the element(s) chosen in A. One can immediately see that if A is limited to a single element, this element has to be chosen so that we can restrict our family of subsets of Z to subsets having at least two elements for the domain of a choice function c.

We will consider a finite set N of individuals. Each individual $i \in N$ has a preference $\succeq _i$ over a finite set of alternatives X.² In the Arrovian framework, one aggregates the individual preferences to get a social preference $\succeq _S$ which we will assume to be a complete binary relation. Such a procedure will be called an aggregation function. Since in this paper, we will not restrict the individual preferences, the universality assumption will be included in the formal definition of the aggregation function. A profile $\pi$ of individual preferences is a n-list $(\succeq _1,...,\succeq _n)$ of individual preferences. Let $\mathbb {P}$ be the set of complete preorders over X, $\mathbb {P}^n$ be the n-fold Cartesian product of $\mathbb {P}$ and $\mathbb {B}$ be the set of complete binary relations over X. Then an aggregation function f is a function from $\mathbb {P}^n$ into $\mathbb {B}$: $f(\pi )=$ $\succeq _S$. When the values of f are complete preorders (transitive complete binary relations), f, following Arrow, is said to be a social welfare function.

In this paper, we are considering social choice functions rather than aggregation functions. If the functions have the same domain, their range is different in the sense that, for a profile $\pi$, the value taken by the function will be a choice function. Then, if $\mathcal {X}$ is the family of subsets of X having at least two elements and $2^X - \emptyset$ is the family of non-empty subsets of X, a choice function c is a function from $\mathcal {X}$ into $2^X - \emptyset$. Let $\mathbb {C}$ be the family of such choice functions. Accordingly, a social choice function f is a function from $\mathbb {P}^n$ into $\mathbb {C}$. This framework originated in some sense in Arrow (1948) where the condition of independence of irrelevant alternatives is ultimately given in terms of choice (even if, in Arrow, the choice derives from the social preference). Later more formal presentations are to be found, for instance, in Douglas Blair et al. (1976), Kotaro Suzumura (1976) and Amartya Sen (2017).³Arrovian independence of alternatives (A-IIA) is defined in this framework as follows. Let $S \in \mathcal {X}$, $\pi = (\succeq _1,...,\succeq _n)$ and $\pi ^{\prime } = (\succeq _1^{\prime },...,\succeq _n^{\prime })$ be two profiles such that for all $i \in N$, $\succeq _i|S =$ $\succeq _i^{\prime }|S$, and $c = f(\pi )$ and $c^{\prime } = f(\pi ^{\prime })$. Then for all $S \in \mathcal {X}$, $c(S) = c^{\prime }(S)$ (in particular, for $S = \{x,y\}$, $c(\{x,y\}) = c^{\prime }(\{x,y\})$. The Pareto condition (P) definition is given by the following statement. Let x and y be two alternatives in X, $\pi$ be a profile such that for all $i \in N$, $x \succ _i y$, and $c = f(\pi )$. Then for all $S \in \mathcal {X}$ such that $x \in S$, $y \notin c(S)$ (in particular for $S = \{x,y\}$, we must have $\{x\} = c(\{x,y\}$). Non-dictatorship (D) can be stated as follows. There exists no individual $i \in N$ such that for any profile $\pi$ and any x and $y \in X$, $x \succ _i y$ implies that, for all $S \in \mathcal {X}$ to which x belongs, $y \notin c(S)$ (in particular implies that $\{x\} = c(\{x,y\}$). Arrow famously proved that there is no social choice function satisfying A-IIA, P and D (with at least three alternatives and two individuals).

In his 1948 document as well as in his book, Arrow provides two examples of social welfare functions allegedly violating A-IIA. One is based on utilitarianism (where individual ‘utilities’ are added) and the other is what is now called Borda’s rule (‘rank-order method of voting’ in Arrow’s words). We will consider here Arrow’s example of Borda’s rule. There are three individuals and four alternatives x, y, z, and w. Individuals 1 and 2 rank them in the order $x \succ y \succ z \succ w$ and individual 3 in the order $z \succ w \succ x \succ y$. Scores are 4 for the alternative ranked first, 3 for the alternative ranked second etc. Then x is chosen. If alternative y is deleted, with scores 4, 3, 2 or 3, 2, 1 ‘we find that x and z are now tied’ (Arrow 1948, page 16). It seems that Arrow’s desire was to get rid of interpersonal utility comparisons and, at the same time, to incorporate a (quite strong) consistency condition, viz., if the set of alternatives shrinks, the chosen alternatives in the smaller set must be identical to the intersection of the chosen alternatives in the larger set with this smaller set.⁴ However, from a formal viewpoint the individual preferences over a smaller set, say $Y \subset X$, give rise to a different set of profiles so that the domain of the social choice function has also shrunk and the range of the function has also been modified: the function, as defined, cannot be the same function.

It is, however, possible (and easy) to devise a correct example. For instance, let us consider four alternatives a, b, c and d and three individuals. Individual 1 complete preorder is given by $a \succ _1 b \succ _1 c \succ _1 d$, individual 2 complete preorder is given by $c \succ _2 b \succ _2 a \succ _2 d$ and individual 3 complete preorder is given by $d \succ _3 c \succ _3 b \succ _3 a$. The score of a in this first profile, $\pi$, is 4 and the score of b is 5 so that $b \succ _S a$. Consider now a second profile, $\pi ^{\prime }$, where individuals 2 and 3 have the same preorder but individual 1 ranks the alternatives in the following way: $a\succ _1^{\prime } c \succ _1^{\prime } d \succ _1^{\prime } b$. The score of a has not been modified, but b has lost two points so that $a \succ _S^{\prime } b$ even though in both profiles individual 1 prefers a to b. Regarding a and b we have in terms of binary relations exactly the same information in both profiles.

To take account of a variation of the considered set of alternatives, it seems that we must enlarge the domain (and range) of the social choice function. This idea is not new. As far as we know there are some hints in Georges Bordes and Nicolaus Tideman (1992). However these authors separate two concepts: the aggregation function (our social choice function) and what they call the voting rule. Our own purpose is to contemplate a single concept, which is, to some extent, what has been done in Partha Dasgupta and Eric Maskin (2008) and in Michel Balinski and Rida Laraki (2010).

3 An expanded framework

Our main objective is to propose a formal framework which can handle situations where some alternatives (or a unique one) ‘drop out’.⁵ For this we will expand the domain and the range of the social choice functions. Individual preferences are going to be defined not only over X, the set of alternatives, but also over all significant subsets of X, that is, in our notation over all $Y \in \mathcal {X}$. The individual i’s preference over $Y \in \mathcal {X}$ will be denoted by $\succeq _i^Y$. A profile/n-list $(\succeq _1^Y,...,\succeq _n^Y)$ will be denoted by $\pi ^Y$. The set of such profiles will be written $\Pi ^Y$ (note that with this new notation $\Pi ^X = \mathbb {P}^n$). Given such a subset Y of X, we will define choice functions on $2^Y - \emptyset$ and denote them $c^Y$. The family of these choice functions will be written $\mathbb {C}^Y$. We can now define a n-generalized social choice function.

Definition 1

A n-generalized social choice function f is a function from $\bigcup _{Y \in \mathcal {X}} \Pi ^Y$ into $\bigcup _{Y \in \mathcal {X}} \mathbb {C}^Y$ such that for $\pi ^Y$, $f(\pi ^Y) \in \mathbb {C}^Y$ ($c^Y = f(\pi ^Y)$).

We can even have a more ‘general’ function if we suppose a variable set of individuals, with subsets of N (with at least two (or three) individuals) so that we have profiles made of 2-lists, 3-lists etc. Then we have to take a double union, over the length of the lists and over the subsets of X. For our present purpose we fix the set of individuals.

We now define the conditions to be satisfied by such a function by slightly modifying Arrow’s conditions and introducing a social choice version of Nash’s independence of irrelevant alternatives.

Properties of a n-generalized social choice function

Generalized Pareto principle (gP). Let $Y \in \mathcal {X}$, and x, $y \in Y$. If, in a profile $\pi ^Y \in \Pi ^Y$, we have for all $i \in N$, $x\succ _i^Yy$ then $y\notin c^Y(Z)$ for all $Z \subseteq Y$ to which x belongs (where $c^Y = f(\pi ^Y)$).

Generalized non-dictatorship (gD). There is no individual $i \in N$ such that for any $Y \in \mathcal {X}$, any profile $\pi ^Y \in \Pi ^Y$ and any x, $y \in Y$, if $x\succ _i^Y y$, then $y\notin c^Y(Z)$ for all $Z \subseteq Y$ to which x belongs (where $c^Y = f(\pi ^Y)$.

Generalized Arrow independence of irrelevant alternatives (gA-IIA). Let $Y \in \mathcal {X}$, $Z \subseteq Y$ and $\pi ^Y$ and $\pi ^{\prime Y} \in \Pi ^Y$ be two profiles such that, for each $i \in N$, $\succeq _i^Y|Z =$ $\succeq _i^{\prime Y}|Z$. Then $c^Y(Z) = c^{\prime Y}(Z)$ (where $c^Y = f(\pi ^Y)$ and $c^{\prime Y} = f(\pi ^{\prime Y}$)).

Nash independence of irrelevant alternatives (N-IIA). Let Y and $Z \in \mathcal {X}$ with $Z \subseteq Y$, $\pi ^Y$ and $\pi ^Z$ be two profiles such that, for each $i \in N$, $\succeq _i^Z =$ $\succeq _i^Y|Z$, and $c^Y = f(\pi ^Y)$ and $c^Z=f(\pi ^Z)$. Then, if, for any W such that $W \subseteq Z$, $c^Y(Z)\cap W \ne \emptyset$ then $c^Z(W)=c^Y(Z)\cap W$.⁶

There is no need to comment on gP and gD since these properties are rather straightforward generalizations of the Arrovian versions of the Pareto principle (unanimity property) and the non-dictatorship. We just want to outline again that, when we are considering the choice in a two-element subset, if one of these elements is discarded the remaining one has to be chosen and is accordingly the unique chosen element.

The property gA-IIA is not crucial for our purpose. It has been introduced regarding tangential results about the possible relations between generalized Arrovian independence and Nash’s independence. It seems that this kind of relations is the object of a rather long development in Balinski and Laraki (2010) where page 59 it is said (this is our interpretation, but we may be wrong) that N-IIA implies gA-IIA. This would immediately lead us to an impossibility theorem as a corollary of Arrow’s theorem.

While the definition of N-IIA may seem complicated, it permits, however, to handle Arrow’s example mentioned above concerning a ‘dropping’ argument: we would have

$$\begin{aligned}&Y = \{x,y,z,w\},\\&Z=\{x,z,w\},\\&c^Y(Y)=\{x\}, \end{aligned}$$

i.e., the choice is over the subset of Y which is Y itself, and $c^Z(Z)=\{x,z\}$, i.e., the choice is over the subset of Z which is Z itself.

Arrow’s example presented above demonstrates that Borda’s rule fails to satisfy N-IIA. In the following, we give examples showing that plurality rule and anti-plurality rule also fail to satisfy N-IIA. We also give another example, sharper than Arrow’s example, regarding Borda’s rule. To remain as simple as possible, we will assume that the individual preferences are given by linear orders (anti-symmetric complete preorders, there are no ties/indifference). For scoring rules, points are attributed to alternatives on the basis of their positions in each individual preference and, given a profile of individual preferences over Y, the score of an alternative a, $sc^Y(a)$, is the summation over all the individuals of points attributed to this alternative. We define n-generalized social choice function on the basis the maximum scores: for a given profile $\pi ^Y$ of individual preferences over a subset of X, $Y \in \mathcal {X}$, for Z such that $Z \subseteq Y$, $f(\pi ^Y) = c^Y$ and $c^Y(Z) = \{x \in Z: sc^Y(x)= max_{y\in Z}(sc^Y(y))$.

Plurality rule

In plurality rule, for a given individual preference, one point is attributed to the alternative ranked first and 0 point to all other alternatives. Let us consider the following profile with $X =\{a,b,c\}$ and $\#N=7$,

• three individuals have a preference given by $a \succ _i^X b \succ _i^X c$,

• two individuals have a preference given by $b \succ _i^X c \succ _i^X a$, and

• two individuals have a preference given by $c \succ _i^X b \succ _i^X a$.

• Obviously, $c^X(X)= \{a\}$.

Now let us consider $Y=\{a,b\}$. The ‘new’ profile of individual preferences over $\{a,b\}$ is:

• three individuals have a preference given by $a \succ _i^Y b$, and

• four individuals have a preference given by $b \succ _i^Y a$.

Obviously, $c^Y(Y) = \{b\}$ even though $c^X(X)\cap Y$ is non-empty and then $c^Y(Y)$ should be equal to $c^X(X)\cap Y$ to satisfy N-IIA.

Anti-plurality rule

In anti-plurality, for a given individual preference, one point is given to all alternatives except the alternative which is ranked last which gets 0 point. Let us consider the following profile with $X = \{a,b,c\}$ and $\#N=7$,

• three individuals have a preference given by $a \succ _i^X b \succ _i^X c$, and

• four individuals have a preference given by $c \succ _i^X b \succ _i^X a$.

• Obviously, $c^X(X)= \{b\}$.

Now let us consider $Y=\{b,c\}$. The restricted profile over $Y=\{b,c\}$ is:

• three individuals have a preference given by $b \succ _i^Y c$, and

• four individuals have a preference given by $c \succ _i^Y b$.

Obviously, $c^Y(Y)= \{c\}$ even though $c^X(X)\cap Y$ is non-empty and then $c^Y(Y)$ should be equal to $c^X(X)\cap Y$ to satisfy N-IIA.

Borda’s rule (another example)

Our purpose is to give an example which is somewhat ‘sharper’ than Arrow’s example. For a subset Y of k alternatives, and a linear ordering over Y, with Borda’s rule $k-1$ points are attributed to the top ranked alternative, $k-2$ to the alternative ranked second etc. till 0 to the alternative ranked last. Let us consider the following profile with $X =\{a,b,c,d,e\}$ and $\#N=3$,

• $a \succ _1^X d \succ _1^X c \succ _1^X b \succ _1^X e$

• $c \succ _2^X b \succ _2^X a \succ _2^X e \succ _2^X d$

• $e\succ _3^X d \succ _3^X b \succ _3^X a \succ _3^X c$.

The maximum score, 7, is obtained by a: $c^X(X)=\{a\}$.

Let us consider $Y_1 = \{a,b,c\}$. The restricted profile $\pi ^{Y_1}$ is:

• $a \succ _1^{Y_1} c \succ _1^{Y_1} b$

• $c\succ _2^{Y_1} b \succ _2^{Y_1} a$

• $b \succ _3^{Y_1} a \succ _3^{Y_1} c$.

This is a profile generating a Condorcet cycle and then the three alternatives with a 2, 1, 0 system of points have the same score. Accordingly, $c^{Y_1}(Y_1)= \{a,b,c\}$.

Let us now consider the subset $Y_2 = \{a,b\}$. The restricted profile is:

• $a \succ _1^{Y_2} b$

• $b \succ _2^{Y_2} a$

• $b \succ _3^{Y_2} a$

  and obviously $c^{Y_2}(Y_2) = \{b\}$.

For both $Y_1$ and $Y_2$ we can easily see that N-IIA is violated.

On the basis of this and other examples, one could imagine that there is, underlying, a general impossibility theorem of the Arrovian type (probably an impossibility theorem which Arrow himself was thinking of) saying there is no n-generalized social choice function satisfying gP, gD and N-IIA. But this is not the case.

Theorem 1

There exists a n-generalized social choice function satisfying gP, gD and N-IIA.

Proof

Let $\succeq$ be a binary relation. The reverse binary relation, $\succeq ^{\prime }$, of $\succeq$ is defined as follows:

• $x \succ ^{\prime } y$ if $y \succ x$, and

• $x \sim ^{\prime } y$ if $x \sim y$ (note that $\sim$ is symmetric).

It is obvious that the reverse of a complete preorder is a complete preorder. On the basis of reverse complete preorders, we construct a generalized social choice function. In the general case, for a profile $\pi ^X$, we consider, for subsets $Y \in \mathcal {X}$, the profiles $\pi ^Y$ constructed from $\pi ^X$ by restricting the individual preferences to Y:

$$\begin{aligned} \pi ^Y = (\succeq _1^Y,...,\succeq _n^Y) = (\succeq _1^X|Y,...,\succeq _n^X|Y). \end{aligned}$$

The choice function $c^Y = f(\pi ^Y)$ is given by taking the set of maximum elements of Z ($Z\subseteq Y$) according to $\succeq _1^Y$, i.e., by taking the most preferred elements of individual 1: $c^Y(Z) = \{x \in Z: x\succeq _1^Y y$ for all $y \in Z\}$.

However, in a particular case (i.e., for a particular profile), viz. when all the individuals who are not 1 have the same preference and this preference is the reverse of individual 1’s preference, the choice function is given by taking the maximum elements of this reverse preference which are the minimum elements of Z according to $\succeq _1^Y$: $c^Y(Z) = \{x \in Z: y\succeq _1^Y x$ for all $y \in Z\}$. One must observe some obvious facts: when we start with X and delete elements to get a proper subset of X, the restricted complete preorder is a complete preorder over the proper subset and the reverse of this complete preorder over the proper subset is the restricted reverse complete preorder of the original complete preorder.

It is easily seen that condition gP is satisfied: if all individuals agree to say that x is preferred to y, we are in the general case and since individual 1 prefers x to y, y will not be chosen in a set which includes x as y can not be a maximum element in this set.

Property gD is also satisfied. Incidentally, the construction is based on the existence of a dictator (individual 1) and the particular case has been mainly created to get gD.

What about N-IIA? Since the construction of the n-generalized social choice functions is based upon the existence of maximum and minimum elements of a set according to a complete preorder, it is rather evident that when other elements are dropped, the maximum or minimum elements remain maximum or minimum elements. When there are two or more maximum elements and some are dropped but a few remains, then those few will be chosen in the smaller set. If all the maximum elements are dropped then the intersection of the chosen elements in the larger set with the smaller set will be empty. This proves the theorem.

Even though the proposed construction proves the theorem, the kind of rule it proposes, it is an euphemism, is not very appealing. Accordingly, one can wonder whether there exists more satisfactory constructions, or whether our construction can suggest a reinforcement of the properties to obtain an impossibility result.

A first comment regarding the construction is that it could also be a construction denying Arrow’s theorem, in particular if we follow what we perceived in Balinski and Laraki’s implication mentioned above that something like N-IIA implies gA-IIA. If this is true the construction would satisfy gP, gD and gA-IIA, disproving Arrow’s theorem (when only the set X in all our definitions is taken into account). Obviously, this is not the case as it can be easily seen that the construction does not satisfy gA-IIA. Let $X=\{a,b,c\}$ and $\pi ^X$ be a profile $(\succeq _1^X,\succeq _2^X,\succeq _3^X)$ such that

• $a \succ _1^X b\succ _1^X c$

• $c\succ _2^X b \succ _2^X a$

• $b\succ _3^X c\succ _3^X a$.

Then let us consider the profile $\pi ^{\prime X}$ such that

• $\succeq _1^{\prime X} =\succeq _1^X$

• $\succeq _2^{\prime X} = \succeq _2^X$

• $c \succ _3^{\prime X} b \succ _3^{\prime X} a$.

For the first profile we are obviously in the so-called general case so that $c^X(\{a,b\})= \{a\}$ and for the second profile in the so-called particular case so that $c^{\prime X}(\{a,b\})= \{b\}$ while the individual preferences over $\{a,b\}$ are identical in the two cases.

4 The failure of a Pareto optimality based rule

In the context of aggregation rules, Sen (1970, 2017) considers what he calls Pareto extension rules. One such rule can be described as follows. Given two alternatives x and y, x is socially preferred to y ($x\succ _S y$) if all the individuals prefer x to y (for all $i \in N$, $x\succ _i y$), and $y \succeq _S x$ otherwise. This rule satisfies all of Arrow’s properties (Pareto principle, non-dictatorship and independence of irrelevant alternatives) but fails to be a social welfare function because $\succeq _S$ is not transitive (in fact, $\sim _S$ is not transitive).

In our choice-theoretic and generalized setting, a somewhat similar rule, is the following. For a given profile $\pi ^Y$ of individual preferences over a subset of X, $Y \in \mathcal {X}$, for Z such that $Z \subseteq Y$, $f(\pi ^Y) = c^Y$ and $c^Y(Z) = \{x \in Z$: there is no $y \in Z$ such that for all $i\in N$ $y\succ _i x \}$. Obviously, this n-generalized social choice function satisfies condition gP (it is based upon gP) and gD. We now show that it violates N-IIA. Let us consider a set $X=\{a,b,c,d,e\}$, a set N with $\#N=3$ and the following profile $\pi ^X$:

• $a\succ _1^X b\succ _1^X c \succ _1^X d\succ _1^X e$

• $b\succ _2^X c\succ _2^X d\succ _2^X e\succ _2^X a$

• $c\succ _3^X d\succ _3^X e\succ _3^X a \succ _3^X b$.

We can see that d is Pareto-dominated by c and e is Pareto-dominated by d. Accordingly, $c^X(X)=\{a,b,c\}$.

Let us now consider the subset $Y=\{a,b,d\}$ and the profile $\pi ^Y$ based upon the restricted individual preferences:

• $a\succ _1^Y b \succ _1^Y d$

• $b\succ _1^Y d \succ _1^Y a$

• $d\succ _1^Y a \succ _1^Y b$.

Again this profile would generate a Condorcet cycle and each alternative in Y is not Pareto-dominated by another alternative in Y: $c^Y(Y)=\{a,b,d\}$. One can observe that $c^X(X)\cap Y$ is non-empty ($=\{a,b\}$) and that $c^X(X)\cap Y \ne c^Y(Y)$. This shows that N-IIA is not satisfied.

It can be verified, however, that gA-IIA is satisfied. Consequently we have exhibited a n-generalized social choice function which satisfies gP, gD and gA-IIA. This does not contradict Arrow’s Theorem (which, of course, is impossible) as will be shown below. What we wish to outline at this step is that the n-generalized social choice function of Theorem 1 where we construct a function satisfying gP, gD and N-IIA (but not gA-IIA) can be contrasted with the present function which satisfies gP, gD and gA-IIA (but not N-IIA). We can argue, on this basis, that the two conditions of independence of irrelevant alternatives are independent.

In the example given above, to prove that the function does not satisfy N-IIA, we show that $c^X(X)\cap Y \ne c^Y(Y)$, precisely $\{a,b\} \ne \{a,b,d\}$. But we can observe that $\{a,b\} \subseteq \{a,b,d\}$. Let us introduce a weak form of N-IIA where equality is replaced by inclusion. This property can be associated with Chernoff (1954) or Sen (1970, 1971, 1982, 2017).

A further property of a n-generalized social choice function.

Chernoff independence of irrelevant alternatives (C-IIA). Let Y and $Z \in \mathcal {X}$ with $Z \subseteq Y$, $\pi ^Y$ and $\pi ^Z$ be two profiles such that, for each $i \in N$, $\succeq _i^Z =$ $\succeq _i^Y|Z$, and $c^Y = f(\pi ^Y)$ and $c^Z=f(\pi ^Z)$. For any W such that $W \subseteq Z$, $c^Y(Z)\cap W \subseteq c^Z(W)$.

Theorem 2

There exists a n-generalized social choice function satisfying gP, gD, gA-IIA and C-IIA.

Proof

Consider the n-generalized social choice function based on Pareto domination which has been proposed above. We just have to prove that it satisfies C-IIA. It suffices to show that if $x \in c^Y(Z)\cap W$ then $x \in c^Z(W)$. Suppose not. Then there exists an alternative $y \in W$ such that for all $i \in N$, $y \succ _i^Z x$. But since $W \subseteq Z \subseteq Y$, y belongs to Y and, of course, for all $i \in N$, $y\succ _i^Y x$, and $x \notin c^Y(Z)$, a contradiction.

Consequently, this function satisfies both gA-IIA and C-IIA. In this context the Chernoff property and the Nash property can be compared in the aggregation functions framework to transitivity of $\succeq _S$ and transitivity of (only) $\succ _S$ (this property of transitivity of the asymmetric part of $\succeq _s$ has often been called quasi-transitivity, following Sen (1970)). A very simple example will explain our comment. Let us consider two individuals, three alternatives $\{a,b,c\}$ and the following profile:

• $a \succ _1 b \succ _1 c$

• $c \succ _2 a \succ _2 b$.

In the aggregation function context with the appropriate Pareto extension rule we get $a \succ _S b$, $a \sim _S c$ and $b \sim _S c$: $\succeq _S$ is not transitive (precisely $\sim _S$ is not transitive).

Now in our generalized social choice function setting:

• $c^{\{a,b,c\}}(\{a,b,c\})=\{a,c\}$

• $c^{\{b,c\}}(\{b,c\}) = \{b,c\}$

• $c^{\{a,b,c\}}(\{a,b,c\})\cap \{b,c\} = \{c\} \subset c^{\{b,c\}}(\{b,c\})$.

5 Comments

A number of questions remains. What we intend to find was a kind of result similar with Arrow’s theorem, i.e., to show that several easily admissible properties, including Nash’s version of independence of irrelevant alternatives, of a generalized social choice function are inconsistent. The set of properties we select are insufficient for this outcome. However our constructive proof is based upon a rather caricatural function based on quasi-dictatorship. A possible route to avoid this positive result would probably be to consider ‘more anonymous’ rules.

Among these ‘more anonymous’ rules, we further demonstrate that some generalized social choice functions based on scoring rules fail to satisfy N-IIA. Incidentally, two of them (plurality and anti-plurality) also fail to satisfy gP. It seems to us that a conjecture saying that all scoring rules based n-generalized social choice functions fail to satisfy N-IIA is provable. We suspect that this can be done by using Saari’s approach.⁷