Topological Methods of Preference and Judgment Aggregation by Alexander M. Jakobsen MA, Economics, University of Calgary, 2009 BA, Economics, University of Calgary, 2007 BSc, Computer Science, University of Calgary, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Mathematics) The University Of British Columbia (Vancouver) June 2011 c Alexander M. Jakobsen, 2011 Abstract Arrow’s Impossibility Theorem is a classical result in social choice theory (a branch of economic theory), which states that any system of rules for combining (“aggregating”) individual preference relations into a single representative relation results in a “dictatorship” where the combined preference only reflects the wishes of a single individual (provided that the aggregation rule satisfies two basic criteria). Since the 1980s, this result has been reformulated and understood using algebraic topology. The topological approach offers some geometric intuition as to why Arrow’s theorem holds, and can also be used to find alternative hypotheses which may escape the dictatorship outcome. A thorough examination of such topological models constitutes the main body of this thesis. Recently, social choice theory has been generalized (resulting in a field called “judgment aggregation”), and results analogous to Arrows theorem have been established. The second part of this thesis introduces this field of study, and studies how some of the techniques from topological social choice theory can be extended to understand dictatorship outcomes in the theory of judgment aggregation. Although the analysis is restricted to a rather simple case, it nonetheless highlights the potential for a more general topological model of judgment aggregation, and exposes the main challenges that must be overcome in constructing such a theory. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Classical Social Choice Theory . . . . . . . . . . . . . . . . . . . . . 3 2.1 Arrow’s Impossibility Theorem . . . . . . . . . . . . . . . . . . . 4 Topological Social Choice Theory . . . . . . . . . . . . . . . . . . . 10 3.1 Continuous Social Choice . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 Chichilnisky and Heal (1983) . . . . . . . . . . . . . . . 12 Discrete Social Choice via Nerves . . . . . . . . . . . . . . . . . 17 3.2.1 Baryshnikov (1993) . . . . . . . . . . . . . . . . . . . . 18 Judgment Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . 29 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 3.2 4 iii List of Tables Table 4.1 The doctrinal paradox . . . . . . . . . . . . . . . . . . . . . . iv 30 List of Figures Figure 3.1 The nerve NP for n = 3. . . . . . . . . . . . . . . . . . . . . 20 Figure 4.1 The nerve NX for X = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}. . . . . . . 34 v Acknowledgments I would like to start by thanking my supervisor, Alejandro Adem, for all of his patience and support during my graduate studies in mathematics, and also for encouraging me to take up the topic of topological social choice theory for my thesis. It has been a pleasure to study problems in the (usually empty) intersection of algebraic topology and economic theory, and I am grateful that he granted me the freedom to do so. I also want to thank all of my new friends here in the UBC mathematics department. There are too many to name them all, but I would particularly like to thank Michele Klaus, Jose Gomez, and Cihan Okay, with whom I have had many helpful discussions. Last but not least, I would also like to thank my parents, Bent and Birte Jakobsen, as well as the rest of my (quickly growing!) family, for all of their support during my many years as a student. I am afraid I will require their patience and support in that regard for a while yet, as I will be taking up PhD study in economics this fall. It is comforting to know that wherever I am, my family is always with me! vi Chapter 1 Introduction This thesis studies various topological approaches to so-called aggregation problems in economic theory. We will be interested in two strands of aggregation theory: that of preferences, and that of “judgments”. The theory of preference aggregation is now a classic component of economic theory. It asks how individual preference relations (orderings) might be combined to give a single ordering which captures the overall wishes of the group of individuals. Of course, there are certain properties that one would like such an aggregation rule to have, and these will be discussed in detail. We also discuss some motivating examples of how this theory might be useful in practical situations (such as the design of voting systems), but will quickly encounter the famous Impossibility Theorem due to Kenneth Arrow. This is a rather negative result, as it states that any aggregation system satisfying two basic (and desirable) criteria will be “dictatorial”. The topological approaches to studying this result yield interesting insights as to why this dictatorship outcome holds true, and also offers a useful framework for identifying aggregation systems which are non-dictatorial. The other type of aggregation problem studied in this thesis is that of judgment aggregation. This is a relatively new branch of theory (having been formulated less than ten years ago), and is currently a very active area of research. In contrast to preference aggregation, judgment aggregation revolves around the problem of aggregating choices that individuals make. Specifically, there is some common set of alternatives, and each individual chooses some subset (subject to the constraint 1 that only some subsets are allowed). In this setting, the aggregation problem asks whether some particular subset can be taken to represent the overall choices of the individuals. This seemingly simple setup actually encompasses a large variety of situations, including that of preference aggregation (we will show that preference aggregation is a special case of judgment aggregation). As the name suggests, judgment aggregation problems were originally motivated by problems in the design of legal systems, and there is also much interplay between judgment aggregation models and the theory of formal systems and languages. We begin in section 2 by presenting the classic theory of preference aggregation (also called social choice theory), including a simple proof of Arrow’s Impossibility Theorem and a brief discussion of how this outcome can be avoided. Next, we present the “continuous” approach to social choice theory. This is a model of preference aggregation analogous to Arrow’s setup, but not formally equivalent. We will see that the problem of finding nice aggregation maps can be fully characterized in this setting using the tools of algebraic topology. Next, we present a topological approach to Arrow’s theorem; that is, we will give a valid proof of Arrow’s theorem by employing methods of algebraic topology. This approach is interesting in its own right, and also reveals useful geometric insights into the classic aggregation problem; insights which can be used to (correctly) formulate conjectures about ways to escape the dictatorship outcome. Finally, in chapter 4 we show how these techniques might be extended to the theory of judgment aggregation. Although we do not present a complete theory of topological judgment aggregation, the analysis we give is encouraging and seems to indicate that a fairly general theory is possible. It also provides some insight into how such a theory might look and what the relevant obstacles to its construction might be. 2 Chapter 2 Classical Social Choice Theory Suppose a group of k individuals must decide how to rank a (finite) number of alternatives. Each individual (which we will also refer to as an agent or a voter) has his or her own personal choice of how to rank the alternatives, and different individuals may have very different orderings. A central question of social choice theory (also called preference aggregation) is whether such individual rankings may be combined in a way which “reasonably” represents the overall wishes of the entire collection of agents. A classic example is that of voting systems, where the alternatives to be ranked are political candidates, and the agents are the general populace, each with their own preferences regarding the desirability of the different candidates running for office. This is the most commonly used example, but it is not ideal since usually the only relevant characteristic of an agent’s ordering is which candidate is ranked at the very top (that is, you vote for one candidate only; you do not necessarily submit your entire ordering of the candidates). One might also imagine a situation where a government has proposed a number of public projects, and wishes to ascertain how important the different projects are to the public. Once such a ranking has been achieved, the government can set about implementing the most desirable project. This differs from the voting example in that the government may face various constraints at different points in time. The purpose of gathering individual rankings (and formulating a “social ranking”) is to have a reasonable idea of what people want. Then, once uncer3 tainty has been resolved regarding, say, financial constraints, the government can set about implementing the most desirable project which is actually feasible (given the constraints), and this may or may not coincide with the highest-ranked project in the social ranking. Alternatively, a group of colleagues (graduate students, perhaps) might be collaborating on a series of projects (joint papers; homework assignments; etc), each of which requires their joint effort. They must decide the order in which to complete these projects, and each of them may have different preferences regarding the order. Can a “fair” ordering be achieved? 2.1 Arrow’s Impossibility Theorem To answer these sorts of questions, social choice theory begins by fixing a finite set X of alternatives (to be ranked) which, for convenience, we will often assume to be the set [n] = {1, . . . , n}. There is also a finite collection of k agents, each of which is represented by some preference relation % over X. Such relations are assumed to be complete (for all i, j ∈ X, at least one of i % j or j % i is satisfied) as well as transitive. The statement i % j should be interpreted as “alternative i is weakly preferred over alternative j”. If both i % j and j % i, we write i ∼ j and say that the agent is indifferent between i and j. Obviously ∼ is an equivalence relation on X. If it happens that i % j but not j % i, then the individual is said to strictly prefer i over j. Corresponding to every preference relation % is a strict part , where i j if and only if i is strictly prefered over j. We take R to be the entire collection of preference relations on X, and let P ⊂ R denote the set of strict preference relations (those without any indifferences; or equivalently, those preference relations which coincide with their strict part). Letting A be either R k or P k , we define a profile of preferences to be a k-tuple of preference relations belonging to A . Finally, a social choice function (also called an aggregation map) is a function f : A → R; that is, it is a rule which assigns to each k-tuple ~% = (%1 , . . . , %k ) of (arbitrary or strict, depending on A ) preference relations a social ranking (or aggregated preference) f (~%) ∈ R. For such a function, we call A the domain of preferences. There are various properties that one might want an aggregation map f to have, 4 one of which is the following: Definition 2.1.1 (Pareto Property). An aggregation map f : A → R satisfies the Pareto property (we also say f is Paretian) if for all x, y ∈ X and all profiles ~% = (%1 , . . . , %k ) ∈ A , we have that %:= f (~%) satisfies x y whenever x i y for every agent i. The Pareto criterion is one of the most basic properties we might expect a reasonable aggregation map to satisfy. It says that if every single agent strictly prefers an alternative x over another alternative y, then the social preference relation must also rank x strictly above y. It can be interpreted as an “agreement” property: if everyone agrees about the ranking between two alternatives, then there is no reason why the social ranking between those two alternatives should not satisfy each individual’s ranking. A slightly more controversial property is the following: Definition 2.1.2 (Independence of Irrelevant Alternatives). An aggregation map f : A → R satisfies the Independence of Irrelevant Alternatives (IIA) axiom if for 0 all x, y ∈ X and all profiles (%1 , . . . , %k ), (%0 , . . . , %0 ) ∈ A (denoted ~% and ~% , 1 I respectively), we have that %i |{x,y} = %0i |{x,y} for all i ⇒ % |{x,y} =%0 |{x,y} , 0 where %:= f (~%) and %0 := f (~% ). In words, this says that the social ranking between two alternatives x, y ∈ X should only depend on how these two alternatives (and not some other alternative 0 z) are ranked by the individuals. That is, if ~% and ~% are two profiles of preferences where no individual has changed their ranking of x and y, then the corresponding social rankings should rank x and y the same way. This seems harmless at first, but we will see that it is in fact quite a powerful axiom. One property which any desirable map f should not satisfy is the following: Definition 2.1.3 (Dictatorship). An aggregation map f : A → R is Dictatorial if there is an agent d such that for all x, y ∈ X and all preference profiles ~% = (%1 , . . . , %I ) ∈ A , we have that %:= f (~%) satisfies x y whenever x d y. (If this happens, agent d is the “dictator”). 5 A dictatorial map is one where the social ranking always agrees with the strict part of the dictator’s ranking. That is, agent d is free to submit any preference relation %d , but if (for any x, y ∈ X) x d y, then the corresponding social ranking will put x strictly above y as well, regardless of how all other agents rank x and y. This is obviously an undesirable property, since it conflicts with practically any sense of “fairness”: all other voters could have y x, but the social ranking will place x strictly above y as long as x d y. The only situation where other voters could (potentially) influence the social ranking of two alternatives is when the dictator is indifferent between those alternatives. At this point, it is worth asking whether this setup (that is, attempting to find non-dictatorial aggregation maps which are Paretian and satisfy IIA) is “reasonable”; does it successfully capture real situations? In the voting example above, the Paretian property is reasonable, but the IIA axiom seems unnecessary since, as we have mentioned, the only issue of relevance in most voting systems is who each individual’s “most preferred” candidate is. However, the other two examples do seem to warrant both the Pareto and IIA axioms. There is also the issue of transitive preferences: it is well documented in psychology and experimental economics that, in various situations, individuals may exhibit preferences which fail to be transitive. Yet, there are also many situations where transitive preferences do make sense (including all three examples at the start of this section). There are other potential shortcomings as well which we do not discuss here. The purpose of this discussion, however, is to point out that an economic model differs from a purely mathematical model in that it consists of a formal model together with an interpretation. As we have seen, any formal model permits several interpretations, some of which may or may not raise doubts about basic assumptions in the formal model. Thus, the “reasonableness” of a theoretical model cannot be evaluated by examining only its formal properties, nor by examining its properties in the context of any single interpretation. No model will ever be completely reasonable in each of its conceivable interpretations; we will be content knowing that there are, at least, many interesting situations where this model is quite reasonable, and focus our attention on the formal properties. Of these, the most famous is the following theorem due to Arrow [1]: 6 Theorem 2.1.1 (Arrow’s Impossibility Theorem). Suppose |X| ≥ 3 and A ∈ {R k , P k }. If f : A → R is Paretian and satisfies the IIA condition, then f is dictatorial. Most proofs of Arrow’s theorem are rather long and complicated (the topological proof we present in section 3.2 is no exception). There is, however, a fairly brief proof given by Geanakoplos [6], which we now present. Lemma 2.1.2 (Geanakoplos, “Extremal Lemma”). Let b ∈ X. Suppose ~% is a profile where, for each i = 1, . . . , k, %i either has b at the very top (meaning b i x for every b 6= x ∈ X) or at the very bottom (x i b for every b 6= x ∈ X). Then %:= f (~%) also ranks b at the very top or the very bottom. Proof. Suppose (toward a contradiction) that there are distinct a, b, c ∈ X and that 0 % satisfies a % b % c. We modify ~% to give a profile ~% by making the following changes to each individual profile %i : • if b i c i a, make no changes; • if b i a i c or b i c ∼i a, move c so that b 0i c 0i a; • if a i c i b or a ∼i c i b, move c so that c 0i a 0i b. 0 0 Notice that ~%|{a,b} = ~% |{a,b} and ~%|{b,c} = ~% |{b,c} (that is, no agents change their 0 rankings between a and b, or between b and c). So, by IIA, %0 := f (~% ) also satisfies a %0 b %0 c (hence a %0 c). However, each order %0i has c 0i a, so that the Pareto property gives c 0 a, a contradiction. Proof of Arrow’s Theorem (Geanakoplos). The proof is given in three steps. Step 1. Let b ∈ X. We claim there is a voter d ∗ = d(b) who, for some profile ~% where f (~%) ranks b at the very bottom, can change his preference (yielding a 0 0 modified profile ~% ) so that f (~% ) ranks b at the very top. To see this, let ~% be a profile where every voter has b at the very bottom of their ranking. By the Pareto property, %:= f (~%) ranks b at the very bottom as well. Now let individual voters successively move b from the bottom to the top, leaving other relative rankings unchanged. Let d ∗ be the first agent for which the corresponding social ranking of b changes (such an agent exists because if all agents have b at the very top, 7 1 then so does the corresponding social ranking). Let ~% denote the profile where 2 agents 1, . . . , d ∗ − 1 have moved b to the top, and let ~% be the profile where agents 2 1, . . . , d ∗ have moved b to the top. By the lemma, %2 := f (~% ) ranks b at the very top. Step 2. Agent d ∗ = d(b) is a dictator over any pair {a, c} with a 6= b 6= c. 3 2 To see this, define ~% from ~% by having d ∗ move a above b (thus voter d ∗ now ranks a at the very top, so that a 3d ∗ b 3d ∗ c), and let the other voters arrange their relative rankings of a and c arbitrarily (but leaving b in its extreme position). The 3 1 1 individual rankings of a and b in ~% agree with those in ~% , and ~% ranks b at the very bottom, so we have a 3 b. The individual rankings of b and c agree with 2 those in ~% , we also have b 3 c. Thus a 3 c. Since we chose a arbitrarily from {a, c} (that is, we could perform the same procedure above with c in place of a), this proves the claim. Step 3. We prove d ∗ is a dictator over every pair {a, b} (hence d ∗ is a dictator in the usual sense). Take some c ∈ / {a, b}, and place c at the bottom of each social ranking (just as in Step 1). Applying Step 2 to this case, we see that there is a voter d(c) who is a dictator over any pair {x, y} with c ∈ / {x, y}. In particular, {a, b} is such a pair. Since d ∗ is a dictator for {a, b}, and since dictators must obviously be unique, this proves that d(c) = d ∗ ; that is, d ∗ is a dictator. Arrow’s theorem is a rather negative result, especially because the hypotheses of the theorem are quite basic and could easily apply to many different situations. Moreover, it is not obvious which requirements should be changed to allow nondictatorial aggregation maps. The Pareto property is clearly quite desirable, and the IIA axiom is also quite natural. Another alternative, and the one which has received the most attention in the literature, is to restrict the domain A of possible preferences. A suitable restriction is found by considering singe-peaked preferences, which we now describe. Given a set [n] = {1, . . . , n} of alternatives, fix a linear order ≥ on [n] (this means ≥ is reflexive, transitive, and complete; we also let > denote the strict part of the relation). A preference relation % on [n] is said to be single-peaked with respect to ≥ if there is an x ∈ [n] so that for all y, z ∈ [n], x ≥ z > y ⇒ z y and y > z ≥ x ⇒ z y. The idea is that if we line up the alternatives in [n] according 8 to the order ≥, then the preference relation has some maximal element x ∈ [n] so that % is “increasing” as we approach x from either side. For example, suppose n = 3 and that ≥ is the strict order 1 > 2 > 3. The set P≥ of strict preference relations which are single-peaked with respect to ≥ must satisfy either 1 2 3, 1 ≺ 2 3, or 1 ≺ 2 ≺ 3. The second form does not put any restrictions on the relative rankings of 1 and 3, so that both 2 3 1 and 2 1 3 qualify. Thus P≥ = {1 2 3, 2 3 1, 2 1 3, 3 2 1}. Interestingly, single-peaked domains do escape the dictatorship result. In fact, if k is odd and preferences are strict, pairwise majority voting gives the desired aggregation map. We do not prove these results here, but remark that, at first glance, there is no obvious reason why single-peaked domains are a suitable restriction for escaping Arrow’s theorem. Indeed, the condition might seem somewhat random or miraculous. We will see in section 3.2, however, that the topological approach to Arrow’s theorem provides appropriate geometric intuition to anticipate singlepeaked domains quite easily. 9 Chapter 3 Topological Social Choice Theory At first glance, social choice theory does not appear to have any connection to topology whatsoever. Indeed, the central ingredients of the theory are quite primitive. Thus far, we have only encountered “combinatorial” arguments in the theory, in that all proofs are given from first principles without any need to introduce more advanced mathematical concepts, let alone the formidable tools of algebraic topology. How is algebraic topology able to help us understand problems of social choice? One possibility is to alter the classical model -that is, to investigate slightly different aggregation problems- so that the model may be more readily susceptible to a topological analysis. Initiated by Chichilnisky [3], this so-called “continuous social choice” model was in fact the first approach taken to understanding results such as Arrow’s Impossibility Theorem in a topological framework, and it has received the most attention in the literature. In section 3.1, we present the main results of this theory, due to Chichilnisky and Heal [4] (an extended version of Chichilnisky’s 1980 paper). One may well wonder if the classical theory can be understood in a topological setting without modifying the aims of the original model. Can Arrow’s theorem, as originally stated, be understood through topological means? As we shall see, a discrete form of Arrow’s theorem (that is, one in which the choice space X is finite) permits a very natural and interesting topological formulation. A hint as to why this is so is the IIA assumption, which can be interpreted as a sort of “sta10 bility” condition: if one does not modify a profile of preferences “too much” (in that the individual rankings of some pair are unchanged in the profile), then the resulting social preference will not change the ranking of that pair. This suggests that the aggregation map f may be continuous in some topology. Indeed, section 3.2 presents a remarkable paper by Baryshnikov [2], where the IIA axiom is exploited to construct a nontrivial topological space (via nerves) to represent agent preferences, transform f to a continuous map, and examine issues of social choice. Hence, we will have faithfully formulated the classical problem in a useful topological setting. It is Baryshnikov’s technique that we will extend in chapter 4 to the theory of judgment aggregation. 3.1 Continuous Social Choice To understand the setup for the continuous social choice model, it is necessary to introduce some ideas and terminology from microeconomic theory. Given a rational preference relation % on a set X, a utility function is a map u : X → R such that for all x, y ∈ X, u(x) ≥ u(y) ⇔ x % y; that is, it is an order-preserving embedding of (X, %) in the reals. The level sets of u, given by {x ∈ X | u(x) = c} for all choices of c ∈ u(X), are called indifference curves. It is easy to see that if I ⊆ X is an indifference curve, then x ∼ y for all x, y ∈ I, so that the collection of indifference curves inherits a strict linear ordering from %. Of course, any given relation % has infinitely many utility representations (simply compose u with any strictly increasing function f : R → R to form a new utility function). It is common in microeconomic theory to consider the choice space X to be some subset of Rn (often the positive orthant), with the interpretation that each axis measures the quantity of some particular good. Under various technical assumptions which we will not discuss here, a utility function u can then be realized as a continuously differentiable function. Chichilnisky and Heal [4] begin by noting that if the gradient ∇(u) of a utility function u : X → R does not vanish on X, then the relation which % represents may be characterized by normalizing ∇(u(x)) to length 1 at every point x ∈ X. Since u is a real-valued utility function, the gradient ∇(u(x)) indicates the “most preferred” direction at a point x ∈ X; however, we are interested only in the ordinal properties 11 of u (that is, the ordering % which u represents), so that by normalizing to length 1 we are ignoring information about the “intensity” of preferences. Obviously a nowhere-vanishing gradient is required to carry out this construction; this means the function u must have no critical points, which (interpreting the underlying economic framework) means there is no satiation (so “more is always better”). For convenience, we take the choice space X to be the closed unit ball in Rn , for some choice of n. Let V (X) denote the space of all C1 vector fields on X, equipped with the C1 topology. Motivated by the above discussion, we define a preference to be a map p : X → Rn such that for every x ∈ X, ||p(x)|| = 1 and there exists a real-valued utility function u : X → R so that p(x) is locally the gradient of u.1 Our objective is to examine problems of social choice for various collections P of such preferences (viewed as subspaces of V (X)). Given a space P ⊆ V (X) of preferences and a collection of k individuals, a social choice rule is a map φ : P k → P. If φ (p1 , . . . , pk ) = φ (pσ (1) , . . . , pσ (k) ) for every permutation σ of the agents, φ is said to be anonymous. If φ (p, . . . , p) = p for every p ∈ P, then φ is unanimous. Note that unanimity is weaker than the Pareto criterion. Of course, φ is required to be continuous. 3.1.1 Chichilnisky and Heal (1983) In this section, we present the main results of Chichilnisky and Heal [4]. In particular, we give a complete characterization of the continuous topological choice problem for the case where P is a CW complex of finite-type.2 Theorem 3.1.1 (C.H. Theorem 1). Suppose P (as a subspace of V (X)) is a connected CW complex of finite type. Then there exists a continuous, unanimous, and anonymous social choice rule φ : P k → P for every k ≥ 2 if and only if P is contractible. Proof. (⇐). If P is contractible, then each homotopy group πi (P) is trivial. We may therefore extend the identity map i : P → P to a map r : V (X) → P by results 1 That is, p is a continuously differentiable, locally integrable vector field. Note that p(x) is not, strictly speaking, equal to the gradient ∇(u(x)) (since we normalize ||p(x)|| = 1), but p(x) is assumed to be in the direction of ∇(u(x)). 2 By this, we mean a CW complex with a finite number of cells in each dimension. Such CW complexes are sometimes called parafinite in the topological social choice literature. 12 of obstruction theory (see, for example, section 8.4 of Spanier [8]). This means r is a retract of V (X) onto P. Let f : P k → V (X) be given by f (p1 , . . . , pk ) = 1k ∑ki=1 pi (this is well-defined because V (X), the space of all vector fields on X, is convex). Define φ : P k → P by φ = r ◦ f . Then, if p ∈ P, we have φ (p, . . . , p) = r ◦ f (p, . . . , p) = r(p) = p, so that φ is unanimous. We also have φ (pσ (1) , . . . , pσ (k) ) = r ◦ f (pσ (1) , . . . , pσ (k) ) = r ◦ f (p1 , . . . , pk ) = φ (p1 , . . . , pk ), so that φ is anonymous, as required. (⇒). We will prove that all homotopy groups πi (P) are trivial; for then the constant map f : P → {p0 } (p0 ∈ P) induces an isomorphism f∗ : πn (P) → πn ({p0 }) for each n. Since P is connected, we may then apply Whitehead’s theorem to conclude f is a homotopy equivalence. Hence P is homotopy equivalent to {p0 }, which means P is contractible. To see that the homotopy groups are trivial, suppose (toward a contradiction) that some minimal index i satisfies πi (P) 6= 0. Case 1: i = 1. Let k ≥ 2; by hypothesis, we have a continuous, anonymous, unanimous map φ : P k → P inducing a homomorphism of groups φ∗ : π1 (P k ) → π1 (P). It is clear by definition that φ∗ inherits the unanimity property of φ , so that φ∗ (x, . . . , x) = x for every x ∈ π1 (P); similarly, φ∗ must also be anonymous. Hence φ∗ (x, . . . , x) = φ∗ ((x, e, . . . , e) · (e, x, e, . . . , e) · . . . · (e, . . . , e, x)) = φ∗ (x, e, . . . , e) · . . . · φ∗ (e, . . . , e, x) = φ∗ (x, e, . . . , e) · . . . · φ∗ (x, e, . . . , e) = φ∗ (x, e, . . . , e)k . So, for all x, y ∈ π1 (P), we have x · y = φ∗ (x, e, . . . , e)k · φ∗ (e, y, e . . . , e)k = φ∗ (xk , yk , e, . . . , e) = φ∗ (yk , xk , e, . . . , e) = y·x . Thus π1 (P) is abelian. By the Hurewicz theorem, H1 (P) is isomorphic to the 13 abelianization of π1 (P); hence H1 (P) ∼ = π1 (P). From cellular homology (and its equivalence to singular homology), we know that H1 (P) is generated by at most d elements, where d is the number of 1-cells of P. By assumption, P has finitely many cells in each dimension, so that H1 (P) (hence π1 (P)) is finitely generated. Let x be a generator of any of the (free part) groups Z in this decomposition. From the calculation above (employing additive notation), we have x = φ∗ (x, . . . , x) = kφ∗ (x); as k was arbitrary, this must hold for every k ≥ 2, forcing x = 0. Similarly, if x ∈ Z p j is a generator for some j, the same condition implies x = 0. Hence all generators of π1 (P) are zero, implying π1 (P) = 0, a contradiction. Case 2: i ≥ 2. By the Hurewicz Isomorphism Theorem and minimality of i, we have πi (P) ∼ = Hi (P). As above, this implies πi (P) is finitely generated. So, the proof for Case 1 above carries through to this case as well (simply let φ∗ denote the induced homomorphism on the ith homotopy group instead of the first group), and we conclude that πi (P) = 0. Hence all homotopy groups of P are trivial. Remark. The proof above is the one given by Chichilnisky and Heal. However, it can be simplified and shortened by observing that all homotopy groups of a connected, finite-type CW complex must be finitely generated. This can be shown using a simplicial approximation argument (see section 2.C of Hatcher [7]). The key idea behind this theorem is that if P is a contractible subspace of V (X), then we may perform an “averaging” operation in V (X) and compose this with a deformation retract r : V (X) → P to yield a continuous, anonymous, and unanimous choice rule (provided P is a CW complex of finite type). In fact, the contractibility hypothesis ensures that any continuous, anonymous, and unanimous choice rule must be “equivalent” to a rule derived from such a convex averaging procedure, because contractibility of P implies that any two maps φ , ψ : P k → P are homotopic. To see this, suppose h : [0, 1] × P → P is a homotopy, where h0 = idP and h1 (p) = p0 for all p ∈ P, where p0 is a point of P. Take H : 14 [0, 1] × P k → P given by ( Ht (p) = h2t ◦ φ (p) for 0 ≤ t ≤ h2(1−t) ◦ ψ(p) for 1 2 1 2 ≤t ≤1 . Clearly H is continuous with H0 = φ and H1 = ψ, so that φ and ψ are homotopic. Hence, we have the following theorem: Theorem 3.1.2 (C.H. Theorem 2). If P (as a subspace of V (X)) is a connected, contractible CW complex of finite type, then any continuous, anonymous, and unanimous social choice rule ψ is homotopic to a convex averaging rule φ . Proof. By Theorem 3.1.1 and its proof, we have a continuous, anonymous, and unanimous rule φ : P k → P which is given by convex averaging. If ψ : P k → P is any other continuous, anonymous, and unanimous rule, then the above argument shows that ψ is homotopic to φ . Corollary 3.1.3 (C.H Corollary 1). Suppose P is a connected CW complex of finite type and let k ≥ 2. Then P is contractible if and only if P k admits 4(P k ) = {(p, . . . , p) ∈ P k | p ∈ P} ∼ = P as a deformation retract. Proof. If P is a deformation retract of P k , then P and P k are homotopy equiv∼ πi (P k ). But πi (P k ) ∼ alent, so that for each i we have πi (P) = = ⊕k πi (P), so j=1 that πi (P) ∼ = ⊕kj=1 πi (P). Since the homotopy groups πi (P) are finitely generated, this implies πi (P) = 0. As in the proof of Theorem 3.1.1, this implies P is contractible. Conversely, suppose r : P → {p0 } (p0 ∈ P) is a deformation retract. The map (idP , r, . . . , r) : P k → P k is continuous and sends P k to the set Q = {(p, p0 , . . . , p0 ) | p ∈ P} , which is homeomorphic to P. Combining the results of Theorems 3.1.1 and 3.1.2, we arrive at an alternate characterization of the social choice problem: a continuous, unanimous, and anonymous choice rule exists for each k ≥ 2 if and only if for every k ≥ 2, P k retracts onto the “unanimous” profiles 4(P k ) = {(p, . . . , p) ∈ P k | p ∈ P}. 15 We may also use the result of Theorem 3.1.1 to examine the social choice problem when P is not connected. Corollary 3.1.4 (C.H. Corollary 2). Suppose P (as a subspace of V (X)) is a CW complex of finite type. Then a continuous, anonymous, and unanimous choice rule exists for each k ≥ 2 if and only if each connected component of P is contractible. Proof. (⇒). Let k ≥ 2, and suppose φ : P k → P is continuous, anonymous, and unanimous. If C is a connected component of P (hence a finite type CW complex as well), then the map φ̃ = φ |Ck → P inherits the unanimity property of φ , and so φ̃ maps any unanimous profile (p, . . . , p) ∈ Ck to p ∈ C. But φ̃ is also continuous, so by connectedness of Ck , we have φ̃ (Ck ) ⊆ C. It is also clear that φ̃ inherits anonymity from φ . Thus, for every k ≥ 2, we have a continuous, anonymous, and unanimous map Ck → C, so that Theorem 3.1.1 implies that C must be contractible. (⇐). Let k ≥ 2 and suppose each connected component of P is contractible. Since P has finitely many cells in each dimension, P must have only finitely many connected components Cα , which we enumerate C1 , . . . ,Cn . Each component is itself a CW complex of finite type, so that by Theorem 3.1.1 we have a continuous, anonymous, and unanimous map φα : Cαk → Cα for each α. Fix an element p∗α in each component Cα , and define a map φ : P k → P as follows: if p = (p1 , . . . , pk ) ∈ P k belongs to some Cαk , set φ (p) = φα (p). Otherwise, suppose pi ∈ Cαi , and let α be the smallest such αi (according to our enumeration C1 , . . . ,Cn ). Consider the profile p0 = (p01 , . . . , p0k ), where p0i = pi if pi ∈ Cα , and p0i = p∗α otherwise. Then set φ (p) = φα (p0 ). It is easy to see that φ must be anonymous and unanimous. To see that φ is continuous, let p = (p1 , . . . , pk ) ∈ P k and let V be an open neighborhood of φ (p). We must find an open neighborhood U of p for which φ (U) ⊆ V . By continuity of the maps φα , this can clearly be done if p ∈ Cαk for some α. So, suppose (without loss of generality) that p1 , . . . , pm belong to the minimal component α, and that m < k (so that all other pi belong to components Cαi with αi > α). By definition, then, φ (p) = φα (p1 , . . . , pm , p∗α , . . . , p∗α ). So φ (p) = φ (p1 , . . . , pm , p∗α , . . . , p∗α ) as well. By continuity of φα , there is a neighborhood Uα of (p1 , . . . , pm , p∗α , . . . , p∗α ) with φα (Uα ) ⊆ V . Hence there are open sets W1 , . . . ,Wk ⊆ Cα with (p1 , . . . , pm , p∗α , . . . , p∗α ) ∈ W1 × . . . × Wk ⊆ Uα , so φα (W1 × . . . × Wk ) ⊆ V as well. Now define U = W1 × . . . ×Wm × Cα1 × . . . ×Cαk−m , where 16 Cαi is the connected component containing pm+i . Then Cα is still the minimal component for any q = (q1 , . . . , qk ) ∈ U, and so φ (q) = φα (q1 , . . . , qm , p∗α , . . . , p∗α ) ∈ V since (q1 , . . . , qm , p∗α , . . . , p∗α ) ∈ W1 × . . . ×Wk . Since U is an open neighborhood of p, this completes the proof. We conclude this section with a simple example. Consider the set of all linear preference relations on the unit ball B ⊂ Rn . This means each utility function u : B → R has the form u(x1 , . . . , xn ) = a1 x1 + . . . + an xn for some constants ai , not all 0. Since such a function can be identified with its gradient vector (a1 , . . . , an ), the set of all such linear functions corresponds to the set of all nonzero vectors of Rn . Recall, however, that we normalize gradient vectors to length 1 since we are only interested in ordinal information. So, in this case our preference space will consist of all unit vectors of Rn ; that is, P = Sn−1 . Obviously this space is not contractible. If, however, we remove a single point (so that we are ignoring all linear utility functions with gradient a multiple of this particular unit vector), the resulting space will be contractible, so we will have continuous, anonymous, and unanimous social choice rules P k → P for every k ≥ 2. An even wilder restriction would be to consider only those points on the sphere where each coordinate is positive, which will obviously be a contractible space as well. Is such a restriction reasonable? This, of course, depends on the interpretation. If the xi indicate quantities of (desirable) goods, then it might be reasonable that all coefficients ai are positive. 3.2 Discrete Social Choice via Nerves One consequence of the IIA axiom is that it allows the aggregation problem to be studied in terms of sets of preference relations, rather than individual relations. For example, suppose f is an IIA social choice function, and that we wish to understand how f ranks alternatives 1 and 2 for different profiles. The IIA axiom tells us that the social ranking of 1 and 2 only depends upon the rankings of 1 and 2 submitted by the voters, and not on how any other alternatives are ranked. That is, each voter could submit a different preference relation, but so long as the rankings of 1 and 2 are unchanged, the social ranking of 1 and 2 will be the same. So, to study the relevant properties of such a function f (for example, dictatorship issues), it will 17 suffice to study how f behaves on sets of profiles where the ranking of pairs is fixed. This is precisely the approach taken by Baryshnikov [2]. We will see that Arrow’s theorem may be understood topologically by studying the intersection properties of these sets; in fact, the main motivation for Baryshnikov’s approach is to develop an alternate proof of Arrow’s theorem which lends itself well to geometric intuition. 3.2.1 Baryshnikov (1993) As in the original framework, let [n] denote the set {1, . . . , n} of alternatives, and let R denote the set of all rational preference relations over [n]. Assume there are k ≥ 2 individuals. We will be interested in the set P ⊂ R of strict relations (those without any indifferences). To see why, consider the following lemma: Lemma 3.2.1 (Baryshnikov Lemma 1). Suppose f : R k → R is a social choice rule satisfying the Pareto property and IIA. Then f (P k ) ⊆ P. Since we are interested in proving Arrow’s theorem, this lemma shows that it will suffice to prove that any map f : P k → P satisfying the Pareto property and IIA is dictatorial. For if a non-dictatorial, Pareto, and IIA map f : R k → R exists, then f |P k would be a non-dictatorial map f : P k → P satisfying IIA and the Pareto property. Proof. Suppose toward a contradiction that there are distinct elements a, b ∈ [n] and some profile ~ = (1 , . . . , k ) ∈ P k with %= f (~) satisfying a ∼ b. Since 0 n ≥ 3, there is some element c ∈ [n] with c ∈ / {a, b}. Let ~ be a profile which agrees with ~ on {a, b}, but where each individual 0i ranks c immediately below 0 b (by this we mean a 0i b ⇒ a 0i b 0i c, and b 0i a ⇒ b 0i c 0i a). Since ~ 0 agrees with ~ on {a, b}, the IIA axiom tells us %0 = f (~ ) satisfies a ∼0 b as well. 00 Similarly, let ~ agree with ~ on {a, b}, but suppose each individual 00i ranks 00 c immediately above b. Letting %00 = f (~ ), we once again have a ∼00 b. The above construction, together with the Pareto property, tells us that b 0 c, so that a ∼0 b 0 c, giving a 0 c. But the Pareto property also implies c 00 b, so that 0 00 c 00 b ∼00 a and so c 00 a. But, as is easily verified, ~ and ~ agree on {a, c}. The IIA axiom, then, implies that %0 and %00 must agree on {a, c}, contradicting our calculation above. 18 With this lemma in place, we will henceforth restrict attention to maps f : Pk → P. As alluded to above, we will focus on sets of preferences where the ranking of two alternatives is fixed. For i, j ∈ [n] with i < j, define Ui+j = {∈ P | i j} and Ui−j = {∈ P | j i} (since we are restricting to preferences in P, we could equally well define Ui−j = P\Ui+j ). Although we have only defined these sets for i < j, for notational convenience we will take U jiσ to mean the set Uiσ̄j (where σ and σ̄ are opposite signs in {+, −}). Let U = {Uiσj | i < j, σ ∈ {+, −}} denote the entire collection of sets Uiσj . We will be interested in the topology of the nerve of U (more specifically, its geometric realization NP ). Theorem 3.2.2 (Baryshnikov Proposition 1). The simplices of maximal dimension in NP are in one-to-one correspondence with orders in P; these simplices have dimension (n+1)(n−2) , 2 and NP coincides with the union of these simplices. n Proof. We know that is the number of ways of choosing a set {i, j} of two 2 elements from [n]. In a strict linear order , any two elements of [n] must be comparable, so every set {i, j} must be accounted for (that is, either Ui+j or Ui−j must contain ). So, provided that the appropriate σ ’s are chosen for the sets Uiσj , the order will be the only element in the intersection of these Uiσj ’s. Therefore n . The intersection will correspond to a simplex of dimension − 1 = (n+1)(n−2) 2 2 n of more than sets must be empty, because some set {i, j} will be represented 2 twice (and Ui+j ∩ Ui−j = 0). / Therefore, the simplices corresponding to orders are of maximal in NP . Finally, note that any nonempty intersection S of dimension n less than sets corresponds to a (strict) partial order on [n]. But any strict 2 partial order can be extended to a linear order3 , so that S belongs to at least one of the simplices of maximal dimension. Hence NP is the union of the maximal simplices. The correspondence between preference relations and maximal simplices of NP given by theorem 3.2.2 will be quite useful throughout this section. For ex3 This is precisely the statement of Szpilrajn’s Extension Theorem, which is the main theorem given in Szpilrajn [9]. 19 Figure 3.1: The nerve NP for n = 3. ample, consider the case n = 3; the geometric realization of NP is given in figure 3.1. There are six cells of dimension 2 = (n+1)(n−2) , 2 each of which clearly cor- responds to a strict order on [n] (we use the notation (pqr) to represent the order p q r). Notice that for n = 3, the nerve NP is homotopy equivalence to S1 = Sn−2 . In fact, this relationship holds for every n ≥ 3: Theorem 3.2.3 (Baryshnikov Theorem 1). The simplicial complex NP is homotopy equivalent to the (n − 2)-dimensional sphere Sn−2 . Proof. Our strategy is to specify a topological space M (homotopy equivalent to Sn−2 ) and an open cover V of M with the exact same intersection properties as U, so that NP = NV . The cover V will be chosen so that it satisfies all requirements of the nerve theorem (see section 4.G of Hatcher [7]), so that we may conclude NP = NV ' M ' Sn−2 . We take M = Rn \4, where 4 = {x1 = . . . = xn } is the diagonal of Rn . For i < j, define Vi+j = {(x1 , . . . , xn ) ∈ Rn | xi > x j } and Vi−j = {(x1 , . . . , xn ) ∈ Rn | xi < x j }. It is clear that the collection V of all such sets Viσj covers M, and that a subcollection of the Viσj ’s has nonempty intersection if and 20 only if the corresponding sets Uiσj (just replace the symbol V with U to get the corresponding set) have nonempty intersection. So NV = NP . It is also clear that the sets Viσj are each convex (hence contractible), so that any intersection of them is either empty or contractible as well. Thus we may apply the nerve theorem to conclude NV ' M. Finally, M can be shown to be homotopy equivalent to Sn−2 as follows. First, we may rotate M to get M ' Rn \{x1 = . . . = xn−1 = 0}, and then perform a linear homotopy to get M ' Sn−1 \{(0, . . . , 0, 1), (0, . . . , 0, −1)}. A stereographic projection gives M ' Rn−1 \{0}, so that another linear homotopy gives M ' Sn−2 . Naturally, we expect a similar topological construction to work for the profile space P k . Let ~σ = (σ1 , . . . , σk ) be a vector of signs in {+, −}, and for i < j define Ui~σj = {(1 , . . . , k ) ∈ P k | ∀m m ∈ Uiσj m } = Uiσj 1 × . . . ×Uiσj k . Clearly, the collection of all such Ui~σj covers P k . Let NP k denote the nerve of this covering. A similar argument to that of Theorem 3.2.2 establishes the following result: Theorem 3.2.4 (Baryshnikov Proposition 3). The simplices of maximal dimension in NP k are in one-to-one correspondence with profiles of orders in P k ; these simplices have dimension (n+1)(n−2) , 2 and NP k coincides with the union of these simplices. One might suspect that the nerve corresponding to the profile space is homotopy equivalent to (Sn−2 )k . This is not the case; indeed, it appears that NP k is rather complicated. However, at least up to dimension n − 2, the homology of NP k behaves like such a product. We record this result in the next theorem, but omit the proof. Theorem 3.2.5 (Baryshnikov Proposition 4). The (singular) homology groups of NP k are zero in positive dimensions up to dimension n − 3, and the (n − 2)-th group is isomorphic to Zk . To complete the transformation of the original social choice model into a topological one, we must determine how a map f : P k → P transforms into a map 21 between nerves NP k → NP . This is straightforward; the IIA axiom ensures that for each i < j and each ~σ , f maps the vertex Ui~σj to exactly one vertex of NP (either Ui+j or Ui−j ). We also know that if (1 , . . . , k ) ∈ P k is a profile (corresponding to some simplex in NP k ), then f (1 , . . . , k ) is a relation (corresponding to some simplex in NP ). Thus f , being defined on the vertices of NP k , may be extended linearly to yield a simplicial map NP k → NP ; we will simply call this map f . Naturally, f is continuous because it is a well-defined simplicial map. We will see that the dictatorship property is closely related to the way f maps generators (basis elements) of Hn−2 (NP k ) ∼ = Zk to elements of Hn−2 (NP ) ∼ = Z. To understand this relation, we must first give a useful characterization of the generators of Hn−2 (NP ), followed by those of Hn−2 (NP k ). Suppose a graph g is a simple unoriented loop of length n with vertices in [n] (for example, g might be the graph 1 − 2 − 3 − . . . − n − 1). If we choose some orientation for the arrows (yielding an oriented graph ~g), we may identify a corre+ sponding set of vertices Uiσj , where an arrow 1 → 2 corresponds to U12 , the arrow − 1 ← 2 corresponds to U12 , and so on. This gives a collection of n vertices (one for each edge of g). The simplex S(~g) spanned by these vertices may or may not belong to the nerve NP ; indeed, if the oriented graph is 1 → 2 → . . . → n → 1 (we will call such a graph an oriented cycle), then the simplex will not belong to the nerve (the intersection of the corresponding sets will be empty since ~g induces relations which do not satisfy transitivity). However, such a simplex will belong to the “total” simplex 4tot (it contains every simplex spanned by any set of vertices in U ). So, if we let the chain h(~g) = ∂ S(~g) denote the boundary of S(~g), we must have that h(~g) is a cycle in 4tot (that is, ∂ h(~g) = 0; this is clear since ∂ 2 = 0). In fact, h(~g) is a cycle in Hn−2 (NP ), and represents a generator whenever ~g is an oriented loop: Theorem 3.2.6 (Baryshnikov Proposition 2). Suppose ~g is an oriented graph on [n] whose unoriented support g is a simple loop of length n. Then the cycle h(~g) is an (n −2)-dimensional cycle of NP (that is, h(~g) represents some class of Hn−2 (NP )). If ~g is an oriented cycle, then h(~g) represents a generator of Hn−2 (NP ); otherwise, h(~g) is trivial in Hn−2 (NP ). Proof. Since S(~g) is spanned by n vertices, S(~g) is a simplex of dimension n − 1; 22 hence the boundary h(~g) is a sum of (n − 2)-dimensional simplices. Each simplex in this sum corresponds to the simplex given by ~g, but with one arrow removed; hence, the vertices corresponding to each (n − 2)-dimensional simplex in the sum give a partial order on [n], which may be extended to a linear order. But then every such simplex must belong to NP , because the simplices of NP correspond to linear orders on [n]. Hence [h(~g)] ∈ Hn−2 (NP ). Similarly, the order corresponding to ~g may be extended to a linear order whenever ~g is not an oriented cycle. But then h(~g) is the boundary of some maximal simplex in NP , so that h(~g) is trivial in Hn−2 (NP ) if ~g is not an oriented cycle. Finally, suppose ~g is an oriented cycle. For each arrow i → j in ~g, we have a half-space Wi+j = Vi+j = {(x1 , . . . , xn ) ∈ Rn | xi > x j }. Consider the collection W of all such half-spaces given by ~g. Clearly ∪W ⊆ M (recall M = Rn \4 from the proof of theorem 3.2.3); if there is some ~x = (x1 , . . . , xn ) ∈ M which does belong to any of the Wiσj , then ~x belongs to the complement of each Wiσj . Supposing (without loss of generality) that ~g is the oriented cycle 1 → 2 → . . . → n → 1, this implies x1 ≤ x2 ≤ . . . ≤ xn ≤ x1 ; that is, we have ~x = (x, . . . , x) ∈ 4, contradicting the fact that ~x ∈ M. Hence W is a cover of M. Since W ⊂ V , the nerve theorem yields a commutative diagram ι NW g NV h M where ι is injection and g and h are homotopy equivalences. Let g−1 and h−1 denote the homotopy inverses of g and h, respectively. Since g = h ◦ ι, we have h−1 ◦ g = h−1 ◦ h ◦ ι ' 1 ◦ ι = ι. But h−1 ◦ g is a homotopy equivalence, so that ι is also a homotopy equivalence. Clearly, [h(~g)] generates Hn−2 (NW ). Thus h(~g) = ι(h(~g)) represents a generator of Hn−2 (NV ) = Hn−2 (NP ). The graph-based approach to characterizing generators can also be used to find useful representations of basis elements of Hn−2 (NP k ). In particular, let ~g = (~g1 , . . . ,~gk ) be a tuple of oriented graphs on [n] where each ~gi has the same unoriented loop (of length n) as its unoriented support (say 1 − 2 − . . . − n − 1). 23 1 n−1 n i ~σ ~σ ~σ ~σ From ~g, we can extract n vertices U12 , . . . ,Un−1,n ,Un1 as follows: for Ui,i+1 , define i i i ~σ = (σ1 , . . . , σk ) by ( σ`i = + if ~g` has arrow i → i + 1 − if ~g` has arrow i ← i + 1 . i ~σ So, we can think of the vertex Ui,i+1 as keeping track of how the k graphs rank i and i+1. Notice that any subset of n−1 of these vertices gives a simplex in NP k : fixing σ n−1 σ1 ` ) will some coordinate `, the intersection of n − 1 sets (for example, U12` , . . . ,Un−1,n result in a transitive partial order on [n], because the unoriented support 1 − 2 − . . . − n − 1 implies that an intransitivity can arise only if n arrows (hence n vertices) are present. Thus each component will correspond to a partial order on [n], so that the (n − 2)-dimensional simplex spanned by the n − 1 vertices will belong to NP k . Summing (with appropriate coefficients) over all possible subsets of size n − 1 therefore gives the boundary h(~g) of some (n − 1)-dimensional simplex; since each simplex in the sum belongs to NP k , this proves that [h(~g)] ∈ Hn−2 (NP k ). Next, we define projection maps p` : NP k → NP , for 1 ≤ ` ≤ k. Obviously, for a profile of preferences we must have p` (1 , . . . , k ) =` . So, for a vertex Ui~σj of NP k , we see that the `th projection is Uiσj ` ∈ NP . Extending this map linearly p` gives our projection map NP k −→ NP , which is clearly simplicial and therefore 1 n−1 ~σ ~σ continuous. To see how p` maps the cycle h(~g), consider S = [U12 , . . . ,Un−1,n ] (that is, S is one of the (n − 2)-dimensional simplices in the sum h(~g)). Then σ1 σ n−1 ` p` (S) = [U12` , . . . ,Un−1,n ], an (n − 2)-dimensional simplex in NP . The projections of other simplices in h(~g) are computed in a similar fashion, so that p` (h(~g)) is a sum of (n − 2)-dimensional simplices in NP . By construction, p` (h(~g)) is a cycle, and therefore belongs to some class of Hn−2 (NP ). Note that p` (h(~g)) = h(~g` ). Theorem 3.2.7 (Baryshnikov Proposition 5). Suppose ~g = (~g1 , . . . ,~gk ) is a tuple of oriented graphs where ~g` is the oriented cycle 1 → 2 → . . . → n → 1, and all other ~gi are acyclic with the same unoriented support 1 − 2 − . . . − n − 1. Define h` = h(~g). Then the set {h1 , . . . , hk } represents a basis for Hn−2 (N k ) ∼ = Zk . P Proof. Consider h` . Since each graph ~gi (i 6= `) is acyclic, each such h(~gi ) is trivial in Hn−2 (NP ), and since ~g` is an oriented cycle, h(~g` ) represents a generator of 24 Hn−2 (NP ) ∼ = Z. This means h` projects to 0 under pi (i 6= `) and to a generator under p` . So, the collection {h1 , . . . , hk } represents a basis for Hn−2 (NP k ). With these characterizations in place, we are now prepared to establish the relationship between dictators and generators. We begin with the following lemma: Lemma 3.2.8. Suppose ~g = (~g1 , . . . ,~gk ) has an associated cycle h(~g) representing a generator h` in Hn−2 (NP k ) (so ~g` is an oriented cycle with unoriented support 1 − 2 − . . . − n − 1). Then f∗ (h(~g)) ∈ Hn−2 (NP ) and corresponds to a graph ~g f with the same unoriented support. Proof. By IIA, the map f : NP k → NP sends a vertex Ui~σj to Uiσj for some σ ∈ {+, −}. We also know that h(~g) ∈ Hn−2 (NP k ) is a sum of (n − 2)-dimensional 1 n i ~σ ~σ simplices of the form [U12 . . .Un1 ] (where one of the vertices Ui~σj is dropped). σn σ1 Therefore f∗ (h(~g)) is a sum of simplices of the form [U12 . . .Un1 ] where each σi ∈ {+, −} and, again, some vertex Uiσj i is dropped. Each of these simplices is an (n − 2)-dimensional simplex belonging to Hn−2 (NP ) (because such a simplex will represent a partial order on [n], and therefore belong to one of the maximal simplices), and so f∗ (h(~g)) ∈ Hn−2 (NP ). Notice also that f∗ (h(~g)) will have verσn σ1 ], so that the corresponding graph ~g f will have unoriented support tices [U12 . . .Un1 1 − 2 − . . . − n − 1. An immediate consequence of this lemma is that f∗ (h(~g)) is either a generator or is trivial in Hn−2 (NP ), according to whether ~g f is an oriented cycle or not. In fact, these two cases correspond to whether or not agent ` is a dictator: Theorem 3.2.9 (Baryshnikov Proposition 7). Agent ` is a dictator if and only if f∗ (h` ) is a generator. Proof. Suppose first that agent ` is a dictator. By the previous lemma, we may assume that h` is represented by a cycle h(~g), where ~g = (~g1 , . . . ,~gk ) is a tuple of graphs with unoriented support 1−2−. . . n−1, ~g` is an oriented cycle, and all other ~gi are acyclic. It will suffice to show that the graph ~g f corresponding to f∗ (h(~g)) is an oriented cycle. Consider alternatives i and i + 1 in [n]. Corresponding to ~g is i ~σ the vertex Ui,i+1 in NP k ; in particular, we must have σ`i = + since ~g` has the arrow i + ~σ i → i + 1. Since ` is a dictator, this implies f maps Ui,i+1 to Ui,i+1 , which means 25 ~g f must have the arrow i → i + 1. Since i was chosen arbitrarily, this means ~g f is actually equal to the graph ~g` , so that ~g f is an oriented cycle. Hence f∗ (h` ) is a generator. Next, suppose f∗ (h` ) is a generator. Take any distinct i, j ∈ [n]; it will suffice to show that f maps Ui~σj to Uiσj ` for any vector ~σ of signs. For concreteness, suppose σ` = +. Obviously there is some oriented cycle (call it ~g` ) of length n on [n] which has the arrow i → j. This allows us to represent h` by a tuple of graphs ~g = (~g1 , . . . ,~g` , . . . ,~gk ), where each ~gi (i 6= `) is acyclic and has the same unoriented support as ~g` . Suppose we modify one arrow in one of the ~gi ’s (i 6= `) in such a way that ~gi remains acyclic (since n ≥ 3, this can obviously be done). This means one agent has reversed his preference between i and j. By the IIA axiom, the resulting social preference will either be unchanged or it will reverse the order of i and j; thus at most one arrow of ~g f will be reversed, and all others will remain the same. By hypothesis, however, ~g f must be an oriented cycle (the modified tuple ~g still represents h` , which means ~g f must still represent a generator). If one arrow of ~g f were reversed, then ~g f would no longer be a cycle; thus ~g f is actually unaffected by changing one arrow in one ~gi (i 6= `). Because of this, we may (without affecting ~g f ) modify the tuple ~g, one arrow at a time, until each ~gi has the arrow i → j (the obvious procedure is to just reverse any i ← j arrows; if doing so causes an oriented cycle, some other arrow in the same graph will need to (+,...,+) be reversed beforehand). Corresponding to this modified ~g is the vertex Ui j which, by the Pareto property, must be mapped to Ui+j by f . This means ~g f has the arrow i → j. As the above argument shows, any vector ~σ can be achieved (with σ` = +) without changing any arrows of ~g f ; in particular, the arrow i → j of ~g f is fixed, so that for any vector ~σ , f will map Ui~σj to Ui+j . Thus ` is a dictator. In view of theorem 3.2.9, Arrow’s theorem will be immediate if we can prove the existence of some h` which f∗ maps to a generator. We will give a simple algebraic proof that this is, indeed, the case. (σ ,...,σ ) Consider a map NP → NP k which sends a vertex Uiσj to Ui j . We can extend this map linearly to get a simplicial map D : NP → NP k (the diagonal map). Clearly, D∗ (h) = (h, . . . , h) for any generator h ∈ Hn−2 (NP ). Consider the following diagram: 26 Zk Z D∗ z }| { Hn−2 (NP ) Z f∗ z }| { Hn−2 (NP k ) ik i1 Hn−2 (NP ) | {z } z }| { Hn−2 (NP ) ... Hn−2 (NP ) | {z } Z Z i` Here, the maps i` are canonical injections 1 7→ (0, . . . , 1, . . . , 0), where the 1 is in the `th spot. We call such a setup purely separated (in dimension n − 2). By lemma 3.2.8, f∗ ◦ i` sends a generator of Hn−2 (NP ) to either 0 or 1. Notice also that the Pareto property implies that f ◦ D is the identity map, so that f∗ ◦ D∗ = ( f ◦ D)∗ is the identity map as well. So, we have f∗ ◦ D∗ (1) = f∗ (1, . . . , 1) = f∗ (1, 0, . . . , 0) + . . . + f∗ (0, . . . , 0, 1) k = ∑ f∗ (i j (1)) j=1 k = ∑ dj ·1 , j=1 where each d j is either 0 or 1. But since f∗ ◦ D∗ is the identity map, we must have ∑kj=1 d j · 1 = 1; this implies that exactly one d j is 1, which means f∗ (h j ) is a generator. By theorem 3.2.9, then, this agent is a dictator, and the proof of Arrow’s theorem is complete. This is obviously not the easiest way to prove Arrow’s theorem (indeed, the short proof we gave in section 2 is much simpler). The advantage of this topological approach, however, is that it gives at least some intuition for why the theorem is true. Namely, the domain of preferences, together with the IIA axiom, yields a nontrivial topological space, and this nontriviality seems to be responsible for the dictatorship outcome. If one wishes to identify restricted domains where nondictatorial maps are possible, then the topological model can be used to generate hypotheses about which domains might be suitable. Consider again the diagram of NP for the case n = 3. Since dictators map to generators (more or less), one can try to remove the possibility of dictatorship by removing enough orders from P 27 to make the nerve contractible. Looking at the diagram, we see that the space will be contractible if we remove the simplices corresponding to the orders 3 1 2 and 1 3 2. The remaining preferences coincide with the single-peaked preferences described in section 2. Remarkably, any contractible subcomplex of NP will correspond to a (sub)domain of single-peaked preferences! This makes the single-peaked condition almost obvious, whereas the classical framework does not provide any obvious intuition whatsoever as to why single-peaked domains may escape the dictatorship result. Note that our topological framework does not prove that single-peaked domains permit non-dictatorial aggregation maps; the relationship “` is a dictator ⇔ f∗ (h` ) is a generator” is built on the premise that the domain is unrestricted, and it is not at all clear that this relationship could hold without that assumption. Still, the topology offers enough intuition that it can be a useful aid in formulating possible candidates for restricted domains. Moreover, the topological construction is, on its own, a very interesting approach to this branch of theory. 28 Chapter 4 Judgment Aggregation Judgment aggregation is a new branch of economic theory which studies the way individual choices (not necessarily preferences) may be aggregated into a single collective choice. One usually begins with some finite set A containing n alternatives and some subset X ⊆ P(A) of “acceptable choices”. There are k agents, and each selects some member of X (one usually represents members of X as vectors x = (x1 , . . . , xn ) with entries in {0, 1}, indicating which members of A have been selected). An aggregation map f : X k → X assigns to each k-tuple ~x = (x1 , . . . , xk ) of X k a vector ~y = f (~x) of X. If, for every `, we have that y` = 1 (resp. 0) whenever x`i = 1 (resp. 0) for each i = 1, . . . , k, then f satisfies the Pareto property. The IIA axiom can also be adapted to this framework: suppose that for each ` = 1, . . . , n and any two profiles ~y,~z ∈ X k where yi` = zi` for each i, we have that f (~y) and f (~z) agree on the `th coordinate (that is, the collective decision regarding the `th element of A depends only on the individual judgments of the `th element). Then f is Independent of Irrelevant Alternatives. Finally, f is Dictatorial if there is some agent d such that for every ~x ∈ X k , f (~x) = xd (that is, the aggregated choice always coincides with the choice of individual d, regardless of what others choose). This framework is clearly very similar to that of the social choice setup. In fact, social choice models are a special case of the judgment aggregation model. To see this, suppose R is the set of rational preference relations over [m]. Since a preference relation % is determined by comparisons between pairs of elements 29 Table 4.1: The doctrinal paradox P Q R Judge 1 Judge 2 Judge 3 T T F T F T T F F Σ T T F of [m], we can take the set A to be the set of all possible pairwise comparisons; that is, A = {i % j : i, j ∈ [m], i 6= j}. Then X will be the set of vectors for which the corresponding chosen pairwise relations give a preference relation on [m]. It is easy to see that the Pareto and IIA definitions of the judgment aggregation model agree with those of the social choice model; in the case of strict preferences, the Dictatorship axioms agree as well (recall that the dictatorship axiom of social choice only requires that the strict part of the aggregated preference agrees with that of the dictator; in the judgment aggregation setup, the aggregated preference must equal the dictator’s preference). The social choice case is a good example of why only certain subsets of A may be admissible. Another possibility is that elements of A may represent logical propositions, and formal relationships between the propositions may force some subsets to be excluded on the grounds of logical consistency. The canonical example is the “doctrinal paradox”. Suppose three judges (J1, J2, and J3) must decide whether a defendant is guilty of a series of crimes (P, Q, and R). Due to legal definitions, one is guilty of R if and only if one is guilty of both P and Q. In this scenario, then, we have A = {P, Q, R} and X = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 1)}, since these are the only logically consistent assignments. To see the difficulty in aggregating the choices of J1, J2, and J3, suppose the aggregation map f is simply a propositionwise majority vote. Then two out of three judges will find the defendant guilty of P (and similarly for Q), but only one of the three will find the defendant guilty of R. But then the aggregated judgment is (1, 1, 0), which is absurd. Situations such as this make the problem of judgment aggregation considerably more delicate than that of preference aggregation (incidentally, this example is also what motived the name “judgment aggregation” for this branch of theory). 30 Despite these difficulties, the problem of characterizing all impossibility domains (those domains X for which every aggregation map f : X k → X satisfying the IIA and Pareto properties is Dictatorial) has recently been resolved. Specifically, Dokow and Holzman [5] have shown that X is an impossibility domain if and only if X is totally blocked and is not an affine subspace (over F2 ). We will not discuss this result (nor the definition of total blockedness), but remark that their result has been helpful for identifying some simple examples for use in this section. Our objective is to explore the potential for understanding such generalized impossibility results in a topological fashion, just as Baryshnikov has done for Arrow’s theorem in social choice. Keeping in mind the judgment aggregation form of preference aggregation, we proceed as follows: given A = [n] (we can make this identification since A is assumed finite) and X ⊆ {0, 1}n , we define for each i ∈ A and σ ∈ {+, −} the sets Uiσ by Ui+ = {x = (x1 , . . . , xn ) ∈ X | xi = 1} and Ui− = {x = (x1 , . . . , xn ) ∈ X | xi = 0} . The analogy with Baryshnikov’s approach is clear; indeed, the above sets coincide in a 1-1 fashion with the sets Uiσj in Baryshnikov’s model when A is the set of all strict relations i j. Naturally, we are interested in the collection U of all such sets Uiσ , and the corresponding nerve NX . Notice that a vector (x1 , . . . , xn ) ∈ X will be the only element in the intersection of sets Uiσi , where σi = + if and only if xi = 1, and that any intersection of more than n sets must be empty (because then some index i is repeated, so that sets Ui+ and Ui− are in the family; but obviously these two sets are disjoint). This means the simplices of maximal dimension in NX will be in one-to-one correspondence with vectors in X, and that these simplices will have dimension n − 1 (being simplices spanned by n vertices). In a similar fashion, we may define sets Ui~σ (where ~σ is a vector of k signs in {+, −}) by (σ1 ,...,σk ) Ui = Uiσ1 × . . . ×Uiσk . The nerve corresponding to the collection of all such sets Ui~σ is denoted NX k . The maximal simplices of NX k correspond to k-tuples of vectors in X, and therefore are 31 also of dimension n − 1. Finally, any aggregation map f : X k → X satisfying the IIA axiom induces a simplicial map NX k → NX (which we also call f ), just as in Baryshnikov’s model.1 At this stage, one encounters the first major difficulty in constructing a general topological theory of judgment aggregation: using this setup, not every impossibility domain X yields a nontrivial nerve NX . For example, take XI = {(0, 0, 0, 0), (0, 1, 0, 1), (1, 0, 0, 1)(1, 1, 1, 1)} . This is Example 4 in Dokow and Holzman [5], and it is easily shown (using their theorem) that XI is an impossibility domain. However, the nerve corresponding to this domain is contractible, and therefore of no use in our setting. A similar problem occurs if one tries to use our procedure for the case of preference aggregation when preferences need not be strict (that is, when the entire domain R of preference relations is permitted). In that case, A consists of all possible pairwise comparisons i % j; in particular, the vector (1, . . . , 1) (corresponding to the indifference relation 1 ∼ 2 ∼ . . . ∼ m) will belong to every set Ui+ ; in general, the possibility of indifferences add enough vectors to each set Uiσ that the resulting nerve is trivial (due to the increased number of nonempty intersections). This is why Baryshnikov’s model considers only the case of strict preferences. Can a similar domain restriction be found for judgment aggregation models? This is probably a difficult task: even if one removes (1, 1, 1, 1) or (0, 0, 0, 0) (or both) from XI , the resulting nerve is still trivial. Recently, however, Tanaka [10] has modified Baryshnikov’s approach by adding vertices U¯i j containing those orders where the relation i ∼ j is not satisfied. In the judgment aggregation model, the set U¯i j would consist of those vectors where (for some particular s,t) s = t = 1 is not satisfied. This certainly yields a nontrivial nerve (indeed, Tanaka only studies the case where there are three elements to be ordered, but the result is a somewhat complicated space). 1 There is a small subtlety here. The IIA axiom tells us that a set U ~σ is mapped to either U + i i or Ui− . This suggests the following problem: suppose X = {(0, 0), (1, 1)} and that k = 2. What (+,−) f (+,−) f (+,−) (+,−) if U1 7→ U1+ and U2 7→ U2− ? The problem is that U1+ ∩ U2− = 0, / but U1 ∩ U2 = {((1, 1), (0, 0))} is nonempty, so that f cannot be a simplicial map. But, by hypothesis, f maps every (+,−) f vector in X k to some element of X. So it cannot be the case that U1 will always send intersecting vertices to intersecting vertices. 32 (+,−) f 7→ U1+ and U2 7→ U2− ; f It seems plausible that a similar approach could be successful in judgment aggregation models. However, by introducing additional vertices, the overall study of the problem becomes significantly more complicated; in particular, we lose the simple correspondence between maximal simplices and vectors of X, which will make it difficult to characterize homologically trivial chains. Although we do not develop these ideas in this thesis, this nonetheless seems like a (possibly) fruitful avenue for future research. We now turn our attention to a simple impossibility domain which does yield a nontrivial nerve. Our examination of this space serves as a prototype for a (possibly) more general theory. Let A be a finite set with n elements (n ≥ 3), and take X to be those subsets of A consisting of only one element. This means we can represent members of X by the “basis” vectors (1, 0, . . . , 0), (0, 1, 0, . . . , 0), . . . , (0, . . . , 0, 1). Although we will not give a proof here, the theorem of Dokow and Holzman can easily be applied to verify that X is, in fact, an impossibility domain. For each i, we have Ui+ = {(0, . . . , 0, 1, 0, . . . , 0)} and Ui− = X\Ui+ , where the 1 is in the ith position of the vector. Notice that Ui+ = viously, the intersection over all sets U j− T − j∈[n]\i U j . Ob- is empty (X does not contain the zero vector), but (as the above expression for Ui+ shows) any collection of n − 1 of the U j− intersect. This means the nerve NX will consist of the boundary of the (n − 1)-dimensional simplex [U1− . . .Un− ], along with a collection of n simplices (corresponding to the vectors in X), each of which is (n − 1)-dimensional and has exactly one face in common with [U1− . . .Un− ]. This is illustrated in figure 4.1 for the case n = 3. Clearly, the nerve NX is homotopy equivalent to the sphere Sn−2 , and the boundary ∂ [U1− . . .Un− ], being a sum of (n − 2)-dimensional simplices, is a cycle representing a generator of Hn−2 (NX ) ∼ = Z. Our goal, of course, is to achieve a purely separated setup in dimension n − 2. Rather than attempting to compute Hn−2 (NX k ), however, we will achieve this by focusing on the topology of NX instead. This is because (as we have seen in Baryshnikov’s model) the homology of NX k might be very complicated, and it 33 Figure 4.1: The nerve NX for X = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}. seems that one can only perform the relevant computations by constructing a clever model for NX k (by this, we mean a collection of sets with the same intersection properties as the Ui~σ , but which satisfy the requirements of the nerve theorem and cover a space M for which the homology can be computed). Any theory which aims to work for a wide array of impossibility domains should, ideally, not require the formulation of a clever new covering every time a new impossibility domain presents itself. In fact, it is quite easy to obtain a purely separated setup without studying the topology of NX k in depth. First, we define projection maps p` : NX k → NX (` = 1, . . . , k) similar to those in section 3.2. Namely, we begin with the projection map p` (x1 , . . . , xk ) 7→ x` and extend the map linearly to yield a simplicial map NX k → NX . 1 n Consider a chain S1 = ∂ [U1~σ . . .Un~σ ] satisfying p1 (S1 ) = ∂ [U1− . . .Un− ], and where all other pi send S1 to trivial chains of Hn−2 (NX ) (such a chain S1 can be constructed by taking σ1j = − for each j = 1, . . . , n, and for each ` 6= 1 choosing one value j∗ ∗ for which σ`j = + and setting all other σ`j = −). Since ∂ [U1− . . .Un− ] is a generator of Hn−2 (NX ) ∼ = Z, this means that (p` )∗ sends the class [S1 ] ∈ Hn−2 (N k ) to 1 ∈ Z, X 34 and that all other projections send S1 to 0. Similarly, we can define chains S` for each ` = 2, . . . , k satisfying p` (S` ) = 1 and p j (S` ) = 0 for all j 6= `. Thus, the ∼ Zk . classes [S1 ], . . . , [Sk ] form a basis for a subgroup G of Hn−2 (N k ), with G = X Next, observe that f∗ ([S` ]) ∈ {0, 1} for each `. This is because the IIA axiom 1 n implies that for each i, f (Ui~σ ) = Uiσ for some σ ∈ {0, 1}. Since S` = ∂ [U1~σ . . .Un~σ ], this means either f (S` ) = ∂ [U1− . . .Un− ] (so f∗ (S` ) = 1) or f (S` ) = ∂ [U1σ1 . . .Unσn ], where exactly one σi is + and all others are − (so that f∗ ([S` ]) = 0). The simplicial map f : NX k → NX induces a homomorphism Hn−2 (NX k ) → Hn−2 (NX ), which obviously restricts to a homomorphism G → Hn−2 (NX ) since G is a subgroup of Hn−2 (NX k ) (we will still call this restricted homomorphism f∗ ). Applying the Pareto property, we see that f∗ (1, . . . , 1) = 1.2 As in Baryshnikov’s model, this is enough to imply that 1 = ∑k`=1 f∗ ([S` ]) = ∑k`=1 d` , where each d` ∈ {0, 1}, so that there is exactly one index, d, for which f∗ ([S` ]) = 1. To see that this agent d is a dictator, we need to show that an agent ` is a dictator if f∗ ([S` ]) = 1. In fact, the converse also holds: Theorem 4.0.10. Agent ` is a dictator if and only if f∗ ([S` ]) = 1. 1 n Proof. Suppose first that ` is a dictator. By definition, S` = ∂ [U1~σ . . .Un~σ ], where 1 each vector ~σ i has a − sign in the `th coordinate. Since ` is a dictator, f maps U1~σ σ1 i to U1 ` = U1− ; similarly, f maps each Ui~σ to Ui− . Thus f maps S` to ∂ [U1− . . .Un− ], which represents a generator of Hn−2 (NX ). Thus f∗ ([S` ]) = 1. Conversely, suppose f maps S` to ∂ [U1− . . .Un− ]. We prove that for each i, f 1 i n maps Ui~σ to Ui− whenever σ`i = −. Given S` = ∂ [U1~σ . . .Un~σ ], we can modify i the “ jth coordinate” ( j 6= i) as follows: given Ui~σ , we can reverse the sign of σ ij ; if σ ij was +, then the jth coordinate of all other vectors is −, so we choose some th m 6= i and set σ m j = + (this way, the j coordinate still projects to a trivial chain m of Hn−2 (NX )). If σ ij was −, then some other σ m j was +; so we change that σ j to − (again, this ensures that the jth coordinate projects to 0). These changes give a modified chain S`0 with p` (S`0 ) = ∂ [U1− . . .Un− ], and all other projections p j send 2 There is a technicality here which needs to be addressed. In order to apply the Pareto property to reach this conclusion, we need to know that in Hn−2 (NX k ), we have [S1 ] + . . . + [Sn ] = [∂ [U1~σ . . .Un~σ ]], where ~σ = (−, . . . , −). That is, the sum of the basis classes should coincide with the class represented by this particular chain which projects to 1 in each coordinate. This does not seem unreasonable. We will discuss this (and a related technical problem) later. 35 S`0 to a trivial chain of Hn−2 (NX ). By hypothesis, then, f maps S`0 to the generator ∂ [U1− . . .Un− ] as well. Notice that for Ui , the only difference between S` and S`0 is that the jth coordinate of ~σ i has switched signs; but the image under f remains the same. Repeating this argument, we see that any vector ~σ i can be achieved (with σ`i = −) without changing the image of Ui~σ under f . In particular, the vector (−,...,−) (−, . . . , −) is attainable, and by the Pareto property, f maps Ui to Ui− . Thus, ~σ i for all i, we have that f (Ui ) = − whenever σ`i = −. This means that for any ktuple (x1 , . . . , xk ) ∈ X k with y = f (x1 , . . . , xk ), we have that xi` = 0 ⇒ yi = 0. But by choice of our domain X, this forces y to equal x` , because each vector in X has exactly one coordinate equal to one, and all others zero. Hence ` is a dictator. Combining this theorem with the result above (namely, that there is some agent d for which f∗ ([Sd ]) = 1), this gives a topological proof that X is an impossibility domain. Remark. The proof of this theorem depends on the fact that any two chains 1 1 n n α, β of the form α = ∂ [U1~σ . . .Un~σ ], β = ∂ [U1~σ . . .Un~σ ] (where p` (α) = p` (β ) = ∂ [U1− . . .Un− ] and all other pm send α and β to trivial chains of Hn−2 (NX )) must, in fact, belong to the class [S` ] (this is needed to ensure that f maps the modified chain S`0 to a generator). This does not seem unreasonable at all; in fact, it would follow easily if we knew that Hn−2 (N k ) ∼ = Zk (because then each projecX tion would send the class [α] − [β ] to 0, forcing [α] − [β ] = 0). Despite this, we have not been successful in finding a rigorous proof. Note that this is essentially the same difficulty mentioned previously, where we need to be able to represent the class [S1 ] + . . . + [Sk ] by the chain ∂ [U1~σ . . .Un~σ ], where ~σ = (−, . . . , −). There seem to be two main options. First, one might attempt to give a general proof that, for nerves constructed in this manner, one always has Hm (N k ) ∼ = (Hm (NX ))k , where X Hm (NX ) is the top homology group of NX . Such a theorem would be quite valuable since, as previously discussed, the homology of NX k is difficult to compute directly, but only information about the top group seems to be required to establish dictatorship results. Alternatively, one might attempt to construct an algorithm yielding a sequence of chains γ1 , . . . , γt (each trivial in Hm (NX k )) with β = α + γ1 + . . . + γt . We regard both approaches as avenues for future research (indeed, either result 36 would be a significant feature of a generalized topological theory of judgment aggregation). Note that for our simple space X, we do not rely on any graph-based or other approaches to identifying generators. This is because the generator ∂ [U1− . . .Un− ] is the only one needed to establish the relationship between dictatorship and mapping properties of f∗ , and no extra language or notation needs to be introduced to describe it. In general, however, there may not be a simple way to represent the relevant generators in an arbitrary domain X. Finding a convenient way of describing generators, just as Baryshnikov has done for the case of strict preferences, seems to be another challenge that must be overcome. At this stage, there is also nothing to rule out the possibility that some domains X may have associated nerves with a more complicated topology. This, in turn, could cause the algebraic portion of the proof to fail. What is the appropriate way to generalize the purely-separated setup in such situations? How will mapping properties of the various generators relate to the dictatorship condition? These questions, and the issues previously mentioned, are quite difficult. Still, the analysis given above of the simple space X is encouraging enough that further research into these problems seems worthwhile, and that (eventually) a more general theory might be found. 37 Bibliography [1] K. Arrow. Social choice and individual values. Yale Univ Pr, 1963. → pages 6 [2] Y. Baryshnikov. Unifying Impossibility Theorems: A Topological Approach. Advances in Applied Mathematics, 14(4):404–415, 1993. → pages 11, 18 [3] G. Chichilnisky. Social Choice and the Topology of Spaces of Preferences. Advances in Mathematics, 37(2):165–176, 1980. ISSN 0001-8708. → pages 10 [4] G. Chichilnisky and G. Heal. Necessary and Sufficient Conditions for a Resolution of the Social Choice Paradox. Journal of Economic Theory, 31 (1):68–87, 1983. ISSN 0022-0531. → pages 10, 11, 12 [5] E. Dokow and R. Holzman. Aggregation of binary evaluations. Journal of Economic Theory, 145(2):495–511, 2010. → pages 31, 32 [6] J. Geanakoplos. Three brief proofs of arrows impossibility theorem. Economic Theory, 26(1):211–215, 2005. → pages 7 [7] A. Hatcher. Algebraic topology. Cambridge: Cambridge University Press, 2002. → pages 14, 20 [8] E. Spanier. Algebraic topology. Springer Verlag, 1994. → pages 13 [9] E. Szpilrajn. Sur lextension de lordre partiel. Fund. Math, 16:386–389, 1930. → pages 19 [10] Y. Tanaka. A topological approach to the arrow impossibility theorem when individual preferences are weak orders. Applied mathematics and computation, 174(2):961–981, 2006. → pages 32 38
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Topological methods of preference and judgment aggregation
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Topological methods of preference and judgment aggregation Jakobsen, Alexander M. 2011
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Topological methods of preference and judgment aggregation |
Creator |
Jakobsen, Alexander M. |
Publisher | University of British Columbia |
Date Issued | 2011 |
Description | Arrow’s Impossibility Theorem is a classical result in social choice theory (a branch of economic theory), which states that any system of rules for combining (“aggregating”) individual preference relations into a single representative relation results in a “dictatorship” where the combined preference only reflects the wishes of a single individual (provided that the aggregation rule satisfies two basic criteria). Since the 1980s, this result has been reformulated and understood using algebraic topology. The topological approach offers some geometric intuition as to why Arrow’s theorem holds, and can also be used to find alternative hypotheses which may escape the dictatorship outcome. A thorough examination of such topological models constitutes the main body of this thesis. Recently, social choice theory has been generalized (resulting in a field called “judgment aggregation”), and results analogous to Arrow's theorem have been established. The second part of this thesis introduces this field of study, and studies how some of the techniques from topological social choice theory can be extended to understand dictatorship outcomes in the theory of judgment aggregation. Although the analysis is restricted to a rather simple case, it nonetheless highlights the potential for a more general topological model of judgment aggregation, and exposes the main challenges that must be overcome in constructing such a theory. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-06-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0071897 |
URI | http://hdl.handle.net/2429/35592 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2011-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2011_fall_jakobsen_alexander.pdf [ 297.28kB ]
- Metadata
- JSON: 24-1.0071897.json
- JSON-LD: 24-1.0071897-ld.json
- RDF/XML (Pretty): 24-1.0071897-rdf.xml
- RDF/JSON: 24-1.0071897-rdf.json
- Turtle: 24-1.0071897-turtle.txt
- N-Triples: 24-1.0071897-rdf-ntriples.txt
- Original Record: 24-1.0071897-source.json
- Full Text
- 24-1.0071897-fulltext.txt
- Citation
- 24-1.0071897.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0071897/manifest