Byzantine Spectral Ranking

• URL: http://arxiv.org/abs/2211.07902v1
• Date: Tue, 15 Nov 2022 05:18:19 GMT
• Title: Byzantine Spectral Ranking
• Authors: Arnhav Datar, Arun Rajkumar, John Augustine
• Abstract summary: We study the problem of rank aggregation where the goal is to obtain a global ranking by aggregating pair-wise comparisons of voters over a set of items. We introduce the Byzantine Spectral Ranking Algorithm, which produces a reliable ranking when the number of good voters exceeds the number of Byzantine voters.
• Score: 3.4272203252843294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of rank aggregation where the goal is to obtain a global ranking by aggregating pair-wise comparisons of voters over a set of items. We consider an adversarial setting where the voters are partitioned into two sets. The first set votes in a stochastic manner according to the popular score-based Bradley-Terry-Luce (BTL) model for pairwise comparisons. The second set comprises malicious Byzantine voters trying to deteriorate the ranking. We consider a strongly-adversarial scenario where the Byzantine voters know the BTL scores, the votes of the good voters, the algorithm, and can collude with each other. We first show that the popular spectral ranking based Rank-Centrality algorithm, though optimal for the BTL model, does not perform well even when a small constant fraction of the voters are Byzantine. We introduce the Byzantine Spectral Ranking Algorithm (and a faster variant of it), which produces a reliable ranking when the number of good voters exceeds the number of Byzantine voters. We show that no algorithm can produce a satisfactory ranking with probability > 1/2 for all BTL weights when there are more Byzantine voters than good voters, showing that our algorithm works for all possible population fractions. We support our theoretical results with experimental results on synthetic and real datasets to demonstrate the failure of the Rank-Centrality algorithm under several adversarial scenarios and how the proposed Byzantine Spectral Ranking algorithm is robust in obtaining good rankings.

Related papers

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We first introduce the Combinatorial Successive Asign algorithm, which is the first algorithm that can identify the best action even when the size of the action class is exponentially large. We show that the upper bound of the probability of error of the CSA algorithm matches a lower bound up to a logarithmic factor in the exponent. We experimentally compare the algorithms with previous methods and show that our algorithm performs better.
  arXiv  Detail & Related papers  (2023-10-24T09:47:32Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
  arXiv  Detail & Related papers  (2023-08-23T08:38:53Z)
• 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)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms. Our proposed UCB-based Top Two simultaneously enjoys non-asymptotic guarantees and competitive empirical performance.
  arXiv  Detail & Related papers  (2022-10-11T13:21:59Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Robust Voting Rules from Algorithmic Robust Statistics [25.313563663123354]
  We give an algorithm that can accurately estimate the central ranking even when a constant fraction of its samples are arbitrarily corrupted. Our work can be thought of as a natural infusion of perspectives from algorithmic robust statistics into one of the central inference problems in voting and information-aggregation.
  arXiv  Detail & Related papers  (2021-12-13T02:30:26Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Guaranteed Fixed-Confidence Best Arm Identification in Multi-Armed Bandit [1.5469452301122177]
  We consider the problem of finding, through adaptive sampling, which of n populations (arms) has the largest mean. Our objective is to determine a rule which identifies the best population with a fixed minimum confidence using as few observations as possible.
  arXiv  Detail & Related papers  (2021-06-12T20:05:29Z)
• 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)
• User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets [28.537935838669423]
  We show that user fairness, item fairness and diversity are fundamentally different concepts. We present the first ranking algorithm that explicitly enforces all three desiderata.
  arXiv  Detail & Related papers  (2020-10-04T02:53:09Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  We show that the regret of the corralling algorithms is no worse than that of the best algorithm containing the arm with the highest reward. We show that the gap between the highest reward and other rewards depends on the gap between the highest reward and other rewards.
  arXiv  Detail & Related papers  (2020-06-16T15:33:12Z)

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.