Collective choice rules on restricted domains based on a priori information

One attempt to avoid the well-known impossibility theorems of Arrow (1978), Gibbard (1973), and Satterthwaite (1975) on collective decision rules is along the line of restricted domains. For instance, the agents’ set of admissible preferences contains only orders of a certain type. In the vast majority, these domain restrictions are considered the same for all agents. Indeed, there are many cases where this symmetric approach is appealing. There are also situations where agents can be modelled asymmetrically. This paper is one of the very few where the sets of admissible preferences per agent may differ. We presume that per agent over all his admissible preferences some parts are constant. These parts as well as the actual preferences on these parts may differ per agent. Actually, this part of the agents’ preference is known in advance and therefore referred to as the a priori information. We determine the a priori information that is needed to allow for non-dictatorial, unanimous and strategy-proof choice rules.

For an agent i, let partial order \(P^{i}\) represent those pairs which are constant over all the admissible preferences of this agent i. This information on that agent may for instance stem from religious backgrounds, strong political engagement, cultural heritage, (internet) behavior in the past, or because the agent has indicated so beforehand. Agent i’s set of admissible preferences consists of all preferences extending this a priori information Pⁱ to a weakly complete linear order. Note that this information may range from a weakly complete partial order to an empty set. In the former case, the preference of the agent is known in which case his set of admissible preferences is a singleton consisting of precisely this weakly complete partial order. In the latter case the set of admissible preferences equals the set of all linear orders.

We analyze precisely which a priori information leads to domains of preference profiles allowing for unanimous, strategy-proof and non-dictatorial choice rules. The necessary and sufficient conditions for such a priori information are based on the union of all the partial orders \( P^{i}\), i.e. \(P^{*}=\bigcup \limits _{i\in N}P^{i}.\) Of particular interest is its set of undominated alternatives¹. Roughly speaking, in this framework a priori information leads to a domain of profiles allowing for unanimous, strategy-proof and non-(image-)dictatorial choice rules, if there are at most two such undominated alternatives on which, for at least two agents the preference is not fixed. As unanimity has no bite on dominated alternatives, in such cases voting between these two possibly undominated alternatives yields a strategy-proof, non-image-dictatorial, and unanimous choice rule. But whether the above condition describes all the situations allowing for such choice rules, is less straightforward. Theorem 1 states that the range of such choice functions consists of precisely two alternatives. As every undominated alternative is in the range of a unanimous choice rule, Theorem 1 implies that there are at most two undominated alternatives. To avoid image-dictatorship now, at least two agents should be able to order these two alternatives freely.

To the best of the authors knowledge Storcken (1985) is the only study on similar domain restrictions. That paper determines those domains based on a priori information allowing for (Arrow-like) welfare functions, which are Pareto-optimal, non-dictatorial, positively associated, and pairwise anonymous. Roughly speaking such domains admit such welfare functions precisely when there is a partial order, say \(\overline{P},\) contained, in \( P^{*}\) such that at every profile the outcome of the welfare function is a linear extension of this partial order \(\overline{P}\). Here, at each profile this extension is determined as follows. For alternatives x and y , such that \((x,y)\notin \overline{P}\) and \((y,x)\notin \overline{P}\) the collective ordering is determined by voting based on thresholds. That is, x is preferred to y if the number of agents in favor of x against y exceeds a given threshold which is depending on the pair (x, y). These thresholds satisfy certain conditions to guarantee completeness, anti-symmetry and transitivity. In addition, \(\overline{P}\) has to satisfy certain conditions to guarantee non-dictatorship for certain (degenerated cases) as well as pairwise anonymity for cases where some agents can freely order three alternatives. Now consider cases where the following three are satisfied: (i) All these conditions related to \(\overline{P}\) as meant above, (ii) there are precisely two undominated alternatives with respect to \(\overline{P},\) and (iii) for at least two agents those preferences between these two alternatives are not fixed. For those cases there exist such welfare functions as well as there exist unanimous, strategy-proof, and non-image-dictatorial choice rules. Moreover, it is not hard to see that every such welfare function relates to such a choice rule in the following way. The best collectively ordered alternative at the welfare function is the chosen alternative at the choice rule.

Besides this relation, the results are independent from each other. In case of welfare functions, the non-dictatorship may be achieved via the collective preference tails. For instance, in case there is one unique undominated alternative, say x, in all the \(P^{i}\), then the conditions of Storcken (1985) may still be satisfied. This means that in such a case the domain allows for such welfare functions. As, however, x is ordered best by every agent at every preference a unanimous choice rule in this case chooses x at every profile. Therefore, in that case the choice rule is a constant rule at which all agents are (image)-dictators.

On the other hand, pairwise anonymity imposes conditions on the tails of \( P^{*},\) which are immaterial for the results deduced here. Example 3 is based on this. It discusses a domain based on a priori information that allows for unanimous, strategy-proof, and non-image-dictatorial choice rules. It does not allow for Pareto-optimal, non-dictatorial, positively associated, and pairwise anonymous welfare functions. This example shows that the results discussed here are not a logical consequence of those of Storcken (1985). Further, as discussed in more detail in the discussion of Sect. 6, Theorem 1 entails a novel impossibility theorem on restricted domains.

There have been many studies on domain restrictions (See e.g. Gaertner (2002)). Some studies look at the situations where restricting the domain leads to impossibility results. These studies intend to strengthen the impossibility result (without being far from complete), see for instance Sanver (2009), Aswal et al. (2003) or Sato (2010). While, other studies discuss domain restrictions allowing for non-dictatorial, unanimous and strategy-proof choice rules. Well known is the restriction to single peaked preferences starting with Black (1948) and developed further by Moulin (1980), which leads to domains for anonymous and strategy-proof choice rules based on majority decisions. However, as previously mentioned, our approach differs from a vast majority of previous such studies because our domain restrictions are not uniform over all agents.

The paper is organized as follows. Besides some basic concepts on preferences, Sect. 2 discusses partial orders, social choice functions and its properties. Section 3 is on the betweenness relation of linear orders. We show that every linear order that is between two admissible ones is also admissible. Sect. 4 is on that the range of unanimous, strategy-proof and non-image-dictatorial choice rules. We prove that in the present framework this range consists of precisely two alternatives. In Sect. 5, we discuss which a priori information leads to domains of preference profiles allowing for such choice rules. In Sect. 6, we provide concluding remarks and consider an application to a model where alternatives belong on a Euclidean plane.

Let A denote a non-empty and finite set of alternatives and R a relation on A. For distinct alternatives x and y, \((x,y)\in R\) means x is preferred to y at R. For a non-empty subset B of A the restriction of R to B is denoted by \(R|_{B}\), i.e. \( R|_{B}=\{(x,y)\in R:x\in B\) and \(y\in B\}\). The best alternatives with respect to R and a subset B of A are defined by \( best(R,B)=\{x\in B:(x,y)\in R\) for all \(y\in B\}\). In many cases best(R, B) is a singleton and we abuse notation by identifying the singleton set with its element. The undominated alternatives with respect to R are defined by \(undom(R)=\) \(\{x\in A:(y,x)\notin R\) for all \(y\in A\backslash \{x\}\}\). Relation R on A is said to beLet \(N=\{1,2,...,n\}\) denote a finite set of n agents. The individual preferences of agents are modelled by linear orders: irreflexive, transitive, weakly complete and asymmetric relations on A. We denote the set of all linear orders on A by \(\mathbb {L}(A).\) To an agent i we associate a partial order \(P^{i}\), i.e. transitive, irreflexive and asymmetric. We interpret \(P^{i}\) as the part of agents i’s preference that is fixed and therewith "known". This means that agent i’s preference contains \(P^{i}.\) So, as \(P^{i}\) is not necessarily weakly complete i’s preference is an extension of \(P^{i}\) to a linear order on A. Let \(\mathbb { L}(P^{i},A)=\{R\in \mathbb {L}(A):P^{i}\subseteq R\}\) denote the set of all these extension of \(P^{i}.\) As we assume to “know” exactly \(P^{i}\) about agent i’s preference, that is no more and no less, agent i’s set of admissible preferences equals \(\mathbb {L}(P^{i},A).\) Note that, if \(P^{i}\) is weakly complete, meaning that i’s preference is completely “known”, then \(\mathbb {L}(P^{i},A)=\{P^{i}\}\). Further, if \(P^{i}\) is empty, meaning that nothing is “known” about i’s preference, then \(\mathbb {L}(P^{i},A)= \mathbb {L}(A).\) In the latter case agent i’s set of admissible preferences is called unrestricted. In all other cases it is called restricted.

Let \(P^{*}=\bigcup _{i\in N}P^{i}\) be the union of all a priori information. Related to \(P^{*}\) we will formulate necessary and sufficient conditions for these restricted domains such that these are possibility domains. Let \(P^{N}\) represent the vector of all individuals’ a priori information.

A profile p assigns to every individual i a preference p(i) in \(\mathbb {L}(P^{i},A)\). Let \(\mathbb {L}(P^{N},A)=\{p\in \mathbb {L(A)} ^{N}:p(i)\in \) \(\mathbb {L}(P^{i},A)\) for all i in N \(\}\) denote the set of profiles. We call \(\mathbb {L}(P^{N},A)\) a domain based on a priori information (\(P^{N}\)). Let p and q be profiles in \( \mathbb {L}(P^{N},A)\) and j be an agent in N. Profile q is a j -deviation of p if \(p(i)=q(i)\) for all agents \(i\in N\backslash \{j\}.\) Further, let x and y be two distinct alternatives such that agent j prefers x consecutively above y,  i.e. \((x,y)\in p(j)\) and \((x,z)\in p(j)\iff (y,z)\in p(j)\) for \(z\in A\backslash \{x,y\}.\) Then \(p^{j,yx}\) denotes the j-deviation of p such that \(p^{j,yx}(j)=(p(j)\backslash \{(x,y)\})\cup \{(y,x)\}.\) So, \(p^{j,yx}(j)\) is obtained from p(j) by swapping the positions of x and y. At \(p^{j,yx}(j)\) alternative y is consecutively preferred to x. In case \(q=p^{i,yx}\) the profiles p and q are called an elementary change in \(\{x,y\}.\) A sequence \(r^{0}\), \( r^{1},r^{2},...,r^{k}\) of profiles in \(\mathbb {L}(P^{N},A)\) is called a path (of elementary changes) from p to q (in \( \mathbb {L}(P^{N},A)\)), if \(r^{0}=p,\) \(r^{k}=q\) and for all \(t\in \{0,1,2,...,k-1\}\) profiles \(r^{t}\) and \(r^{t+1}\) form an elementary change, say in \(\{x^{t},y^{t}\}.\) That means, for some agent \(i^{t}\) the profile \( r^{t+1}=(r^{t})^{i^{t},x^{t}y^{t}}\).

For a non-empty subset B of A and a profile p, the restriction of p to B is defined agent wise for an agent i in N by \( (p|_{B})(i)=p(i)|_{B}.\) Further, for an arbitrary set of profiles \(\mathbb {S} \) let \(\mathbb {S}|_{B}=\{p|_{B}:p\in \mathbb {S}\}\) denote the set of profiles restricted to B.

Next, we introduce some representations for preferences and profiles. Let a,  b and c be alternatives. Let p denote a profile. Let i be an agent. Then \(...ab...=p(i)\) denotes that a is consecutively preferred to b by agent i. Further, \(ab...=p(i)\) means that a is best and b second best for agent i at p(i). In case A \(=\{a,b,c\}\) the preference at which a is best, b second best and c is worst is denoted by abc. Further, \(((abc)^{j},p|_{N\backslash \{j\}})\) denotes the j-deviation, say q,  of p where \(q(j)=abc.\) Here, \(p|_{N\backslash \{j\}}\)denotes the restriction of p to \(N\backslash \{j\}.\) Similar notations like \( ...yz_{1}z_{2}...z_{l}x...=p(1)\) or \((p(1),r(2),p|_{N\backslash \{1,2\}})\) have the obvious interpretations.

A (collective) choice rule is a function f from \(\mathbb {L} (P^{N},A)\) to A. It assigns to every profile p, a collective choice f(p) in A.

Unanimity: \(f(p)=a\) for all profiles p and alternatives a such that for all individuals i, \(best(p(i),A)=\{a\}\),

Surjectivity: For all alternatives x in A there are profiles p in \(\mathbb {L}(P^{N},A)\) such that \(f(p)=x\),

Strategy-proofness: \((f(p),f(q))\in p(j)\) for all individuals j and all the j-deviations q of p,

Maskin Monotonicity: for all profiles p and q such that \( (f(p),x)\in p(i)\) implies \((f(p),x)\in q(i)\) for all individuals i and all alternatives x, we have that \(f(q)=f(p)\),

Non-dictatorship: for all individuals j there are profiles p such that \(f(p)\ne \) best(p(j), A),

Non-image-dictatorship: for all individuals j there are profiles p such that \(f(p)\ne \) \(best(p(j),f(\mathbb {L}(P^{N},A)))\), where \(f( \mathbb {L}(P^{N},A))=\{f(p):p\in \mathbb {L}(P^{N},A)\}\) is the range of f.

Strategy-proofness, Maskin monotonicity, unanimity and non-dictatorship are standard in literature. Surjectivity is a well-known property for functions also known as “onto”. We will not comment on these further.

The following Example 1 shows that, in the setting at hand, non-dictatorship is not sufficient to ensure that the outcome of the choice rule is completely determined by one single agent.

Let i and j be distinct agents and a and b be distinct alternatives. Let \((a,b)\in P^{i}\) and \(b\in \) \(undom(P^{j})\). In that case, define f for an arbitrary profile as followsThis choice rule is strategy-proof, unanimous and image-dictatorial with image-dictator j, but it is non-dictatorial as b is not chosen if it is j’s best alternative. \(\square \)

The above example shows that a domain based on a priori information allows for non-dictatorial, unanimous, and strategy-proof choice rules if there are agents i and j such that \(undom(P^{i})\ne undom(P^{j}).\) At these choice rules, however, the agents in \(N\backslash \{j\}\) are immaterial for the outcome, which we think is not according to the spirit of a possibility result.

To avoid rules like in Example 1 we impose non-image-dictatorship. Clearly non-image-dictatorship is a stronger condition than non-dictatorship, because \(f(p)=\) best(p(j), A) implies \( best(p(j),A)\in f(\mathbb {L}(P^{N},A))\) and therefore \(f(p)=\) best(p(j), A) implies \(f(p)=\) \(best(p(j),f(\mathbb {L}(P^{N},A)))\). Lemma 1 shows that under strategy-proofness, non-image-dictatorship of a choice rule f is equivalent to non-dictatorship of choice rule h,  where h is the restriction of f to its range. Further, in Sect. 6, from the results on non-image-dictatorship we derive in a few lines a characterization of those domains allowing for non-dictatorial, unanimous, and strategy-proof choice rules.

In Kemeny and Snell (1962) the following notion of betweenness on linear orders is discussed. Let \(R^{1},\) \(R^{2}\) and \(R^{3}\) be linear orders. We say that an order \(R^{3}\) is between \(R^{1}\) and \(R^{2}\), if \((R^{1}\cap R^{2})\subseteq R^{3}\subseteq (R^{1}\cup R^{2})\). For example, for alternatives a, b, c, an order \(R^{3}=acb\) is in between \(R^{1}=abc\) and \( R^{2}=cab\). In general, by successively swapping consecutively ordered pairs of alternatives linear order \(R^{2}\) can be obtained from linear order \( R^{1} \). The minimal number of swaps needed is equal to \(\#(R^{1}\backslash R^{2})=\#(R^{2}\backslash R^{1}).\) All intermediate orders on this swap path are between \(R^{1}\) and \(R^{2}.\) Reversely, it is well-known that all orders, being between \(R^{1}\) and \(R^{2},\) are on such a shortest swap path.

We call an arbitrary set of linear orders \(\mathbb {S}\) betweenness closed, if for all \(R^{1},\) \(R^{2}\in \mathbb {S}\) and all \(R^{3}\in \mathbb { L}(A)\)Hence, set \(\mathbb {S}\) of linear orders is betweenness closed if for any two orders, \(R^{1}\) and \(R^{2}\) in \(\mathbb {S}\) all linear orders on any shortest swap path from \(R^{1}\) to \(R^{2}\) are in \(\mathbb {S}.\) The following Proposition 1 shows that to each non-empty betweenness closed set \(\mathbb {S}\) of linear orders, we may associate a partial order P such that \(\mathbb {S}\) consists precisely of all linear extensions of P.

The following Remark 1 is an immediate consequence of Proposition 1.

In this section, we prove that the range of a non-image-dictatorial, strategy-proof, and unanimous choice rule on a domain based on a priori information consists of precisely two alternatives. We need three basic results. The first one shows that for such domains and choice rules, there exists a non-constant, surjective, strategy-proof and non-dictatorial choice rule on the preference domains, which are restricted to the range of that choice rule.

The second basic result proves that for strategy-proof rules dictatorship on certain subsets of the domain extends to profiles which are elementary changes of a profile in that subset. This result entails the “epidemic" spread of decisiveness often noticed in proofs of impossibility theorems.

The third basic result shows that at least one \(P^{i}\) is neither weakly complete nor empty in case the domain allows for surjective, strategy-proof, and non-dictatorial choice rules with a range of at least three alternatives.

Next, we prove in our setting the range of non-image-dictatorial, strategy-proof and unanimous choice rules consists of precisely two alternatives.

In view of Lemma 1 it is sufficient to prove \(\mathcal {P}(k)\) for all k by induction on \(k\ge 3.\)

Let \(\#A=3\) and let \(\mathbb {L}(P^{N},A)\) be a domain based on a priori information. To the contrary of \(\mathcal {P}(3)\), suppose choice rule f from \(\mathbb {L}(P^{N},A)\) to A is strategy-proof, non-dictatorial, and surjective. Let a,  b, and c be the distinct alternatives in A. So, \(f(\mathbb {L}(P^{N},A))=\{a,b,c\}=A.\) Without loss of generality we may assume that we have taken \(P^{i}\) inclusion maximal for all agents i. That is for partial orders \(\widetilde{P}^{i},\) with \( P^{i}\subseteq \widetilde{P}^{i},\) and domains based on a priori information \(\mathbb {L}(\widetilde{P}^{i},A)\), there are surjective, strategy-proof and non-dictatorial choice rules h from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A,  only if \(P^{i}=\widetilde{P}^{i}\) for all agents i. By Lemma  3 we may assume that for some agents j the a priori information \(P^{j}\) is neither weakly complete nor empty. Without loss of generality let \(P^{1}\) be neither empty nor weakly complete. We will show the contradiction, that is for some partial orders \(\widetilde{P}^{1},\) with \(P^{1}\subsetneq \widetilde{P}^{1}\), \(\widetilde{P}^{i}=P^{i}\) for all i in \(N\backslash \{1\}\), and domain \(\mathbb {L}(\widetilde{P }^{N},A)\), there exist surjective, strategy-proof and non-dictatorial choice rules h from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A. As \(P^{1}\) is neither complete nor empty, we may distinguish the following two cases.

So, after a possible renaming of the alternatives, we have \(P^{1}=\{(a,b)\}\) and \(\mathbb {L}(P^{1},A)=\{abc,acb,cab\}.\) Define \(\widetilde{P}^{j}=P^{j}\) for \(j\in N\backslash \{1\}\) and \(\widetilde{P}^{1}=\{abc,acb\}.\) As f is surjective, there are profiles, say \(q_{a}\) and \(q_{b}\) in \(\mathbb {L} (P^{N},A)\) with \(f(q_{a})=\) a and \(f(q_{b})=b.\) As a is ranked best at preference abc, by Maskin monotonicity we may assume that \(q_{a}(1)=abc.\) As b is ranked worst at acb and at cab by Maskin monotonicity we may assume that \(q_{b}(1)=abc.\) This means that there are profiles \(q_{a}\) and \( q_{b}\) in \(\mathbb {L}(\widetilde{P}^{N},A)\) such that \(a=f(q_{a})\) and \( b=f(q_{b}).\) We distinguish the following two sub-cases.

Sub-case There are profiles r with \(r(1)\in \{abc,acb\}\) and \( f(r)=c.\)

Define function \(h=f|_{\mathbb {L}(\widetilde{P}^{N},A)}\) from \(\mathbb {L}( \widetilde{P}^{N},A)\) to A as the restriction of f to \(\mathbb {L}( \widetilde{P}^{N},A).\) Clearly h is surjective, as \(q_{a},q_{b},\) and r are in \(\mathbb {L}(\widetilde{P}^{N},A)\) and \(a=f(q_{a})=h(q_{a}),\) \( b=f(q_{b})=h(q_{b})\), and \(c=f(r)=h(r).\) Further, h inherits strategy-proofness from f. To complete this case we prove that h is not dictatorial. To the contrary suppose h is dictatorial with dictator i. For agents j with \(P^{j}\ne \emptyset \) we have that y is not ordered best for those agents j when \((x,y)\in P^{j}.\) As the range of f is A, y is chosen at some profile. Therefore, such agents j, with \(P^{j}\ne \emptyset ,\) cannot be dictator at h. This means that the domain \(\mathbb {L }(\widetilde{P}^{i},A)\) of i is unrestricted. So, \(i\ne 1\) and \(\mathbb {L} (\widetilde{P}^{i},A)=\mathbb {L}\). As all profiles in \(\mathbb {L}(P^{N},A)\) are connected via paths of elementary changes, repeated applications of Lemma  2 implies that f is dictatorial if \(h=f|_{\mathbb {L}( \widetilde{P}^{N},A)}\) is dictatorial. As f is not dictatorial it therewith follows that h is not dictatorial.

So, h is a non-dictatorial, strategy-proof, and surjective choice rule from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A. Clearly this contradicts that \(P^{i}\) is inclusion maximal for all agents i.

Sub-case There are no profiles r with \(r(1)\in \{abc,acb\}\) and \( f(r)=c.\)

Define function h for an arbitrary profile p in \(\mathbb {L}(\widetilde{P} ^{N},A)\) as followsWe prove that rule h is surjective, strategy-proof and non-dictatorial.

(surjectivity) Let p in \(\mathbb {L}(\widetilde{P}^{N\backslash \{1\}},A)\) be an arbitrary profile. Further, suppose \(f((abc)^{1},p)=a.\)

Then strategy-proofness implies \(f((acb)^{1},p)=a\) and \(f((cab)^{1},p)=a\) or \( f((cab)^{1},p)=\) c. If \(f((abc)^{1},p)=c,\) then strategy-proofness implies \(f((acb)^{1},p)\) \(=f((cab)^{1},p)=c.\) And if \(f((abc)^{1},p)=b\), then strategy-proofness implies either \(f((acb)^{1},p)=\) \(f((cab)^{1},p)=c\) or it implies \( f((acb)^{1},p)=f((cab)^{1},p)=b.\) So, all in all the outcomes \( f((abc)^{1},p)\), \(f((acb)^{1},p),\) and \(f((cab)^{1},p)\) are correlated as depicted in the table below.Let us call p of type I if \(f((abc)^{1},p)=a,\) \(f((acb)^{1},p)=a\) and \( f((cab)^{1},p)=a.\) Similarly, we define the other four types. According to the sub-case assumption, there are no profiles of type III and no profiles of type IV. As f has range A and there are no type III and no type IV profiles, there are profiles of type II and type V. Therefore, by the definition of h we have that c and b are in the range of h.

Consider a profile of type II, say \(r^{II},\) and one of type V, say \(r^{V}.\) We claim that these cannot form an elementary change. To the contrary assume \(r^{II}\) and \(r^{V}\) form an elementary change. We deduce a contardiction. Using the table we have \(f((abc)^{1},r^{II})=a\) and \(f((abc)^{1},r^{V})=b\). Remark 1 implies that \(r^{II}\) and \(r^{V}\) form an elementary change is in \(\{a,b\}\). By the table we also have \(f((cab)^{1},r^{II})=c\) and \(f((abc)^{1},r^{V})=b.\) Remark 1 implies that this elementary change is in \(\{c,b\}\). As \(\{a,b\}\ne \{b,c\}\) we have a contradiction. So, type II and type V profiles do not form elementary chages. As there is a connecting path of elementary changes between \(r^{II}\) and \(r^{V}\) this means that there are profiles of type I implying that a is also in the range of h. Hence, h is surjective.

(strategy-proofness) By definition \( h((abc)^{1},p)=h((acb)^{1},p)=f((cab)^{1},p)\) for all profiles p in \( \mathbb {L}(\widetilde{P}^{N\backslash \{1\}},A)\), so agent 1 cannot manipulate at a profile. Consider an i-deviation p and q in \(\mathbb {L} (\widetilde{P}^{N\backslash \{1\}},A)\). By strategy-proofness of f we have \((f((cab)^{1},p),f((cab)^{1},q))\in p(i)\). By the definition of h we therefore have \((h((abc)^{1},p),h((abc)^{1},q))\in p(i)\) and \( (h((acb)^{1},p),h((acb)^{1},q))\in p(i).\) So, h cannot be manipulated by an agent i in \(N\backslash \{1\}.\)

(non-dictatorship) For an agent j,  with \((x,y)\in P^{j}\) and \( x\ne y,\) alternative y is not ordered best at p(j) for all profiles p in \(\mathbb {L}(\widetilde{P}^{N},A).\) As at some profiles alternative y is chosen under rule h, such agents j cannot be dictator at h. Let agent i be such that \(\mathbb {L}(\widetilde{P}^{i},A)=\mathbb {L}(A)\). Hence, \( \widetilde{P}^{i}\) empty and therewith \(i\ne 1.\) Assume i is dictator at h. We deduce a contradiction. By the definition of h we have that \( f((cab)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})=h((acb)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})=c\). The sub-case assumption yields \(f((acb)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})\ne c.\) As profiles \(((cab)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})\) and \(((acb)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})\) form elementary change in \(\{a,c\}\) and f is strategy-proof, Remark 1 implies \(f((acb)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})\) \(=a\). Furthermore, definition of h and i being dictator at h also implies that \(f((cab)^{1},(bca)^{i},p|_{N \backslash \{1,i\}})=h((acb)^{1},(bca)^{i},p|_{N\backslash \{1,i\}})=b\). As b is ordered worst for agent 1 strategy-proofness implies \(f((acb)^{1},(bca)^{i},p|_{N\backslash \{1,i\}})=b\). Comparing \(f((acb)^{1},(cba)^{i},p|_{N\backslash \{1,i\}})=a\) and \(f((acb)^{1},(bca)^{i},p|_{N\backslash \{1,i\}})=b\) yields a contradiction with strategy-proofness of f. Hence, h is non-dictatorial.

So, h is a non-dictatorial, strategy-proof, and surjective choice rule from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A. Clearly this contradicts that \(P^{i}\) is inclusion maximal for all agents i.

By symmetry we may assume that \(P^{1}=\{(a,b),(a,c)\}.\) So, \( \mathbb {L}(P^{1},A)=\{abc,acb\}.\) For arbitrary profiles p in \(\mathbb {L}( \widetilde{P}^{N\backslash \{1\}},A)\), strategy-proofness imposes that the outcomes at \(f((abc)^{1},p)\) and \(f((acb)^{1},p)\) are correlated as in one of the following four types depicted in the table below.As f is surjective, it follows that profiles of type II are in \(\mathbb {L} (P^{N\backslash \{1\}},A).\) Between all profiles p and q in \(\mathbb {L} (P^{N\backslash \{1\}},A)\) there is a sequence of profiles in \(\mathbb {L} (P^{N\backslash \{1\}},A)\), say \(r^{0}=p\), \(r^{1},r^{2},...,r^{k}=q\) such that for all \(0\le t<\) k the profiles \(r^{t}\) and \(r^{t+1}\) form elementary change. Let that elementary change be in \(\{x^{t},y^{t}\}.\) Like above, a type IV profile and a type II profile cannot form an elementary change. So, if profiles of type II and profiles of type IV are present in \(\mathbb {L} (P^{N\backslash \{1\}},A)\), then there are also profiles of type III in \( \mathbb {L}(P^{N\backslash \{1\}},A)\) or profiles of type V in \(\mathbb {L} (P^{N\backslash \{1\}},A)\). As f is surjective this means that profiles of types II, III, and IV are present in \(\mathbb {L}(P^{N\backslash \{1\}},A),\) or profiles of types II, III, and V are present in \(\mathbb {L} (P^{N\backslash \{1\}},A)\), or profiles of types II, IV, and V are present in \(\mathbb {L}(P^{N\backslash \{1\}},A)\). In the first two cases it follows that \(\{f((abc)^{1},p):p\in \mathbb {L}(P^{N\backslash \{1\}},A)\}=\{a,b,c\}\) , where in the latter case \(\{f((acb)^{1},p):p\in \mathbb {L}(P^{N\backslash \{1\}},A)\}=\{a,b,c\}.\) If \(\{f((abc)^{1},p):p\in \mathbb {L}(P^{N\backslash \{1\}},A)\}=\{a,b,c\},\) then define \(P^{j}=\widetilde{P}^{j}\) for \(j\in N\backslash \{1\}\) and \(\widetilde{P}^{1}=abc\) and if\(\{f((acb)^{1},p):p\in \mathbb {L}(P^{N\backslash \{1\}},A)\}=\{a,b,c\},\) then define \(P^{j}= \widetilde{P}^{j}\) for \(j\in N\backslash \{1\}\) and \(\widetilde{P}^{1}=acb.\) Define \(h=f|_{\mathbb {L}(\widetilde{P}^{N},A)}.\) Clearly h is strategy-proof and has range \(\{a,b,c\}\) by definition. Next, we prove that it is non-dictatorial.

To the contrary assume that h is dictatorial with dictator i. We prove the contradiction that f is dictatorial with dictator i. Because the range of h is A it follows that \(\widetilde{P}^{i}\) is empty. Otherwise for some \((x,y)\in P^{i}\), by surjectivity at some profile y is chosen while it is not i’s best. So, \(\mathbb {L}(\) \(\widetilde{P}^{i},A)=\mathbb {L }(A).\) As \(f|_{\mathbb {L}(\widetilde{P}^{N},A)}\) is dictatorial with dictator i,  Lemma 2 implies that f is dictatorial with dictator i.

So, h is a non-dictatorial, strategy-proof, and surjective choice rule from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A. Clearly this contradicts that \(P^{i}\) is inclusion maximal for all agents i and concludes the proof of the induction basis.

Induction step Let \(\mathcal {P}(k),\) with \(k\ge 3.\) Suppose \(\#f( \mathbb {L}(P^{N},A))=k+1.\) We deduce a contradiction. Without loss of generality we may assume that \(P^{i}\) is inclusion maximal for all agents i . That is for partial orders \(\widetilde{P}^{i},\) with \(P^{i}\subseteq \widetilde{P}^{i},\) and domains based on a priori information \(\mathbb {L}( \widetilde{P}^{i},A)\), there are surjective, strategy-proof and non-dictatorial choice rules h from \(\mathbb {L}(\widetilde{P}^{N},A)\) to A,  only if \(P^{i}=\widetilde{P}^{i}\) for all agents i. By Lemma  3 we may assume that for some agents j the a priori information \(P^{j}\) is neither weakly complete nor empty. Without loss of generality let \(P^{1}\) be neither empty nor weakly complete. Therefore, there exist distinct alternatives x and y that are incomparable at \(P^{1},\) that is \((y,x)\notin P^{1},(x,y)\notin P^{1},\) and for all \(z\in A\backslash \{x,y\}\)² Let \(\widetilde{P}^{j}=P^{j}\) for all \(j\ge 2\) and let \(\widetilde{P} ^{1}=P^{1}\cup \{(x,y)\}.\) Define \(h=f|_{\mathbb {L}(\widetilde{P}^{N},A)}.\) Then h is strategy-proof. There are two cases.

Case 1 \(h(\mathbb {L}(\widetilde{P}^{N},A))=f(\mathbb {L}(P^{N},A))\)

Then h cannot be dictatorial, as by Lemma 2, this would imply that f is dictatorial. But then h is a strategy-proof, surjective, and non-image-dictatorial rule contradicting that all \(P^{i}\) are inclusion maximal.

Case 2 \(\#h(\mathbb {L}(\widetilde{P}^{N},A))\le k\)

We prove that the range of h equals \(A\backslash \{y\}\) and that h is non-dictatorial. So, \(\#h(\mathbb {L}(\widetilde{P}^{N},A))=k\ge 3.\) This then contradicts \(\mathcal {P}(k)\) by which the proof ends.

(range \(h(\mathbb {L}(\widetilde{P}^{N},A))=A\backslash \{y\}\)) Consider an alternative \(a\in A\backslash \{y\}.\) It is sufficient to prove that \(h(q)=a\) for some profile \(q\in \mathbb {L}(\widetilde{P}^{N},A).\) Note that for some profile \(f(p)=a.\) If \(p(1)\in \mathbb {L}(\widetilde{P}^{1},A),\) then we are done as we may take \(q=p.\) If \(p(1)\notin \mathbb {L}(\widetilde{P }^{1},A),\) then obviously \((y,x)\in p(1).\) Let \( ...yz_{1}z_{2}...z_{l}x...=p(1).\) Meaning that at p(1) alternative y is consecutively preferred to \(z_{1}\), \(z_{1}\) is consecutively preferred to \( z_{2},...\)and so on, where this is ending with \(z_{l}\), which is consecutively preferred to x. By the choice of x and y for all \(z\in A\backslash \{x,y\}\) we have \((y,z)\in P^{1}\) implies \((x,z)\in P^{1}.\) So, as \( (z_{1},x)\in p(1)\) and therewith \((x,z_{1})\notin P^{1}\), it follows that \( (y,z_{1})\notin P^{1}.\) So, \(p^{1,z_{1}y}\in \) \(\mathbb {L}(P^{N},A)\). But then as \(a\ne y\), Maskin monotonicity of f implies \(f(p^{1,z_{1}y})=a.\) Repeating this process yields a profile q \(\in \) \(\mathbb {L}(\widetilde{P} ^{N},A)\), such that \(...z_{1}z_{2}...z_{l}xy...=q(1)\) and \(f(q)=a.\) But then \(h(q)=a.\)

(non-dictatorial) To the contrary let h be dictatorial on \( \mathbb {L}(\widetilde{P}^{N},A)\) with dictator i. There are two sub-cases.

Sub-case \(i=1\)

As \(h(\mathbb {L}(\widetilde{P}^{N},A))=A\backslash \{y\},\) agent 1 being dictator of h means for all \(a\in A\backslash \{y\}\) there is a preference p(1) in \(\mathbb {L}(P^{1},A),\) with \((x,y)\in p(1),\) such that \( best(p(1),A)=a.\) So, \(P^{1}\subseteq (A\backslash \{y\})\times \{y\}.\) As \( P^{1}\) is non-empty and \((x,y)\notin P^{1}\), there are \(b\in A\backslash \{x,y\}\) with \((b,y)\in P^{1}\). So, y is not a best alternative for all preferences p(1) in \(\mathbb {L}(P^{1},A).\) As i is dictator of h and \( P^{1}\subseteq (A\backslash \{y\})\times \{y\}\) we have \(f(p)=best(p(1),A)\) for all \(p\in \mathbb {L}(P^{N},A),\) with \((x,y)\in p(1).\) As \(y\ne best(p(1),A)\), Maskin monotonicity implies that \(f(r)=best(r(1),A)\) for all \( r\in \mathbb {L}(P^{N},A).\) But then \(f(\mathbb {L}(P^{N},A))=A\backslash \{y\} \) which contradicts our assumptions.

Sub-case \(i\ne 1\)

Lemma 2 now implies \(f(p)=best(p(i)|_{A\backslash \{y\}},A\backslash \{y\}).\) Hence, we have a contradiction, as the range of f does not contain y. \(\square \)

In this section we show that a domain based on a priori information allows for unanimous, non-image-dictatorial, and strategy-proof choice rules if an only if there are two distinct alternative, such that The following example shows that these two conditions are sufficient.

Let a and b be distinct alternatives such that \(undom(P^{*})\subseteq \{a,b\}.\) Let \(n_{ab}=\#\{i\in N:(a,b)\in P^{i}\}\) and \( n_{ba}=\#\{i\in N:(b,a)\in P^{i}\}.\) Suppose \(n-(n_{ab}+n_{ba})\ge 2.\) Consider a fixed (threshold) integer, say \(\tau ,\) such that \(n_{ab}<\tau <n-n_{ba}\). Define choice rule \(f_{\tau }\) from \(\mathbb {L}(P^{N},A)\) to A at an arbitrary profile p as followsSo, \(f_{\tau }\) chooses a if the support for it compared to b is at least equal to the threshold. Otherwise, \(f_{\tau }\) chooses b. As \(undom(P^{*})\subseteq \{a,b\}\), all alternatives which are not equal to a or to b are dominated. Hence, f is unanimous as there are no profiles where these alternatives are ordered best by all agents. Since the choice rule can be seen as a (Maskin) monotone-voting rule between two alternatives, it is strategy-proof. Because \( n-(n_{ab}+n_{ba})\ge 2,\) threshold \(\tau \) can be chosen strictly between \( n_{ab}\) and \(n-n_{ba}\). Therewith the choice rule is not image-dictatorial. \(\square \)

The following Theorem shows that the sufficient conditions spelled out in Example 2 are necessary.

Among the domains based on a priori information, Theorem 2 specifies those domains which allow for unanimous, strategy-proof and non-image-dictatorial choice rules. On such domains there are two alternatives for which at least two agents have no fixed preference and, further for any other alternative, say z,  there are alternatives \( z^{\prime },\) and some agent, such that in all his admissible preferences \( z^{\prime }\) is preferred to z. To the best of our knowledge Storcken (1985) and the present paper are the only two papers on domains based on a priori information. Storcken (1985) studies Pareto optimal, non-dictatorial, positively associated and pairwise anonymous welfare functions. That is, Theorem 4.7 (page 288) of Storcken (1985) characterizes those domains based on a priori information allowing for welfare functions having these four properties. The following Example 3 is based on a domain with a priori information that allows for unanimous, strategy-proof and non-image-dictatorial choice rules but not for non-dictatorial positively associated and pairwise anonymous welfare functions. Therewith, it shows that this result of Storcken (1985) does not logically imply Theorem 2.

Let \(A=\{x,y,a,b,c\}\) and \(N=\{1,2\}.\) Let \(P^{1}=\{(x,a),(x,b),(x,c)\}\) and \(P^{2}=\{(y,a),(y,b),(y,c)\}.\) So, \(undom(P^{*})=\{x,y\}.\) Let choice rule f from \(\mathbb {L}(P^{N},A)\) to A for an arbitrary profile p in \(\mathbb {L}(P^{N},A)\) be defined byIt is clear that f is voting between x and y with threshold \(\tau =1\) (in favor of x against y). So, this choice rule is non-image dictatorial, unanimous and strategy-proof. This confirms Theorem 2. Next, consider a Welfare function, say F,  on this domain that is independent of irrelevant alternatives and Pareto optimal. As both the agents can order the alternatives in \(\{a,b,c\}\) in six different ways, such a triple is also known as a free triple. Restricting F to this free triple means \(F|_{\{a,b,c\}}\) is defined by \(F|_{\{a,b,c\}}(p)=F(p)|_{\{a,b,c \}}\)). This restriction F, for any profile p in \(\mathbb {L}(P^{N},A),\) then yields by Arrow’s impossibility theorem that \(F|_{\{a,b,c\}}\) is dictatorial. This means that F violates the pairwise anonymity condition, i.e. for profiles p and q in \(\mathbb {L}(P^{N},A)\) and alternatives v and w in A, \( \#\{i\in N:(v,w)\in p(i)\}=\#\{i\in N:(v,w)\in q(i)\}\) implies \(F(p)|_{\{v,w\}}=F(q)|_{\{v,w\}}\).

As the independence of irrelevant alternatives is implied by the positive association it follows that this domain does not allow for welfare functions discussed in Storcken (1985).

Since conditions allowing for non-image-dictatorial, strategy-proof and unanimous choice rules are rather restrictive, Theorem 2 can also be seen as an impossibility theorem. Actually, the same holds for Theorem 1. This theorem, for instance implies that on domains based on a priori information a unanimous and strategy-proof choice rule, having a range of at least three alternatives, is image-dictatorial. It therewith relates to classical impossibility theorems such as Gibbard (1973). Here we traded the unrestricted domain for the unanimity condition of the choice rule. Note that, in all the proofs we only used the fact that between any two profiles there is at least one shortest swap path. Our domain restriction condition means that all such short paths are present in the domain where we only need one to deduce the presented conditions. This means that the domains which just satisfy this existence of a shortest swap path will yield the same outcome. Thus on such domains only image-dictatorial choice rules, having a range of at least three alternatives, will be strategy-proof and unanimous. Therefore, it is worthwhile to note that Theorem 2 holds for these more general class of domain restrictions.

In general, our finding may have applications in small committee decisions, where there are finite numbers of alternatives to decide on. The application then lays in deleting those alternatives that are extreme compared to the others. It is therefore rather limited. For example, consider the following reorganization of a firm. Within some given budget limits, four options are suitable. These options differ mainly from each other by the levels of computer support (K), labor force (L) and (fossil) energy (E) that is required. In the table below, these levels are given by their relative monetary costs.

It can be seen that option A is highly automated, while option D involves a low level of computer assistance. Both these options require the same energy level. In option B, this energy level is higher but the computer support and labor force are mediocre. Option C requires the lowest energy level. Thus, the committee members in favor of having a higher labor force will prefer D to A whereas those, who prefer to have more computer assistance, would prefer to have A to D. These extreme options can then be discarded and a “regular” voting mechanism can be used to select the best alternative between B and C (Table 1).

To be specific, let the preferences of the committee members be represented by Cobb-Douglas utility functions U, i.e. \(U(K,L,E)=K^{\alpha }L^{\beta }E^{\gamma }\), where \(\alpha ,\beta ,\gamma \) are strictly positive numbers. Now, a relative large \(\alpha \) as compared to \(\beta \) and \(\gamma \), i.e., \(\alpha \ge \beta +\gamma ,\) characterizes committee members favoring computer assistance. Those favoring labor force can be characterized by relative large \(\beta \) as compared to \(\alpha \) and \(\gamma ,\) i.e. \(\beta \ge \alpha +\gamma \). By doing so, in all preferences of committee members favoring computer support, option A is strictly preferred to D. In constrast, Option D is strictly preferred to option A in all preferences of committee members favoring a high labor force. During committee meeting(s), we assume that the discussion on these four options has revealed that some agents have such strong preferences for option A and some for option D. Hence, assuming Cobb-Douglas utility functions we have that \(P^{i}=\{(A,D)\}\) for those agents i who have a strong preference for option A. Where \( P^{j}=\{(D,A)\}\) for committee members having a strong preference for option D. Theorem 2 now shows that by considering A and D as outliers a monotone-vote with respect to Maskin monotonicity between B and C would yield a unanimous and strategy-proof outcome.

Theorem 2 describes the restricted domains based on a priori information, which allow for unanimous, non-image-dictatorial and strategy-proof choice rules. It shows that by allowing for such choice rules on these domains, there are at most two undominated alternatives with respect to the united a priori information, and that the range of the rule consists of precisely two alternatives. Having precisely two alternatives in the range means that the choice rule boils down to a non-dictatorial and Maskin monotone choice rule between these two alternatives. So, apart from the domain, even the possible choice rules are determined.

We end this section with a discussion on alternatives for the two chosen properties: unanimity and non-image-dictatorship. The condition of anonymity imposes that agents are equally strong with respect to their decision power. Usually it does so by imposing that the choice rule is symmetric in its arguments. Here this may create a problem as the agents’ admissible sets of preferences may differ. Therefore, consider a formulation that ensures that agents have as much as possible an equal influence on the outcome.³ Excluding constant choice rules, this yields that the choice rule is non-image-dictatorial. Therewith the analysis results in Theorems 1 and 2 with one difference. The choice rules between the two alternatives in the range are now, like the choice rules in Example 2, based on the numbers of agents having a specific preference between these two.

Relaxing non-image-dictatorship to non-dictatorship leads to the following result.

Another condition frequently imposed on choice rules is Pareto-optimality. It means that an alternative x is not chosen when there are alternatives y,  which all individuals (strictly) prefer to x. As Pareto-optimality implies unanimity, substituting Pareto-optimality for unanimity implies by Theorem 1 that the range consists of two alternatives. As the rules of Example 2 are not necessarily Pareto-optimal, the only implication \((1)\Longrightarrow (2)\) of Theorem 2 holds. So, for Pareto-optimal, strategy-proof and non-image-dictatorial choice rule f from \(\mathbb {L}(P^{N},A)\) to A there are distinct alternatives a and b, such that \(undom(P^{*})\subseteq \{a,b\},\) and \( \#N-(\#N_{ab}+\#N_{ba})\ge 2,\) where \(N_{ab}=\{i\in N:(a,b)\in P^{i}\}\) and \(N_{ba}=\{i\in N:(b,a)\in P^{i}\}.\) In general, it depends on the a priori information whether some of the rules in Example 2 are Pareto-optimal. To illustrate this consider the following two examples.

Let \(A=\{a,b,x,y\}\) be a set of four distinct alternatives. Let \(\#N=2k+1\) for some positive number k. For agents \(i\le k\) let \(P^{i}=\{(a,x)\}\) and for agents \(j\ge k+2\), let \(P^{j}=\{(b,y)\}.\) So, \(P^{k+1}\) is empty. We argue that on a domain based on this a priori information there are no Pareto-optimal, strategy-proof and non-image-dictatorial choice rules. Suppose there exist such choice rules f. We deduce a contradiction. As Pareto-optimality implies unanimity, by Theorem 1 we have that the range of f contains precisely two alternatives. As a and b are both undominated at \(P^{*}\) it follows that this range of f equals \( \{a,b\}. \) Next, consider profile p defined as followsAt this profile a is Pareto-dominated by y and b is Pareto dominated by x. So, f violates Pareto-optimality as its range is \(\{a,b\}.\) However, adding \(P^{k+1}=\{(b,y),(a,x)\}\) yields a domain based on a priori information, where a and b cannot be Pareto-dominated simultaneously. Defining \(f_{\tau },\) like in Example 2, with \(\tau =k+1,\) yields a Pareto optimal, strategy-proof and non-image-dictatorial choice rule. To show this, it is sufficient to prove that a is not chosen when it is Pareto-dominated by y. Note that in that case all agents \(j\ge k+1\) prefer b to y and y to a. So, the support for a against b is less than or equal to k. This means that a is not chosen.

Note that for thresholds \(\tau \ge k+2\), choice rule \(f_{\tau }\) is not Pareto-optimal. For those \(\tau \), there are profiles at which the support for a against b equals \(k+1\) and b is Pareto-dominated by x. Similarly, it follows that for thresholds \(\tau \le k\) choice rule \(f_{\tau }\) is not Pareto-optimal. \(\square \)

Next we discuss a domain that allows for Pareto-optimal, strategy-proof, and non-image-dictatorial choice rules.

Let A denote the set of alternatives, and let a and b be two distinct alternatives in A. Assume that \((a,c)\in P^{*}\) for all \(c\in A\backslash \{a,b\}\). Now the following rule f is defined for an arbitrary profile p as followsChoice rule f is Pareto-optimal, strategy-proof and non-image-dictatorial. \(\square \)

The two foregoing examples clarify that it is at least not straight forward to find necessary and sufficient conditions such that a domain based on a priori information allows for Pareto-optimal, strategy-proof and non-image-dictatorial choice rules. Given the rather restrictive result spelled out by Theorem 1 we therefore did not incorporate an extensive study on this discussion.