CPS 296.3 Social Choice & Mechanism DesignVoting over outcomesVoting (rank aggregation)Example voting rulesPairwise electionsCondorcet cyclesVoting rules based on pairwise electionsEven more voting rules…Slide 9Condorcet criterionMajority criterionMonotonicity criteriaMonotonicity criteria…Independence of irrelevant alternativesArrow’s impossibility theorem [1951]Muller-Satterthwaite impossibility theorem [1977]ManipulabilityGibbard-Satterthwaite impossibility theoremSingle-peaked preferencesSome computational issues in social choiceWhat is mechanism design?Example: (single-item) auctionsWhich auction generates more revenue?Bayesian gamesConverting Bayesian games to normal formBayes-Nash equilibriumMechanism design: settingWhat should the center do?Quasilinear utility functionsDefinition of a (direct-revelation) mechanismIncentive compatibilityIndividual rationalityThe Clarke (aka. VCG) mechanism [Clarke 71]The Clarke mechanism is strategy-proofAdditional nice properties of the Clarke mechanismClarke mechanism is not perfectWhy restrict attention to truthful direct-revelation mechanisms?The revelation principleA few computational issues in mechanism designCPS 296.3Social Choice & Mechanism DesignVincent Conitzer [email protected] over outcomes>>>>voting rule (mechanism) determines winner based on votesVoting (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 rankingExample 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 pluralityPairwise 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” preferencesVoting 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 worst pairwise result is the best wins•Slater: create an overall ranking of the candidates that is inconsistent with as few pairwise elections as possible•Cup/pairwise elimination: pair candidates, losers of pairwise elections drop out, repeatEven more voting rules…•Kemeny: create an overall ranking of the candidates that has as few disagreements as possible with a vote on a pair of candidates•Bucklin: start with k=1 and increase k gradually until some candidate is among the top k candidates in more than half the votes•Approval (not a ranking-based rule): every voter labels each candidate as approved or disapproved, candidate with the most approvals wins•… how do we choose a rule from all of these rules?•How do we know that there does not exist another, “perfect” rule?•Let us look at some criteria that we would like our voting rule to satisfyEven more voting rules…•Kemeny: create an overall ranking of the candidates that has as few disagreements as possible with a vote on a pair of candidates•Bucklin: start with k=1 and increase k gradually until some candidate is among the top k candidates in more than half the votes•Approval (not a ranking-based rule): every voter labels each candidate as approved or disapproved, candidate with the most approvals wins•… how do we choose a rule from all of these rules?•How do we know that there does not exist another, “perfect” rule?•Let us look at some criteria that we would like our voting rule to satisfyCondorcet criterion•A candidate is the Condorcet winner if it wins all of its pairwise elections•Does not always exist…•… but if it does exist, it should win•Many rules do not satisfy this•E.g. for plurality:–b > a > c > d–c > a > b > d–d > a > b > c•a is the Condorcet winner, but it does not win under pluralityMajority criterion•If a candidate is ranked first by most votes, that candidate should win•Some rules do not even satisfy this•E.g. Borda:–a > b > c > d > e–a > b > c > d > e–c > b > d > e > a•a is the majority winner, but it does not win under BordaMonotonicity criteria•Informally, monotonicity means that “ranking a candidate higher should help that candidate”, but there are multiple nonequivalent definitions•A weak monotonicity requirement: if –candidate w wins for the current votes, –we then improve the position of w in some of the votes and leave everything else the same,then w should still win.•E.g. STV does not satisfy this:–7 votes b > c > a–7 votes a > b > c–6 votes c > a > b•c drops out first, its votes transfer to a, a wins•But if 2 votes b > c > a change to a > b > c, b drops out first, its 5 votes transfer to c, and c winsMonotonicity criteria…•A strong monotonicity requirement: if –candidate w wins for the current votes, –we then change the votes in such a way that for each vote, if a candidate c was ranked below w originally, c is still ranked below w in the new votethen w should still win.•Note the other candidates can jump around in the vote, as long as they don’t jump ahead of w•None of our rules satisfy thisIndependence of