Parameterized Aspects of Distinct Kemeny Rank Aggregation

• URL: http://arxiv.org/abs/2309.03517v1
• Date: Thu, 7 Sep 2023 06:58:19 GMT
• Title: Parameterized Aspects of Distinct Kemeny Rank Aggregation
• Authors: Koustav De, Harshil Mittal, Palash Dey, Neeldhara Misra
• Abstract summary: We study the problem of computing all distinct Kemeny rankings under the lens of parameterized complexity. We find that any desirable number of Kemeny rankings can also be found without substantial increase in running time.
• Score: 4.792851066169871
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is NP-hard. Consequently, the computational task of finding a Kemeny ranking has been studied under the lens of parameterized complexity with respect to many parameters. We first present a comprehensive relationship, both theoretical and empirical, among these parameters. Further, we study the problem of computing all distinct Kemeny rankings under the lens of parameterized complexity. We consider the target Kemeny score, number of candidates, average distance of input rankings, maximum range of any candidate, and unanimity width as our parameters. For all these parameters, we already have FPT algorithms. We find that any desirable number of Kemeny rankings can also be found without substantial increase in running time. We also present FPT approximation algorithms for Kemeny rank aggregation with respect to these parameters.

Related papers

• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers [0.5490714603843316]
  HodgeRank generalizes ranking algorithms to rank alternatives based on real-world (often incomplete) data using graphs and discrete exterior calculus. We develop a quantum algorithm that approximates the HodgeRank solution with complexity independent of dimension.
  arXiv  Detail & Related papers  (2024-07-29T23:16:23Z)
• Ranking with Slot Constraints [25.715799711674457]
  We devise a new ranking algorithm, called MatchRank, for slot-constrained problems. The goal of MatchRank is to produce rankings that maximize the number of filled slots if candidates are evaluated by a human decision maker in the order of the ranking. Our theoretical analysis shows that MatchRank has a strong approximation guarantee without any independence assumptions between slots or candidates.
  arXiv  Detail & Related papers  (2023-10-27T03:14:50Z)
• Partitioned Saliency Ranking with Dense Pyramid Transformers [4.449304130658638]
  Saliency ranking has emerged as a challenging task focusing on assessing the degree of saliency at instance-level. Previous approaches undertake the saliency ranking by directly sorting the rank scores of salient instances, which have not explicitly resolved the inherent ambiguities. We propose the ranking by partition paradigm, which segments unordered salient instances into partitions and then ranks them based on the correlations among these partitions.
  arXiv  Detail & Related papers  (2023-08-01T02:33:10Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  We propose a model agnostic post-processing framework xOrder for achieving fairness in bipartite ranking. xOrder is compatible with various classification models and ranking fairness metrics, including supervised and unsupervised fairness metrics. We evaluate our proposed algorithm on four benchmark data sets and two real-world patient electronic health record repositories.
  arXiv  Detail & Related papers  (2023-07-27T07:42:44Z)
• Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
  We consider the problem of ranking n experts based on their performances on d tasks. We make a monotonicity assumption stating that for each pair of experts, one outperforms the other on all tasks.
  arXiv  Detail & Related papers  (2023-06-05T06:55:39Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  We consider the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well.
  arXiv  Detail & Related papers  (2022-01-21T16:43:03Z)
• On the Linear Ordering Problem and the Rankability of Data [0.0]
  We use the degree of linearity to quantify what percentage of the data aligns with an optimal ranking. In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight. We show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking.
  arXiv  Detail & Related papers  (2021-04-12T21:05:17Z)
• Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability [0.0]
  We consider mixtures of two Mallows models for top-$k$ rankings. We propose efficient sampling algorithms for Mallows top-$k$ rankings.
  arXiv  Detail & Related papers  (2020-10-27T13:00:37Z)
• Necessarily Optimal One-Sided Matchings [49.0517583218216]
  We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences.
  arXiv  Detail & Related papers  (2020-07-17T16:01:34Z)
• Augmented Parallel-Pyramid Net for Attention Guided Pose-Estimation [90.28365183660438]
  This paper proposes an augmented parallel-pyramid net with attention partial module and differentiable auto-data augmentation. We define a new pose search space where the sequences of data augmentations are formulated as a trainable and operational CNN component. Notably, our method achieves the top-1 accuracy on the challenging COCO keypoint benchmark and the state-of-the-art results on the MPII datasets.
  arXiv  Detail & Related papers  (2020-03-17T03:52:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.