1 Introduction
1.1 Background
This paper contributes to a question with a long history. A (single-valued) choice function assigns to each choice set (i.e., subset of the set of all alternatives) an element of that choice set. The condition of independence of irrelevant alternatives (IIA) requires that if the alternative chosen from a choice set is still available in a subset of the choice set, then it should also be chosen from that subset. This condition already occurs as condition no. 7 in Nash’s axiomatic bargaining model (1950).1 Closely related is the Weak Axiom of Revealed Preference (WARP), which says that if x is chosen from some choice set where also y is available, then y should never be chosen from any choice set where also x is available.2 Another way of phrasing this, is that the preference relation revealed by the choice function has no cycles of length two. As is well-known and easy to show, for collections of choice sets that are closed under nonempty intersection, IIA and WARP are equivalent.3
1.2 This paper: main outlook
In this paper, we consider choice correspondences instead of choice functions: these assign to each choice set a nonempty subset, rather than a unique element. In the classical choice literature, often the expression ‘choice function’ is used where we use ‘choice correspondence’. The main interpretation that we have in mind is that, indeed, a set is chosen, rather than a short-list from which later a singleton has to be chosen—for instance, a set of courses (starter, main, dessert) and a selection of wines in a restaurant; or a committee of fixed or variable size in a society or university. This differs from the, often employed, interpretation that the chosen set is a kind of preamble or, indeed, short-list for the final winner, although this interpretation is not excluded by our approach.4
Advertisement
Our purpose is to consider extensions of IIA to this model, and their relation with an extended version of WARP. All these extensions can already be found in the existing literature, but we will establish some relations which, to the best of our knowledge, are new. Moreover, in the last part of the paper (Sect. 4) we study, in detail, choice correspondences that satisfy the strongest extension of IIA, by means of so-called strong sets: choice sets that uniquely determine the choice correspondence, as will be explained in more detail below.
1.3 Extensions of IIA
We consider three extensions of IIA for choice functions to choice correspondences.
The probably earliest extension of IIA to choice correspondences has again been proposed by Nash in an informal note in 1950 (see Shubik 1982, p. 420): if F is the choice correspondence, X is a choice set, and F(X) has a nonempty intersection with a subset Y of X, then F(Y) is equal to this intersection. The same condition also appears as Postulate 6 in Chernoff (1954) and Condition C4 in Arrow (1959). This extension is a natural one if the set of alternatives chosen by a choice correspondence is viewed as the set of best alternatives (in some sense or another) among the available ones: consequently, each of these alternatives is also best in any subset of available alternatives to which it belongs. We refer to this extension simply again as Independence of Irrelevant Alternatives (IIA).5
The second extension we consider requires, in the same situation, that, F(Y) be contained in the intersection of F(X) and Y. Following a similar interpretation, F still chooses among the best alternatives, but not necessarily all available ones. Think of choosing a committee within a society: for a subset of the society one may need to choose a strictly smaller committee, even if more members of the original committee are still available. Or, in terms of a restaurant’s menu choice, not only the lunch menu may be a subset of the dinner menu, but also lunch itself may be lighter than dinner: one may want to consume wine of just one kind instead of several, even if more kinds are still available. This extension appears as condition W2 in Schwartz (1976). Clearly, it is a weakening of the first extension, and we call it Weak IIA (WIIA).
Advertisement
The third extension to be considered, says the following. If Y is contained in X and contains F(X), then F(Y) is equal to F(X). One interpretation is clear: if we regard F(X) as the set of best choices from X, and all these choices are still available in a smaller set Y, then they are also the best choices in Y. In terms of the restaurant’s menu: if the collection of available dishes decreases but the courses that we chose earlier are still available, then we choose them again. Clearly, this extension is another weakening of IIA, and we call it Restricted IIA (RIIA). Also this condition has appeared before in the literature. See Aizerman (Aizerman 1985, Definition 1), and for instance Johnson and Dean (Johnson and Dean 2001, Lemma 2). For the case of finitely many alternatives, it coincides with the ‘attention filter’ condition in Masatlioglu et al. (2012). It is also equivalent to ‘Condition \(\hat{\alpha }\)’ in Brandt and Harrenstein (2011), see below; and it appears as ‘Irrelevance of Rejected Items’ in Alva (2018).6
1.4 Extension of WARP
As to revealed preference for sets, our main condition is the following. If, from some choice set Z, the subset X is chosen while also Y is available (i.e., Y is also a subset of Z), then Y should never be chosen from some other choice set \(Z'\) if also X is available. This is an obvious extension of the Axiom of Revealed Preference for choice functions to choice correspondences, and we use the same name for it, again abbreviated to WARP. The expression WARP is also used in Alva (2018) for the same condition. Brandt and Harrenstein (2011) consider the condition of ‘set-rationalizability’, which looks very similar to WARP. Indeed, the two conditions turn out to be equivalent (see Sect. 2).
1.5 Our results
In Sect. 2, we formally introduce the model, and the conditions IIA, WIIA, RIIA, and WARP. The set of alternatives is an arbitrary finite or infinite set without any additional structure imposed.
In Sect. 3, we establish relations between these conditions. Theorem 3.1 says that RIIA and WARP are equivalent. This is in line with Theorem 1 in Alva (2018). It is also in line with results in Brandt and Harrenstein (2011). Specifically, they consider a property called Condition \(\hat{\alpha }\) and show (their Theorem 2) that this condition is equivalent to what they call ‘set-rationalizability’. They also show (their Lemma 1) that Condition \(\hat{\alpha }\) is equivalent to RIIA (they do not use this name). Since RIIA is equivalent to WARP, it follows that their set-rationalizability condition is equivalent to WARP: i.e., it excludes cycles of length two in the revealed preference relation on choice sets.
We also show that IIA is stronger that WARP; Theorem 3.6 says, that IIA is equivalent to WARP combined with a condition called preference axiom (PA).7 This condition PA says that if a set X is revealed preferred to a set Y and a subset Z of X contains the intersection of X and Y, then also Z is revealed preferred to Y. In the special case that X and Y are disjoint, PA thus implies that every subset of X is revealed preferred to Y. On a general note, consider the interpretation of a choice correspondence as picking the set of ‘best’ alternatives (from which, perhaps, later on a definite choice can be made, like in the case of a short-list). As mentioned, this interpretation is reflected in particular by IIA. Put differently, complementarities between alternatives are not considered. Revealed preference on sets, however, may reflect such complementarities. To illustrate this, suppose a diner must choose a meal from two dishes, steak s or fish f, and two wines, red r or white w. When everything is available the diner selects steak and red wine, hence \(F(\{s, f , r,w\}) = \{s,r\}\) and \(\{s,r\}\) is revealed preferred to \(\{f,w\}\). However, if the restaurant runs out of red wine the diner selects fish and white wine, hence \(F(\{s, f , w\}) = \{f,w\}\) and \(\{f,w\}\) is revealed preferred to \(\{s\}\).8 This is a violation of IIA but it is not difficult to extend the definition of F so that it satisfies WARP. Our axiom PA on revealed preference excludes such a situation: with \(X=\{s,r\}\), \(Y=\{f,w\}\), and \(Z=\{s\}\), it would require that \(\{s\}\) is revealed preferred to \(\{f,w\}\).
We further show (Theorem 3.8) that IIA implies that the revealed preference relation is transitive and acyclic.9
The remainder of Sect. 3 is devoted to studying the relation between WIIA and WARP. One of the results (Theorem 3.11) says that if the choice correspondence F is a projection (i.e., \(F = F \circ F\)), then WIIA implies WARP. In turn, WARP implies that F is a projection, as is also observed in Brandt and Harrenstein (2011). If the set of all alternatives is finite, then WIIA implies that a sufficiently often repeated version of the choice correspondence satisfies WARP (Corollary 3.13).
In Sect. 4, we return to the IIA condition and consider so-called ‘strong sets’. A set of alternatives S is a strong set at a choice correspondence if to any choice set X which has a nonempty intersection with S, the choice correspondence assigns exactly this intersection. We show that under IIA these strong sets form a partition of the set of all alternatives, the elements of which are completely and acyclically ordered by the revealed preference relation (Theorem 4.6). This way, these strong sets characterize the (IIA) choice correspondence.
1.6 Further literature
1.6.1 Rationalizability
Following a tradition initiated for consumer theory by Samuelson (1938) and Houthakker (1950), and continued for general choice problems by—among others—Arrow (1959) and Richter, (1966), there is a large literature focusing on ‘rationalizability’: when does a choice correspondence pick the set of those alternatives that are maximal for some binary relation on the set of alternatives? Arrow (1959) shows that a choice correspondence is rationalizable by a complete and transitive binary relation if and only if it satisfies IIA. Sen (1971) shows that a choice correspondence is rationalizable by a binary relation if and only if it satisfies the Chernoff property (see Sect. 1.6.2) and a condition, proposed as Property \(\gamma \), but later also referred to as the Expansion condition (e.g., Moulin 1985).10 Adding to this the Aizerman condition (see again Sect. 1.6.2) results in the choice correspondence being rationalizable by an ordering which is complete and has a transitive strict part (Schwartz 1976; Moulin 1988). Finally, Aizerman and Malishevski (1981) show that a choice correspondence satisfies both the Chernoff property and the Aizerman condition if and only if it is pseudo-rationalizable by a collection of single-valued, complete, and transitive orderings; that is, if in each choice set, the choice correspondence picks the maximal elements of all the orderings in this collection.
In our context, rationalizability would naturally mean that there is a binary relation on the set of choice sets (rather than single alternatives) such that the choice correspondence picks that subset from a choice set that is maximal according to this binary relation. In our model, this is equivalent to WARP. We refer to Theorem 1 in Alva (2018) for a formalization of this observation. A further requirement would be that this relation is representable by a (utility) function, but for this, the binary relation should be acyclic.
1.6.2 Other IIA extensions
Apart from IIA, WIIA, and RIIA, there are other possible extensions of IIA from choice functions to choice correspondences.
A fourth possible extension says that, if \(Y\subseteq X\) and \(F(X) \cap Y \ne \emptyset \), then F(Y) should at least contain the intersection of F(X) and Y. As an interpretation, it could be that additional best alternatives become available in the smaller set. For instance, a first preferred choice of wine from a restaurant’s menu is no longer available, making a second preferred choice a best alternative (additional to the still available best menu choices). This condition has first been proposed as Postulate 4 in Chernoff (1954), and has consequently been referred to as the Chernoff property (e.g., Moulin 1985; 1988). It also appears as Property \(\alpha \) in Sen (1971).
Fifth, a still weaker version of the first three conditions is the following (e.g., Fishburn 1973): if F(X) is contained in Y, then F(Y) should be contained in F(X). This condition, studied in Aizerman and Malishevski (1981), is usually referred to as the Aizerman condition; it is implied by Condition W3 in Schwartz (1976).
1.7 Organization of the paper
In Sect. 2, we introduce the model and the main conditions on a choice correspondence that we consider. Section 3 studies the relations between these properties. Section 4 introduces the collection of strong sets and studies its relation with IIA. Section 5 concludes with a summary of the main results of the paper and a few open questions.
2 Model and properties
Let A be a finite or infinite set of alternatives and let \(\mathcal {A}\) denote the set of its nonempty subsets.11 A choice correspondence is a map \(F: \mathcal {A}\rightarrow \mathcal {A}\) such that \(F(X) \subseteq X\) for every \(X \in \mathcal {A}\). A choice correspondence F induces a binary relation \(R_F \subseteq \mathcal {A}\times \mathcal {A}\) (hence, on sets rather than single alternatives) byfor all \(X,Y \in \mathcal {A}\). In this case we say that X is revealed preferred to Y by F, and call \(R_F\) the revealed preference relation of F. Observe that \(R_F\) is reflexive, i.e., \((X,X) \in R_F\) for all \(X\in \mathcal {A}\).
$$\begin{aligned} (X,Y)\in R_F \Leftrightarrow \text{ there } \text{ exist } Z\in \mathcal {A}\hbox { with } X=F(Z)\hbox { and } Y \subseteq Z, \end{aligned}$$
Later on, we also use the following definitions and notations. A binary relation R on a set \(\Omega \) is transitive if \((\omega ^1,\omega ^2), (\omega ^2,\omega ^3) \in R\) implies \((\omega ^1,\omega ^3) \in R\) for all distinct \(\omega ^1,\omega ^2,\omega ^3 \in \Omega \). The binary relation R has a cycle of length n, where \(n \in \mathbb {N}\setminus \{1\}\), if there are distinct \(\omega ^1,\ldots ,\omega ^n \in \Omega \) such that \((\omega ^i,\omega ^{i+1}) \in R\) for all \(i\in \{1,\ldots ,n-1\}\) and \((\omega ^n,\omega ^1)\in R\); R is acyclic if, for every \(n \in \mathbb {N}\setminus \{1\}\), it has no cycle of length n.
For a choice correspondence F, we use the notation \(F^n(X)\) as shorthand for \(F \circ \, \cdots \, \circ \, F(X)\), that is, the n-fold composition of F with itself.
In the sequel, we denote a generic choice correspondence by F and consequently, its revealed preference relation by \(R_F\).
We now introduce four properties of choice correspondences that we study in this paper. The first property is the standard notion of revealed preference adapted to the present context. As we will show in the next section, this condition is equivalent to the condition called ‘set-rationalizability’ in Brandt and Harrenstein (2011). It also appears in Alva (2018).
Weak axiom of revealed preference (WARP) For all distinct \(X, Y\in \mathcal {A}\), if \((X,Y)\in R_F\), then \((Y,X)\not \in R_F\).
In conformity with the literature, in the revealed preference relation, WARP excludes cycles of length two12 but does not exclude longer cycles13. For completeness, we provide the following example of a choice correspondence satisfying WARP, which contains a cycle of length three, but cycles of arbitrary length can be easily constructed in similar examples.
Example 2.1
Let \(A=\{a,b,c\}\) and define F byIt can be easily checked that F satisfies WARP. However, \(R_F\) contains a cycle of length three since \((\{a\}, \{b\}), (\{b\},\{c\}), (\{c\},\{a\})\in R_F\).14\(\lhd \)
$$\begin{aligned} F(X)={\left\{ \begin{array}{ll} \{a,b,c\} &{} \text {if } X=\{a,b,c\} \\ \{a\} &{} \text {if } X\in \{\{a,b\},\{a\}\} \\ \{b\} &{} \text {if } X\in \{\{b,c\},\{b\}\} \\ \{c\} &{} \text {if } X\in \{\{a,c\},\{c\}\}. \end{array}\right. } \end{aligned}$$
The other three properties are the announced extensions of the IIA condition for choice functions to choice correspondences. The first extension has first been proposed by Nash (cf. Shubik 1982), and occurs also in Chernoff (1954) and Arrow (1959).
Independence of irrelevant alternatives (IIA) For all \(X,Y\in \mathcal {A}\) such that \(Y\subseteq X\), if \(F(X)\cap Y\ne \emptyset \), then \(F(Y) = F(X) \cap Y\).
The second extension requires the following. Given a set X, if F(X) is the set chosen, then from every subset of X that has a nonempty intersection with F(X), only alternatives in F(X) are chosen. This property appears as condition W2 in Schwartz (1976).
Weak independence of irrelevant alternatives (WIIA) For all \(X,Y\in \mathcal {A}\) such that \(Y\subseteq X\), if \( F(X)\cap Y\ne \emptyset \), then \(F(Y)\subseteq F(X)\).
The third extension requires that, given a set X, if F(X) is the set chosen, then from every subset of X that contains F(X), exactly the alternatives of F(X) are chosen. It appears as Postulate 5* in Chernoff (1954), as condition O in Aizerman and Malishevski (1981) (see also Aizerman 1985), as the ‘strong superset property’ in Bordes (1979), and as the ‘outcast’ property in Aizerman and Aleskerov (1995). More recently, the property also appears as ‘irrelevance of rejected items’ in Alva (2018), and in Brandt and Harrenstein (2011)—see the next section.
Restricted independence of irrelevant alternatives (RIIA) For all \(X,Y\in \mathcal {A}\) such that \(Y \subseteq X\), if \(F(X) \subseteq Y\), then \(F(Y)=F(X)\).
3 WARP, IIA, WIIA, and RIIA
In this section, we study the four properties introduced in Sect. 2, and focus on the relations between WARP on the one hand and IIA, WIIA, and RIIA, on the other.
3.1 WARP and RIIA
The first result in this subsection is the (non-novel) observation that WARP and RIIA are equivalent. Since for single-valued choice functions, the conditions of IIA and WARP are equivalent (in a domain closed under intersection such as ours), in this respect RIIA can be seen as the appropriate extension of IIA for choice functions to choice correspondences.
Theorem 3.1
Let F be a choice correspondence. Then F satisfies WARP if and only if it satisfies RIIA.
Proof
For the only-if direction, suppose F satisfies WARP. Let \(X,Y \in \mathcal {A}\) with \(F(X) \subseteq Y \subseteq X\). We show that \(F(Y)=F(X)\). Since \((F(X), Y') \in R_F\) for all \(Y' \subseteq Y\), we have in particular that \((F(X), F(Y)) \in R_F\). Since \(F(X) \subseteq Y\), we also have \((F(Y), F(X)) \in R_F\). Hence by WARP, \(F(X)=F(Y)\).
For the if-direction, suppose F satisfies RIIA. Take \(X,Y,Z,Z' \in \mathcal {A}\) such that \(X=F(Z)\), \(Y=F(Z')\), \(Y \subseteq Z\), \(X \subseteq Z'\). To prove that F satisfies WARP, it is sufficient to prove that \(X=Y\). Since \(X = F(Z) \subseteq Z \cap Z' \subseteq Z\), RIIA implies that \(F(Z \cap Z') = F(Z) = X\). Similarly, one shows that \(F(Z \cap Z') = Y\). Hence, \(X=Y\) and the proof is complete. \(\square \)
Brandt and Harrenstein (2011) show (their Lemma 1) that RIIA is equivalent to the following condition.
Condition \(\hat{\alpha }\) For all \(X,Y \in \mathcal {A}\), if \(F(X \cup Y) \subseteq X \cap Y\), then \(F(X\cup Y) = F(X)\).
Condition \(\hat{\alpha }\) is a set-valued version of the Chernoff property, which is Postulate 4 in Chernoff (1954) and appears as Property \(\alpha \) in Sen (1971). See also Moulin (1985; 1988) for studies of this property.
Brandt and Harrenstein (2011) then prove (their Theorem 2) that, in turn, Condition \(\hat{\alpha }\) is equivalent to the following condition.
Set-rationalizability There exists a binary relation R on \(\mathcal {A}\), with strict part P,15 such that for all \(X,Z \in \mathcal {A}\),Thus, it follows from Theorem 3.1 that the set-rationalizability condition of Brandt and Harrenstein (2011) is equivalent to WARP.
$$\begin{aligned} X = F(Z) \text{ if } \text{ and } \text{ only } \text{ if } YPX\hbox { for no }Y \subseteq Z. \end{aligned}$$
A simple consequence of Theorem 3.1 is that if F satisfies WARP then it is a projection, i.e., \(F^2 = F \circ F = F\).16
Corollary 3.2
Let F satisfy WARP. Then, for all \(X\in \mathcal {A}\), \(F^{2}(X)=F(X)\).
Proof
By Theorem 3.1, for all pairs \(X,Y\in \mathcal {A}\) such that \(Y\subseteq X\), \(F(X)=F(Y\cup F(X))\). Choosing \(Y=F(X)\) implies \(F^2(X)=F(X)\). \(\square \)
The converse of Corollary 3.2 is not true, as is shown by the following example.
Example 3.3
Let \(A=[0,1]\) and define F byClearly \(F^2(X)=F(X)\). Next, consider the sets [0, 1] and \(\left[ \frac{1}{2}, 1\right] \). Since \(\left[ \frac{1}{2},1\right] \subseteq [0,1]\) and \(F([0,1])=\{1\}\), \(\left( \left\{ 1\right\} ,\left[ \frac{1}{2},1\right] \right) \in R_F\); and since \(\{1\}\subseteq \left[ \frac{1}{2},1\right] \) and \(F\left( \left[ \frac{1}{2},1\right] \right) =\left[ \frac{1}{2},1\right] \), \(\left( \left[ \frac{1}{2},1\right] ,\{1\}\right) \in R_F\). Therefore, F violates WARP. A similar example with a finite set A can easily be constructed.\(\lhd \)
$$\begin{aligned} F(X)={\left\{ \begin{array}{ll} \{1\} &{}\text {if }X=A\\ X &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$
3.2 IIA
As mentioned, for single-valued choice, IIA is equivalent to WARP as long as the domain of choice sets is closed under nonempty intersection. For choice correspondences, since IIA implies RIIA, Theorem 3.1 and Corollary 3.2 imply the following lemma, of which a direct proof is also straightforward.
Lemma 3.4
Let F satisfy IIA. Then \(F^2=F\) and F satisfies WARP.
The following example confirms that the converse of this lemma does not hold.
Example 3.5
Let \(A=\{a,b,c\}\) and define F byIt can be easily checked that F satisfies WARP and (hence) \(F^2=F\). However, since \(\{a,b\}\subseteq \{a,b,c\}\) and \(\{a,b\}\cap F(\{a,b,c\})\ne \emptyset \), it follows that \(F(\{a,b\})=\{a\}\) violates IIA. By partitioning a set into three nonempty subsets, the example can be easily adapted to an infinite A.\(\lhd \)
$$\begin{aligned} F(X)={\left\{ \begin{array}{ll} \{a\} &{} \text {if }X\in \{\{a,b\},\{a,c\}\}\\ \{b\} &{} \text {if }X=\{b,c\}\\ X &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$
Preference axiom (PA) For all distinct \(X,Y,Z\in \mathcal {A}\) such that \(X\cap Y\subseteq Z\subseteq X\), if \((X,Y)\in R_F\), then \((Z,Y)\in R_F\).
This axiom implies that, if X and Y are disjoint, then every nonempty subset of X is revealed preferred to Y—this would be natural in case the choice correspondence picks those alternatives (from some set Z containing both X and Y) that are maximal according to some criterion. Under this interpretation, at least any subset of X that contains the intersection of X and Y, i.e., the ‘maximal’ alternatives of Y, should still be revealed preferred to Y, and this is exactly what PA says.
We now have the following characterization of IIA.
Theorem 3.6
F satisfies IIA if and only if it satisfies WARP and PA.
Proof
(a) Let F satisfy IIA. Then, F satisfies WARP by Lemma 3.4. We show that F satisfies PA. Let distinct \(X,Y,Z\in \mathcal {A}\) such that \(X\cap Y\subseteq Z\subseteq X\) and \((X,Y)\in R_F\). Since \((X,Y)\in R_F\), there is a \(U \in \mathcal {A}\) such that \(X=F(U)\) and \(Y \subseteq U\). Since \(\emptyset \ne X = F(U) \cap (X \cup Y)\), IIA implies that \(F(X \cup Y) = F(U) \cap (X \cup Y) = X\). Since \(Z \cup Y \subseteq X \cup Y\) and \(F(X\cup Y) \cap (Z \cup Y) = X \cap (Z \cup Y) = (X \cap Z) \cup (X \cap Y) = Z \ne \emptyset \), IIA of F implies \(F(Z \cup Y) = Z\). Therefore, \((Z,Y) \in R_F\).
(b) Let F satisfy WARP and PA. We show that F satisfies IIA. Let \(X,Y\in \mathcal {A}\) with \(Y\subseteq X\) and \(F(X)\cap Y \ne \emptyset \). Since \(F(Y) \subseteq Y \subseteq X\), it follows that \((F(X), F(Y))\in R_F\). In addition, \((F(X) \cap F(Y)) \subseteq (F(X)\cap Y) \subseteq F(X)\), so that by PA, \((F(X)\cap Y, F(Y))\in R_F\). But also, \(F(X)\cap Y \subseteq Y\) implies \((F(Y), F(X)\cap Y)\in R_F\). Hence, by WARP, \(F(Y)=F(X)\cap Y\). Thus, F satisfies IIA. \(\square \)
In Example 3.5, F satisfies WARP but not IIA. Hence it follows from Theorem 3.6 that F does not satisfy PA either. This can also be easily established directly. E.g., in Example 3.5, let \(X=\{a,b,c\}\), \(Y=\{b\}\), and \(Z = \{a,b\}\), then \((X,Y) \in R_F\) but \((Z,Y) \notin R_F\).
The next example shows that PA does not imply IIA or WARP.
Example 3.7
Let \(A=\{a,b,c,d\}\) and define F byIt is straightforward to show that F satisfies PA. Since \(\{a,b\} \subseteq \{a,b,c,d\}\), \(\{a,b\}\)
$$\begin{aligned} F(X)={\left\{ \begin{array}{ll} \{a,b\} &{} \text {if } X=\{a,b,c,d\}\\ \{a\} &{} \text {if } X\subsetneq \{a,b,c,d\}\text { and }a\in X\\ \{b\} &{} \text {if } X\subseteq \{b,c,d\} \text { and }b\in X\\ \{c\} &{} \text {if } X\subseteq \{c,d\} \text { and }c\in X\\ \{d\} &{} \text {if } X = \{d\}. \end{array}\right. } \end{aligned}$$
\(\cap \, F(\{a,b,c,d\}) \ne \emptyset \), and \(F(\{a,b\})=\{a\}\), it follows that F does not satisfy IIA, and by Theorem 3.6, it also does not satisfy WARP.\(\lhd \)
For (single-valued) choice functions on a collection of choice sets that is closed under nonempty intersection, IIA or, equivalently, WARP does not necessarily imply acyclicity of the revealed preference relation.17 For choice correspondences (including choice functions) on the collection of all nonempty subsets of a set of alternatives, IIA implies WARP (Theorem 3.6) and, moreover, transitivity and acyclicity of the revealed preference relation, as the next result shows.
Theorem 3.8
Let F satisfy IIA. Then \(R_F\) is transitive and acyclic.
Proof
By Theorem 3.6, F satisfies WARP. It is sufficient to prove that \(R_F\) is transitive, since with WARP this implies acyclicity. Let distinct \(X_1,X_2,X_3\in \mathcal {A}\) with \((X_1,X_2),(X_2,X_3) \in R_F\). We prove that \((X_1,X_3)\in R_F\). Let \(Z = X_1 \cup X_2 \cup X_3\).
Observe that \((F(X_2 \cup X_3),X_2) \in R_F\) by definition of \(R_F\). Since \((X_2,X_3) \in R_F\) there is \(Z'\in \mathcal {A}\) such that \(X_2 = F(Z')\) and \(X_3 \subseteq Z'\). In particular, \((X_2,F(X_2\cup X_3)) \in R_F\). Hence, by WARP, \(X_2 = F(X_2 \cup X_3)\).
If \(F(Z) \cap X_3 \ne \emptyset \), then by IIA we have \(F(X_2 \cup X_3) = F(Z) \cap (X_2 \cup X_3)\), hence \(X_2 = F(Z) \cap (X_2 \cup X_3)\), which implies \(F(Z) \subseteq X_1 \cup X_2\). If \(F(Z) \cap X_3 = \emptyset \), then trivially \(F(Z) \subseteq X_1 \cup X_2\). By definition of \(R_F\), \((F(Z),X_1) \in R_F\). On the other hand, since \((X_1,X_2) \in R_F\) there is \(Z'' \in \mathcal {A}\) such that \(F(Z'') = X_1\) and \(X_2 \subseteq Z''\); in particular, since \(F(Z) \subseteq X_1 \cup X_2 \subseteq Z''\), this implies \((X_1,F(Z)) \in R_F\). Therefore, by WARP, \(F(Z)=X_1\), and since \(X_3 \subseteq Z\) we obtain \((X_1,X_3) = (F(Z),X_3) \in R_F\). \(\square \)
3.3 WIIA
We first show by two examples that WIIA and WARP (or RIIA) are logically independent.
Example 3.9
Let \(A = \mathbb {N}\) and define F byLet \(Y\subseteq X\) such that \(Y\cap F(X)\ne \emptyset \). If X is infinite, then \(Y\cap F(X) = Y \cap X = Y\) and \(F(Y) \subseteq Y = Y \cap F(X)\). If X is finite and \(|Y|=1\), then \(F(Y)=Y=Y\cap F(X)\). Otherwise, \(F(Y) \subseteq Y\cap F(X)\). Hence, F satisfies WIIA. However, let \(X=\{1,2,3\}\) and \(Y=\{1,2\}\). Then \(F(X)=\{1,2\}\) implies \((\{1,2\}, \{1\})\in R_F\), while \(F(Y)=\{1\}\) implies \((\{1\}, \{1,2\})\in R_F\). Hence, F does not satisfy WARP. Similar statements hold for \(A = \{1,2, \dots ,n\}\) with \(n \ge 3\).\(\lhd \)
$$\begin{aligned} F(X)= {\left\{ \begin{array}{ll} X & {} \text {if } |X|=1\text { or }X\text { is infinite}\\ X \setminus \{ \max (X)\} & {} \text {if }1< |X| < \infty . \end{array}\right. } \end{aligned}$$
Example 3.10
Let \(A = [0,1]\) and define F byThen, \(F([0,1]) = (0,1]\), whereas \(F([0,\frac{1}{2}]) = [0,\frac{1}{2}]\); hence, F does not satisfy WIIA. By direct inspection or by using Theorem 3.1 it is straightforward that F satisfies WARP. The example can be easily adapted to finite A. \(\lhd \)
$$\begin{aligned} F(X)= {\left\{ \begin{array}{ll} X \setminus \{0\} &{} \text {if } X \subseteq [0,1]\text { with }X \cap (\frac{1}{2},1] \ne \emptyset \\ X &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$
If we add the condition that F be a projection, then WIIA implies WARP.
Theorem 3.11
Let F satisfy WIIA and \(F^2 = F\). Then F satisfies WARP.
Proof
By Theorem 3.1 is is sufficient to prove that F satisfies RIIA. Let \(X,Y \in \mathcal {A}\) with \(F(X) \subseteq Y \subseteq X\). We prove that \(F(Y)=F(X)\). By WIIA, \(F(Y) \subseteq F(X) \cap Y = F(X)\). Again by WIIA, since \(F(X) \subseteq Y\) and \(F(Y) \cap F(X) = F(Y) \ne \emptyset \) we have \(F(F(X)) \subseteq F(Y) \cap F(X) = F(Y)\), hence \(F(X) \subseteq F(Y)\) since \(F^2 = F\). Thus, \(F(Y)=F(X)\). \(\square \)
The converse of Theorem 3.11 does not hold. If F satisfies WARP then by Corollary 3.2 it is a projection, but Example 3.10 shows that WIIA does not have to hold.
The following result shows that if F satisfies WIIA, then so does every n-fold composition of F with itself. As a corollary, we will obtain that for a finite set of alternatives A, WIIA implies that \(F^{|A|-1}\) satisfies WARP.
Lemma 3.12
Let F satisfy WIIA and let \(n \in \mathbb {N}\) with \(n \ge 2\). Then \(F^{n}\) satisfies WIIA.
Proof
The proof is based on induction: \(F^1=F\) satisfies WIIA, and assume that \(F^k\) satisfies WIIA for every \(k = 2,\ldots ,n-1\). Let \(X,Y \in \mathcal {A}\) with \(Y \subseteq X\) and \(F^n(X) \cap Y \ne \emptyset \). We show that \(F^n(Y) \subseteq F^n(X)\).
Note that \(F^k(X) \cap Y \ne \emptyset \) and the induction assumption imply that \(F^k(Y) \subseteq F^k(X)\) for every \(k = 1,\ldots ,n-1\) and thus thatWe now first prove thatwhere \(F^0(Y)=Y\). The proof of (2) is by induction. By assumption, \(F^n(X) \cap F^0(Y) = F^n(X) \cap Y \ne \emptyset \). Let \(2 \le \ell \le n-1\) and assume that \(F^n(X) \cap F^k(Y) \ne \emptyset \) for every \(k=1,\ldots ,\ell -1\). We show that \(F^n(X) \cap F^\ell (Y) \ne \emptyset \). First, since \(\emptyset \ne F^{n-1}(X) \cap F^{\ell -1}(Y) \subseteq F^{n-1}(X)\) by (1), and \(F^n(X) \cap (F^{n-1}(X) \cap F^{\ell -1}(Y)) = F^{n}(X) \cap F^{\ell -1}(Y) \ne \emptyset \) by the induction assumption for this part, WIIA of F impliesSecond, since since \(\emptyset \ne F^{n-1}(X) \cap F^{\ell -1}(Y) \subseteq F^{\ell -1}(Y)\) by (1), and \(F^\ell (Y) \cap (F^{n-1}(X) \cap F^{\ell -1}(Y)) = F^\ell (Y) \cap F^{n-1}(X) \ne \emptyset \) by (1), WIIA of F impliesBy (3) and (4), \(F^n(X) \cap F^\ell (Y) \ne \emptyset \), which completes the proof of (2).
$$\begin{aligned} F^\ell (X) \cap F^m(Y) \ne \emptyset \text{ for } \text{ all } \ell ,m \in \{1,\ldots ,n-1\}. \end{aligned}$$
(1)
$$\begin{aligned} F^n(X) \cap F^k(Y) \ne \emptyset \text{ for } \text{ every } k=0,\ldots ,n-1 \end{aligned}$$
(2)
$$\begin{aligned} F(F^{n-1}(X) \cap F^{\ell -1}(Y)) \subseteq F^n(X). \end{aligned}$$
(3)
$$\begin{aligned} F(F^{n-1}(X) \cap F^{\ell -1}(Y)) \subseteq F^\ell (Y). \end{aligned}$$
(4)
Now, since \(F^{n-1}(X) \cap Y \ne \emptyset \), the assumed WIIA of \(F^{n-1}\) implies \(F^{n-1}(Y) \subseteq F^{n-1}(X)\). Since by (2), we have \(F^n(X) \cap F^{n-1}(Y) \ne \emptyset \), WIIA of F implies \(F^n(Y) \subseteq F^n(X)\). This completes the proof of the lemma. \(\square \)
If A is finite, then there exists \(n \in \mathbb {N}\) with \(n \le |A|-1\) such that \(F^\ell = F^n\) for all \(\ell \ge n\). In that case, we have the following corollary.
Corollary 3.13
Let A be finite and let F satisfy WIIA. Then \(F^{|A|-1}\) satisfies WARP.
Proof
If A is infinite, then an n as in the finite case does not necessarily exist. However, we may define \(F^\infty \) by \(F^\infty (X) = \cap _{n \in \mathbb {N}} F^n(X)\) for every \(X \in \mathcal {A}\), assuming that this set is nonempty for every \(X \in \mathcal {A}\). The following example shows that the last condition is not necessarily satisfied if F satisfies WIIA.
Example 3.14
Let \(A=[0,1]\) and for every \(X \in \mathcal {A}\), let m(X) be the maximal number in \(\mathbb {N} \cup \{0\}\) such that \(X\subseteq [0,\frac{1}{2^{m(X)}}]\). We define F byIt is easy to check that F satisfies WIIA. However, \(\cap _{n\in \mathbb {N}} F^n(A \setminus \{0\}) = \cap _{n\in \mathbb {N}} (0,\frac{1}{2^n}] = \emptyset \). \(\lhd \)
$$\begin{aligned} F(X)= {\left\{ \begin{array}{ll} X\setminus \Big (\frac{1}{2^{m(X)+1}},\frac{1}{2^{m(X)}}\Big ] &{} \text {if } X\setminus \Big (\frac{1}{2^{m(X)+1}},\frac{1}{2^{m(X)}}\Big ]\ne \emptyset \\ X &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$
Remark 3.15
If F satisfies WIIA and \(F^\infty \) is well defined, then it follows from Lemma 3.12 that \(F^\infty \) satisfies WIIA. Namely, let \(X,Y \in \mathcal {A}\), \(Y \subseteq X\), and \(F^\infty (X) \cap Y \ne \emptyset \). Then in particular \(F^n(X) \cap Y \ne \emptyset \) for every \(n \in \mathbb {N}\), so that by Lemma 3.12 we have \(F^\infty (Y) = \cap _{n\in \mathbb {N}} F^n(Y) = \cap _{n\in \mathbb {N}} (F^n(X) \cap Y) = (\cap _{n\in \mathbb {N}} F^n(X)) \cap Y = F^\infty (X) \cap Y\).
Even, however, if \(F^\infty \) is well-defined, and F and thus \(F^\infty \) satisfy WIIA, \(F^\infty \) does not have to be a projection. For instance, let \(A = \{-1,0\} \cup \{\frac{1}{2^{n}} \mid n \in \mathbb {N} \}\). Define F byThen, \(F^\infty \) is well-defined, and both F and \(F^\infty \) satisfy WIIA. Since \(F^\infty (A) = \{-1,0\}\) and \(F^\infty (\{-1,\) \(0\}) = \{-1\}\), we have \(F^\infty \circ F^\infty (A) = \{-1\} \ne F^\infty (A)\). Hence, \(F^\infty \circ F^\infty \ne F^\infty \). In particular, by Corollary 3.2, \(F^\infty \) does not satisfy WARP. \(\lhd \)
$$\begin{aligned} F(X)= {\left\{ \begin{array}{ll} X \setminus \{ \max \{x : x\in X \} \} &{} \text {if } |X|>1\\ X &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$
We have already seen (Examples 3.9 and 3.10) that WIIA and WARP are logically independent. The same is true for WIIA and PA. In Example 3.9, F satisfies WIIA but not PA. The following example shows that PA does not imply WIIA.
Example 3.16
Let \(A=\{a,b,c\}\) and define F byIn this case, F does not satisfy WIIA since \(F(\{a,b\}) = \{a,b\} \not \subseteq \{a\} = F(A) \cap \{a,b\}\). To show that F satisfies PA, let X, Y, Z as in the statement of PA and \(V\in \mathcal {A}\) such that \(F(V)=X\) and \(Y\subseteq V\). If \(|X|=1\) then either \(V=X\) and then \(Z=X=Y\), a contradiction since \(Z \ne Y\); or \(V=A\), which implies \(X=\{a\}\) and therefore \(Z=\{a\}=X\), so that \((Z,Y)\in R_F\). If \(|X|=2\), then \(V=X\) and \(Y \subseteq X\) with \(|Y|=1\); this implies \(Z=X\) and thus \((Z,Y)\in R_F\). \(\lhd \)
$$\begin{aligned} F(X)={\left\{ \begin{array}{ll} \{a\} &{} \text {if } X=A\\ X &{} \text {otherwise.}\\ \end{array}\right. } \end{aligned}$$
4 Strong sets
In this section, we introduce so-called strong sets. We show that any IIA choice correspondence induces a collection of such strong sets, which is a partition of A, such that the revealed preference relation restricted to these strong sets is complete and acyclic (Theorem 4.6). Conversely, each partition of A ordered by a binary relation with these properties, defines a unique IIA choice correspondence (Corollary 4.9). Moreover, we show how such strong sets may be constructed (Lemma 4.8, Remark 4.10).
A set \(S\in \mathcal {A}\) is a strong set if the following holds: for every choice set where some alternatives that are also in S, are chosen, all the available alternatives of S are chosen, and only these. Formally, we have the following definition.
Definition 4.1
\(S\in \mathcal {A}\) is a strong set of choice correspondence F if for all \(X\in \mathcal {A}\) for which \(F(X)\cap S\ne \emptyset \), we have \(F(X)= S\cap X\). The set of strong sets at F is denoted by \(\mathcal {S}_F\). By \(R_{\mathcal {S}_F} = \{(X,Y)\in R_F \mid X,Y\in \mathcal {S}_F\}\) we denote the restriction of \(R_F\) to \(\mathcal {S}_F\).\(\lhd \)
Before going into the formalities, we describe how these strong sets are generated by an IIA choice correspondence F, for the case where A is finite. Construct the sequence of sets starting with \(S_1=F(A)\), next \(S_2=F(A \setminus S_1)\), next \(S_3=F(A \setminus (S_1 \cup S_2))\), etc. Then for a choice set \(X \in \mathcal {A}\), take the first set in this sequence with which X has a nonempty intersection: then F(X) is equal to this intersection. In this case, the sets thus constructed are exactly all the strong sets; we formally show this in Lemma 4.8 below.
Example 4.2
Let \(A= \{x_1,\ldots ,x_m\}\) be a finite set, and let Q be a weak ordering on A (i.e., a complete and transitive binary relation). For every \(X \in \mathcal {A}\) let F(X) be the set of elements in X that are maximal—ranked highest—according to Q. Let \(S_k\) be the set of elements of A that are ranked at position k according to Q. Then the sets \(S_k\), where k is at most m, are exactly the strong sets of F. Observe that \(S_1 = F(A)\), \(S_2 = F(A \setminus S_1)\), etc.
\(\lhd \)
For the case where A is infinite, we can define a sequence of sets in the same way, and all these will be strong sets, but we may not find all strong sets: see Remark 4.10 below.
We now first show that strong sets are pairwise disjoint, and next that \(R_{\mathcal {S}_F}\) is complete and acyclic if F satisfies IIA.
Lemma 4.3
Let \(S,T\in \mathcal {S}_F\) with \(S \ne T\). Then \(S \cap T = \emptyset \).
Proof
Let \(Z=S\cup T\). Without loss of generality assume that \(F(Z)\cap S\ne \emptyset \). Then \(S\in \mathcal {S}_F\) implies \(F(Z)=S \cap Z = S\). If \(S\cap T\ne \emptyset \), then \(F(Z)\cap T\ne \emptyset \); hence \(T\in \mathcal {S}_F\) implies \(F(Z)=T\cap Z = T\). This contradicts \(S\ne T\). Consequently, \(S \cap T = \emptyset \). \(\square \)
Lemma 4.4
Let F satisfy IIA. Then \(R_{\mathcal {S}_F}\) is complete and acyclic.
Proof
Let \(S,T\in \mathcal {S}_F\) with \(S\ne T\). By the definition of \(\mathcal {S}_F\), \(F(S\cup T)\in \{S,T\}\); hence, \(R_{\mathcal {S}_F}\) is complete. Without loss of generality assume that \(F(S \cup T) = S\), hence \((S,T)\in R_{\mathcal {S}_F}\). We show that \((T,S) \notin R_{\mathcal {S}_F}\), which implies that \(R_{\mathcal {S}_F}\) has no cycles of length 2. To show this, let \(Z \in \mathcal {A}\) with \(S\cup T \subseteq Z\). If \((S\cup T)\cap F(Z)\ne \emptyset \), then by IIA, \(S= F(S\cup T) = (S\cup T)\cap F(Z)\). Since \(S\in \mathcal {S}_F\), this implies that \(F(Z)=S\). Since Z was arbitrary, we have \((T,S) \notin R_{\mathcal {S}_F}\).
To show that \(R_{\mathcal {S}_F}\) has also no cycles of length larger than 2, it is sufficient to prove that it is transitive. Let \((S,T),(T,V) \in R_{\mathcal {S}_F}\) for distinct \(S,T,V \in \mathcal {S}_F\). Then for \(X=S\cup T \cup V\) we have \(S=F(X)\), so that \((S,V) \in R_{\mathcal {S}_F}\). \(\square \)
The next technical lemma is needed in the proof of the theorem below.
Lemma 4.5
Let choice correspondence F satisfy IIA, and let \(\emptyset \ne \mathcal {Z} \subseteq \mathcal {A}\) such that \(\cap _{Z \in \mathcal {Z}} F(Z)\) \(\ne \emptyset \). Then \(\cup _{Z\in \mathcal {Z}}F(Z) = F\left( \cup _{Z\in \mathcal {Z}}Z\right) \).
Proof
Let \(x \in \cap _{Z \in \mathcal {Z}} F(Z)\). Since \(F\left( \cup _{Z\in \mathcal {Z}}Z\right) \subseteq \cup _{Z\in \mathcal {Z}}Z\), there is \(Z'\in \mathcal {Z}\) such that \(Z' \cap F\left( \cup _{Z\in \mathcal {Z}}Z\right) \ne \emptyset \), so that \(F(Z') = F\left( \cup _{Z\in \mathcal {Z}}Z\right) \cap Z'\) by IIA. Hence, \(x \in F\left( \cup _{Z\in \mathcal {Z}}Z\right) \), so that \(Z' \cap F\left( \cup _{Z\in \mathcal {Z}}Z\right) \ne \emptyset \) for all \(Z'\in \mathcal {Z}\), and hence \(F(Z') = F\left( \cup _{Z\in \mathcal {Z}}Z\right) \cap Z'\) for all \(Z'\in \mathcal {Z}\) by IIA. The statement in the lemma now follows. \(\square \)
Theorem 4.6
Let F satisfy IIA. Then \(\mathcal {S}_F\) is a partition of A, and \(R_{\mathcal {S}_F}\) is complete and acyclic.
Proof
Let \(x \in A\). In view of Lemmas 4.3 and 4.4, we only still have to prove that there is an \(S \in \mathcal {S}_F\) such that \(x \in S\). Define \(\mathcal {Z}= \{ Z \in \mathcal {A}\mid x \in F(Z) \}\), which is nonempty since \(\{x\}\in \mathcal {Z}\), and \(S = F(\cup _{Z \in \mathcal {Z}} Z)\). By Lemma 4.5 we have \(S = \cup _{Z \in \mathcal {Z}} F(Z) \ni x\), so that it is sufficient to prove that \(S \in \mathcal {S}_F\). To this end, let \(X \in \mathcal {A}\) such that \(F(X) \cap S \ne \emptyset \), then it is sufficient to prove that \(F(X) = S \cap X\).
Since \(F(X) \cap S \ne \emptyset \), Lemma 4.5 implies \(F(X) \cup S = F(X) \cup F(\cup _{Z \in \mathcal {Z}} Z) = F(X \cup \left( \cup _{Z \in \mathcal {Z}} Z\right) )\). In particular, this implies that \(F(X \cup \left( \cup _{Z \in \mathcal {Z}} Z\right) ) \cap X \ne \emptyset \) so that by IIA we obtain \(F(X) = F(X \cup \left( \cup _{Z \in \mathcal {Z}} Z\right) ) \cap X \supseteq F(\cup _{Z \in \mathcal {Z}} Z) \cap X\), hence \(S \cap X \subseteq F(X)\). Therefore, it is sufficient to prove that \(F(X) \subseteq S \cap X\).
By Lemma 4.5, \(F(X)\cap S\ne \emptyset \) implies \(F(X)\cap \left( \cup _{Z\in \mathcal {Z}} F(Z)\right) \ne \emptyset \). Hence, for some \(Z'\in \mathcal {Z}\), \(F(X)\cap F(Z')\ne \emptyset \). Thus, by Lemma 4.5, \(F(X\cup Z')=F(X)\cup F(Z')\). It follows that \(x\in F(X\cup Z')\) and thus, \(X\cup Z' \in \mathcal {Z}\). In addition, since \(S=\cup _{Z\in \mathcal {Z}} F(Z)\), we have \(F(X\cup Z')\subseteq S\), and hence, \(F(X)\cup F(Z')\subseteq S\). Therefore, \(F(X)\subseteq S\) and trivially, \(F(X)\subseteq S\cap X\). \(\square \)
The converse of Theorem 4.6 does not hold. The following example describes a choice correspondence F of which the strong sets partition A, and are completely and acyclically ordered by \(R_F\), but which does not satisfy IIA.
Example 4.7
Let \(F(A)\subsetneq A\) and for all \(X\subseteq \mathcal {A}\) define F byIt is straightforward to verify that \(\mathcal {S}_F = \{F(A),A\setminus F(A)\}\), which is a partition of A. Also, \(R_{\mathcal {S}_F} = \{(F(A),A\setminus F(A))\}\). (In fact, it is not difficult to show that F satisfies WARP and is a projection.) Let \(X,Y \in \mathcal {A}\) such that \(F(A) \subseteq X\), \(Y \subseteq X\), \(Y\not \subseteq F(A)\), \(F(A) \not \subseteq Y\), and \(Y\cap F(A) \ne \emptyset \). Then \(F(X)=F(A)\) but \(F(Y) = Y \setminus F(A) \not \subseteq Y \cap F(A) = Y \cap F(X)\). Hence, F does not satisfy IIA. \(\lhd \)
$$\begin{aligned} F(X)= {\left\{ \begin{array}{ll} F(A) &{} \text {if } F(A) \subseteq X \\ X &{} \text {if } X \subseteq F(A) \\ X\setminus F(A) &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$
As mentioned above, if the set A of all alternatives is finite, then the collection of strong sets of an IIA choice correspondence is easily constructed, as follows. Let \(S_0 = \emptyset \) and, recursively, \(S_i = F(A \setminus \cup _{j=0}^{i-1} S_j)\) for every \(i=1,2,\ldots \) Clearly, if A is finite then there is an \(\ell \ge 1\) such that \(S_i = S_\ell \) for all \(i > \ell \). In that case, \(\{S_1,\ldots ,S_\ell \}\) is a partition of A. We have:
Lemma 4.8
Let A be finite. If F satisfies IIA, then \(\mathcal {S}_F = \{S_1,\ldots ,S_\ell \}\) and \(S_i R_{\mathcal {S}_F} S_j\) for all \(i,j \in \{1,\ldots ,\ell \}\) with \(i<j\).
Proof
Let F satisfy IIA. The second statement follows directly from the construction of the sets \(S_i\). For the first statement, it is in view of Lemma 4.3 sufficient to prove that each element of \(\{S_1,\ldots ,S_\ell \}\) is a strong set. Let \(k \in \{1,\ldots ,\ell \}\) and \(X \in \mathcal {A}\) such that \(F(X) \cap S_k \ne \emptyset \). By repeated application of IIA it follows that \(X \subseteq A\setminus \cup _{i=1}^{k-1} S_i\). Since \(X \cap S_k = X \cap F(A\setminus \cup _{i=1}^{k-1} S_i) \ne \emptyset \), IIA implies \(F(X) = X \cap F(A\setminus \cup _{i=1}^{k-1} S_i) = X \cap S_k\). Hence, \(S_k\) is a strong set. \(\square \)
A converse of Lemma 4.8, for general sets A, is the following corollary, which says that every ‘well-ordered’ partition of \(\mathcal {A}\) induces a unique IIA choice correspondence.
Corollary 4.9
Let \(\mathcal {T}\) be a partition of A and let R be a reflexive, complete, and acyclic binary relation on \(\mathcal {T}\) such that for every \(X \in \mathcal {A}\) the collection \(\{T \in \mathcal {T}\mid T \cap X \ne \emptyset \}\) has a maximal element \(T_X\) with respect to R.18Then F, defined by \(F(X)=X \cap T_X\) for all \(X \in \mathcal {A}\), satisfies IIA, \(\mathcal {S}_F=\mathcal {T}\), and \(R_{\mathcal {S}_F}=R\). Moreover, if G satisfies IIA, \(\mathcal {S}_G=\mathcal {T}\), and \(R_{\mathcal {S}_G}=R\), then \(G=F\).
Proof
The statements about F are straightforward. Let G be as in the lemma, and \(X \in \mathcal {A}\). We prove that \(G(X) = X \cap T_X\). For this, by IIA, it is sufficient to prove that \(G(T_X \cup (\cup _{T \in \mathcal {T}: T_X R T} T)) = T_X\). If this were not true, then the definition of strong sets would imply \(G(T_X \cup (\cup _{T \in \mathcal {T}: T_X R T} T)) = T' \ne T_X\) for some \(T' \in \mathcal {T}\) with \(T_X R\, T'\), in contradiction with \(R = R_{\mathcal {S}_G}\). \(\square \)
We conclude with a remark about the construction of all strong sets.
Remark 4.10
For infinite A the construction above, resulting in the sets \(S_1,S_2,\ldots \), does not necessarily produce all strong sets, or, equivalently, does not necessarily result in a partition of A. For instance, let \(A = \mathbb {N}\), \(E = \{2,4,\ldots \}\) and define F byfor all \(X \in \mathcal {A}\). Choice correspondence F satisfies IIA, and \(S_i = \{2i\}\) for every \(i = 1,2,\ldots \) However, the collection of strong sets is \(\{S_1,S_2,\ldots ,T_1,T_2,\ldots \}\), where \(T_i=\{2i-1\}\) for every \(i=1,2,\ldots \) , \(S_i R_F S_j\) and \(T_i R_F T_j\) for all i, j with \(i<j\), and \(S_i R_F T_j\) for all i, j. Observe that this collection can be constructed by first determining the sets \(S_i\) and then repeating the construction starting with the set \(A \setminus \cup _{i=1}^\infty S_i = A \setminus E = \{1,3,\ldots \}\).
$$\begin{aligned} F(X) = \left\{ \begin{array}{ll} \min X \cap E &{} \hbox { if}\ X \cap E\ne \emptyset \\ \min X &{} \text{ otherwise } \end{array} \right. \end{aligned}$$
5 Concluding remarks
The main results of the paper are summarized in Table 1. The main feature distinguishing these results from the existing literature is that preferences over sets rather than singletons are considered.
Table 1
Summary of the main results
WARP | \({\mathop {\Longleftrightarrow }\limits ^{{\text {Theorem}} 3.1}}\) | RIIA (\(\Longleftrightarrow \) Condition \(\hat{\alpha }\)) |
\({\mathop {\Longrightarrow }\limits ^{{\text {Corollary}} 3.2}}\) | \(F^2 = F\) | |
IIA | \({\mathop {\Longleftrightarrow }\limits ^{{\text {Theorem}} 3.6}}\) | WARP and PA |
\({\mathop {\Longrightarrow }\limits ^{{\text {Theorem}} 3.8}}\) | \(R_F\) transitive and acyclic | |
\({\mathop {\Longrightarrow }\limits ^{{\text {Theorem}} 4.6}}\) | \(\mathcal {S}_F\) partition, \(R_{\mathcal {S}_F}\) complete and acyclic | |
\(F^2=F\) & WIIA | \({\mathop {\Longrightarrow }\limits ^{{\text {Theorem}} 3.11}}\) | WARP |
We also repeat that the results in Sect. 3.1 are not new, but appear (with different terminology) in the literature. No additional structure on the set of alternatives is presumed. Of course, more specific results may be attainable if this set has more structure.
An open question is how to obtain a set-theoretic characterization of WIIA choice correspondences. In an earlier version of this paper20 we introduced the concept of weak sets, and although some of the results obtained for IIA correspondences and strong sets have analogues for WIIA correspondences and weak sets, these weak sets do not fully determine the correspondence; in other words, we do not obtain an analogue of Corollary 4.9.
A similar question can be asked with respect to RIIA choice correspondences. Other open questions concern the implications of still other IIA-extensions, such as the extensions discussed in Sect. 1.6.2.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.