Social choice theory = preference aggregation = truthful votingSocial 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?ProofStronger version of Arrow’s theoremVoting rules that avoid Arrow’s impossibility (by changing what the voters can express)Social choice theory = preference aggregation= truthful votingTuomas 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 xAgenda 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 {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, 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 A and every 1 ,…,n , ’1 ,…, ’n 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•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 * 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 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 b A, and for every i {0,…,n} define a preference profile i in which exactly the first i players rank b above a. By pairwise unanimity, in F(0) we have a b, while in F(n) we have b a. Thus, for some i* the ranking of a and b flips: in F(i*-1) we have a b, while in F(i*) we have b a.•We conclude the proof by showing that i* is a dictator:•Lemma. Take any c d 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 i*, but the preferences for (c,e) are identical to the preferences for (a,b) in i*-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–f is monotonic if [ x = f() and x maintains its position in ’ ] => f( ’) = x–x maintains its position whenever x i y => x i’ y •Proof. From f we construct a social welfare function F
View Full Document