Social choice theory = preference aggregation = voting assuming agents tell the truth about their preferencesSocial choiceCondorcet paradox [year 1785]Agenda paradoxPareto dominated winner paradoxInverted-order paradoxBorda rule also vulnerable to irrelevant alternativesMajority-winner paradoxIs there a desirable way to aggregate agents’ preferences?Proof (follows logic of Nisan’s proof in Algorithmic Game Theory book, but fixes errors and includes missing part)Stronger version of Arrow’s theoremVoting rules that avoid Arrow’s impossibility (by changing what the voters can express)Social choice theory = preference aggregation= voting assuming agents tell the truth about their preferencesTuomas SandholmProfessorComputer Science Department Carnegie Mellon UniversitySocial choice•Collectively choosing among outcomes–E.g. presidents–Outcome can also be a vector•E.g. allocation of money, goods, tasks, and resources•Agents have preferences over outcomes•Center knows each agent’s preferences –Or agents reveal them truthfully by assumption•Social choice function aggregates those preferences & picks outcome•Outcome is enforced on all agents•CS applications: Multiagent planning [Ephrati&Rosenschein], computerized elections [Cranor&Cytron], accepting a joint project, collaborative filtering, rating Web articles [Avery,Resnick&Zeckhauser], rating CDs...Condorcet paradox [year 1785]•Majority rule•Three voters:1. x > z > y 2. y > x >z3. z > y > xx > z > y > xUnder some preferences there is a Condorcet winner.Agenda paradox•Binary protocol (majority rule) = cup•Three types of agents:xxyyzzxx y yzzx xyyzz• Power of agenda setter (e.g. chairman)• Vulnerable to irrelevant alternatives (z)• Plurality protocol • For each agent, most preferred outcome gets 1 vote• Would result in x1. x > z > y (35%) 2. y > x > z (33%)3. z > y > x (32%)Pareto dominated winner paradoxVoters:xxxyyyyaaabbbb1. x > y > b > a2. a > x > y > b3. b > a > x > yInverted-order paradox•Borda rule with 4 alternatives–Each agent gives 4 points to best option, 3 to second best...•Agents:•x=22, a=17, b=16, c=15•Remove x: c=15, b=14, a=131. x > c > b > a2. a > x > c > b3. b > a > x > c4. x > c > b > a5. a > x > c > b6. b > a > x > c7. x > c > b > aBorda rule also vulnerable to irrelevant alternatives1. x > z > y (35%) 2. y > x > z (33%)3. z > y > x (32%)•Three types of agents: •Borda winner is x•Remove z: Borda winner is yMajority-winner paradox•Agents:•Majority rule with any binary protocol: a•Borda protocol: b=16, a=15, c=111. a > b > c2. a > b > c 3. a > b > c 4. b > c > a5. b > c > a6. b > a > c7. c > a > bIs there a desirable way to aggregate agents’ preferences?•Set of alternatives A •Each agent i in {1,..,n} has a ranking <i of A•Social welfare function F: Ln -> L•To avoid unilluminating technicalities in proof, assume <i and < are strict total orders•Some possible (weak) desiderata of F–1. Unanimity: If all voters have the same ranking, then the aggregate ranking equals that. Formally, for all < in L, F(< ,…,<) =<.–2. Nondictatorship: No voter is a dictator. Voter i is a dictator if for all <1 ,…,<n , F(<1 ,…,<n) = <i–3. Independence of irrelevant alternatives: The social preference between any alternatives a and b only depends on the voters’ preferences between a and b. Formally, for every a, b in A and every <1 ,…,<n , < ’1 ,…,< ’n in L , if we denote < = F(<1 ,…,<n) and < ’ = F(< ’1 ,…,< ’n), then a <i b <=> a < ’i b for all i implies that a < b <=> a < ’ b.•Arrow’s impossibility theorem [1951]: If |A| ≥ 3, then no F satisfies desiderata 1-3.Proof (follows logic of Nisan’s proof in Algorithmic Game Theory book, but fixes errors and includes missing part)•Assume F satisfies unanimity and independence of irrelevant alternatives•Lemma. Any function F: Ln -> L that satisfies unanimity and independence of irrelevant alternatives also satisfies pairwise unanimity. That is, if for all i, a <i b, then a < b.–Proof. Let <* in L be such that a <* b. By unanimity, a < b in F(<* ,..,<*). If <1,...,<n are all such that a <i b, then we have a <i b <=> a <* b, and so by independence of irrelevant alternatives, for <' = F(<1,...,<n), we have a <' b. ■•Lemma (pairwise neutrality). Let >1 ,…,>n and >’1 ,…, >’n be two player profiles such that a >i b <=> c >’i d. Then a > b <=> c >’ d.–Proof. Assume wlog that a > b and c not equal to d. We merge each >i and >’i into a single preference >i by putting c just above a (unless c = a) and d just below b (unless d = b) and preserving the internal order within the pairs (a,b) and (c,d). –By pairwise unanimity, c > a and b > d. Thus, by transitivity, c > d. ■•Take any a not equal to b in A, and for every i in {0,…,n} define a preference profile Pi in which exactly the first i players rank b above a. By pairwise unanimity, in F(P0) we have a > b, while in F(Pn) we have b > a. Thus, for some i* the ranking of a and b flips: in F(Pi*-1) we have a > b, while in F(Pi*) we have b > a.•We conclude the proof by showing that i* is a dictator:•Lemma. Take any c not equal to d in A. If c >i* d then c > d.–Proof. Take some alternative e that is different from c and d. For i < i* move e to the top in >i, for i > i* move e to the bottom in >i, and for i* move e so that c >i* e >i* d. By independence of irrelevant alternatives, we have not changed the social ranking between c and d. –Notice that the players’ preferences for the ordered pair (d,e) are identical to their preferences for (a,b) in Pi*, but the preferences for (c,e) are identical to the preferences for (a,b) in Pi*-1, and thus using the pairwise neutrality claim, socially e > d and c > e, and thus by transitivity c > d in the preferences where e was moved. By independence of irrelevant alternatives, moving e does not affect the relative ranking of c and d; thus c > d also under the original preferences. ■ ■Stronger version of Arrow’s theorem•In Arrow’s theorem, social welfare function F outputs a ranking of the outcomes•The impossibility holds even if only the highest ranked outcome is sought:•Thm. Let |A| ≥ 3. If a social choice function f: Ln -> A is monotonic and Paretian, then f is dictatorial.–Definition. f is monotonic if [ x = f(>) and x maintains its position in >’ ] => f(>’) =