Computing Kemeny and Slater Rankings Vincent Conitzer (Joint work with Andrew Davenport and Jayant Kalagnanam at IBM Research.)Voting/rank aggregation rulesThe Kemeny ruleSlater rulePairwise election graphsKemeny on pairwise election graphsSlater on pairwise election graphsComputing Slater Rankings Using Similarities Among Candidates [Conitzer AAAI06]Sets of similar candidatesA useful property of sets of similar candidatesHow to use the lemmaFinding a set of similar candidatesUsing similar candidates as preprocessing step for searchExperimental setup1 issue, 191 voters2 issues, 191 voters2 issues, 3 voters10 issues, 191 voters2 issues, 5 parties, 191 votersNP-hardnessConclusions on computing Slater rankings using similarities among candidatesImproved Bounds for Computing Kemeny Rankings [Conitzer, Davenport, Kalagnanam AAAI06]Edge-disjoint cycle lower bound [Davenport & Kalagnanam AAAI-04]Overlapping cycle lower boundA more difficult example…Trying overlapping cycle boundSlide 27Who says we have to subtract the minimum weight?Slide 29Slide 30Slide 31LP formulation and dualAn equivalent linear program with a polynomial number of constraintsMean deviation of bounds from optimalCPU time to compute boundsOverall computation timeConclusions on bounds for computing Kemeny rankingsComputing Kemeny and Slater Rankings Vincent Conitzer (Joint work with Andrew Davenport and Jayant Kalagnanam at IBM Research.)Voting/rank aggregation rules•Set of m candidates (outcomes, alternatives)•n voters; each voter ranks the candidates (the voter’s vote)–E.g. b > a > c > d•Voting rule f maps every vector of votes to a compromise ranking of the candidatesThe Kemeny rule•Given a ranking r, a vote v, and two candidates a, b, let δab(r, v) = 1 if r and v disagree on the relative ranking of a and b, and 0 otherwise•A Kemeny ranking r minimizes ΣabΣvδab(r, v) [Kemeny 59]•Kemeny rule gives maximum likelihood estimate of the “correct” outcome given [Condorcet 1785]’s noise model [Young 95]–... though other noise models lead to other rules [Conitzer & Sandholm UAI-05]•Kemeny rule is NP-hard to compute [Bartholdi et al. 89], even with only 4 votes [Dwork et al. WWW-01]Slater rule•Pairwise election between a and b: compare how often a is ranked above b vs. how often b is ranked above a in the votes to determine the winner of the pairwise election•Given a ranking r of the candidates and two candidates a, b, let δab(r) = 1 if r ranks the winner of the pairwise election between a and b lower than the loser, and 0 otherwise•A Slater ranking r minimizes Σabδab(r)–I.e. it minimizes the number of disagreements with pairwise electionsPairwise election graphs•Pairwise election between a and b: compare how often a is ranked above b vs. how often b is ranked above a•Graph representation: edge from winner to loser (no edge if tie), weight = margin of victory•E.g. for votes a > b > c > d, c > a > d > b givesaaabadac222Kemeny on pairwise election graphs•Final ranking = acyclic tournament graph•Kemeny ranking seeks to minimize the total weight of the inverted edgesaaabadac2210442pairwise election graphKemeny rankingaaabadac22(b > d > c > a)Slater on pairwise election graphs•Final ranking = acyclic tournament graph•Slater ranking seeks to minimize the number of inverted edgesaaabadacaaabadacpairwise election graphSlater ordering(a > b > d > c)Computing Slater Rankings Using Similarities Among Candidates[Conitzer AAAI06]Sets of similar candidates•Assume no pairwise ties for simplicity•A subset S of the candidates consists of similar candidates if for any s1, s2  S, t  C - S, s1 wins its pairwise election against t if and only if s2 wins its pairwise election against t•Example: aaabadac•{b, d} consists of similar candidates•{a, b} does not (one beats c and the other does not)A useful property of sets of similar candidates•Lemma. If S consists of similar candidates, then there exists a Slater ranking in which all candidates in S are adjacent.•Proof:–Suppose we have a Slater ranking in which they are not all adjacent, say … > s1 > T > s2 > …–If s1 and s2 each defeat at least half of the candidates in T then … > s1 > s2 > T > … gives at least as high a score–If s1 and s2 each defeat at most half of the candidates in T then … > T > s1 > s2 > … gives at least as high a score–Repeated application makes all candidates in S adjacentHow to use the lemma•Because we know all of S can be adjacent, we can replace S by a single “supercandidate”aaabadacaaabdacbig edges have twice the weight•Solve the reduced instance (here: a > bd > c)•Solve S internally (here: b > d)•Obtain final ranking (here: a > b > d > c)Finding a set of similar candidates•We can model this as a satisfiability instance–in(a) means a is in the set of similar candidatesaaabadac•in(a) and in(b)  in(c)•in(a) and in(c)  in(b) and in(d)•in(a) and in(d)  in(b) and in(c)•in(b) and in(c)  in(a) and in(d)•in(b) and in(d) •in(c) and in(d)  in(a)•Only solutions:–Trivial: at most 1 candidate in S, or all candidates in S–Nontrivial (useful): S = {b, d}•Nontrivial solutions can be found in polytimeUsing similar candidates as preprocessing step for search•Straightforward search algorithm:–At each search tree node, decide whether or not the final ranking will be consistent with the next edge–Apply transitivity if possible–Admissible heuristic: number of edges for which it has been decided that the final ranking will be inconsistent with them•Preprocessing technique:–Find a nontrivial set of similar candidates–If found, solve reduced instances recursively•Experimental comparison between–the straightforward search algorithm, and–the preprocessing technique applied recursively, followed by the same search algorithm when preprocessing technique no longer appliesExperimental setup•Candidates and voters draw random positions in [0, 1]d –(d = number of issues)•Voters rank candidates by (Euclidean) distance to their own position•In one of the experiments, we consider parties: –parties draw random positions in [0, 1]d–candidates randomly choose a party, then take the average of the party’s position and a random point as their own position•30 data points per instance1 issue, 191 voters•Not surprising: these are single-peaked preferences, so that the graph must be acyclic2 issues, 191 voters2 issues, 3 voters10