Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Philosophy > Faculty    Search Help Login pdf version printable version 

Publications [#236229] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V, Computing slater rankings using similarities among candidates, Proceedings of the National Conference on Artificial Intelligence, vol. 1 (November, 2006), pp. 613-619.
    (last updated on 2024/03/28)

    Abstract:
    Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One important voting rule is the Slater rule. It selects a ranking of the alternatives (or candidates) to minimize the number of pairs of candidates such that the ranking disagrees with the pairwise majority vote on these two candidates. The use of the Slater rule has been hindered by a lack of techniques to compute Slater rankings. In this paper, we show how we can decompose the Slater problem into smaller subproblems if there is a set of similar candidates. We show that this technique suffices to compute a Slater ranking in linear time if the pairwise majority graph is hierarchically structured. For the general case, we also give an efficient algorithm for finding a set of similar candidates. We provide experimental results that show that this technique significantly (sometimes drastically) speeds up search algorithms. Finally, we also use the technique of similar sets to show that computing an optimal Slater ranking is NP-hard, even in the absence of pairwise ties. Copyright © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.


Duke University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login