10 21 2008 15 251 Social Choice Voting and Auctions Great Theoretical Ideas in Computer Science Lecture 17 October 21 2008 Big picture Big picture some more Say you like pizza hotdogs burgers People have private information We ask you for your preferences so that we can order food for the review session You want to get that information If you ask them will they tell you the truth I ll choose the option that gets most 1st place votes Well they might lie if telling a lie helps them strategic behavior What should you tell me What if you know the rest of the class has 20 votes each for hotdogs and burgers and 15 for pizza How do you elicit the truth Who s the winner Three candidates in town Three voters in town let s start simple 1st 2nd 3rd a b c b c a c a b Who s the winner What s the best ordering of the candidates 1 10 21 2008 Condorcet s Paradox Marie Jean Antoine Nicolas de Caritat Marquis de Condorcet 1st 2nd 3rd Social Choice Ranking A set of alternatives say a b c d L set of all possible rankings or linear orderings of these alternatives e g a d b c or b c d a a b c b c a c a b Given any potential winner say a a majority prefer another candidate c to this person N people each with their ranking Want to combine these into one social ranking Two questions Given the rankings of the N individuals Social Choice Output the alternative that s the winner i e output an element of A Social Ranking Output a ranking that best captures the rankings of the individuals E g 1 A a b In this case L a b b a Population person 1 person 2 person 3 person 4 a b a b b a a b Social Choice maybe use plurailty and output a Social Ranking a b E g 2 E g 3 A a b c L a b c a c b b c a b a c c a b c b a A a b c L a b c a c b b c a b a c c a b c b a Population person 1 person 2 person 3 person 4 Population person 1 person 2 person 3 a b c a b c b a c c a b Social Choice maybe use plurailty and output a Social Ranking maybe a b c a b c b c a c a b Social Choice For each output majority of people prefer some other candidate Social Ranking 2 10 21 2008 Notation Social ranking function F LN L takes 1 2 N output what are some properties we d like Social choice function G LN A takes 1 2 N a Some properties Unanimity Some properties Independent of Irrelevant Alternatives F is unanimous if when all individuals have a b for some a b in A then the output satisfies a b F is IIA if the relative ranking of a and b in the outcome depends only on the voters rankings of a and b I e whenever all voters rank a and b the same the output is the same regardless of the other alternatives Some properties The case for A 2 Dictator Voter j is a dictator in F if F 1 2 N j F is a dictatorship if there is some j that is a dictator in F Fact If there are 2 alternatives the IIA property is trivially satisfied Facts Note that plurality satisfies unanimity and is not a dictatorship 3 10 21 2008 The case for A 3 or more Copeland s Method Here are two ways to output an ordering Copeland s method Borda s method The Borda system Social Choice functions Some properties What about social choice functions Remember a social choice function outputs a single choice I e G LN A takes 1 2 N a Unanimity G is unanimous if when all individuals have a at the top of their rankings then G outputs a 4 10 21 2008 Some properties Monotone Some properties Dictator G is monotone if whenever G 1 2 j N a and G 1 2 j N a then it must be the case that voter j moved a above a in his ranking Voter j is a dictator in G if G 1 2 N choice at top of j G is a dictatorship if there is some j that is a dictator in G I e G is incentive compatible It does not reward lying Plurality Output the option at the top of most people s rankings Unanimity Again some simple cases Monotonicity Instant Runoff Voting Remove alternative with fewest first place votes and repeat Unanimity Monotonicity What are some good social ranking and social choice functions for A 3 5 10 21 2008 The case for A 3 or more Theorem Arrow Any social ranking function with A 3 or more that satisfies unanimity and IIA is a dictatorship The case for A 3 or more Theorem Gibbard Satterthwaite Any social choice function with A 3 or more that satisfies unanimity and monotonicity is a dictatorship Gibbard Satterthwaite Arrow s Theorem Note that we wanted to ask people for their secret preferences and use that to pick a social choice We don t want them to lie Hence we want the social choice function to be monotone Gibbard Satterthwaite Theorem Two important results with very similar proofs But that is impossible So what do we do How to get around these impossibility results Two solutions 1 Money 2 Change the representation Mechanisms with money Measure not just that a preferred to b but also by how much Each individual j or player j has a valuation for each alternative a in A Denoted as vj a Also each player values money the same So if we choose alternative a and give m to j then j s utility is vj a m 6 10 21 2008 Selfishness Auctions Suppose there is a single item a to be auctioned Each player acts to maximize her utility Each player has value vj a or just vj for it If item given to j and j pays p then utility j vj p and utility j 0 for all other players j Auctions Picture However auctioneer does not know these private valuations Auctioneer wants to give the item to the person who values it the most Think of artist giving a painting to the person who wants it the most Not revenue maximizing here What should the auctioneer do Try 1 Ask each person for their valuation bids give it to the person j with highest bid bj Auctioneer gets bids bj which should ideally be the valuations vj But may be higher or lower if it helps players they ll report something else Try 2 Ask each person for their valuation give it to the person j with highest bid bj ask for payment bj 7 …
View Full Document
Unlocking...