资源论文A Maximum Likelihood Approach towards Aggregating Partial Orders

A Maximum Likelihood Approach towards Aggregating Partial Orders

2019-11-12 | |  67 |   38 |   0
Abstract In many of the possible applications as well as the theoretical models of computational social choice, the agents’ preferences are represented as partial orders. In this paper, we extend the maximum likelihood approach for de?ning “optimal” voting rules to this setting. We consider distributions in which the pairwise comparisons/incomparabilities between alternatives are drawn i.i.d. We call such models pairwise-independent models and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rules such as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satis?es neutrality, when the outcome space is the set of all alternatives. We then study which voting rules de?ned for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (including any ranking/candidate scoring rule) based on the weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensions to pro?les of partial orders. Finally, we propose a speci?c MLE model ?k for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of ?k .

上一篇:Online Planning for Ad Hoc Autonomous Agent Teams Feng Wu Shlomo Zilberstein Xiaoping Chen?

下一篇:An Ef?cient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments

用户评价
全部评价

热门资源

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Rating-Boosted La...

    The performance of a recommendation system reli...

  • Hierarchical Task...

    We extend hierarchical task network planning wi...