15 251 Great Theoretical Ideas in Computer Science Social Choice Voting and Auctions Lecture 17 October 21 2008 Big picture Say you like pizza hotdogs burgers We ask you for your preferences so that we can order food for the review session I ll choose the option that gets most 1st place votes 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 Big picture some more People have private information You want to get that information If you ask them will they tell you the truth Well they might lie if telling a lie helps them strategic behavior How do you elicit the truth let s start simple Who s the winner Three candidates in town Three voters in town 1st 2nd 3rd a b c b c a c a b Who s the winner What s the best ordering of the candidates Condorcet s Paradox Marie Jean Antoine Nicolas de Caritat Marquis de Condorcet 1st 2nd 3rd a b c b c a c a b Given any potential winner say a a majority prefer another candidate c to this person 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 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 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 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 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 Population person 1 person 2 person 3 a b c b c a c a b Social Choice For each output majority of people prefer some other candidate Social Ranking what are some properties we d like Notation Social ranking function F LN L takes 1 2 N output Social choice function G LN A takes 1 2 N a Some properties Unanimity F is unanimous if when all individuals have a b for some a b in A then the output satisfies a b Some properties Independent of Irrelevant Alternatives 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 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 The case for A 2 Fact If there are 2 alternatives the IIA property is trivially satisfied Facts Note that plurality satisfies unanimity and is not a dictatorship The case for A 3 or more Here are two ways to output an ordering Copeland s method Borda s method Copeland s Method The Borda system Social Choice functions What about social choice functions Remember a social choice function outputs a single choice I e G LN A takes 1 2 N a Some properties Unanimity G is unanimous if when all individuals have a at the top of their rankings then G outputs a Some properties Monotone 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 I e G is incentive compatible It does not reward lying Some properties Dictator 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 Again some simple cases Plurality Output the option at the top of most people s rankings Unanimity Monotonicity What are some good social ranking and social choice functions for A 3 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 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 But that is impossible Arrow s Theorem Gibbard Satterthwaite Theorem Two important results with very similar proofs 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 Selfishness Each player acts to maximize her utility Auctions Suppose there is a single item a to be auctioned 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 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 Picture Auctioneer gets bids bj which should ideally be the valuations v j But may be higher or lower if it helps players they ll report something else Try 1 Ask each person for their valuation bids give it to the person j with highest bid bj Try 2 Ask each person for their valuation give it to the person j with highest bid bj ask for payment bj Try 3 Ask each person for their valuation give it to the person j with highest bid bj ask for payment bk where k has 2nd highest bid Called Vickery second price auction Truth telling is a good strategy here Suppose …
View Full Document
Unlocking...