We formulate the problem of eliciting agents' preferences with the goal of
finding a Kemeny ranking as a Dueling Bandits problem. Here the bandits' arms
correspond to alternatives that need to be ranked and the feedback corresponds
to a pairwise comparison between alternatives by a randomly sampled agent. We
consider both sampling with and without replacement, i.e., the possibility to
ask the same agent about some comparison multiple times or not.
We find approximation bounds for Kemeny rankings dependant on confidence
intervals over estimated winning probabilities of arms. Based on these we state
algorithms to find Probably Approximately Correct (PAC) solutions and elaborate
on their sample complexity for sampling with or without replacement.
Furthermore, if all agents' preferences are strict rankings over the
alternatives, we provide means to prune confidence intervals and thereby guide
a more efficient elicitation. We formulate several adaptive sampling methods
that use look-aheads to estimate how much confidence intervals (and thus
approximation guarantees) might be tightened. All described methods are
compared on synthetic data.

通过对代理人的偏好进行赋值，我们将找到 Kemeny 排名作为对抗式武装强盗问题。我们考虑了采样和不采样的情况，并提供了概率近似正确（PAC）解决方案的算法，同时详细说明了其采样复杂度。如果所有代理人的偏好都是对备选项的严格排名，我们提供了剪枝置信区间的方法，以便更有效地赋值，并提出了几种自适应采样方法进行比较。

引发 Kemeny 排名

Eliciting Kemeny Rankings

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.

Kemeny 方法是一种用于排名整合的热门工具，我们研究了在参数化复杂性条件下计算不同 Kemeny 排名的问题，并提供了已有的 FPT 算法和近似算法。