Ambiguous social choice functions

Demeze-Jouatsa, Ghislain-Herman Working Paper Ambiguous social choice functions Center for Mathematical Economics Working Papers, No. 660 Provided in Cooperation with: Center for Mathematical Economics (IMW), Bielefeld University Suggested Citation: Demeze-Jouatsa, Ghislain-Herman (2021) : Ambiguous social choice functions, Center for Mathematical Economics Working Papers, No. 660, Bielefeld University, Center for Mathematical Economics (IMW), Bielefeld, https://nbn-resolving.de/urn:nbn:de:0070-pub-29603681 This Version is available at: https://hdl.handle.net/10419/249883 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ 660 December 2021 Ambiguous Social Choice Functions Ghislain-Herman Demeze-Jouatsa Center for Mathematical Economics (IMW) Bielefeld University Universit¨atsstraße 25 D-33615 Bielefeld ·Germany e-mail: [email protected] uni-bielefeld.de/zwe/imw/research/working-papers ISSN: 0931-6558 Unless otherwise noted, this work is licensed under a Creative Commons Attribution 4.0 International (CC BY) license. Further information: https://creativecommons.org/licenses/by/4.0/deed.en https://creativecommons.org/licenses/by/4.0/legalcode.en Ambiguous Social Choice Functions Ghislain-Herman DEMEZE-JOUATSA1 Center for Mathematical Economics, Bielefeld University demeze [email protected] This version: December 22, 2021 Abstract: Call a mechanism that associates each profile of preferences over candidates to an ambiguous act an Ambiguous Social Choice Function (ASCF). This paper studies the strategy-proofness of ASCFs. We find that an ASCF is unanimous and strategyproof if and only if there exists a nonempty subset of voters, called the set of top voters, such that at each preference profile, the range of the selected act equals the set of top-ranked candidates of top voters. We provide a full characterization of the class of unanimous, strategyproof, and anonymous ASCFs, and provide a large subclass of ASCFs that satisfy the additional property of neutrality. Keywords: Social Choice Function, Ambiguity Aversion, Ellsberg Urns, Strategy-proofness, Unanimity, Anonymity, Neutrality. JEL classification: D71, D72, D81, D82 1 Introduction A major weakness of voting mechanisms is their non-strategy-proofness: by misrepresenting their preferences, a voter can favor the selection of a candidate he or she prefers to the candidate that would otherwise be selected, see Gibbard (1973) and Satterthwaite (1975). Such an operation is generally possible because the voting mechanism is perfectly known and unambiguously associates each declared profile of preferences to the election winner. It 1I gratefully acknowledge financial support from the DAAD and the DFG (Deutsche Forschungsgemeinschaft / German Research Foundation) via grant Ri 1128-9-1 (Open Research Area in the Social Sciences, Ambiguity in Dynamic Environments) and thank Frank Riedel, Herbert Dawid, Chiaki Hara, Joel Sobel, Roland Pongou, Tondji Jean-Baptiste, Henrietta Acquah-Swanzy, Niels Boissonet, Manuel F¨orster, Gerrit Bauch, Zhaojun Xing, Eric Bahel and Christoph Kuzmics for useful comments. I also thank seminar participants at Bielefeld University. Ghislain-H DEMEZE-JOUATSA Bielefeld University is natural to wonder if strategyproof voting mechanisms can be constructed if the designer is allowed to leave some of their aspects uncertain. One can for instance easily conceive a voting situation where a menu of deterministic voting mechanisms is announced to the voters, from which one will be (ex-post) chosen, after they cast their ballots, to aggregate the preferences. Ex-post, the selection of the aggregating mechanism (within the given set) can for instance be conditioned on the outcome of a horse race or the realization of an imprecise probabilistic device, such as an Ellsberg urn. Think for instance of a peer-reviewing process, where the reviewers (voters in this case), prior to submitting their recommendations (preferences) for the paper under review, only have partial information about the aggregation process (or the type of the editor in charge): the editor is either pessimistic (aggregates the recommendations of reviewers using anti-plurality rule), neutral (aggregates the recommendations of reviewers using the Borda rule), or optimistic (aggregates the recommendations of reviewers using the plurality rule). In such a scenario, instead of pointing out a given candidate as the election winner, the proposed mechanism selects an act: a function that associates each possible state of nature to an election winner. Call such aggregating mechanism an Ambiguous Social Choice Function (ASCF).2 Call an ASCF unanimous if it selects the constant act which is equivalent to the topranked candidate of all players, whenever such candidate exists. This study provides a full characterization of the set of unanimous and strategyproof ASCFs, and a full characterization of ASCFs that are additionally anonymous. It is assumed that voters are ambiguity averse and aim to maximize their worst-case payoff: the preferences of voters over the set of candidates are extended to preferences over acts using the maxmin (Gilboa and Schmeidler (1989)) with lexicographic maxmin tie break rule (Pattanaik and Peleg (1984)). Our interest in this class of preferences is two-folds. In addition to capturing the aversion to ambiguity, it is complete, and indifference classes are smaller than those obtained under the maxmin extension (Gilboa and Schmeidler (1989)). See Barber`a et al. (2004) for an overview of other possible extensions of preference relations and their axiomatizations. We show that unanimous and strategyproof ASCFs are ex-post Pareto optimal: for each profile of preferences and each state of nature, the selected candidate is always the top-ranked candidate of at least one voter. The main result stipulates that an ASCF is unanimous and strategyproof if and only if it is a top selection: there exists a subgroup N0of voters, say the set of top voters, such that the range of the act selected at any profile of preferences 2Under an ASCF F, the election proceeds as follows. At time t=−1, the planner sets the ASCF F as well as the randomization device (think of an Ellsberg Urn) that will be used to determine the state of nature. At time t= 0, voters cast their ballots, and the profile of preferences, say RN, is known. At time t= 1, the ASCF Fis used to determine the selected act, say F(RN). At time t= 2, the state of nature, say ω, is drawn and candidate F(RN, ω) is elected. page 2 Ghislain-H DEMEZE-JOUATSA Bielefeld University is always the set of top-ranked candidates of voters of the group N0.3Preferences of other voters are taken into account only in the assignment of candidates to states of nature. In this sense, preferences of all voters can be taken into account by a unanimous and strategyproof ambiguous social choice function, even if the group N0contains only 2 voters, given that the state space is rich enough. In the case that the set N0is restricted to a singleton, the top selection is unique and is a dictatorship: at each profile of preferences, the selected act is constant and corresponds to the top-ranked candidate of the unique voter of the block N0, the dictator. We show that an ASCF is unanimous, strategyproof, and anonymous if and only if it is a top selection with top voters N0=N, and each state of nature corresponds to a deterministic anonymous social choice function. We uncover a class of ASCFs that are unanimous, strategyproof, anonymous, and neutral. Each ASCF of the later class is constructed using a different deterministic anonymous and neutral aggregation process.4 Closest to our analysis is the recent paper by Bahel and Sprumont (2020). In that paper, the authors analyze unanimous and strategyproof ASCFs in presence of expected utility-maximizing voters. They show that unanimous and strategyproof ASCFs are expost Pareto optimal in the sense that for all preference profiles, the outcome of the selected act coincides with the top-ranked candidate of at least one voter in each state of nature. Our analysis confirms that such property remains true if voters have maxmin preferences with lexicographic maxmin tie break rule. Our findings are different from that of Bahel and Sprumont (2020) as the set of top voters (N0) in our setting is constant, while in their setting the set of top voters might vary with the preference profile. In this paper, we assume that the extended preferences of voters over the set of acts are of maxmin type. Voters, therefore, rank acts accordingly to their support: two acts with the same support are equivalent. In this sense, our analysis also belongs to the social choice correspondence literature. In particular, for the case of two voters, our main result (Theorem 1) is similar to the one of Barber`a et al. (2001), even though voters are ambiguity averse in our model, while preferences of voters over sets of alternatives are conditionally expected utility consistent in their model. In the case that there are more than 2 voters, many other unanimous and strategyproof mechanisms emerge. We provide a full characterization of those mechanisms. In works as Pattanaik (1974), Pattanaik (1973), and Pattanaik (1976), Pattanaik studies the stability of social choice correspondences. In those papers, the extensions of preferences are of maxmin type, as the lexicographic maxmin extension used in our analysis. However, the research questions in those papers are different from that of 3The idea of top selection is closely related the omninomination rule defined in the social choice correspondence literature, see Brandt (2015), Example 6 in Benoit (2002) and Example 4 in G¨ardenfors (1976). 4Think of a deterministic aggregation process as a mechanism that associates each profile of preferences over candidates to a social ranking. page 3 Ghislain-H DEMEZE-JOUATSA Bielefeld University the current paper. The maxmin extension with lexicographic maxmin rule generalises other support-based extensions as the Kelly-extension (Kelly (1977)), the Fishbrun-extension, and the Gardenfors-extension (G¨ardenfors (1976)). In particular, our top selections are Kellystrategyproof, Fishburn-strategyproof, and Gardenfors-strategyproof. But our main result, Theorem 1, does not necessarily hold under other support-based preference extensions. For instance, the Pareto rule, which associates each profile of preferences over candidates to an act whose support equals to the set of Pareto optimal candidates is Kelly-strategyproof. Our analysis is also related to probabilistic social choice literature. Brandl et al. (2018) studies strategyproof social decision schemes. Those are social choice functions that assign each profile of preferences to a probability distribution over candidates. The authors show that there exists no unanimous and neutral social decision schemes that are efficient are strategyproof, assuming that preferences of voters over candidates are extended to lotteries over candidates in the stochastic dominance sense. Proposition 3of this paper shows that the finding of Brandl et al. (2018) does not extend to the case where preferences of voters over the set of candidates are strict and are extended to preferences over lotteries in a lexicographic-maxmin fashion. Gibbard (1977) studies the strategy-proofness of social decision schemes. When the unanimity condition is imposed, their main result says that a social decision scheme is strategyproof if and only if it is a convex combination of dictatorships. Our main result, Theorem 1, can be viewed as a robustness check of the findings of Gibbard (1977) when unanimity is required.5In particular, some top selection mechanisms can be viewed as sets of random dictatorships, and could alternatively be called ambiguous dictatorships. It is for instance the case if each state of nature corresponds (see Proposition 1) to a deterministic dictatorship. But in the general case, state space can be richer, and could for instance include (see Proposition 1) any deterministic social choice function that always selects a candidate top-ranked by at least one top voter. The paper proceeds as follows. Section 2presents the model and two real-life situations where the decision process can be modeled as an ambiguous social choice function, and Section 3presents the main findings of the paper. Some properties and examples of ASCF are provided in Section 4, and Section 5concludes the paper. 5Nandeibam (2013) provides another robustness check, assuming that voters have cardinal preferences over outcomes, and rank lotteries with respect to the expected utility. page 4 Ghislain-H DEMEZE-JOUATSA Bielefeld University 2 The model The set of voters is finite and denoted by N={1,· · · , n}. The set of alternatives or candidates or deterministic outcomes is also finite and denoted by A={a1,· · · , am}. Subsets of candidates will be denoted by A,B,· · ·. We assume that there are at least two voters (n≥2) and three candidates (m≥3). Each voter has a strict preference (complete, transitive, and antisymmetric) over the set of candidates. Denote by Lthe set of strict preferences over A. For all candidates x, y ∈A, and preference Ri∈L,xRiymeans that voter istricly prefers candidate xto candidate y, or x=y. If x6=yand xRiy, we simply write xPiy. For all i∈Nand Ri∈L, b(Ri)∈Adenotes the candidate ranked first by voter iaccording to Ri. Denote by LNthe set of profiles of preferences. For all candidates x, y ∈Adenote by Rx,y N the preference profile obtained from RNby permuting the positions of candidates xand y. For all profile of preferences RN= (R1,· · · , Rn)∈LN, i ∈N, and Qi∈L, (Qi, R−i) denotes the profile obtained from RNby replacing the i−th entry Riby Qi. For all l≤m, Ri∈L and A ⊆ A, minl(Ri,A) denotes, if it exists, the l−th worst candidate of Aaccording to Ri. A deterministic Social Choice Function (SCF) is represented with a map f:LN→A. It maps each profile of preferences over candidates RNto the election winner f(RN)∈A. Denote by F={f:LN→A}the set of all deterministic SCF on the same set of candidates A, and the same set of voters N. We now introduce the concept of Ambiguous Social Choice Function (ASCF). Let Ω be a finite set of states of nature. A function g: Ω →A is called social act. Denote by Gthe set of all social acts on the same set of states Ω and candidates A. For all candidates x, y ∈A, denote by gx,y the social act obtained from gby permuting the occurrences of candidates xand yin the expression of g. For all social act g∈ G,A(g) = {g(ω)|ω∈Ω}denotes the range of g. An ambiguous social choice function is represented with a map F:LN→ G. It maps each profile of preferences over candidates RN∈LNto a social act F(RN)∈ G. When election comes, each voter icasts his/her ballot Riand the social act F(RN) is selected. If the state ω∈Ω is realized, then the candidate F(RN)(ω), simply denoted F(RN, ω), is elected. Deterministic social choice functions are particular ASCFs where the set of states Ω is restricted to a single element. Example 1 A real-life example of ambiguous social choice function Karin (a researcher) submitted a research article to a peer-reviewed journal. The editor in charge suitably chooses a set of 4 (N={1,2,3,4}) reviewers to evaluate the paper. In addition to their report, each reviewer has to make a recommendation. Each can recommend accepting the paper (AP ), rejecting the paper (RP), or recommend revising and resubmitting page 5 Ghislain-H DEMEZE-JOUATSA Bielefeld University the paper (R&RS). After uploading their reports and recommendations, the decision is immediate if the reviewers have made the same recommendation. In the other case, the editor is asked if he or she is available to produce an additional report and make a decision (subjectively) within one week. (The editor is not allowed to make a decision that is worse or better for the researcher than each of the recommendations of reviewers: the editor can not reject (RP) or accept (AP ) the paper if none of the reviewers recommended it.) If the editor is available, then his/her recommendation will be the decisive one, and Karin receives all the reports. Otherwise, the decision is given by the worst recommendation of the reviewers. In the latter case Karin receives all the negative reports, but a lower number of positive reports. This review process can be modeled as an ambiguous social choice function with voters N= {1,2,3,4}, candidates A={AP, RP, R&RS}, and state space Ω = {al, anl, na}, where al means ”the editor is available and likes the paper”, anl means ”the editor is available and does not like the paper”, and na means that ”the editor is unavailable”. Each reviewer (voter) submits a ranking of preferences over the set A, even if the decision process uses only the best candidate (recommendation) of each voter. Given a profile of preferences of reviewers, the final decision is an act, as it depends on the availability of the editor and his/her preferences after he/she reads the paper, both unknown at the moment the reviewers submit their recommendations. Consider for instance a preference profile summarized by (R&RS, R&RS, AP, RP), in which reviewers 1 and 2 recommend revising and resubmitting, reviewer 3 recommends accepting, and reviewer 4 recommends rejecting the paper. At this profile, the paper is automatically rejected if the editor is not (immediately) available. But if he/she is (immediately) available and likes the paper, then the paper might be accepted. In this example, the role of the editor is not to break the ties, as he/she can recommend a revise and resubmit even if no reviewer recommended it. Example 2 A professorship position in a research center will be open in two years. To fulfill the position optimally (avoiding delay and reducing productivity uncertainty), the research center decided to immediately hire up to three 2-year-postdoctoral researchers and wishes to offer the professorship, after two years, to the most productive hired postdoctoral researcher. The productivity of a postdoctoral researcher will be measured with his number of publications and citations during those two years. This process of filling the professorship position can be modeled as an ambiguous social choice function. In this case, the set Aof candidates corresponds to the set of applicants, and the set of states of nature equals the whole set of possible productivity levels of applicants. Obviously, the underlying hiring mechanism does not select a candidate as the election winner, but an act: at the moment the members of the committee cast their ballots, they do not know the true state of the nature.6 6Similar hiring process has been used in Mannheim in order to fill a professorship position. page 6 Ghislain-H DEMEZE-JOUATSA Bielefeld University An ASCF is called unanimous if for all profile RN∈LNsuch that b(Ri) = b(Rj) for all i, j ∈N, the social act F(RN) is constant, and F(RN, ω) = b(R1) for all ω∈Ω. We now extend the definition of strategy-proofness to ASCFs. At election time, voters neither know the realized state of nature nor the distribution it will be issued from. We assume that voters are ambiguity averse and wish to maximize their worst expected outcomes. If two acts have the same worst outcome, then voters prefer the act with the greatest second-worst outcome, and so on. We have the following definition. Definition 1 (Extension of preferences) Let g, h ∈ G, i ∈N, and Ri∈L. We say that voter iwith preference Riprefers act gover act h(and we write gRih) if A(g)RiA(h) where for all A,B ⊆ A, we have A RiBif •min1(Ri,A)Pimin1(Ri,B)or • ∃k∈ {1,· · · ,|B|} | ∀l= 1,· · · , k−1,minl(Ri,A) = minl(Ri,B)and mink(Ri,A)Pimink(Ri,B) or • ∀l= 1,· · · ,|B|,minl(Ri,A) = minl(Ri,B)and |A| ≥ |B|. Both the strict part of the preference relation Ri∈Land its extension on the set Gof acts are denoted Pi. The preference relation Riis called lexicographic maxmin extension (lexmin) of the preference Ri. See Pattanaik and Peleg (1984) for an axiomatization of lexmin preferences. Example 3 lexmin extension of preferences in presence of three candidates. Assume that there are three candidates, x, y and z. For all subset A ⊆ Aof candidates, let gAbe an arbitrary act whose range is A. Let R=xyz ∈Lbe a preference such that x is the top-ranked candidate, yis the second-ranked candidate, and zis the worst candidate. Then the strict part Pof the lexicographic maxmin extention of the preference Ris such that g{x}P g{x,y}P g{y}P g{x,z}P g{x,y,z}P g{y,z}P g{z}. An ASCF Fis called manipulable if there exists RN∈LN, i ∈N, and Qi∈Lsuch that F(Qi, R−i)PiF(RN), and called strategyproof if it is not manipulable. An ASCF Fis called dictatorship if there exists a voter i∈Nsuch that for all profile RN∈LN, F(RN) is the constant act which takes the value b(Ri) in each state. Under the full preference domain condition (any ranking of acts is allowed), only the dictatorships are unanimous and strategyproof, see Gibbard (1973) and Satterthwaite (1975). We introduce a new class of unanimous and strategyproof mechanisms. Let Fbe an ASCF, and N0⊆N a subset of voters. The ASCF Fis called N0−top selection if for all profile RN∈LNof page 7 Ghislain-H DEMEZE-JOUATSA Bielefeld University ASCFs that satisfy those three requirements. Denote by Ω1⊆ F an arbitrary subset of F that contains deterministic unanimous and anonymous SCFs. The set Ω1could for instance be empty or contain the plurality or the Borda count with lexicographic tie break rule. Now let Ω = {f1,· · · , fn} ∪ Ω1where for all k∈ {1,· · · , n}and profile RN∈LN, fk(RN) = (mink(R0,{b(Ri), i ∈N})if k < |{b(Ri), i ∈N}| b(R0,{b(Ri), i ∈N})if not, where b(R0,{b(Ri), i ∈N})is the top-ranked candidate of the set {b(Ri), i ∈N}according to the lexicographic preference R0. The simple ASCF FΩis a top selection and therefore unanimous and strategyproof, see Theorem 1. As each f∈Ωis anonymous, we conclude that FΩis anonymous as well. Proposition 2 A simple Ambiguous Social Choice Function FΩis unanimous, strategyproof and anonymous if and only if FΩis a top selection with top voters N, and each f∈Ωis anonymous. Proof of Proposition 2.Let FΩbe a simple unanimous, strategyproof and anonymous ASCF. From Theorem 2,FΩis a top selection with top voters N. From Definition 2, it follows directly that each FΩis anonymous if and only if each f∈Ω is anonymous. Finally recall that top selections are unanimous and strategyproof. Definition 4 An ambiguous social choice function F:LN→ G is neutral if for all preference profile RN∈LN, act g∈ G, and candidates x, y ∈A, if F(RN) = g, then F(Rx,y N) = gx,y (4.1) Definition 4says that an ASCF Fis neutral if it treats candidates equally: if a profile of preferences Rx,y Nis obtained from a given one RNby permuting the positions of candidates xand y, then the act F(Rx,y N) selected under Fat the profile Rx,y Nis obtained from the act F(RN) by permuting the positions of xand y. Let F∗be the set of simple ASCFs defined as follows. For all neutral and anonymous deterministic aggregation process f:LN→L, let the family Ω(f) = {f1,· · · , fn}be the familly of deterministic SCFs such that for all k∈ {1,· · · , n}and all profile RN∈LN, fk(RN) = (mink(f(RN),{b(Ri), i ∈N}) if k < |{b(Ri), i ∈N}| b(f(RN),{b(Ri), i ∈N}) if not, page 14 Ghislain-H DEMEZE-JOUATSA Bielefeld University where b(f(RN),{b(Ri), i ∈N}) is the top-ranked candidate of the set {b(Ri), i ∈N}according to the preference f(RN). 7A simple ASCF Fbelongs to F∗if and only if there exists a deterministic neutral aggregation process fsuch that F=FΩ(f). Proposition 3 Any simple ambiguous social choice function F∈ F∗is unanimous, anonymous, neutral and strategyproof. Proof of Proposition 3.Let FΩ(f)∈ F∗. By construction, the range of the act FΩ(f)(RN) selected at a given profile RN∈LNis exactly the set of top ranked candidates {b(Ri), i ∈N}. That is FΩ(f)is a top selection. From Theorem 1, it follows that Fis unanimous and strategyproof. Furthermore, as fis anonymous, each fk, k ∈ {1,· · · , n}is anonymous. It follows from Proposition 2that FΩ(f)is anonymous. The neutrality of FΩ(f)follows from that of f. 5 Conclusion and discussion This paper analyzes unanimous and strategyproof ambiguous social choice functions. The main result, Theorem 1, tells that an ambiguous social choice function is unanimous and strategyproof if and only if it is a top selection. That is, there exists a subset N0of voters, called the set of top voters, such that at each preference profile, the range of the selected act coincides with the set of top-ranked candidates of top voters. We show that an ambiguous social choice function is unanimous, strategyproof, and anonymous if and only if it is a top selection with top voters N0=N, and each state of nature corresponds to a deterministic anonymous social choice function. See Theorem 2and Proposition 2. We also uncover a large class of ambiguous social choice functions that additionally satisfy the neutrality, see Proposition 3. In the analysis of this paper, we assume that all voters are ambiguity averse. In the case that Subjective Expected Utility (SEU) maximizers and ambiguity-averse voters co-exist, new unanimous and strategyproof mechanisms arise. As an illustration, consider an election with set of candidates A={a, b, c}, and voters N={1,2,3}. Assuming that voters 1 and 2 are ambiguity averse and voter 3 is a SEU maximizer, the ambiguous social choice function Fthat selects the most preferred act F(RN) of voter 3 within the set of acts with range {b(R1), b(R2)}is unanimous and strategyproof. A full characterization of the set of 7Given a profile of preferences RN∈LN, the ranking f(RN) could for instance be obtained using the Borda rule where ties are broken according to the preference R1of voter 1: candidates are ranked according to their Borda score, and if two or more candidates have the same score, they are ranked according to the preferences of voter 1. Such aggregation process is obviously anonymous and neutral. page 15 Ghislain-H DEMEZE-JOUATSA Bielefeld University unanimous and strategyproof ambiguous social choice functions in such cases remains to be found. As argued in the introduction, Bahel and Sprumont (2020) together with our findings show that in presence of SEU maximizers or ambiguity averse voters, any unanimous and strategyproof ambiguous social choice function is ex-post Pareto optimal: for all profile of preferences, the outcome of the selected act coincides with the best candidate of at least one voter in each state of nature. One might wonder if such property holds for other classes of preferences as the α−maxmin (Ghirardato et al. (2004)), or the smooth preference (Klibanoff et al. (2005)). The idea of ASCFs easily extends to Arrowian aggregation setup, see Arrow (2012). The natural extension of the Pareto efficiency and the Independence of Irrelevant Alternatives (IIA) properties to Ambiguous Aggregation Procedure (AAP) is such that an AAP Fthat transforms any arbitrary profile of preferences RN= (R1,· · · , Rn) into an act F(RN) whose outcomes Fω(RN) in each state ω∈Ω of nature is a ranking over the set of candidates, satisfies Pareto efficiency and the IIA properties if and only if each single aggregation process RN7→ Fω(RN) satisfies them, and additionally the unrestricted domain property. In the latter case, each aggregation process Fωmust be a dictatorship in the sense that there exists a player i(ω) such that for all profile of preferences RN, the outcome Fω(RN) of the act F(RN) in the state ωalways coincides with the preference Riof voter i(w), see Arrow (2012). This means that an AAP Fsatisfies the Pareto efficiency, and the IIA properties if and only if there exists a subset N0of voters, which we refer to as top voters, such that for all profile of preferences RN, the range of the act RNis exactly the set of preferences of top voters. Our method can be used to analyse the group-strategy-proofness of ASCFs.8In fact, our characterized mechanisms, the top selections, give no room for compromises. Voters, therefore, need to vote strategically if they have conflicting preferences, and wish to favor the selection of a compromise act. In particular, if there are at least two top voters (the set N0has more than one element), the coalition N0can jointly manipulate the election. A simple illustration is an election with three candidates (a, b, and c), where top voters have the same second-ranked candidate, candidate b, but do not have the same top-ranked candidate. In this case, sincere voting under the given top selection mechanism leads to the selection of an act with range {a, c}, while a strategic voting, for instance favoring the selection of the constant act b, might be profitable for each top voter. In the case that there 8See Barbera (1979), Green and Laffont (1979), and Bennett and Conn (1977) for examples of study of group-strategyproof of aggregation mechanisms. page 16 Ghislain-H DEMEZE-JOUATSA Bielefeld University is only one top voter, the top selection is a dictatorship and is not vulnerable to coalitional deviations. That is dictatorships are the only unanimous and group strategyproof ASCFs. Sufficient conditions provided by Barber`a et al. (2010), which guarantee the equivalence between group strategy-proofness and individual strategy-proofness, therefore do not hold in our setting. References Kenneth J Arrow. Social choice and individual values. Yale University Press, 2012. Eric Bahel and Yves Sprumont. Strategyproof choice of social acts. American Economic Review, 110(2): 596–627, 2020. Salvador Barbera. A note on group strategy-proof decision schemes. Econometrica, pages 637–640, 1979. Salvador Barber`a, Bhaskar Dutta, and Arunava Sen. Strategy-proof social choice correspondences. Journal of Economic Theory, 101(2): 374–394, 2001. Salvador Barber`a, Walter Bossert, and Prasanta K Pattanaik. Ranking sets of objects. In Handbook of utility theory, pages 893–977. Springer, 2004. Salvador Barber`a, Dolors Berga, and Bernardo Moreno. Individual versus group strategyproofness: When do they coincide? Journal of Economic Theory, 145(5): 1648–1674, 2010. Elaine Bennett and David Conn. The group incentive properties of mechanisms for the provision of public goods. Public Choice, 29(2): 95–102, 1977. Jean-Pierre Benoit. Strategic manipulation in voting games when lotteries and ties are permitted. Journal of Economic Theory, 102(2): 421–436, 2002. Florian Brandl, Felix Brandt, Manuel Eberl, and Christian Geist. Proving the incompatibility of efficiency and strategyproofness via smt solving. Journal of the ACM (JACM), 65(2): 1–28, 2018. Felix Brandt. Set-monotonicity implies kelly-strategyproofness. Social Choice and Welfare, 45(4): 793–804, 2015. Peter G¨ardenfors. Manipulation of social choice functions. Journal of Economic Theory, 13 (2): 217–228, 1976. page 17 Ghislain-H DEMEZE-JOUATSA Bielefeld University Paolo Ghirardato, Fabio Maccheroni, and Massimo Marinacci. Differentiating ambiguity and ambiguity attitude. Journal of Economic Theory, 118(2): 133–173, 2004. Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica, pages 587–601, 1973. Allan Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, pages 665–681, 1977. Itzhak Gilboa and David Schmeidler. Maxmin expected utility with a non-unique prior. Journal of Mathematical Economics, 18: 141–153, 1989. Jerry Green and Jean-Jacques Laffont. On coalition incentive compatibility. The Review of Economic Studies, 46(2): 243–254, 1979. Jerry S Kelly. Strategy-proofness and social choice functions without singlevaluedness. Econometrica, pages 439–446, 1977. Peter Klibanoff, Massimo Marinacci, and Sujoy Mukerji. A smooth model of decision making under ambiguity. Econometrica, 73(6): 1849–1892, 2005. Shasikanta Nandeibam. The structure of decision schemes with cardinal preferences. Review of Economic Design, 17(3):205–238, 2013. Prasanta K Pattanaik. On the stability of sincere voting situations. Journal of Economic Theory, 6(6):558–574, 1973. Prasanta K Pattanaik. Stability of sincere voting under some classes of non-binary group decision procedures. Journal of Economic Theory, 8(2):206–224, 1974. Prasanta K Pattanaik. Collective rationality and strategy-proofness of group decision rules. Theory and Decision, 7(3):191, 1976. Prasanta K Pattanaik and Bezalel Peleg. An axiomatic characterization of the lexicographic maximin extension of an ordering over a set to the power set. Social Choice and Welfare, 1(2): 113–122, 1984. Mark Allen Satterthwaite. Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2): 187–217, 1975. page 18 Ghislain-H DEMEZE-JOUATSA Bielefeld University Appendix A Properties of the lexmin extension of preferences In this section, we discuss some properties of the lexmin extension of preferences. We will use them later to prove Theorem 1. Proposition 4 The lexicographic maxmin extension of a preference relation Ri∈Lover the set Gof acts satisfies the following properties. P-1) Voter i(with preference Ri) is indifferent between two acts fand gif and only those acts have the same range. P-2) If the least preferred candidate bm(Ri)of voter i(with preference Ri) does not belong to the range of the act f, then voter istrictly prefers the act fto any act other act g whose range includes the candidate bm(Ri). P-3) Let A ⊆ A, x, y ∈Asuch that x, y 6∈ A. Then voter i(with preference Ri) strictly prefers an act with range A∪{x}to an act with range A∪{y}if and only if he/she strictly prefers candidate xover candidate y. P-4) If voter i(with preference Ri) strictly prefers an act fto a constant act x, then voter iweakly prefers any candidate ythat belongs to the range of the act fto the candidate x. P-5) If x6=b(Ri), then voter i(with preference Ri) weakly prefers any act fwith range {x, b(Ri)}to any other act gwhose range contains x. Furthermore, if the range of the act gcontains more than 2 candidates, then voter istrictly prefers the act fto the act g. P-6) Voter i(with preference Ri) weakly prefers any act with range A∪{b(Ri)}to any other act whose range contains A. The preference is strict if b(Ri)6∈ A. P-7) Let A ⊆ A, x, y ∈Asuch that x6=y. Let Ri∈Lsuch that b(Ri) = xand b2(Ri) = y. Then an act fwhose range includes Ais weakly preferred to a given act with range A∪{y}if and only if the range of the act fis either A∪{y}or A∪{x}or A∪{x, y}. P-8) Let A ⊆ A,B ⊆ A and x∈A. If voter i(with preference Ri) strictly prefers any candidate y∈ A to candidate x, then he/she strictly prefers any act with range Bto any act with range A∪{x}. page 19 Ghislain-H DEMEZE-JOUATSA Bielefeld University Properties stated in Proposition 4follow directly from the definition of the lexicographic maxmin extension of a preference relation. We therefore omit the proof. B Proof of the main result: case with 2 voters When there are only two voters, top selections are equivalent, according to the lexmin extension, to the class of dictatorships or bi-dictatorships social choice correspondences. In this case, Theorem 1is similar to the characterization result (Theorem 3.3) obtained by Barber`a et al. (2001). In their paper, the authors provide a characterization of unanimous and strategyproof social choice correspondences, assuming that preferences of voters over sets of alternatives are conditionally expected utility consistent. In this section, we adapt their method to the setting of this paper and obtain a proof of Theorem 1for the case n= 2. In the following, an element x∈Awill also refer to the constant act that has range {x}, and the set G∩Awill denote the set of all constant acts. We will need the following definition. Definition 5 Let RN∈LNbe a profile of preferences, and let g∈ G be an act. We say that the act gis achievable by voter igiven RN(or simply R−i) if there exists a preference Qi∈Lof voter isuch that F(Qi, R−i) = g. Lemma 1 Suppose that there are two voters (1 and 2). Let Fbe a unanimous and strategyproof ASCF. Then the set O2(R1) = {g∈ G ∩ A| ∃R2∈Lsuch that F(R1, R2) = g} of constant acts achievable by voter 2 given R1depends only on the best candidate b(R1)of voter 1. From the unanimity condition, the set of constant acts O2(R1) achievable by voter 2 given the preference R1of voter 1 is always nonempty, as it contains the constant act which is equal to the candidate ranked first by voter 1. Lemma 1says that O2(R1) depends only on the candidate b(R1) ranked first by voter 1. Proof of Lemma 1.Let R1, R0 1∈Lsuch that b(R1) = b(R0 1). Let aj=b(R1). Assume that there exists a constant act aksuch that ak∈ O2(R1)\O2(R0 1). Let R2∈Lbe a preference of voter 2 such that b(R2) = akand b2(R2) = aj. Notice that the lexicographic maxmin extension of the preferences relations R1, R0 1, R2to the set Gsatisfy •ajP1g P1akfor all acts g∈ G such that the range of gis {aj, ak}; •ajP0 1g P0 1akfor all acts g∈ G such that the range of gis {aj, ak}. page 20 Ghislain-H DEMEZE-JOUATSA Bielefeld University •akP2g P2ajP2hfor all acts g, h ∈ G such that the range of gis {aj, ak}and the range of his neither {aj}nor {ak}nor {aj, ak}. The constant act akhas to be selected by Fat the profile (R1, R2). If not voter 2 will profitably deviate from (R1, R2), as ak∈ O2(R1). As Fsatisfies the unanimity condition, we have aj∈ O2(R0 1). Furthermore, as Fis strategyproof, the range of the act F(R0 1, R2) must be either {aj, ak}or {aj}. (Recall that ak6∈ O2(R0 1).) In both cases, voter 1 manipulates at (R1, R2) by choosing R0 1. We conclude that such akcan not exist. That is O2(R1) = O2(R0 1). Lemma 2 Suppose that there are two voters (1 and 2). Let Fbe a unanimous and strategyproof ASCF, and R1∈L. Then |O2(R1)| ∈ {1, m}. This lemma says that given any preference R1∈Lof voter 1, either all constant acts are achievable by voter 2, or only one constant act is achievable by voter 2. Notice that the constant act m(R1) is always achievable by voter 2 at R1. This follows from the unanimity condition. Proof of Lemma 2.We proceed by contradiction. Let R1∈Lsuch that 1 <|O2(R1)|< m. Let aj=b(R1) and ak, al∈A\{aj}such that ak∈ O2(R1) and al6∈ O2(R1). If akP1al, then exchange the position of akand alin R1. This operation will not change the fact that ak∈ O2(R1) and al6∈ O2(R1) as from Lemma 1,O2(R1) depends only on b(R1). Let R2∈Lsuch that b(R2) = aland b2(R2) = ak. The lexicographic maxmin extension of the preferences relations R1, R2to the set Gsatisfy •alP1g P1akfor all acts g∈ G such that the range of gis {ak, al}. •alP2g P2akP2hfor all acts g, h ∈ G such that the range of gis {al, ak}and the range of his neither {al}nor {ak}nor {al, ak} As ak∈ O2(R1), the strategy-proofness of Fimplies that the range of F(R1, R2) must be either {al, ak}or {ak}. (Recall that al6∈ O2(R1).) In both cases, voter 1 can manipulate the elections at (R1, R2) by choosing any preference Q1∈Lsuch that b(Q1) = al. Lemma 3 Suppose that there are two voters (1 and 2). Let Fbe a unanimous and strategyproof ASCF. If there exists R1∈Lsuch that |O2(R1)|=m, then |O2(Q1)|=mfor all Q1∈L. page 21 Ghislain-H DEMEZE-JOUATSA Bielefeld University This lemma says that the number of constant acts achievable by voter 2 is the same for all preferences of voter 1. Either all constant acts are achievable by voter 2 at any given preference of voter 1, or only one constant act is achievable by voter 2 at any given preference of voter 1. Proof of Lemma 3.Assume that there exists R1, R0 1∈Lsuch that |O2(R0 1)|= 1 and |O2(R1)|=m. Then O2(R0 1) = {b(R0 1)}. Let aj=b(R1) and ak=b(R0 1). From Lemma 1, we have that aj6=ak. Let al∈A\{aj, ak}. If alP1ak, then exchange the positions of aland akin the ranking R1. This operation does not change the number of elements of O2(R1), see Lemma 1. Now let R2∈Lsuch that b(R2) = aland b2(R2) = ak. The lexicographic maxmin extension of the preferences relations R1, R2to the set Gsatisfy •akP1g P1alfor all acts g∈ G such that the range of gis {ak, al}. •alP2g P2akP2hfor all acts g, h ∈ G such that the range of gis {al, ak}and the range of his neither {al}nor {ak}nor {al, ak}. As |O2(R1)|=m, we have that the best act of voter 2 (with preference R2), al, is achievable by voter 2 at (R1, R2). Therefore F(R1, R2) = al. Furthermore, as the constant act b2(R2) = akbelongs to O2(R0 1), the range of the act selected at the profile (R0 1, R2) must be either {ak, al}or {ak}. Recall that al6∈ O2(R0 1). In each case, voter 1 can manipulate at (R1, R2) by choosing R0 1. This contradicts the fact that Fis strategyproof. Lemma 4 Suppose that there are two voters (1 and 2). Let Fbe a unanimous and strategyproof ASCF. If there exists a preference profile RN∈LNsuch that b(R1)6=b(R2)and that the constant act b(R1)is selected at the profile RN, then voter 1 is a dictator. Proof of Lemma 4.Assume that b(R1)6=b(R2) and that the constant act b(R1) is selected at the profile RN. Let QN∈LN. We show that the constant act b(Q1) is selected at the profile QN. As the constant act b(R1) is selected at the profile RN, both constant acts b(R1) and b(R2) are achievable by voter 1 if voter 2 chooses R2. From Lemma 2, all constant acts are achievable by voter 1 given that voter 2 chooses R2. And from Lemma 3, all constant acts are achievable by voter 1 given that voter 2 chooses Q2. The strategy-proofness of F implies that the best act of voter 1, b(Q1), is selected at QN. We conclude that voter 1 is a dictator. That is Fis a {1}−top selection. Lemma 5 Suppose that there are two voters (1 and 2). Let Fbe a unanimous and strategyproof ASCF, and RN= (R1, R2)∈LNbe a profile of preferences. Then the range of the act selected at RNis included in {b(R1), b(R2)}. page 22 Ghislain-H DEMEZE-JOUATSA Bielefeld University Proof of Lemma 5.Without loss of generality, we assume in this proof that Fis not a dictatorship. Let RN∈LN. We wish to show that the range of the act F(RN) is included in the set {b(R1), b(R2)}. As Fis strategyproof, we have that F(R1, R1)R1F(R1, R2)R1F(R2, R2). Therefore, if b(R1) = b(R2), then the act F(RN) is constant, and equals b(R1). This follows from Unanimity. In that case, the range of the act F(RN) is included in the set {b(R1), b(R2)}. From now we assume that b(R1)6=b(R2). •Let QNbe another arbitrary profile such that b(Q1)6=b(Q2). If F(QN) = b(Q1) or F(QN) = b(Q2), then Fis a dictatorship, see Lemma 4. This is a contradiction. Assume that there exists a candidate x∈Asuch that F(QN) = xwith x6∈ {b(Q1), b(Q2)}. Then from Lemma 2, all constant acts are achievable by voter 1 at the profile QN. The strategy-proofness of Ftherefore implies that F(QN) = b(Q1). This contradicts the fact that x6∈ {b(Q1), b(Q2)}. From now on, we assume that (H 1) whenever the two voters do not have the same top-ranked candidate, the range of the selected act has at least two elements. •Let x, y ∈Asuch that x6=b(R2) and y6=b(R1). Consider two preferences Q1, Q2∈L such that (b(Q1) = xand b2(Q1) = b(R2); b(Q2) = yand b2(Q2) = b(R1). As b1(R2) = b2(Q1)∈ O1(R2), the range of the act F(Q1, R2) must be either {x} or {b(R2)}or {x, b(R2)}. From (H 1), the latter range is neither {x}nor {b(R2)}. Therefore, the range of the act F(Q1, R2) is {x, b(R2)}. Similarly, the range of the act F(R1, Q2) is {b(R1), y}. This implies the following. (H 2) For all candidate x∈A, at least one act with range {b(R1), x}is achievable by voter 2 at (R1, R2), and at least one act with range {b(R2), x}is achievable by voter 1 at (R1, R2). •If the range of the act F(RN) is {b(R1), x}with x6=b(R2), then voter 2 will manipulate the election, as at least one act with the range {b(R1), b(R2)}is achievable by voter 2 at RN, and any act with range {b(R1), b(R2)}is strictly preferred by voter 2 (with preference R2) to any act with range {b(R1), x}. Similarly, the range of the act F(RN) can not be {x, b(R2)}with x6=b(R2). •Now we show that the range of the act F(RN) can not be {x, y}with x, y ∈A\{b(R1), b(R2)}. We proceed by contradiction. Suppose that the range of the act F(RN) is {x, y}with x, y ∈A\{b(R1), b(R2)}. Without loss of generality, suppose that x P1y. Consider page 23 Ghislain-H DEMEZE-JOUATSA Bielefeld University the range of the act F(R1, R2, R−1,2)is {b(Ri), i ∈N0} ∪ {b(R1)}, see Lemma 11. This contradicts the fact the range of the act F(R1, R2, R−1,2)is {b(Ri), i ∈N0} ∪ {b(R1), x}with x6∈ {b(Ri), i ∈N0}∪{b(R1), b(R2)}. Similarly, the range of the act F(RN)can not take the form {b(Ri), i ∈N0}∪{y, b(R2)}with y6∈ {b(Ri), i ∈N0}∪{b(R1), b(R2)}. Case 5 Now we show that the range of the act F(RN)can not be {b(Ri), i ∈N0}∪{x, y}with x, y 6∈ {b(Ri), i ∈N0} ∪ {b(R1), b(R2)}. We proceed by contradiction. Suppose that the range of the act F(RN)is {b(Ri), i ∈N0}∪{x, y}for some x, y 6∈ {b(Ri), i ∈N0}∪{b(R1), b(R2)}. Without loss of generality, suppose that x P1y. Consider a preference Q2∈Lsuch that b(Q2) = xand b2(Q2) = y. If an act with range {b(Ri), i ∈N0}∪{x}is achievable by voter 2 at RN(and therefore at (R1, Q2, R−1,2)), then at least one act with range {b(Ri), i ∈N0}∪{z} would be achievable by voter 2 at the profile RN, for all z∈A, see Lemma 10. In that case, the range of the act F(RN)is {b(Ri), i ∈N0} ∪ {b(R2)}. This is a contradiction. In the case that no act with range {b(Ri), i ∈N0}∪{x}is achievable by voter 2at RN, the range of the act F(R1, Q2, R−1,2)must be {b(Ri), i ∈N0}∪{x, y}, as at least one act with range {b(Ri), i ∈N0} ∪ {x, y}is achievable by voter 2 at (R1, Q2, R−1,2). But then voter 1 can profitably deviate (manipulate), by ranking candidate xfirst. This contradicts the strategyproofness of F. Case 6 Now we show that the range of the act F(RN)can not take the form {b(Ri), i ∈ N0}∪Awhere A∩{b(Ri), i ∈N0}=∅and ∅ 6=A 6⊆ {b(R1), b(R2)}. We proceed by contradiction. Without loss of generality, we suppose that |A| is minimal in the sense that there exists no profile R0 N∈LNsuch that the range of the act F(R0 N)contains more elements of A\{b(Ri), i ∈N0}than A. First observe that b(R1)6∈ A. If b(R1)∈ A, then b(R1)6∈ {b(Ri), i ∈N0}. Consider Q2∈L such that b(Q2) = b(R2)and b2(Q2) = b(R1). From Proposition 5, the range of the act F(R1, Q2, R−1,2)must either be {b(Ri), i ∈N0}∪{b(R1)}or {b(Ri), i ∈N0}∪{b(R1), b(R2)} or {b(Ri), i ∈N0} ∪ {b(R2)}. If the range of the act F(R1, Q2, R−1,2)is {b(Ri), i ∈N0} ∪ {b(R2)}or {b(Ri), i ∈N0} ∪ {b(R1), b(R2)}, then voter 2 can profitably deviate from RN by choosing Q2, as {b(Ri), i ∈N0}∪{b(R1)}is included in the range of the act F(RN). If the range of the act F(R1, Q2, R−1,2)is {b(Ri), i ∈N0}∪{b(R1)}, then the range of the act F(R1, R2, R−1,2)is {b(Ri), i ∈N0} ∪ {b(R1)}, see Lemma 11. This contradicts the fact that A 6⊆ {b(R1), b(R2)}. Write A={x1,· · · , xk}where x1P1x2· · · xk−1P1xkand let Q2∈Lbe such that bl(Q2) = xlfor all l∈ {1,· · · , k}and bm(Q2) = b(R1). The preference Q2is such that x Q2yfor all x∈ A and y∈ {b(Ri), i ∈N0}. It therefore follows that page 30 Ghislain-H DEMEZE-JOUATSA Bielefeld University (H 7) for all non empty B(A, voter 2 (with preference Q2) prefers any act with range {b(Ri), i ∈N0}∪B to any other act with range {b(Ri), i ∈N0}. The range of the act F(Q2, R−2)must be {b(Ri), i ∈N0}∪A. The latter holds for the following reasons. •If the range of the act F(Q2, R−2)is {b(Ri), i ∈N0}, then voter 2 will manipulate the election at the profile (Q2, R−2)by strategically announcing R2, see (H 7). •If the range of the act F(Q2, R−2)is {b(Ri), i ∈N0}∪{x}with x6∈ {b(Ri), i ∈N0} ∪ {b(R1)}, then from Lemma 10, at least one act with range {b(Ri), i ∈N0} ∪ {b(R2)} is achievable by voter 2 at (Q2, R−2). This implies that the range of the act F(RN)is {b(Ri), i ∈N0}∪{b(R2)}. This contradicts the fact that A 6⊆ {b(R1), b(R2)}. •Similarly as above, see Case 4and Case 5, the range of the act F(Q2, R−2)takes the form {b(Ri), i ∈N0}∪{x, y}with x, y 6∈ {b(Ri), i ∈N0}only if {x, y}={b(R1), b(Q2)}. This in turn is not possible as the act F(RN)would be strictly preferred by voter 2 (with preference Q2) to the act F(Q2, R−2), see Property P-2, contradicting the strategyproofness of F. •Obviously, any act with range {b(Ri), i ∈N0} ∪ A is strictly preferred by voter 2 ( with preference Q2) to any other act with range {b(Ri), i ∈N0}∪B, where B 6=A, B ∩ {b(Ri), i ∈N0}=∅and Yhas at least as many elements as A. Therefore, the range of the act F(Q2, R−2)must be {b(Ri), i ∈N0}∪A. But now voter 1 can manipulate the elections by strategically ranking candidate x1first, see Lemma 7. This is a contradiction. We conclude that the range of the act F(RN)is included in {b(Ri), i ∈N0}∪{b(R1), b(R2)}. Lemma 13 Let Fbe a unanimous and strategyproof ASCF such that F1,2is a N0∪{2}−top selection. Let RN∈LNbe a profile of preferences. Then the range of the act F(RN)contains at least one element of the set {b(R1), b(R2)}. Proof of Lemma 13.In this proof, the range of the act F(RN) selected at a given profile RNwill be denoted AF(RN). Let RN∈LN. a) If b(R1) = b(R2), then the range AF(RN) of the act F(RN) is exactly {b(Ri), i ∈N0} ∪ {b(R2)}, see Lemma 7. We therefore have that AF(RN)∩ {b(R1), b(R2)} 6=∅. b) If b(R1)∈ {b(Ri), i ∈N0}or b(R2)∈ {b(Ri), i ∈N0}, then AF(RN)∩ {b(R1), b(R2)} 6=∅, page 31 Ghislain-H DEMEZE-JOUATSA Bielefeld University see Lemma 8. c) If voter 2 (with preference R2) strictly prefers b(R1) to any candidate x∈ {b(Ri), i ∈N0}, then, as at least one act with range {b(Ri), i ∈N0}∪{b(R1)}is achievable by voter 2 at RN, see Lemma 7, the range of the act F(RN) is either {b(Ri), i ∈N0} ∪ {b(R1)}or {b(Ri), i ∈N0} ∪ {b(R2)}or {b(Ri), i ∈N0} ∪ {b(R1), b(R2)}, see Lemma 12. In each case we have AF(RN)∩ {b(R1), b(R2)} 6=∅. d) Now assume that b(R1)6=b(R2), b(R1), b(R2)6∈ {b(Ri), i ∈N0}, and that there exists x∈ {b(Ri), i ∈N0}such that voter 2 with preference R2strictly prefers xto b(R1). In this case, (H 8) voter 2 with preference R2strictly prefers any act with range {b(Ri), i ∈N0} to any act with range {b(Ri), i ∈N0}∪{b(R1), b(R2)}. From here we proceed by contradiction. Assume that (H 9) the range AF(RN) of the act F(RN) is {b(Ri), i ∈N0}and that b(R1), b(R2)6∈ AF(RN). The later assumption is without loss of generality, see Lemma 8and Lemma 12. Let Q1∈L such that b(Q1) = b(R1) and b2(Q1) = b(R2). d-1) The range of the act F(Q1, R−1) is {b(Ri), i ∈N0} ∪ {b(R1), b(R2)}. From Proposition 5, the range of the act F(Q1, R−1) is either {b(Ri), i ∈N0} ∪ {b(R1), b(R2)}or {b(Ri), i ∈N0} ∪ {b(R1)}or {b(Ri), i ∈N0} ∪ {b(R2)}. If the range of the act F(Q1, R−1) is {b(Ri), i ∈N0} ∪ {b(R2)}, then the range of the act F(RN) is {b(Ri), i ∈N0} ∪ {b(R2)}, see Lemma 11. This contradicts (H 9). If the range of the act F(Q1, R−1) is {b(Ri), i ∈ N0} ∪ {b(R1)}, then voter 1 will manipulate the election at RN, favoring the selection of the act F(Q1, R−1), see Property P-6. d-2) Let Q2∈Lbe such that b(Q2)∈ {b(Ri), i ∈N0}. Then the range of the act F(R1, Q2, R−1,2) is {b(Ri), i ∈N0}, as at least one act with range {b(Ri), i ∈N0}is achievable by voter 2 at (R1, Q2, R−1,2), see (H 9), and {b(Ri), i ∈N0}⊆AF(R1, Q2, R−1,2), see Lemma 8. From Lemma 12, the range of the act F(Q1, Q2, R−1,2) is included in {b(Ri), i ∈ N0} ∪ {b(Q1)}, and must contain {b(Ri), i ∈N0}, see Lemma 8. The latter range can not be {b(Ri), i ∈N0} ∪ {b(Q1)}, as voter 1 would profitably deviate from (R1, Q2, R−1,2) to (Q1, Q2, R−1,2), see Property P-6. Therefore, the range of the act F(Q1, Q2, R−1,2) is {b(Ri), i ∈N0}. But now voter 2 can profitably deviate from (Q1, R−1)=(Q1, R2, R−1,2) to (Q1, Q2, R−1,2),see (H 8). This contradicts the strategy-proofness of F. From Lemmata 11,12, and 13, it follows that for all profile of preferences R= (R3,· · · , Rn)∈ LN\{1,2}of voters {3,· · · , n}, there exists a nonempty subset NR⊆ {1,2}such that the range page 32 Ghislain-H DEMEZE-JOUATSA Bielefeld University of the act F(R1, R2, R) is {b(Ri), i ∈N0∪NR}for all R1, R2∈L. We have the following lemma. Lemma 14 Let Fbe a unanimous and strategyproof ASCF such that F1,2is a N0∪{2}−top selection, where |N0| ≥ 2. Let i, j ∈N0,R∈LN\{1,2}be a profile of preferences of voters of the block N\{1,2}such that {b(Rk), k ∈N0} 6=A. Let Qi∈Lbe a preference of voter i such that Qi=Rjand let Q= (Qi, R−i). Then NR=NQ. In Lemma 14, the profile Qis obtained from the profile Rbe replacing the entry Riof voter iby Rj. The lemma says that the set NRremains unchanged after such an operation. Proof of Lemma 14.We proceed by contradiction. Assume that NR6=NQ. We introduce an additional notation: for all A ⊆ Aand preference Ri∈L,w(A, Ri) denotes the least preferred candidate a∈ A with respect to Ri. We consider 3 cases. Case 7 NR={1}and NQ={2}. Let R1, R2∈Lsuch that b(R1) = w(A\{b(Ri), i ∈ N0\{i}}, Ri), and R2=Ri. As the range of the acts F(R1, R2, R)and F(R1, R2, Q)are respectively {b(Rk), k ∈N0}∪{b(R1)}and {b(Rk), k ∈N0}, voter ican profitably manipulate the election from (R1, R2, R)to (R1, R2, Q), see Property P-8. Case 8 NR={1}and NQ={1,2}. Let R1, R2∈Lsuch that R1=Riand b(R2) = w(A\{b(Rk), k ∈N0}, Qi). As the ranges of the acts F(R1, R2, R)and F(R1, R2, Q)are respectively {b(Rk), k ∈N0}and {b(Rk), k ∈N0}∪{b(R2)}, voter ican profitably manipulate the election from (R1, R2, Q)to (R1, R2, R), see Property P-8. Case 9 NR={1,2}and NQ={1}. Similarly as above, let R1, R2∈Lsuch that R1= Riand b(R2) = w(A\{b(Rk), k ∈N0}, Ri). As the ranges of the acts F(R1, R2, R)and F(R1, R2, Q)are respectively {b(Rk), k ∈N0}∪{b(R2)}and {b(Rk), k ∈N0}, voter ican profitably manipulate the election from (R1, R2, R)to (R1, R2, Q), see Property P-8. Any other possible scenario is equivalent to one of the three previous cases. Proof of Lemma 6.We show that NRis independent from Rwhenever {b(Ri), i ∈N0} 6= A. a) Let R= (R3,· · · , Rn)∈LN\{1,2}such that {b(Ri), i ∈N0} 6=A. Let j∈ {3,· · · , n}\N0, and Qj∈L. Let Q= (Qj, R−j). The reader can check that if NR6=NQ, then voter j can profitably manipulate the elections. This implies that the set NRis independent of the preference of any voter j∈ {3,· · · , n}\N0. page 33 Ghislain-H DEMEZE-JOUATSA Bielefeld University b) Assume that |N0|= 1, and write N0={i0}. Let R∈LN\{1,2}such that {b(Ri), i ∈N0} 6= A. Let Qi0∈L. Let Q= (Qi0, R−i0). We show by contradiction that NR=NQ. Assume that NR6=NQ. There is no loss to further assume that Qi0is obtained from Ri0by permuting two consecutive candidates. This implies that b(Ri0)6=bm(Qi0) and b(Qi0)6=bm(Ri0). •If NR={1}and NQ={2}. Let R1, R2∈Lsuch that b(R1) = bm(Ri0) and R2=Ri0. As the ranges of the acts F(R1, R2, R) and F(R1, R2, Q) are respectively {bm(Ri0), b(Ri0)}and {b(Ri0), b(Qi0)}, voter i0can manipulate the election from (R1, R2, R) to (R1, R2, Q), see Property P-2. •If NR={1}and NQ={1,2}. Let R1, R2∈Lsuch that R1=Ri0and b(R2) = bm(Qi0). As the ranges of the acts F(R1, R2, R) and F(R1, R2, Q) are respectively {b(Ri0)} and {b(Ri0), bm(Qi0), b(Qi0)}, voter i0can manipulate the election from (R1, R2, Q) to (R1, R2, R), see Property P-8. •If NR={1,2}and NQ={1}. Similarly as above, let R1, R2∈Lsuch that R1=Ri0 and b(R2) = bm(Ri0). As the ranges of the acts F(R1, R2, R) and F(R1, R2, Q) are respectively {b(Ri0), bm(Ri0)}and {b(Ri0), b(Qi0)}, voter i0can manipulate the election from (R1, R2, R) to (R1, R2, Q), see Property P-2. •Any other case is similar to one of the three cases above. c) Let R, Q ∈LN\{1,2}be two profiles such that {b(Ri), i ∈N0} 6=Aand {b(Qi), i ∈ N0} 6=A. We show that NR=NQ. Consider the profile Qobtained from the profile R by replacing each entry Riby Qifor all i∈ {3,· · · , n}\N0. From a) NR=NQ. From b) NQ=NQif |N0|= 1. In the case that |N0|>1, we have NR=N(Qi0,R−i0)=NQ, see Lemma 14. Therefore, NRis independent of Rwhenever {b(Ri), i ∈N0} 6=A. d) Let x, y, z ∈Abe 3 distinct candidates. Let R∈LN\{1,2}be such that b(Ri) = zfor all i∈ {3,· · · , n}. Let R1, R2∈Lsuch that b(R1) = xand b(R2) = y. From Lemmata 8,12, and 13, the range of the act F(R1, R2, R−1,2) must be either {x, z},{y, z}, or {x, y, z}. From c), we have the following: •if the range of the act F(R1, R2, R−1,2) is {x, z}, then Fis a N0∪ {1}−top selection; •if the range of the act F(R1, R2, R−1,2) is {y, z}, then Fis a N0∪ {2}−top selection; •if the range of the act F(R1, R2, R−1,2) is {x, y, z}, then Fis a N0∪{1,2}−top selection. This concludes the proof of Lemma 6. page 34