Local-global equivalence in voting models: A characterization and applications

Kumar, Ujjwal; Roy, Souvik; Sen, Arunava; Yadav, Sonal; Zeng, Huaxia Article Local-global equivalence in voting models: A characterization and applications Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Kumar, Ujjwal; Roy, Souvik; Sen, Arunava; Yadav, Sonal; Zeng, Huaxia (2021) : Local-global equivalence in voting models: A characterization and applications, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 16, Iss. 4, pp. 1195-1220, https://doi.org/10.3982/TE4177 This Version is available at: https://hdl.handle.net/10419/253524 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-nc/4.0/ Theoretical Economics 16 (2021), 1195–1220 1555-7561/20211195 Local-global equivalence in voting models: A characterization and applications Ujjwal Kumar Economic Research Unit, Indian Statistical Institute, Kolkata Souvik Roy Economic Research Unit, Indian Statistical Institute, Kolkata Arunava Sen Economics and Planning Unit, Indian Statistical Institute, New Delhi Sonal Yadav Department of Economics, Umeå University Huaxia Zeng School of Economics, Shanghai University of Finance and Economics and Key Laboratory of Mathematical Economics (SUFE), Ministry of Education The paper considers a voting model where each voter’s type is her preference. The type graph for a voter is a graph whose vertices are the possible types of the voter. Two vertices are connected by an edge in the graph if the associated types are “neighbors.” A social choice function is locally strategy-proof if no type of a voter can gain by misrepresentation to a type that is a neighbor of her true type. A social choice function is strategy-proof if no type of a voter can gain by misrepresentation to an arbitrary type. Local-global equivalence (LGE) is satisfied if local strategy-proofness implies strategy-proofness. The paper identifies a condition Ujjwal Kumar: [email protected] Souvik Roy: [email protected] Arunava Sen: [email protected] Sonal Yadav: [email protected] Huaxia Zeng: [email protected] We are grateful to Shurojit Chatterji, Debasis Mishra, Eyal Winter, and several referees for valuable comments and suggestions. We would also like to thank the participants of the 2015 IDGP workshop at Universitat Autònoma de Barcelona, the conferences on economic design at Bilgi University, Istanbul (2015), the University of York (2017), and Corvinus University, Budapest (2019), the meetings of the Society for Social Choice and Welfare at Lund University (2016) and Seoul National University (2018), and the 2019 Conference on Economic Design and Algorithms at the Higher School of Economics, St. Petersburg as well as seminar participants at the Stockholm School of Economics, the City University of Hong Kong, and Ashoka University for their helpful comments. Huaxia Zeng acknowledges that his work was supported by the National Natural Science Foundation of China (No. 71803116), the Program for Professor of Special Appointment (Eastern Scholar) at Shanghai Institutions of Higher Learning (No. 2019140015), and the Fundamental Research Funds for the Central Universities (No. 2018110153). Sonal Yadav gratefully acknowledges financial support from the Jan Wallander and Tom Hedelius Foundation. ©2021 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE4177 1196 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) on the graph that characterizes LGE. Our notion of “localness” is perfectly general. We use this feature of our model to identify notions of localness according to which various models of multidimensional voting satisfy LGE. Finally, we show that LGE for deterministic social choice functions does not imply LGE for random social choice functions. Keywords. Local incentive constraints, strategy-proofness, mechanism design, strategic voting. JEL classification. D71. 1. Introduction Mechanism design theory is concerned with models where agents have private information (called a type) that has to be elicited by the mechanism designer. The cornerstone of the theory is the collection of strategy-proofness constraints that ensure that agents do not have incentives to misreport their types (or manipulate). The standard assumption in the theory is that the proposed social choice function must be immune to all possible misreports of agents. There is, however, considerable experimental evidence that agents do not always lie in an optimal payoff-maximizing way. For instance, Fischbacher and Föllmi-Heusi (2013) conduct an experiment where agents are paid money on the basis of a report of a privately observed roll of a die. In their results, only 20 percent of the subjects lie optimally, 39 percent are fully honest, and the remaining lie partially. Agents often choose to lie credibly by misreporting only to types that are near or close to their true types. We consider a model where an agent of a particular type can only misreport to an arbitrary set of pre-specified local types. Our main contribution is a complete answer to the following question: under what circumstances is immunity to misreporting via a local type (local strategy-proofness) equivalent to immunity to misreporting via an arbitrary type (strategy-proofness)? The equivalence issue has important conceptual and practical implications.1If it is not satisfied, the mechanism designer can choose from a wider class of locally strategyproof social choice functions. It may enable her, in principle, to avoid negative results such as the Gibbard–Satterthwaite theorem (Gibbard (1973), Satterthwaite (1975)). Alternatively, suppose that the problem at hand satisfies equivalence. So as to verify that a social choice function is strategy-proof, it suffices to check that it is locally strategyproof. The latter is a simpler task because it involves checking fewer constraints. We consider a model where an agent’s type is a strict preference ordering over a finite set of alternatives. There are no monetary transfers. For convenience, we refer to this model as the voting model and refer to the agent as a voter, even though the model could apply to other settings such as matching. For our purpose, it is sufficient to restrict attention to the case of a single voter.2The set of possible preferences is called a domain.Anenvironment is an undirected graph whose vertices are preferences in the domain. The agent whose preference is specified by a particular vertex can only misreport to another preference (or vertex) if the two vertices are connected by an edge in 1They are also discussed extensively in Carroll (2012) and Sato (2013). 2Our results can easily be interpreted in the multi-voter setting. Theoretical Economics 16 (2021) Local-global equivalence 1197 the environment. The set of vertices connected by an edge to a vertex are its neighbors. A social choice function is locally strategy-proof if no type of the agent can gain by manipulating to a neighbor; it is strategy-proof if the agent cannot gain by manipulating to any vertex in the graph. An environment satisfies local-global equivalence (LGE) if local strategy-proofness implies strategy-proofness.3 Section 2of the paper contains some examples and observations that highlight the issues underlying LGE. It serves to motivate our main result in Section 3,Theorem1, which is a characterization of environments that satisfy LGE. Section 4contains a discussion of the computational complexity of Property Land its relationship with earlier results in the literature. Section 5applies Theorem 1to multidimensional voting environments. Finally, Section 6uses Theorem 1to construct an example of an environment where LGE holds but equivalence fails for random social choice functions. The LGE property depends on the existence of certain types of paths in the environment. For every pair of preferences Pand Pin the domain and alternative a,theremust exist a path from Pto Psatisfying a monotonicity property with respect to all alternatives that are ranked worse than aaccording to P. Specifically, the relative ranking of aand any alternative branked worse than aaccording to P, can change at most once along the path. We call this condition Property L. According to Theorem 1,PropertyLis both necessary and sufficient for LGE. One of the strengths of our approach is that our notion of neighbors in the definition of local strategy-proofness is perfectly general. The earlier literature (discussed below) used the Kemeny distance metric to define “localness.” Thus, two preferences are neighbors if there is a single pair of consecutively ranked alternatives that are switched between the two preferences. Preferences that are neighbors in this sense are referred to as being adjacent. A limitation of adjacency is that it excludes several multidimensional voting models that are of interest. In these models, an alternative is an m-tuple (m>1) and preferences are typically assumed to satisfy some form of separability. Consequently, it is not always possible to switch a consecutively ranked pair of alternatives without affecting the ranking of other alternatives. We consider two such domains— separable domains and multidimensional single-peaked domains—and propose natural notions of neighbors such that the resulting environments satisfy LGE. The question of local-global equivalence also arises naturally in the context of random social choice functions. We follow the standard approach of comparing lotteries via stochastic dominance (see Gibbard (1977)). Earlier results (again discussed below) suggest that environments that satisfy LGE for deterministic social choice functions also do so for random social choice functions. We use our characterization result for the deterministic case to show that this is not true generally. We construct an environment that satisfies Property Land, therefore, satisfies deterministic LGE. We also find a random social choice in the same environment that satisfies local strategy-proofness but violates strategy-proofness. 3The converse is, of course, always true. 1198 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) 1.1 Related literature Two important papers on LGE in voting models are Carroll (2012)andSato (2013). Both papers use the adjacency version of localness. Carroll (2012) considers random social choice functions and shows that specific preference domains, such as the set of all strict preferences, the set of all single-peaked preferences, and particular subsets of single-crossing preferences satisfy LGE. Sato (2013) provides a necessary condition and a stronger sufficiency condition for LGE in the context of deterministic social choice functions. Section 4.2 describes the relationship between Sato’s results and ours in greater detail. As already mentioned, there are two significant ways in which our main result extends and refines the earlier analysis. The first is that our notion of neighbors is completely general; the second is that we have a complete characterization. Both aspects of our result permit a wider range of applications than was earlier possible. Cho (2016) provides sufficient conditions for LGE with random social choice functions. The notion of neighbors is once again adjacency, but several notions of preference extensions to lotteries are considered. In particular, it shows that a stronger version of the sufficient condition proposed in Sato (2013) (see Property Uin Section 4.2) is sufficient for LGE if lotteries are compared via stochastic dominance. We show in Section 6that the condition that is necessary and sufficient for LGE with deterministic social choice functions (using adjacency as the notion of localness) is not sufficient for LGE with random social choice functions. There are several papers that investigate LGE in models where monetary transfers to agents are permitted and preferences are quasilinear in the usual sense (see, for instance, Carroll (2012), Archer and Kleinberg (2014), and Mishra et al. (2016)). Although the basic question is the same, the flavor of the analysis and the results in the two models are very different from each other. In a companion paper (Kumar et al. (2021)), we consider a multi-voter model and address the question, “Under what conditions on the environment is it the case that every locally strategy-proof social choice function that also satisfies the mild condition of unanimity4is also strategy-proof?” We show that a condition much weaker than Property Lis sufficient for LGE in this sense for both deterministic and random social choice functions. 2. The model Let A={a,b,}denote a finite set of alternatives with |A|≥2. Throughout the paper, we assume that there is a single voter. This assumption is without loss of generality as is soon apparent. Apreference Pis an antisymmetric, complete, and transitive binary relation over A, i.e., given a,b∈A,aPb is interpreted as ais strictly preferred to baccording to P.Let Pdenote the set of all preferences: the set Pis referred to as the universal domain.We refer to an arbitrary set D⊆Pas a domain. 4A deterministic social choice function satisfies unanimity if it always picks an alternative in a profile where it is first-ranked by all voters. In the case of a random social choice function such an alternative is picked with probability 1. Theoretical Economics 16 (2021) Local-global equivalence 1199 An environment is an (undirected) graph G= D,E. The set of vertices of the graph is a domain D. The set of edges is the set E.IfP,P∈Dand (P,P)∈E, the two preferences are said to be neighbors or are local. The notion of neighbors is perfectly general. One possible specification is that used by Carroll (2012)andSato (2013). Fix a pair of preferences P,P∈D. Two alternatives aand bin Aare reversed if aPb and bPa,orbPa and aPb.LetPP={{a,b}⊆A: aand bare reversed in Pand P}be the set of all reversed pairs of alternatives between Pand P.5Two preferences Pand Pare called adjacent if |PP|=1.6An environment where neighbors are defined by adjacency is referred to as an adjacency environment. Whenever the notion of neighbors is defined by adjacency, we denote the set of edges by Eadj. An adjacency environment typically is denoted by G=D,Eadj.InSection5,we provide an example of a nonadjacency environment. Definition 1. A social choice function (SCF) is a map f:D→A. Definition 2. Consider an environment G= D,E.AnSCFf:D→Ais locally manipulable at Pif there exists P∈Dwith (P,P)∈Esuch that f(P)Pf (P).TheSCFfis locally strategy-proof if it is not locally manipulable at any P∈D. Consider a graph or an environment. An SCF labels each vertex of the graph with an alternative. It is locally strategy-proof if the voter with a preference for a particular vertex cannot gain by misrepresenting her preference to a vertex that is a neighbor of her true preference. In contrast to local strategy-proofness, an SCF is strategy-proof if the voter cannot gain by an arbitrary misrepresentation. Definition 3. An SCF f:D→Ais manipulable at Pif there exists P∈Dsuch that f(P)Pf (P).TheSCFfis strategy-proof if it is not manipulable at any P∈D. A strategy-proof SCF is clearly locally strategy-proof. We investigate the structure of an environment when the converse is true. Definition 4. The environment G= D,Esatisfies local-global equivalence (LGE) if every locally strategy-proof SCF f:D→Ais strategy-proof. The next subsection makes some important observations regarding LGE. 2.1 Preliminary observations Our goal in this subsection is to illustrate the issues involved in LGE and to provide some intuition behind our result. We begin with some standard concepts from graph theory. 5We are guilty of abuse of notation here. Since a preference is an ordered pair, PPshould include both ordered pairs (a,b)and (b,a)if aand bare reversed in Pand P. In our notation, PPincludes only the unordered pair {a,b}in this case. 6An alternative and equivalent statement is that the Kemeny distance between Pand Pis exactly 1. 1200 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Table 1. Domain D. P1P2P3P4P5 c cccc [a][ b][ b][ b]a b aaa [b] z zzzz vvvuu wwuvv uuwww Let G=D,Ebe an environment. A path π=(P1,,Pt)is a sequence of distinct vertices in Dsatisfying the property that consecutive vertices are neighbors, i.e., (Pk,Pk+1)∈Efor all k=1, ,t−1.7Let (P,P)denote the set of all paths from P to Pin G. For any path π=(P1,,Ps,Ps+1,,Pt),weletπ|[Ps,Pt]denote the subpath (Ps,Ps+1,,Pt).WesayGis connected if there exists a path between every pair of vertices in G, i.e., (P,P)= ∅ for all P,P∈D. The example below highlights the reasons why LGE may fail. Example 1. Let A={a,b,c,z,u,v,w}. Consider the adjacency environment G= D,Eadj,whereD={P1,P2,P3,P4,P5}(Table 1). It is convenient to represent Gby Figure 1. The SCF f:D→Apicks aat P1and bat other preferences.8The SCF fis locally strategy-proof. However, it is not strategy-proof since the voter with preference P5can manipulate via P1.♦ The cause of the failure of strategy-proofness while maintaining local strategyproofness can be clearly identified from Example 1. Consider the path π=(P5,P4,P3, P2,P1). The outcome at P5is b. Since b“improves” at P4relative to P5, local strategyproofness implies that the outcome at P4must be b; otherwise the voter would manipulate locally to P5. Local strategy-proofness also implies that the outcomes at P3and P2must be b.Notethatb“declines” at P1with respect to a. There are two options at P1that are consistent with the requirement of local strategy-proofness (with respect to P1). The outcome can remain bor it can switch to a. In the former case, we maintain strategy-proofness since the outcome is beverywhere along the path π. However, if the outcome is a, a problem with strategy-proofness arises since ais preferred to bat P5. Figure 1. The environment G=D,Eadj.9 7In other words, repetitions of vertices in a path are ruled out. 8This is indicated by the square brackets on the alternative chosen by fat each preference. 9Two vertices are connected by an edge in Gif and only if the preferences represented by the vertices are adjacent. For instance, P1and P2are adjacent; in particular aP1band bP2a. The edge between P1and P2 Theoretical Economics 16 (2021) Local-global equivalence 1201 The failure of LGE in G= D,Eadjarises from an inherent asymmetry in the “monotonicity” requirement imposed by local strategy-proofness. If the outcome of an SCF at a preference improves10 relative to a local preference, the same outcome continues to be chosen at the new neighbor preference. However, if the outcome at a preference falls relative to a local preference, the new outcome can either remain the same or switch to an alternative that has improved (relative to the original outcome) in the new preference. Combining the latter option together with an improvement in the same path can lead to a failure of strategy-proofness without violating local strategy-proofness. A key feature of the path πin Example 1is that aand bswitch relative ranking more than once in the path. Thus, aP5b,bP4a,andaP1b. The preceding discussion makes it clear that such paths may be problematic for LGE. Definition 5. Let G= D,Ebe an environment and let a,b∈A.Apathπ= (P1,P2,,Pt)satisfies no {a,b}restoration if the relative ranking of aand bis reversed11 at most once along π, i.e., there do not exist integers q,r,andswith 1 ≤q<r< s≤tsuch that either (i) aPqb,bPraand aPsbor (ii) bPqa,aPrband bPsa.12 Let P,P∈Dand a,b∈Abe such that aPb. We say that bovertakes ain path π∈ (P,P)if bPlafor some preference Plin the path π. The notion of overtaking can be used to restate the definition of an {a,b}restoration in an obvious way. For instance, in case (i) of Definition 5,bovertakes ain the path π1=(Pq,,Pr)and aovertakes bin the path π2=(Pr,,Ps). It is sometimes useful to consider paths without restoration for a pair of alternatives. Let P,P∈Dand a,b∈Abe such that aPb.Letπ=(P1,P2,,Pt)∈(P,P)be a path without {a,b}restoration. If aPb, then aPrbfor all preferences Pron the path π. Suppose bPainstead. Then there exists a unique preference Pron πsuch that aPsbfor all s=1, ,rand bPsafor all s=r+1, ,t. To further clarify the relationship between the LGE property and paths without restoration, we make two modifications to Example 1. Example 2. As in Example 1,A={a,b,c,z,u,v,w}. We consider six additional preferences P0,P6,P7,P8,P9,P10 as shown in Table 2.LetDand D∗be the domains D=D∪{P0}and D∗=D∪{P6,P7,P8,P9,P10}. These domains are used to construct two adjacency environments G=D,Eadjand G∗=D∗,Eadj. These environments are shown in Figures 2and 3. Consider Gand a locally strategy-proof SCF ¯ f:D→Asuch that ¯ f(P5)=b. Using the same arguments as in Example 1,alongthepathπ=(P5,P4,P3,P2,P1), we can infer is labelled {a,b}so as to signify that the only “difference” between the two preferences is the ranking of a and b. 10We are intentionally informal in this description. These notions are made precise in due course. 11Recall that a pair of alternatives a,bis reversed in the pair of preferences Pand Pif they are ranked differently in Pand P. 12It is worth emphasizing that in our definition of {a,b}restoration, we are not referring to an ordered pair (a,b).Thus,{a,b}restoration and {b,a}restoration are the same in our definition. We use expressions such as “the path has no {a,b}restoration” and “the path has no restoration for the pair {a,b}” interchangeably. 1202 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Table 2. Preferences P0and P6,P7,P8,P9,P10. P0P6P7P8P9P10 c aaaa a a cccc c bbzzzb z zbbb z vuuvvv uvvuww w wwwu u that local strategy-proofness implies ¯ f(Pk)=bfor all k=5, 4, 3, 2 and ¯ f(P1)is either b or a. Due to the presence P0, there is now another path ¯π=(P5,P0,P1)from P5to P1. This path has no {a,b}restoration. Furthermore, the path ¯πhas the properties that (i) a and bare identically consecutively ranked, and (ii) calways ranks above a, while z,u,v, and ware all ranked below b. Clearly, bdoes not switch places with any other alternative along ¯π. As a result, local strategy-proofness forces the outcome of ¯ fto be beverywhere along ¯π, which rules out the manipulability of ¯ f. Now consider G∗and a locally strategy-proof SCF f∗:D∗→Asuch that f∗(P5)=b. Once again, local strategy-proofness along the path π=(P5,P4,P3,P2,P1)implies that f∗(Pk)=bfor all k=5, 4, 3, 2 and f∗(P1)is either bor a. Consider the path π∗=(P5,P6,P7,P8,P9,P10,P1). Observe that π∗has no restoration for aand any of the alternatives in the set Z={b,z,u,v,w}, which are all ranked below ain P5.Alternatives of Zswitch places among themselves along π∗(see, for example, the subpath (P6,P7,P8,P9,P10)). Consequently, the local strategy-proofness of f∗does not preclude the outcomes for preferences along π∗from belonging to Z. Suppose f∗(P1)=a. Since f∗(P5)=b, local strategy-proofness implies that some alternative in Zmust “jump above” aand then “jump below” a(so as to conform with P1)alongthepathπ∗.13 However, this is explicitly ruled out by the observation that π∗has no restoration for aand any of the alternatives in Z. Therefore, it must be the case that f∗(P1)=b.Infact, only two possibilities can arise: (i) f∗(Pk)=bfor all k=1, , 10 or (ii) f∗(Pk)=bfor all k=1, 2, 3, 4, 5, 6, 10 and f∗(Pk)=zfor all k=7, 8, 9. In either case, f∗is strategyproof. Figure 2. The environment G=D,Eadj. 13We can first easily rule out the possibility that cis chosen at some preference in the subpath (P6,P7,P8,P9,P10 ). In that case, local strategy-proofness forces the outcome of f∗to be ceverywhere in G∗. Theoretical Economics 16 (2021) Local-global equivalence 1209 now be used to construct an appropriate path from Pto P.Let ˜ Pbe the first vertex in the path ˜π(proceeding from Pto ¯ P) that also lies on ˆπ.Letπbethesequenceofvertices obtained by the concatenation of the subpaths ˜π|[P,˜ P]and ˆπ|[˜ P,P]. Clearly π∈(P,P). Since ˜πsatisfies no {a,b}restoration for all b∈L(a,P)and a=r1(¯ P), it follows that no alternative in L(a,P)overtakes ain ˜π|[P,˜ P], i.e., L(a,P)⊂L(a,˜ P).Thesubpathˆπsatisfies no {a,b}restoration for all b= a; therefore, the subpath ˆπ|[˜ P,P]satisfies no {a,b} restoration for all b∈L(a,P). We can summarize the argument thus far as follows. Pick an arbitrary b∈L(a,P)and consider the path π.IfaPb, then blies everywhere less preferred to aalong π.IfbPa, then bis less preferred to ain πuntil ˜ Pand overtakes aonce from ˜ Pto P.Inotherwords,πsatisfies no {a,b}restoration for all b∈L(a,P). In Section 5, we apply Property Lto various environments so as to show LGE. 4. Discussion We comment on some aspects of our results. 4.1 Computational complexity The problem of determining whether an environment satisfies Property Lis not computationally hard. The depth first search algorithm17 for efficiently traversing graphs can be modified easily to construct an algorithm that decides whether an environment satisfies Property L. The worst case time complexity of the algorithm is O(|A|2|D|(|D|+|E|)), which is polynomial in the parameters of the problem. The details of the argument can be found in Chatterjee (2020). 4.2 Relationship with earlier results Carroll (2012) proved that the the environments P,Eadjand DSP,Eadjsatisfy LGE.18 Both these environments satisfy a stronger version of Property Lthat we refer to as Property U. Property U. The environment G= D,Esatisfies the universal pairwise no-restoration property (Property U)ifforallP,P∈D, there exists a path in (P,P)that satisfies no restoration for all pairs {a,b}. Let π∈(P,P)be the path that satisfies no restoration for all pairs of alternatives as required by Property U.Thenπalso satisfies no {a,b}restoration for any a∈Aand b∈L(a,P). Clearly, Property Lis satisfied. Alternatively, Property Ldoes not imply Property U. To see this, consider the environment G∗in Example 2, which satisfies Property L.Forthepair(P1,P5), the clockwise path has {a,b}restoration while the counterclockwise path has {c,a}restoration. Clearly, Property Uis violated. 17See Cormen et al. (2001). 18Recall that Pis the set of all strict preferences. Also DSP is the domain of single-peaked preferences. A formal definition of single-peaked preferences can be found in Section 5. 1210 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Sato (2013) showed that Property Pbelow is necessary for LGE in adjacency environments. Property P. The environment G= D,Esatisfies the pairwise no-restoration property (Property P)ifforallP,P∈Dand a,b∈A, there exists a path in (P,P)that satisfies no {a,b}restoration. Example 3.2 in Sato (2013) shows that Property Pis not sufficient for LGE. The difficulty is that Property Pdoes not specify the relationship between the no-restoration paths for different pairs of alternatives: the path satisfying no restoration between Pand Pfor {a,b}could be distinct from the no-restoration path between the same vertices for another pair {c,d}.PropertyLis clearly a strengthening of Property P. Sato (2013) also introduced a sufficient condition for LGE in adjacency environments (we refer to this condition as Property Sfor convenience) that is weaker than Property U. Property S. Let G= D,Eadjbe an environment. Consider P,P∈D.Apathπ= (P1,P2,,Pt)∈(P,P)satisfies the antidote property with respect to the pair (P,P) if, for all pairs a,b∈Asuch that πis with {a,b}restoration and aP1b, then for each h∈{1, ,t}such that bPh−1aand aPhb, there exists a path π∈(P,Ph)along which a does not overtake any alternative. The environment Gsatisfies Property Sif, for every P,P∈D, there exists a path satisfying the antidote property with respect to (P,P). Environment G∗in Example 2violates Property S, which establishes that Property S is stronger than Property L. Consider the pair (P1,P5). As noted earlier, the clockwise path from P1to P5has {a,b}restoration since aP1b,bP4a,andaP5b. For it to satisfy the antidote property, ashould not overtake any alternative in the counterclockwise path from P1to P5. However, adoes overtake con this path. Property Lis nevertheless satisfied since there is no restoration with aand any of the alternatives ranked below ain P1 along this path. 5. Multidimensional voting:The separable domain and the multidimensional single-peaked domain In this section, we apply our results to a well known voting model. The set of alternatives has a Cartesian product structure, i.e., A=× j∈MAj,whereM={1, 2, ,m}is a finite set of components with m≥2. For each j∈M, the component set Ajcontains a finite number of elements with |Aj|≥2. For any j∈M,A−j=× i=jAi.Analternativea∈Ais an m-tuple a≡(a1,,am). We sometimes write ain the form (aj,a−j),whereaj∈Aj and a−j∈A−j. A preference Pis a linear order over A.Amarginal preference over component jis a linear order over Aj. Theoretical Economics 16 (2021) Local-global equivalence 1211 A preference Pis separable if, for all aj,bj∈Aj,c−j,d−j∈A−j,andj∈M, (aj,c−j)P(bj,c−j)implies (aj,d−j)P(bj,d−j). Thus, every separable preference Pinduces an m-tuple of marginal preferences (P1,,Pm).19 Let DSdenote the set of all separable preferences. Note that for every component jand any marginal preference Pj over the component set Aj,thereexistsP∈DSsuch that Pinduces the marginal preference Pjover Aj. There is a large literature on committee voting following Barberà et al. (1991), which assumes separable preferences. Another domain of preferences that we consider is that of multidimensional singlepeaked preferences introduced by Barberà et al. (1993). (See also Le Breton and Sen (1999).) This notion generalizes the well known class of single-peaked preferences (see Moulin (1980)). For this purpose, additional structure is introduced on each component set. Let ≺jdenote a linear order over Ajfor each j∈M.Agrid is an m-tuple (≺1,, ≺m).20 Let Pbe a preference over Awhose first-ranked alternative is x.ThenPis multidimensional single-peaked with respect to the grid (≺1,,≺m)if for all distinct a,b∈A,wehave[xjjaj≺jbjor bj≺jajjxjfor all j∈Mwith aj= bj]⇒[aPb].21 The domain DMSP contains preferences that are not separable (see Section 3 in Le Breton and Sen (1999)). However DS∩DMSP = ∅. To see this, pick an arbitrary m-tuple of marginal preferences (P1,,Pm), where each Pj,j∈M, is single-peaked with respect to ≺j.ConstructPas follows. For all distinct c,d∈Awith c= d,letjbe the integer in Msuch that cj= djand cr=drfor all r<j.ThencPd if and only if cjPjdj. It is easy to verify that P∈DS. We also claim P∈DMSP. Suppose xis the first-ranked alternative in P. Pick distinct alternatives a,b∈A. Clearly, aj= bjfor some j∈M. Assume further that xjjaj≺jbjor bj≺jajjxjfor all j∈Mwith aj= bj.Letk∈M be the lowest component such that ak= bk. By virtue of the single-peakedness of Pk, xkkak≺kbkor bk≺kakkxkimplies akPkbk.ThenaPb follows directly from the construction of P. We introduce a new notion of neighbors that applies to any domain that includes separable preferences. Let P,P∈DS. We say that Pand Pare separably adjacent (denoted by (P,P)∈ESA)ifthereexistj∈Mand aj,bj∈Ajsuch that [{x,y}∈PP]⇒ [xj=aj,yj=bjand xk=ykfor all k= j].Thus,Pand Pare separably adjacent if all pairs of alternatives that are reversed between Pand Pdiffer in the values of exactly 19The converse is not true however. Several preferences can induce the same tuple of marginal preferences. For instance, consider additively separable preferences. Preferences over each component jhave a utility representation uj:Aj→. Utility representations over Aare obtained by summing utilities over components. By considering different affine transformations of uj, one can obtain different preferences over Awithout changing marginal preferences. Details can be found in Le Breton and Sen (1999). 20A grid can be interpreted as a product of lines. The notion of multidimensional single-peakedness can be generalized on a product of trees where our result still holds. For notational convenience, let ajjbj denote either aj≺jbjor aj=bj. 21In the case where m=1, multidimensional single-peakedness reduces to single-peakedness. The definition of multidimensional single-peakedness is silent regarding the comparison of some alternatives. For instance, suppose m=2, ≺is the <ordering on real numbers, and A1=A2={0, 1}.Let (0, 0) be the highest-ranked alternative in the multidimensional single-peaked preference ¯ P.Wemusthave (0, 0)¯ P(1, 0),(0, 0)¯ P(0, 1),(0, 0)¯ P(1, 1),(1, 0)¯ P(1, 1), and (0, 1)¯ P(1, 1)by definition. 1212 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Table 3. Domains DSand DMSP. P1P2P3P4P5P6P7P8 (0, 0)( 0, 0)( 0, 1)( 0, 1)( 1, 0)( 1, 0)( 1, 1)( 1, 1) (0, 1)( 1, 0)( 0, 0)( 1, 1)( 0, 0)( 1, 1)( 0, 1)( 1, 0) (1, 0)( 0, 1)( 1, 1)( 0, 0)( 1, 1)( 0, 0)( 1, 0)( 0, 1) (1, 1)( 1, 1)( 1, 0)( 1, 0)( 0, 1)( 0, 1)( 0, 0)( 0, 0) one component.22 We emphasize that separable adjacency applies only to separable preferences. Separable adjacency does not cover the standard adjacency case. We, therefore, consider a strengthened version of separable adjacency: Pand Pare adjacent–separably adjacent (denoted by (P,P)∈EASA)23 if either (P,P)∈Eadj or (P,P)∈ESA holds. Two separable preferences Pand Pare neighbors in the ASA sense if one can be obtained from the other by a “minimal” change. Example 3. Let A=A1×A2with A1=A2={0, 1}. In the special case |Aj|=2forall j∈M,wehaveDS=DMSP, implying that the environments DS,EASAand DMSP,EASA are the same. Table 3lists the preferences in DSand DMSP. Note that the domain satisfies minimal richness. This environment is shown in Figure 4. The thicker lines in the figure show the environment DS,Eadj, i.e., Eadj ={(P1,P2),(P3,P4),(P5,P6),(P7,P8)}. The other edges inthefigurebelongtoESA.Notethat (P1,P2)/∈ESA since P1P2={{(0, 1),(1, 0)}}. Also P1P3={{(0, 0),(0, 1)},{(1, 0),(1, 1)}}. Observe that the set of alternatives that are reversed between P1and P3can be obtained by switching the value of component 2 from 0 to 1 at different values of component 1. Clearly (P1,P3)∈ESA. Alternatively, (P2,P4)/∈ESA since {(0, 0),(1, 1)}∈P2P4. We show later that the environment DMSP,EASAsatisfies Property L. Clearly, part (i) of Property Lis satisfied as indicated by the four thick edges in Figure 4.Nowconsider the preference P1and the alternative (1, 1), which is not first-ranked in P1.We Figure 4. DS,EASAand DMSP,EASA. 22Separably adjacency is based on a notion of Kemeny distance that applies to separable preferences. Two (separable) preferences are separably adjacent if they disagree on the relative ranking of two alternatives that differ in the values of exactly one component. Further analysis of separable adjacency can be found in Chatterji and Zeng (2019). 23The acronym ASA stands for adjacent–separably adjacent. Theoretical Economics 16 (2021) Local-global equivalence 1213 have (1, 1)first-ranked in preference P8and the path (P8,P7,P4,P3,P1)has no restoration for (1, 1)and any other alternative. Consequently, the requirement of part (ii) of Property Lis satisfied in this case. ♦ Example 3and Figure 4also lead to the conclusion that the environments DS,ESA, DMSP,ESA,DS,Eadj,andDMSP,Eadjfail LGE. The graphs in these environments are not connected, which can be verified by inspection and by our earlier remarks. According to the main result in this section, combining the adjacency and separable adjacency notions of neighbors with the separable and multidimensional single-peaked domains leads to LGE. Proposition 2. The environments DS,EASAand DMSP,EASAsatisfy LGE. The proof of Proposition 2can be found in the Appendix. 6. LGE and random social choice functions In this section, we examine LGE in the context of random social choice functions. Our result is that an environment that satisfies LGE for deterministic social choice functions may not satisfy LGE for random social choice functions. Let (A)denote the set of probability distributions over A.Anelementλ∈(A)is referred to as a lottery.Weletλadenote the probability with which a∈Ais selected by λ. Thus, 0 ≤λa≤1anda∈Aλa=1. Arandom social choice function (RSCF) is a map ϕ:D→(A)that associates a lottery ϕ(P)with each P∈D. For every P∈D,andk=1, 2, ,|A|,letrk(P)∈Adenote the kth ranked alternative in P, i.e., rk(P)=aimplies |{b∈A:bPa}|=k−1. The lottery λstochastically dominates (sd) lottery λat P∈D(denoted by λPsdλ)ift k=1λrk(P)≥t k=1λ rk(P)for all t=1, ,|A|. Let G= D,Ebe an environment. A RSCF ϕ:D→(A)is locally sd-strategyproof if ϕ(P)Psdϕ(P)for all (P,P)∈E.ARCSFϕ:D→(A)is sd-strategy-proof if ϕ(P)Psdϕ(P)for all P,P∈D. The environment G= D,Esatisfies random local-global equivalence (RLGE) if every locally sd-strategy-proof RSCF ϕ:D→(A)is also sd-strategy-proof. In the case where a RSCF is deterministic, local sd-strategy-proofness and sdstrategy-proofness reduce to local strategy-proofness and strategy-proofness, respectively. An immediate consequence of this observation is that an environment that satisfies RLGE also satisfies LGE. The results of Carroll (2012)andCho (2016) show that the converse is true for several special domains. The example below shows that LGE does not imply RLGE. Example 4. Let A={a,b,c,v,w,x,y,z}.Thedomain˜ Dis described in Table 4.The environment ˜ G=˜ D,EadjisshowninFigure5. By using arguments similar to those in Example 2, we can show that ˜ Gsatisfies Property L. Therefore, Theorem 1implies that ˜ Gsatisfies LGE. We construct a RSCF that satisfies local sd-strategyproofness but not sd-strategy-proofness. 1214 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Figure 5. The environment ˜ G=˜ D,Eadj. For any d∈A,weleteddenote the degenerate lottery that picks dwith probability 1. Consider the RSCF ϕ:˜ D→(A): ϕPk= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2ea+1 2ebif k∈{1, 10}, 1 2ea+1 4eb+1 4ecif k∈{2, 3, 4, 5}, 1 4ea+1 2eb+1 4ecif k∈{6, 7, 8, 9}. So as to verify the local sd-strategy-proofness of ϕ, it suffices to show that the voter cannot gain by manipulation in each of the following cases: (i) from P1to P2and vice versa, (ii) from P5to P6and vice versa, and (iii) from P9to P10 and vice versa. This can be verified easily in each of the cases. Consider (i), for instance. Observe that c locally overtakes bfrom P1to P2. Correspondingly, probability 1 4is transferred from bto c(keeping other probabilities fixed) as we move from ϕ(P1)to ϕ(P2). Therefore, ϕ(P2)P2 sdϕ(P1)and, symmetrically, ϕ(P1)P1 sdϕ(P2). The same argument can be made in cases (ii) and (iii). However, it is not the case that ϕ(P5)P5 sdϕ(P1)(in fact, ϕ(P1)P5 sdϕ(P5)). Consequently, ϕis not sd-strategy-proof. ♦ We make two observations about Example 4. Observation 1. As mentioned earlier, Carroll (2012)andCho (2016) have established the equivalence of local sd-strategy-proofness and sd-strategy-proofness in specific adjacency environments. These environments all satisfy Property U. The environment ˜ G in Example 4violates Property Usince both the clockwise and counterclockwise paths between P1and P5have restorations. Table 4. Domain ˜ D. P1P2P3P4P5P6P7P8P9P10 a aaaabbbb b b cccbaccc a cbbbccaaac v v wwwwwwv v wwvvvvvvww x xxxxxxxx x yyyzzzzyyy zzzyyyyzzz Theoretical Economics 16 (2021) Local-global equivalence 1215 Observation 2. The key feature of the example in Example 4that makes the LGE and RLGE results differ is that some lotteries under ϕhave support {a,b,c}, e.g., ϕ(Pk), k=2, , 9. However, no locally strategy-proof SCF can have a range that includes all three alternatives a,b,andc. To see this, let f:˜ D→Abe a locally strategy-proof SCF. Theorem 1implies that fis strategy-proof. Suppose {a,b,c}⊆Range(f)={d∈ A:f(P)=dfor some P∈˜ D}. Thus, there exists a preference where ftakes value a and another preference where ftakes value b. Strategy-proofness immediately implies f(Pk)=afor all 1 ≤k≤5andf(Pl)=bfor all 6 ≤l≤10. Hence, we have a contradiction. A characterization for RLGE appears to be significantly more difficult than that for LGE. In our companion paper Kumar et al. (2021), we derive a weak sufficient condition for RLGE in multi-voter models where RSCFs satisfy the additional property of unanimity. Appendix:Proof of Proposition 2 We begin by observing that both the separable domain DSand the multidimensional single-peaked (MSP) domain DMSP satisfy the minimal richness property. Applying Theorem 1and Proposition 1, it suffices to show that both domains satisfy Property L.Furthermore both domains satisfy part (i) of Property Las is shown in Appendices E.2 and E.5 of Chatterji and Zeng (2019). Therefore, we only verify part (ii) of Property L.24 We first investigate the separable domain DS. Next, we show part (ii) of Property L on the intersection of the separable domain and the multidimensional single-peaked domain DS∩DMSP, and then extend the result to the multidimensional single-peaked domain DMSP. In the proofs, we occasionally employ a special type of separable preferences called lexicographic separable preferences. Let (P1,,Pm)be an m-tuple of marginal preferences and let P0be strict order over the set M. The preference Pis lexicographically separable with respect to the (m+1)-tuple (P0,P1,Pm)if, for all a,b∈A, [ajPjbjand ar=brfor all rsuch that rP0j]⇒[aPb].Inotherwords,ais ranked strictly better than baccording to Pif ajis ranked higher than bjaccording to the marginal preference Pjand ar=brfor all components rthat are ranked strictly higher than jaccording to the component preference P0. We write a lexicographically separable preference Pas P≡(P0,P1,,Pm). We first prove two preliminary lemmas. Lemma 2. Let distinct P,P∈DSinduce the same marginal preferences. Then there exists a path from Pto Pin DS,Eadjsuch that there is no restoration for any pair of alternatives. This lemma follows from Fact 5 of Chatterji and Zeng (2019). 24Part (i) of Property Listhesameastheinterior +property of Chatterji and Zeng (2019). Hence, we can directly apply their result for this part. However, part (ii) of Property Lis stronger than their exterior+ property,sowehavetoshowthisindependently. 1216 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Lemma 3. Fix marginal preferences P1,,Pm.Letabe an alternative such that ajis not the first-ranked element in Pjfor some j∈M. For each component k, let Xk={xk∈Ak: xkPkak}∪{ak}.LetX=X1×···×Xm. Pick component jand let bj,cj∈Xjor bj,cj∈ Aj\Xjbe consecutively ranked elements in Pj. Then there exists a separable ordering ¯ P(j) that satisfies the properties (i) ¯ P(j)induces the marginal preferences P1,,Pm (ii) [x¯ P(j)a]⇒[for each k∈M,either xkPkakor xk=ak,i.e.,x∈X] (iii) (bj,z−j)and (cj,z−j)are consecutively ranked in ¯ P(j)for all z−j∈A−j. Proof. We construct a partition of the set A. To do so, define the sets A−j=× k=jAk, X−j=× k=jXk,Yj=Aj\Xj,andY−j=A−j\X−j.ThesetsX,B=Xj×Y−j,C=Yj× X−j,andD=Yj×Y−jconstitute a partition of the set A. The ordering ¯ P(j)is defined by two conditions: (a) We have that X¯ P(j)B¯ P(j)C¯ P(j)D, i.e., all alternatives in Xare ranked above those in B, which in turn are ranked above those in C, while all alternatives in Dare ranked below those in C. (b) Wehavethat ¯ P(j)over Xis lexicographically separable according to (P0(j),P1, ,Pm),wherejis ranked last in the component preference P0(j), i.e., given x,y∈ X,[xkPkykand xr=yrfor all rP0(j)k]⇒[x¯ P(j)y]. Similarly, ¯ P(j)is lexicographically separable over alternatives in B,C,andDrelative to (P0(j),P1,,Pm),respectively. Observe that akis the lowest-ranked element in Xkaccording to Pkfor all k∈M. Therefore, by construction, ais the worst alternative in Xaccording to ¯ P(j).AsXis the highest-ranked block according to ¯ P(j), it follows that all alternatives xthat are ranked higher than aaccording to ¯ P(j)must satisfy x∈X. This establishes part (ii) of Lemma 3. To show that ¯ P(j)is a separable preference and satisfies part (i) of Lemma 3,itsuffices to show that for an arbitrary pair of alternatives that disagree in exactly one component, say x=(xk,z−k)and y=(yk,z−k),wehave[(xk,z−k)¯ P(j)(yk,z−k)] ⇒[xkPkyk]. If xand yboth belong to one of the sets X,B,C,orD, the result follows immediately. Henceforth, assume that xand ybelong to two different sets of X,B,C,andD. Suppose k=j. We know that either z−j∈X−jor z−j∈Y−j.Ifz−j∈X−j,(xk, z−k)¯ P(j)(yk,z−k)implies x∈Xand y∈C. Similarly, if z−j∈Y−j,(xk,z−k)¯ P(j)(yk,z−k) implies x∈Band y∈D. Consequently, in both cases, xj∈Xjand yj∈Yj,and,hence, xjPjyj. Suppose k= j.Letz−jk denote the vector z−kwith its element of component j deleted. Since x¯ P(j)y,andxand yagree on component j, we know that either x∈Xand y∈Bor x∈Cand y∈D,bothofwhichimply(xk,z−jk)∈X−jand (yk,z−jk)∈Y−j. Since X−jis a Cartesian product set, (xk,z−jk)∈X−jimplies xk∈Xkand z−jk ∈× r=j,kXr. Last, since z−jk ∈× r=j,kXr,(yk,z−jk)/∈X−jimplies yk/∈Xk. Therefore, xkPkyk. Hence, ¯ P(j)is a separable preference and induces marginal preferences P1,,Pm. Theoretical Economics 16 (2021) Local-global equivalence 1217 Part (iii) of Lemma 3is an immediate consequence of the fact that ¯ P(j)over alternatives of Xand B, respectively, is lexicographically separable with respect to the component preference P0(j),wherecomponentjis ranked last. We now show that the separable domain DSsatisfies part (ii) of Property L. Proof of Proposition 2in the environment DS,EASA.ConsiderP∈DSand a∈ Asuch that ais not the first-ranked alternative in P.LetP 1,,P mbe the induced marginal preferences of P. Without loss of generality, assume that a1,a2,,ar,r≤ m, are not first-ranked in P 1,P 2,,P r, respectively, while av=r1(P v)for all v=r+ 1, ,m. We construct a sequence of preferences that are edges in DS,EASAwith the property that akeeps “rising” along the sequence. The sequence terminates in a preference P∈DS,whereais first-ranked. Then the reverse path from Pto Phas no {a,b} restoration for all b∈A\{a}, as required by part (ii) of Property L. We start from P 1.LetP1denote the set of all marginal preferences over A1.Picka marginal ordering P1such that a1is first-ranked. By Proposition 4.1 of Sato (2013), we have a path π1=(P1 1,,Pt 1)from P 1to P1in P1,Eadjwhich has no restoration for any pair of elements of A1.25 Since L(a1,P 1)⊂L(a1,P1),a1must keep rising along the path π1, i.e., L(a1,Pk 1)⊆L(a1,Pk+1 1)for all 1 ≤k<t. Therefore, for all 1 ≤k<t,ifa1is involved in the local switching elements across Pk 1and Pk+1 1,itistruethatx1Pk 1a1and a1Pk+1 1x1for some x1∈A1. For each k=1, ,t,letXk 1={x1∈A1:x1Pk ia1}∪{a1}. For each k=1, ,t−1, consider (Pk 1,Pk+1 1)and let Pk 1Pk+1 1={{bk 1,ck 1}}. Since L(a1,Pk 1)⊆L(a1,Pk+1 1), it must be the case that either bk 1,ck 1∈Xk 1or bk 1,ck 1∈A1\Xk 1. Next, for each k= 1, ,t, by Lemma 3,let ¯ Pk(1)∈DSbe such that (i) it induces the marginal preferences Pk 1,P 2,,P m, (ii) if x¯ Pk(1)a,thenforallj∈M,eitherxj=aj,orxjis strictly better than ajaccording to the jth marginal ordering of ¯ Pk(1), and (iii) (bk 1,z−1)and (ck 1,z−1)are consecutively ranked in ¯ Pk(1)for all z−1∈A−1.Letˆ Pk(1)be the ordering obtained by switching all alternatives of the type (bk 1,z−1)and (ck 1,z−1)for some z−1∈A−1. It is clear that ˆ Pk(1)is a separable preference with the same marginal preferences as ¯ Pk(1)for all components other than 1. For component 1, ck 1is now ranked immediately above bk 1, while the rankings of other elements are unchanged. Therefore, there are three properties of ˆ Pk(1)that are important: (a) (¯ Pk(1),ˆ Pk(1)) ∈ESA and ¯ Pk(1)ˆ Pk(1)={{(bk 1,z−1),(ck 1,z−1)}:z−1∈A−1};(b)L(a,¯ Pk(1)) ⊆L(a,ˆ Pk(1)),where the strict inclusion holds if and only if a1=ck 1;(c) ˆ Pk(1)and ¯ Pk+1(1)have the same marginal preferences, and L(a,ˆ Pk(1)) ⊆L(a,¯ Pk+1(1)) by part (ii) of Lemma 3in the construction of ¯ Pk+1(1). Now, we have a sequence P→¯ P1(1)→ˆ P1(1)→¯ P2(1)→···→ ¯ Pt−1(1)→ˆ Pt−1(1)→¯ Pt(1). 25For instance, we generate P1by moving a1directly to the top of P 1while keeping the rankings of other elements unchanged, and then construct the path from P 1to P1in P1,Eadjby progressively moving a1to the top of P 1. 1218 Kumar, Roy, Sen, Yadav, and Zeng Theoretical Economics 16 (2021) Note that ¯ Pt(1)has marginal preference P1,wherea1is the first-ranked element. Since Pand ¯ P1(1)have the same marginal preferences P 1,P 2,,P m, we know that either P=¯ P1(1)or there exists a path ¯π0from Pto ¯ P1(1)in DS,Eadjthat has no restoration for any pair of alternatives (by Lemma 2). Similarly, for all 1 ≤k<t, we know that either ˆ Pk(1)=¯ Pk+1(1)or there exists a path ¯πkfrom ˆ Pk(1)to ¯ Pk+1(1)in DS,Eadj that has no restoration for any pair of alternatives. Since (¯ Pk(1),ˆ Pk(1)) ∈ESA for all k=1, ,t−1, we construct a concatenated path ¯π=(¯π0,¯π1,,¯πt−1)from Pto ¯ Pt(1)in DS,EASA.26 Recall that L(a,P)⊆L(a,¯ P1(1)),L(a,¯ Pk(1)) ⊆L(a,ˆ Pk(1)),and L(a,ˆ Pk(1)) ⊆L(a,¯ Pk+1(1)) for all k=1, ,t−1. Then no restoration on subpaths ¯π0,¯π1,,¯πt−1implies that akeeps rising along the path ¯π. We can clearly repeat this procedure, progressively moving a1to the top in the marginal preference P1and then doing the same for a2until ar. The procedure generates a path in DS,EASAthat culminates in a preference P∈DS,whereais first-ranked. Moreover if aovertakes some xat some preference on the path, it beats xat all preferences further along the path. It follows immediately that the reverse path from Pto P satisfies no {a,b}restoration for all b∈A\{a}. This establishes part (ii) of Property L and, hence, proves Proposition 2for the separable domain DS. To show part (ii) of Property Lin the multidimensional single-peaked domain DMSP, we first consider the domain DS∩DMSP. We make several observations. First, DS∩DMSP satisfies part (i) of Property Lby Appendix E.4 of Chatterji and Zeng (2019). Second, Lemma 2remains valid in DS∩DMSP according to Fact 11 of Chatterji and Zeng (2019). Third, Lemma 3holds when we set the marginal preferences P1,,Pmto be singlepeaked with respect to ≺1,,≺m, respectively, and change preference ¯ P(j)to be both separable and multidimensional single-peaked. Finally, in the verification of part (ii) of Property Lin the separable domain, if we replace DSwith DS∩DMSP,replaceP1with S1, which is the set of all single-peaked marginal preferences with respect to ≺1,and replace the reference to Proposition 4.1 of Sato (2013) with a reference to Proposition 4.2 of Sato (2013), our earlier proof works for verifying part (ii) of Property Lin DS∩DMSP. Therefore, DS∩DMSP satisfies Property L. To extend the result to the multidimensional single-peaked domain, we use the following lemma, which follows from Lemma 8 of Chatterji and Zeng (2018). Lemma 4. Given distinct P,P∈DMSP, let r1(P)=r1(P). Then there exists a path from P to Pin DMSP,Eadjsuch that there is no restoration for any pair of alternatives. We now show part (ii) of Property Lin the multidimensional single-peaked domain DMSP. 26The concatenated path ¯πhas no repeated preference. Given two preferences ˆ Pand ˜ Pin ¯π,weknow that ˆ P∈¯πkand ˜ P∈¯πkfor some 0 ≤k,k≤t−1. If k=k, it is evident that ˆ P= ˜ Pby the definition of the path ¯πk. Next assume k<k .Notethatˆ Pk(1)and ¯ Pk+1(1)induce the same marginal preference Pk+1 1, and the path ¯πkconnecting ˆ Pk(1)and ¯ Pk+1(1)has no restoration for any pair of alternatives. Then ˜ P∈¯πk implies that ˜ Pinduces the marginal preference Pk+1 1. Symmetrically, ˆ Pinduces the marginal preference Pk+1 1, which is distinct from Pk+1 1. Therefore, ˆ Pand ˜ Pmust be distinct.