Duke CPS 296.3 - Social Choice & Mechanism Design (39 pages)

Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of 39 page document
View Full Document

Social Choice & Mechanism Design

Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of actual document.

View Full Document
View Full Document

Social Choice & Mechanism Design

28 views

Other

Pages:
39
School:
Duke University
Course:
Cps 296.3 - Algorithms in the Real World
Algorithms in the Real World Documents
• 10 pages

• 12 pages

• 9 pages

• 15 pages

• 8 pages

• 8 pages

• 28 pages

• 6 pages

• 6 pages

• 11 pages

• 10 pages

• 10 pages

• 28 pages

Unformatted text preview:

CPS 296 3 Social Choice Mechanism Design Vincent Conitzer conitzer cs duke edu Voting over outcomes voting rule mechanism determines winner based on votes Voting rank aggregation Set of m candidates aka alternatives outcomes n voters each voter ranks all the candidates E g if set of candidates a b c d one possible vote is b a d c Submitted ranking is called a vote A voting rule takes as input a vector of votes submitted by the voters and as output produces either the winning candidate or an aggregate ranking of all candidates Can vote over just about anything political representatives award nominees where to go for dinner tonight joint plans allocations of tasks resources Also can consider other applications e g aggregating search engine s rankings into a single ranking Example voting rules Scoring rules are defined by a vector a1 a2 am being ranked ith in a vote gives the candidate ai points Plurality is defined by 1 0 0 0 winner is candidate that is ranked first most often Veto or anti plurality is defined by 1 1 1 0 winner is candidate that is ranked last the least often Borda is defined by m 1 m 2 0 Plurality with 2 candidate runoff top two candidates in terms of plurality score proceed to runoff whichever is ranked higher than the other by more voters wins Single Transferable Vote STV aka Instant Runoff candidate with lowest plurality score drops out if you voted for that candidate your vote transfers to the next live candidate on your list repeat until one candidate remains Similar runoffs can be defined for rules other than plurality Pairwise elections two votes prefer Kerry to Bush two votes prefer Kerry to Nader two votes prefer Nader to Bush Condorcet cycles two votes prefer Bush to Kerry two votes prefer Kerry to Nader two votes prefer Nader to Bush weird preferences Voting rules based on pairwise elections Copeland candidate gets two points for each pairwise election it wins one point for each pairwise election it ties Maximin aka Simpson candidate whose

View Full Document

Unlocking...