# Parameterized Aspects of Distinct Kemeny Rank Aggregation

Koustav De
email<EMAIL_ADDRESS>
Harshil Mittal
email<EMAIL_ADDRESS>
Palash Dey
email<EMAIL_ADDRESS>
Neeldhara Misra
email<EMAIL_ADDRESS>
###### Abstract

The Kemeny method is one of the popular tools for rank aggregation. However,
computing an optimal Kemeny ranking is $\mathsf{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 $\mathsf{FPT}$ algorithms. We find that any
desirable number of Kemeny rankings can also be found without substantial
increase in running time. We also present $\mathsf{FPT}$ approximation
algorithms for Kemeny rank aggregation with respect to these parameters.

Keywords: Diversity, Voting, Kemeny, Kendall-Tau

##  1 Introduction

Aggregating individual ranking over a set of alternatives into one societal
ranking is a fundamental problem in social choice theory in particular and
artificial intelligence in general. Immediate examples of such applications
include aggregating the output of various search engines [DKNS01a],
recommender systems [PHG00], etc. The Kemeny rank aggregation method is often
the method of choice in such applications due to its many desirable properties
like Condorcet consistency that is electing the Condorcet winner (if it
exists), etc. A Condorcet winner is a candidate who defeats every other
candidate in pairwise election. The Kemeny method outputs a ranking $R$ with
minimum sum of dissatisfaction of individual voters known as Kemeny score of
$R$; the dissatisfaction of a voter with ranking $P$ with respect to $R$ is
quantified as the number of pairs of candidates that $P$ and $R$ order
differently [Kem59]. This quantity is also called the Kendall-Tau distance
between $P$ and $R$. A ranking with minimum Kemeny score is called the Kemeny
ranking.

The computational question of finding optimal Kemeny rankings is intractable
in very restricted settings (for instance, even with a constant number of
voters). Therefore, it has been well-studied from both approximation and
parameterized perspectives. A problem is said to be _fixed-parameter
tractable_ or $\mathsf{FPT}$ with respect to a parameter $k$ if it admits an
algorithm whose running time can be described as $f(k)\cdot n^{O(1)}$ where
the input size is $n$, implying that the algorithm is efficient for instances
where the parameter is “small” [CFK+15]. For the Kemeny rank aggregation
problem, the following parameters (among others) have enjoyed attention in the
literature:

  * •

_Range._ The range of a candidate in a profile is the difference between its
positions in the voters who rank him/her the lowest and the highest [BFG+09].
The maximum and average range of a profile is defined as, respectively, the
maximum and average ranges of individual candidates. Profiles which are
“homogeneous”, $i.e.$ where most candidates are viewed somewhat similarly by
the voters, are likely to have low values for range, while a single polarizing
candidate can skew the max range parameter considerably.

  * •

_KT-distance._ The average (respectively, maximum) KT distance is the average
(respectively, maximum) of the Kendall-Tau distances between all pairs of
voters [BFG+09]. Recall that the KT distance between a pair of rankings is the
number of pairs that are ordered _differently_ by the two rankings under
consideration.

A pair of candidates are said to be _unanimous_ with respect to a voting
profile if all votes rank them in the same relative order. Consider the
following “unanimity graph” associated with a profile $P$ and defined as
follows: every candidate is represented by a vertex, and there is an edge
between a pair of candidates if and only if they are unanimous with respect to
the profile. We use $G_{P}$ to denote this graph. Note that the structure of
the _complement_ of this graph, denoted $\overline{G_{P}}$, carries
information about candidates about whom the voters are not unanimous in their
opinion. In particular, for every pair of candidates $a$ and $b$ that have an
edge between them in the complement of the unanimity graph, there is at least
one voter who prefers $a$ over $b$ and at least one who prefers $b$ over $a$.
Thus every edge signals a lack of consensus, and one could think of the number
of edges in this graph as a measure of the distance of the profile from an
“automatic consensus”, which is one that can be derived from the information
about unanimous pairs alone. Motivated by this view, we propose and consider
also the following structural parameters:

  * •

_Consensus Distance._ This is simply the number of edges in the complement of
the unanimity graph $\overline{G_{P}}$.

  * •

_Blocking Size._ This is the size of the largest _clique_ — which is a
collection of mutually adjacent vertices — in the complement of the unanimity
graph $\overline{G_{P}}$. It represents the largest number of candidates that
the profile collectively finds mutually incomparable.

  * •

_Unanimity width._ It is the pathwidth of the unanimity graph
$\overline{G_{P}}\text{ }i.e.$ the co-comparability graph or the complement of
the comparability graph of the unanimity(partial) order of the input which is
the specific order on the pairs of candidates on which all the voters agree,
as studied by [AFL+21] and it turns out to be a structural measure of how
close the existing consensus in the input profile is to a complete ranking.
The definition of pathwidth comes next.

The relationship between range and KT-distances is reasonably well understood,
and these parameters are largely mutually incomparable. Our first contribution
in this work is to extend these comparisons to the three parameters defined
above, namely the consensus distance, blocking size, and unanimity width. The
pathwidth of the complement of the unanimity graph turns out to be
“sandwiched” between these two new parameters (consensus distance, blocking
size) that we have proposed: it is at least the size of the largest
independent set of the unanimity graph, and at most the number of edges in it.
We compare these parameters and study them from an empirical perspective. We
evaluate their values on various profiles sampled using a Mallows model on an
assumed consensus.

Our second contribution concerns enumerating optimal Kemeny rankings. In
recent times, there is considerable research interest in finding a set of
diverse optimal or near-optimal solutions of an optimization problem. Indeed,
it is often difficult to encode all aspects of a complex system into a neat
computational problem. In such scenarios, having a diverse set of optimal
solutions for a problem $\Gamma$ allows the user to pick a solution which
meets other aspects which are not captured in $\Gamma$. In the context of rank
aggregation, such other external constraints may include gender fairness,
demographic balance, etc. For the Kemeny rank aggregation method, Arrighi et
al. [AFdOOW20] present a parameterized algorithm to output a set of diverse
Kemeny rankings with respect to unanimity width as the parameter.

However, note that external requirements are often independent of the
constraints in the optimization problem, and consequently they may not be
correlated with diversity based on distance parameters. In particular, for
useful externalities like gender fairness or geographic balance — these
features of the candidates may not have any relation with their position in
the voters’ rankings, and therefore, diversity _between_ solutions may not
imply diversity _within_ any of the solutions. This becomes particularly stark
when most near-optimal rankings do not meet the external requirements. Indeed,
there is a substantial literature that considers the problem of accounting for
these requirements explicitly, and studies trade-offs between optimality of
solutions and the degree to which demands of diversity can be met.

In this contribution, we shift our focus from finding diverse solutions to
finding as many _distinct_ solutions as possible. Enumerating solutions is a
fundamental goal for any optimization problem. The literature on counting
optimal Kemeny rankings is arguably limited considering that even finding one
is hard in very restricted settings, and that instances could have
exponentially many rankings — which would be too expensive to enumerate.
Indeed, consider a profile that consists of two votes over $m$ candidates,
where one vote ranks the candidates in lexicographic order and the other ranks
the candidates in reverse lexicographic order. For this instance, every
ranking is an optimal ranking. However, note that real world preferences often
have additional structure: for example, profiles with an odd number of voters
that are single-peaked [CGS13] or single-crossing [CGS13] have unique optimal
solutions. To address scenarios where the number of optimal solutions is
large, we allow the user to specify the number $r$ of optimal solutions that
she wants the algorithm to output. In our problem called Distinct OPT Kemeny
Ranking Aggregation, the input is a set of rankings over a set of candidates
and an integer $r$, and we need to output $\max\\{r,\text{number of optimal
solutions}\\}$ Kemeny rankings.

###  1.1 Our Contributions

#### Experimental Results

We establish comprehensively relationships between all pairs of the following
parameters: (a) maximum range, (b) average KT distance, (c) unanimity width,
(d) blocking size, and (e) consensus distance. We also evaluate the values of
these parameters on several profiles sampled using the Mallows model with
various dispersion parameters. Intuitively, all of these parameters are
proportional to the _heterogeneity_ of the profiles: in other words, more
“similar looking” profiles have smaller values for these parameters. We are
able to quantify this empirically by showing that the parameters decrease as
we increase the dispersion of the Mallows distribution we sample from. It
turns out that the higher the dispersion, the more the probability mass is
concentrated around votes “close to” a central ranking.

#### Algorithms for Distinct Kemeny Rank Aggregation

The first parameter that we consider is the optimal Kemeny score $k$, also
called the standard parameter. Many applications of rank aggregation, for
example, faculty hiring, etc. exhibit correlation among the individual
rankings — everyone in the committee may tend to prefer some candidate with
strong academic background than some other candidate with weak track record.
In such applications, the optimal Kemeny score $k$, average Kendall-Tau
distance $d$ (a.k.a. Bubble sort distance) among input rankings, maximum range
of the positions of any candidate $r_{\text{max}}$, and unanimity width $w$
will be small, and an $\mathsf{FPT}$ algorithm becomes useful. We show that
there is an algorithm for Distinct OPT Kemeny Ranking Aggregation running in
time $\mathcal{O}^{*}\left(2^{k}\right)$ [Theorem 1]. We next consider the
number of candidates, $m$ as the parameter and present an algorithm running in
time $\mathcal{O}^{*}\left(2^{m}r^{\mathcal{O}(1)}\right)$ [Theorem 2] where
$r$ is the required number of solutions. For $d$ and $r_{\text{max}}$, we
present algorithms with running time $\mathcal{O}^{*}(16^{d})$ and
$\mathcal{O}^{*}\left(32^{r_{\text{max}}}\right)$ [Theorems 3 and 4]
respectively. Our last parameter is the unanimity width $w$ which is the
pathwidth of the co-comparability graph of the unanimity order and we present
an algorithm running in time $\mathcal{O}^{*}\left(2^{\mathcal{O}(w)}\cdot
r\right)$ [Theorem 5].

Some instances may have a few optimal solutions, but have many close-to-
optimal solutions. To address such cases, we study the Distinct approximate
Kemeny Ranking Aggregation problem where the user gives a real number
$\lambda\geq 1$ as input and looks for $\max\\{r,\text{number of optimal
solutions}\\}$ rankings with Kemeny score at most $\lambda$ times the optimal
Kemeny score. For this problem, we design algorithms with running time
$\mathcal{O}^{*}\left(2^{\lambda k}\right)$ [Corollary 1],
$\mathcal{O}^{*}\left(2^{m}r^{\mathcal{O}\left(1\right)}\right)$ [Corollary 2]
and $\mathcal{O}^{*}\left(16^{\lambda d}\right)$ [Theorem 6].

We observe that the running time of all our algorithms are comparable with the
respective parameterized algorithms for the problem of finding one Kemeny
ranking. We note that this phenomenon is in sharp contrast with the diverse
version of Kemeny rank aggregation where we have an $\mathsf{FPT}$ algorithm
only for unanimity width as the parameter. Also, the running time of the
algorithm for the diverse version is significantly more than the standard non-
diverse version [AFL+21].

###  1.2 Related Work

Kemeny rule [Kem59] shows us its most significant and popular mechanism for
ranking aggregation. However, Bartholdi et al. [BTT89] have established that
Kemeny Score is NP-complete even if we apply the restriction of having only
four input rankings [DKNS01b]. Fixed-parameter algorithms for Kemeny voting
rule have been proved to be an effective and important area for research by
Betzler et al. [BFG+09] considering structural parameterizations such as
“number of candidates”, “solution size i.e. Kemeny Score”, “average pairwise
distance”, “maximum range”, “average range” of candidates in an election. A
multi-parametric algorithm for Diverse Kemeny Rank Aggregation over partially
ordered votes has been studied in [AFL+21]. A small error in the construction
proof from [DKNS01b] has been rectified by Biedl et al. [BBD09] and they have
established the approximation factor of $2-2/k$, improving from the previous
approximation factor of 2.

Further classification in more exact manner of the classical computational
complexity of Kemeny elections has been provided by Hemaspaandra et al.
[HSV05]. With respect to the practical relevance of the computational hardness
of the Kemeny Score, polynomial-time approximation algorithms have been
developed where a factor of $8/5$ is seen in [VZW09] and a factor of $11/7$ is
proved in [ACN08a]. As we can see a polynomial-time approximation scheme
(PTAS) developed by Kenyon-Mathieu and Schudy [KMS07] is not very practical,
we can refer to various approximation algorithms and heuristics provided by
Schalekamp and van Zuylen [SZ09] as an evaluation. Some greedy techniques and
branch-and-bound methods can be seen from Conitzer, Davenport and Kalagnanam
[DK04, CDK06] where the authors have performed their studies heuristically.
From [PHG00, DKNS01a] we can verify the methods used for merging results from
various search engines and the notion of collaborative filtering.

Polynomial time algorithms producing good solutions for rank aggregation rule
is a consequence of thorough computational studies [vZW07, ACN08b]. Cornaz et
al. [CGS13] have established polynomial time computability of the single-
peaked and single-crossing widths and have proposed new fixed-parameter
tractability results for the computation of an optimal ranking according to
the Kemeny rule by following the results of Guo te al. [GHN04]. In social
choice theory [Kla04, BTT89], the ideas related to diverse sets of solutions
have found tremendous applicability. The study in [Zwi18] introduced the
$(j,k)$-Kemeny rule which is a generalization of Kemeny’s voting rule that
aggregates ballots containing weak orders with $j$ indifference classes into a
weak order with $k$ indifference classes. In social choice theory, different
values of $j$ and $k$ yield various rules of the interest of the community
turning up as special cases. The minimum Kendall-Tau distance between pairs of
solutions has a nice analogy with $min$ Hamming distance over all pairs of
solutions as shown in [HHOW05, HOW07].

##  2 Preliminaries

For an integer $\ell$, we denote the set $\\{1,\ldots,\ell\\}$ by
$\left[\ell\right]$. For two integers $a,b$, we denote the set
$\\{i\in\mathbb{N}:a\leq i\leq b\\}$ by $\left[a,b\right]$. Given two integer
tuples
$\left(x_{1},\ldots,x_{\ell}\right),\left(y_{1},\ldots,y_{\ell}\right)\in\mathbb{N}^{\ell}$,
we say
$\left(x_{1},\ldots,x_{\ell}\right)>_{\text{lex}}\left(y_{1},\ldots,y_{\ell}\right)$
if there exists an integer $i\in\left[\ell\right]$ such that we have (i)
$x_{j}=y_{j}$ for every $j\in\left[i-1\right]$, and (ii) $x_{i}>y_{i}$.

Let $\mathcal{C}$ be a set of candidates and
$R=\left\\{\pi_{1},\ldots,\pi_{r}\right\\}$ a multi-set of rankings (complete
orders) on $\mathcal{C}$. For a ranking $\pi$ and a candidate $c$ let us
define $\text{pos}_{\pi}(c)$ to be
$|\left\\{c^{\prime}\in\mathcal{C}:c^{\prime}\succ_{\pi}c\right\\}|$. We
define the range $r$ of $c$ in a set of rankings $\Pi$ to be
$\max\limits_{\pi_{i},\pi_{j}\in\Pi}\left\\{|\text{pos}_{\pi_{i}}\left(c\right)-\text{pos}_{\pi_{j}}\left(c\right)|\right\\}+1$.
We denote the set of all complete orders over $\mathcal{C}$ by
$\mathcal{L}(\mathcal{C})$. The Kemeny score of a ranking
$Q\in\mathcal{L}(\mathcal{C})$ with respect to $R$ is defined as

$\text{Kemeny}_{R}(Q)=\sum_{i=1}^{r}\text{d}_{\text{KT}}(Q,\pi_{i})$

where d${}_{\text{KT}}(\cdot,\cdot)$ is the Kendall-Tau distance – the number
of pairs of candidates whom the linear orders order differently – between two
linear orders, and $N_{R}(x>y)$ is the number of linear orders in $R$ where
$x$ is preferred over $y$. A Kemeny ranking of $R$ is a ranking $Q$ which has
the minimum $\text{Kemeny}_{R}(Q)$; the score $\text{Kemeny}_{R}(Q)$ is called
the optimal Kemeny score of $R$.

We now define our problems formally. For a set of rankings $\Pi$, we denote
the set of (optimal) Kemeny rankings and rankings with Kemeny score at most
some integer $k$ for $\Pi$ respectively by $K(\Pi)$ and $K(\Pi,k)$, and the
minimum Kemeny score by $k_{\text{OPT}}(\Pi)$.

###### Definition 1

(Distinct OPT Kemeny Ranking Aggregation). Given a set of rankings (complete
orders) $\Pi$ over a set of candidates $\mathcal{C}$ and integer $r$, compute
$\ell=\min\\{r,|K(\Pi)|\\}$ distinct Kemeny rankings
$\pi_{1},\ldots,\pi_{\ell}$. We denote an arbitrary instance of it by
$(\mathcal{C},\Pi,r)$.

For a set of rankings $\Pi$ over a set of candidates $\mathcal{C}$, we say
that a complete order $\pi$ respects unanimity order if we have
$x\succ_{\pi}y$ whenever $x\succ y$ for all $\succ\in\Pi$.

###### Definition 2

(Distinct approximate Kemeny Ranking Aggregation). Given a set of ranking
(complete order) $\Pi$ over a set of candidates $\mathcal{C}$, an
approximation factor $\lambda\geq 1$, and integer $r$, compute
$\ell=\min\\{r,|K(\Pi,\lambda\cdot k_{\text{OPT}}(\Pi))|\\}$ distinct rankings
$\pi_{1},\ldots,\pi_{\ell}$ such that each ranking $\pi_{i},i\in[\ell]$
respects unanimity order with respect to $\Pi$ and the Kemeny score of each
ranking $\pi_{i},i\in[\ell]$ is at most $\lambda\cdot k_{\text{OPT}}(\Pi)$. We
denote an arbitrary instance of it by $(\mathcal{C},\Pi,\lambda,r)$.

###### Definition 3

(Distinct Kemeny Ranking Aggregation). Given a list of partial votes $\Pi$
over a set of candidates $\mathcal{C}$, and integers $k$ and $r$, compute
$\ell=\min\\{r,|K(\Pi,k)|\\}$ distinct rankings $\pi_{1},\ldots,\pi_{\ell}$
such that the Kemeny score for each ranking $\pi_{i}$ is at most $k$ and each
$\pi_{i},i\in[\ell]$ respects unanimity order? We denote an arbitrary instance
of it by $(\mathcal{C},\Pi,k,r)$.

We use $\mathcal{O}^{*}(\cdot)$ to hide polynomial factors. That is, we denote
$\mathcal{O}(f(k)\text{poly}(n))$ as $\mathcal{O}^{*}(f(k))$ where $n$ is the
input size.

We define a path decomposition of a graph $G=\left(V,E\right)$ by a tuple
$\mathcal{P}=\left(\mathcal{B}_{i}\right)_{i\in\left[t\right]}$ where each bag
$\mathcal{B}_{i}\subseteq V$, $t$ is the number of bags in $\mathcal{P}$ and
$\mathcal{P}$ satisfies the following additional constraints : (1)
$\bigcup_{i\in\left[t\right]}\mathcal{B}_{i}=V$, (2) $\exists
i\in\left[t\right]$ such that $u,v\in\mathcal{B}_{i}~{}\text{for each
}\left(u,v\right)\in E$ and (3)
$\mathcal{B}_{i}\cap\mathcal{B}_{k}\subseteq\mathcal{B}_{j}$ for each
$i,j,k\in\left[t\right]$ satisfying $i<j<k$. The width of $\mathcal{P}$
denoted by $w\left(\mathcal{P}\right)$ is defined as
$\max_{i\in\left[t\right]}|\mathcal{B}_{i}|-1$. The $pathwidth$ of $G$ is
denoted by $pw\left(G\right)$ which is defined as the minimum width of a path
decomposition of $G$.

For a dispersion parameter $\theta>0$ and a central ordering $\pi_{0}$ of a
set $\mathcal{C}$ of candidates, the _Mallows model_ associates the following
probability mass with each ordering $\pi$ of $\mathcal{C}$:

$\frac{e^{-\theta\cdot\big{(}\mbox{d}_{\text{KT}}(\pi,\pi_{0})\big{)}}}{\underset{\tiny{\begin{subarray}{c}\sigma:\sigma\in\mathcal{L}(\mathcal{C})\end{subarray}}}{\Sigma}e^{-\theta\cdot\big{(}\mbox{d}_{\text{KT}}(\sigma,\pi_{0})\big{)}}}.$

##  3 Parameters and Experiments

| range | average KT distance | unanimity width | blocking size | distance to consensus
---|---|---|---|---|---
range |  |  $\star$ $\dagger$ |  $\geq$ $\dagger$ |  $\star$ $\dagger$ |  $\leq$ $\star$
average KT distance |  |  |  $\star$ $\dagger$ |  $\star$ $\dagger$ |  $\leq$ $\star$
unanimity width |  |  |  |  $\geq$ $\dagger$ |  $\leq$ $\star$
blocking size |  |  |  |  |  $\leq$ $\star$
distance to consensus |  |  |  |  |
Table 1: Relationships between parameters. Read the entries in the table as
follows: the row label, followed by the entry, followed by the column label. A
“$\star$” is to be read as “can be arbitrarily smaller than”; while a
“$\dagger$” is to be read as “can be arbitrarily larger than”. The signs are
to be read as is, but is a slight abuse of notation in the sense that there
may be constant factors involved in the inequalities.
$1.5$$3$$5$$8$$0$$1$$2$$3$$4$$5$$6$$13$$14$$15$$\theta~{}\rightarrow$average
values of the parameters$~{}\rightarrow$maximum rangeaverage KT-
distanceunanimity widthblocking sizedistance to consensus Figure 1: This plot
illustrates that for $200$ votes and $10$ candidates, the average (over $20$
samples) values of the parameters drop with increase in $\theta$.

The parameter comparisons are summarized in Table 1. Here we briefly justify
the claims implicit to Table 1, noting that the incomparability of range and
average KT distance was established already in [BFG+09], and we do not repeat
those examples here. The following constructions imply the remaining claims.

Let $p$ be an integer. Consider a profile with $2p$ candidates, say
$c_{1},\ldots,c_{p},d_{1},\ldots,d_{p}$. We have two votes:
$c_{1}>\cdots>c_{p}>d_{1}>\cdots>d_{p}$, and
$d_{1}>\cdots>d_{p}>c_{1}>\cdots>c_{p}$. Note that the complement of the
unanimity graph is a complete bipartite graph, with each part having size $p$.
Here, the unanimity width is $p$, the range is $p$, the distance to consensus
is $p^{2}$, but the blocking size is $2$. This shows that the blocking size
can be arbitrarily smaller than these remaining parameters.

Consider a profile with two votes $a>b>c>d>\cdots$ and $b>a>d>c>\cdots$; i.e,
where consecutive candidates are swapped. The complement of the unanimity
graph is a matching on $m/2$ edges, the average KT distance is $m/2$, while
the range is $2$ and the unanimity width is $1$.

Consider a profile where a particular vote is repeated $(n-1)$ times and the
last vote is the reversal of the common vote. This profile has constant
average KT distance, but all remaining parameters are functions of $m$.

Next, we turn to the bounds. Note that the claim that the consensus distance
is an upper bound for the blocking size and unanimity width follows directly
from graph-theoretic definitions. Further, the claim that is an upper bound
for the average KT distance follows from the fact that the average KT distance
is at least the minimum KT distance, which is witnessed by some specific pair
of votes: but these manifest directly as edges in the complement of the
unanimity graph.

The claim that the distance to consensus is an upper bound for the maximum
range follows from the fact that if the maximum range is $r$, then there are
at least $r$ non-unanimous pairs in the profile, each of which contributes an
edge to the complement of the unanimity graph. The fact that the unanimity
width is at least the blocking size is also a standard graph-theoretic fact
(the pathwidth is lower bounded by the clique size). The fact that the
pathwidth is upper bounded by the range can be observed by constructing an
appropriate path decomposition over $m$ bags, where the $i$-th bag contains
all candidates whose range contains the $i$-th position. It is easily verified
that this is a valid path decomposition whose width is $O(r)$.

$10$$25$$50$$100$$200$$0$$1$$2$$3$$4$$5$$6$$13$$14$$15$number of
votes$~{}\rightarrow$average values of the parameters$~{}\rightarrow$maximum
rangeaverage KT-distanceunanimity widthblocking sizedistance to consensus
Figure 2: This plot illustrates that for $\theta=1.5$ and $10$ candidates, the
average (over $20$ samples) values of the parameters do not change much with
increase in the number of votes.

#### Experimental Setup.

We computed the values of the five parameters, namely (a) maximum range, (b)
average KT distance, (c) unanimity width, (d) blocking size, and (e) consensus
distance, on profiles with 10 candidates and 10, 25, 50, 100, and 200 voters.
We used two inbuilt functions of SageMath, namely clique_number() and
treewidth(), to compute blocking size and unanimity width respectively. The
remaining parameters were computed with a direct implementation.

Each value reported is averaged over 20 samples. We also varied the dispersion
parameter between the values 1.5, 3, 5, and 8. Our main observation from the
empirical data was twofold: first, the values of all parameters dropped as we
increased the dispersion parameter, which is as one would expect, since a
higher dispersion parameter gives us more homogeneous profiles (cf. Figure 1);
and second, for a fixed dispersion parameter, the values of the parameters did
not change much between small and large profiles (i.e, variations in the
number of votes did not lead to large variations in the parameter, cf. Figure
2).

#Voters | 10 | 25 | 50 | 100 | 200
---|---|---|---|---|---
maximum range | 5.700 | 5.100 | 5.250 | 5.150 | 5.200
average Kendall-Tau distance | 4.170 | 4.014 | 4.316 | 3.997 | 4.207
unanimity width | 2.500 | 2.500 | 2.700 | 2.400 | 2.350
blocking size | 3.350 | 3.350 | 3.500 | 3.300 | 3.300
distance to consensus | 14.400 | 13.550 | 14.400 | 13.350 | 14.050
Table 2: The values of the parameters we consider for $\theta=1.5$. #Voters | 10 | 25 | 50 | 100 | 200
---|---|---|---|---|---
maximum range | 3.050 | 2.950 | 2.850 | 2.850 | 2.500
average Kendall-Tau distance | 1.028 | 0.883 | 0.863 | 0.896 | 0.741
unanimity width | 1.300 | 1.150 | 1.150 | 1.050 | 0.950
blocking size | 2.300 | 2.150 | 2.150 | 2.050 | 1.950
distance to consensus | 4.650 | 3.950 | 3.750 | 3.850 | 3.000
Table 3: The values of the parameters we consider for $\theta=3$. #Voters | 10 | 25 | 50 | 100 | 200
---|---|---|---|---|---
maximum range | 1.650 | 1.700 | 1.600 | 1.650 | 1.500
average Kendall-Tau distance | 0.130 | 0.180 | 0.166 | 0.168 | 0.130
unanimity width | 0.650 | 0.550 | 0.600 | 0.650 | 0.500
blocking size | 1.650 | 1.550 | 1.600 | 1.650 | 1.500
distance to consensus | 0.650 | 0.900 | 0.750 | 0.800 | 0.650
Table 4: The values of the parameters we consider for $\theta=5$. #Voters | 10 | 25 | 50 | 100 | 200
---|---|---|---|---|---
maximum range | 1.000 | 1.050 | 1.050 | 1.150 | 1.000
average Kendall-Tau distance | 0.000 | 0.010 | 0.010 | 0.030 | 0.000
unanimity width | 0.000 | 0.050 | 0.050 | 0.150 | 0.000
blocking size | 1.000 | 1.050 | 1.050 | 1.150 | 1.000
distance to consensus | 0.000 | 0.050 | 0.050 | 0.150 | 0.000
Table 5: The values of the parameters we consider for $\theta=8$.

##  4 Algorithms for Distinct Kemeny Ranking Aggregation

We start with an easy Turing reduction from Distinct OPT Kemeny Ranking
Aggregation to Distinct Kemeny Ranking Aggregation.

###### Observation 1

Suppose there exists an algorithm for Distinct Kemeny Ranking Aggregation
running in time $\mathcal{O}(f(m,n))$. Then there exists an algorithm for
Distinct OPT Kemeny Ranking Aggregation running in time
$\mathcal{O}(f(m,n)\log(mn))$.

Proof. We note that the optimal Kemeny score belongs to the set
$\\{0,1,\ldots,n{m\choose 2}\\}$. To solve Distinct OPT Kemeny Ranking
Aggregation, we perform a binary search in the range from $0$ to $n{m\choose
2}$ to find the smallest $k$ such that the algorithm for Distinct Kemeny
Ranking Aggregation returns at least one ranking. $\square$

We now present a bounded search based $\mathsf{FPT}$ algorithm for Distinct
Kemeny Ranking Aggregation parameterized by the optimal Kemeny score. Hence,
we also have an $\mathsf{FPT}$ algorithm for Distinct OPT Kemeny Ranking
Aggregation parameterized by the optimal Kemeny score.

###### Theorem 1

Let $k$ be the Kemeny score of a Kemeny ranking. There is an $\mathsf{FPT}$
algorithm for Distinct Kemeny Ranking Aggregation parameterized by $k$ which
runs in time $\mathcal{O}^{*}\left(2^{k}\right)$. Hence, we have an
$\mathsf{FPT}$ algorithm for Distinct OPT Kemeny Ranking Aggregation
parameterized by $k_{\text{OPT}}$ which runs in time
$\mathcal{O}^{*}\left(2^{k_{\text{OPT}}}\right)$.

Proof. Due to 1, it is enough to present an algorithm for Distinct Kemeny
Ranking Aggregation. We design an algorithm for a more general problem
Distinct Kemeny Ranking Aggregation′ where every output ranking needs to
respect the relative order of some set of pair of candidates given as input.
If the set of pairs of candidates is empty, then the new problem is the same
as Distinct Kemeny Ranking Aggregation.

Let $(\mathcal{C},\Pi,k,r)$ be an arbitrary instance of Distinct Kemeny
Ranking Aggregation. We define $\mathcal{X}=\\{a>b:a,b\in\mathcal{C},\text{
every ranking in }\Pi\text{ prefers }a\text{ over }b\\}$ to be the unanimity
order of $\Pi$. We find a solution of Distinct Kemeny Ranking Aggregation′
instance $(\mathcal{C},\Pi,k,r,\mathcal{X})$. We now design a bounded search
based algorithm. We maintain a set SSof solutions, which is initialized to the
empty set. If every pair of candidates belong to $\mathcal{X}$ and $k\geq 0$,
then we put the ranking induced by $\mathcal{X}$ in SS. If $k<0$, then we
discard this branch. Otherwise, we pick a pair $(a,b)$ of candidates not
present in $\mathcal{X}$, solve $(\mathcal{C},\Pi,k-|\\{\pi\in\Pi:~{}b\succ
a\text{ in }\pi\\}|,r,\text{transitive closure of }\mathcal{X}\cup\\{a>b\\})$
and $(\mathcal{C},\Pi,k-|\\{\pi\in\Pi:~{}a\succ b\text{ in
}\pi\\}|,r,\text{transitive closure of }\mathcal{X}\cup\\{b>a\\})$
recursively, and put solutions found in SS. We note that, since $(a,b)$ is not
a unanimous order of $\Pi$, the target Kemeny score $k$ decreases by at least
one on both the branches of the search tree. Hence, the height of the search
tree is at most $k$. Thus, the number of leaves and nodes in the search tree
are at most respectively $2^{k}$ and $2\cdot 2^{k}$. After the search
terminates, we output $\min\\{r,|\SS|\\}$ rankings from SS. If SSremains empty
set, report that there is no ranking whose Kemeny score is at most $k$. The
computation at each node of the search tree (except the recursive calls)
clearly takes a polynomial amount of time. Hence, the runtime of our algorithm
is $\mathcal{O}^{*}\left(2^{k}\right)$. The correctness of our algorithm
follows from the observation that every ranking $R$ whose Kemeny score is at
most $k$, appears in a leaf node of the search tree of our algorithm. This
also follows from Section 4.2 of [BFG+09]. $\square$

Running the algorithm in Theorem 1 with target Kemeny score $\lambda k$ where
$k$ is the optimal Kemeny score gives us the following result.

###### Corollary 1

There is an algorithm for Distinct approximate Kemeny Ranking Aggregation
running in time $\mathcal{O}^{*}\left(2^{\lambda k}\right)$ parameterized by
both $\lambda\text{ and }k$.

We now consider the number of candidates $m$ as our parameter and present a
dynamic programming based $\mathsf{FPT}$ algorithm for Distinct Kemeny Ranking
Aggregation.

###### Theorem 2

There is an algorithm for Distinct Kemeny Ranking Aggregation which runs in
time $\mathcal{O}^{*}\left(2^{m}r^{\mathcal{O}(1)}\right)$. In particular,
Distinct Kemeny Ranking Aggregation and Distinct OPT Kemeny Ranking
Aggregation are $\mathsf{FPT}$ parameterized by the number of candidates since
the number $r$ of output rankings can be at most $m!$.

Proof. Let $(\mathcal{C},\Pi,k,r)$ be an arbitrary instance of Distinct Kemeny
Ranking Aggregation. We maintain a dynamic programming table $\mathcal{T}$
indexed by the set of all possible non-empty subsets of $\mathcal{C}$. For a
subset $\SS\subseteq\mathcal{C},\SS\neq\emptyset$, the table entry
$\mathcal{T}[\SS]$ stores at most $\min\\{r,|\SS|!\\}$ distinct rankings on
SSwhich have the least Kemeny score when the votes are restricted to SS. Let
us define $\kappa=\min\\{r,|\SS|!\\}$. We initialize table $\mathcal{T}$ for
the trivial cases like $\mathcal{T}[\SS]=\left(\right)\text{ when
}|\SS|=0,~{}\mathcal{T}[\SS]=\left(\text{the element from }\SS\right)\text{
when }|\SS|=1\text{ and }\mathcal{T}[\SS]=\left(x\succ y\right)\text{ when
}\SS=\left\\{x,y\right\\}$ and $x\succ y$ has the least Kemeny score when
$\Pi$ is restricted to $\left\\{x,y\right\\}$ or
$\mathcal{T}[\SS]=\left(x\succ y,~{}y\succ x\right)\text{ when
}\SS=\left\\{x,y\right\\}$ and both $x\succ y$ and $y\succ x$ have the least
Kemeny score when $\Pi$ is restricted to $\left\\{x,y\right\\}$. To update the
table entry $\mathcal{T}[\SS]$ for $|\SS|\geq 3$, we include to that entry
$\min\\{r,|\SS|!\\}$ rankings that have the least Kemeny score (when the votes
are restricted to $\SS$) among all rankings of the form $c>\pi$, where $c$ is
a candidate in $\SS$ and $\pi$ is a ranking stored in
$\mathcal{T}[\SS\setminus\\{c\\}]$. Updating each table entry takes at most
$\mathcal{O}^{\star}(r^{\mathcal{O}(1)})$ time. As there are $2^{m}-1$ table
entries, the running time of our algorithm is at most
$\mathcal{O}^{\star}\big{(}2^{m}r^{\mathcal{O}(1)}\big{)}$.

We now present the proof of correctness of our algorithm. Suppose we have
$\SS=\\{c_{1},...,c_{\ell}\\}$ and $c_{1}>...>c_{\ell}$ be a ranking in
$\mathcal{T}[\SS]$. Then $c_{1}>...>c_{\ell}$ is a Kemeny ranking if the votes
in $\Pi$ are restricted to $\SS$. But then $c_{2}>...>c_{\ell}$ is a Kemeny
ranking if votes are restricted to $\SS\setminus\\{c_{1}\\}$. If not, then
suppose $c_{2}^{\prime}>...>c_{\ell}^{\prime}$ be a ranking with Kemeny score
less than $c_{2}>...>c_{\ell}$. Then the Kemeny score of
$c_{1}>c_{2}^{\prime}>...>c_{\ell}^{\prime}$ is less than the Kemeny score of
$c_{1}>c_{2}>...>c_{\ell}$ contradicting our assumption that
$c_{1}>...>c_{\ell}$ is a Kemeny ranking when votes are restricted to SS.
Hence, the update procedure of our dynamic programming algorithm is correct.
$\square$

Corollary 2 follows immediately from the algorithm presented in the proof of
Theorem 2.

###### Corollary 2

Distinct approximate Kemeny Ranking Aggregation is FPT parameterized by the
number of candidates $m$.

Proof. Consider an instance $(\mathcal{C},\Pi,\lambda,r)$ of Distinct
approximate Kemeny Ranking Aggregation. We run the algorithm of Theorem 2 on
instances $(\mathcal{C},\Pi,0,1),(\mathcal{C},\Pi,1,1)$, $\ldots$ of Distinct
Kemeny Ranking Aggregation. We stop once we encounter a YES instance, say
$(\mathcal{C},\Pi,k^{*},1)$. Note that $k^{*}$ is the optimum Kemeny score for
the election profile $(\mathcal{C},\Pi)$. Next, we run the algorithm of
Theorem 2 on the instance $(\mathcal{C},\Pi,\lambda\cdot k^{*},r)$ of Distinct
Kemeny Ranking Aggregation to get the desired output. As
$k^{*}\leq\binom{m}{2}\cdot|\Pi|$, the overall running time of the algorithm
is at most $\mathcal{O}^{*}\big{(}2^{m}r^{\mathcal{O}(1)}\big{)}$. So, as
$r\leq m!$, it follows that Distinct approximate Kemeny Ranking Aggregation is
FPT parameterized by the number of candidates $m$. $\square$

Our next parameter is the “average pairwise distance (Kendall-Tau distance)”
$d$ of the input rankings. We present a dynamic programming based
$\mathsf{FPT}$ algorithm parameterized by $d$.

###### Theorem 3

Let $d$ be the average KT-distance of an election
$\left(\Pi,\mathcal{C}\right)$. There is an $\mathsf{FPT}$ for Distinct OPT
Kemeny Ranking Aggregation parameterized by $d$ which runs in time
$\mathcal{O}^{\star}\left(16^{d}\right)$.

Proof. Let $|\mathcal{C}|=m,~{}|\Pi|=n\text{ and
}p_{avg}\left(c\right)\coloneqq\frac{1}{n}\cdot\sum\limits_{v\in\Pi}v(c)$
where $v(c)\coloneqq|\left\\{c^{\prime}\in\mathcal{C}:c^{\prime}\succ c\text{
in }v\in\Pi\right\\}|$. Formally for an election
$\left(\Pi,\mathcal{C}\right)$,
$d\coloneqq\frac{\sum\limits_{v\in\Pi}\sum\limits_{w\in\Pi}\text{d}_{\text{KT}}\left(v,w\right)}{n\cdot(n-1)}$.
Following the proof of both Lemma 6 and Lemma 7 from Betzler et al. [BFG+09],
we have a set of candidates say ${P_{i}}\coloneqq\left\\{c\in\mathcal{C}\mid
p_{avg}(c)-d<i<p_{avg}(c)+d\right\\}$ for each position
$i\in\left[m-1\right]_{0}$ in an optimal Kemeny Consensus and we know that
$|P_{i}|\leqslant 4d~{}~{}\forall i\in\left[m-1\right]_{0}$. Our FPT dynamic
programming algorithm is an extension of the algorithm presented in Fig. 4. of
section 6.4 of [BFG+09].

Let the subset of candidates that are forgotten at latest at position $i$, be
denoted by $F(i)\coloneqq P_{i-1}\setminus P_{i}$ and the subset of candidates
that are introduced for the first time at position $i$ be denoted by
$I(i)\coloneqq P_{i}\setminus P_{i-1}$. We maintain a three dimensional
dynamic programming table $\mathcal{T}$ indexed by $\forall
i\in\left[m-1\right]_{0},\forall\text{ }c\in P_{i}\text{ and }\forall
P_{i}^{\prime}\subseteq P_{i}\setminus\left\\{c\right\\}$ of size at most
$\mathcal{O}\left(16^{d}\cdot d\cdot m\right)$. We define the partial Kemeny
Score $\text{pK-
score}(c,\mathcal{R})\coloneqq\sum\limits_{c^{\prime}\in\mathcal{R}}\sum\limits_{v\in\Pi}d_{v}^{\mathcal{R}}(c,c^{\prime})$
where $d_{v}^{\mathcal{R}}(c,c^{\prime})\coloneqq 0\text{ if
}c\succ_{v}c^{\prime}\text{ and }d_{v}^{\mathcal{R}}(c,c^{\prime})\coloneqq
1\text{ otherwise}$ and $\mathcal{R}\subseteq\mathcal{C}$. At each table entry
$\mathcal{T}(i,c,P_{i}^{\prime})$, we store a sequence of at most
$\min\left(r,4d\right)$ number of partial Kemeny Scores sorted in non-
decreasing order by considering and iterating over the entries in
$\mathcal{T}(i-1,c^{\prime},(P_{i}^{\prime}\cup
F(i))\setminus\left\\{c^{\prime}\right\\})$ $\forall c^{\prime}\in
P_{i}^{\prime}\cup F(i)$ and we store the tuple

$\biggl{(}\mathcal{T}(i-1,c^{\prime},(P_{i}^{\prime}\cup
F(i))\setminus\left\\{c^{\prime}\right\\})$ $+\text{pK-
score}(c,(P_{i}\cup\bigcup\limits_{i<j<m}I(j))\setminus(P_{i}^{\prime}\cup\left\\{c\right\\}))\biggl{)}_{c^{\prime}\in
P_{i}^{\prime}\cup F(i)}$

in that table entry unlike storing only the minimum partial Kemeny Score at
each table entry. K-score of an election is the Kemeny Score of an optimal
Kemeny ranking.
$\text{K-score}(\Pi,\mathcal{C})=\sum\limits_{i=0}^{m-2}\text{pK-
score}(c_{i},\mathcal{R}_{i})$.

At each entry of the table candidate $c$ takes position $i$ and all of
$P_{i}^{\prime}$ take position smaller than $i$. The initialization step is
same as the algorithm presented in Fig. 4. of section 6.4 of [BFG+09] but the
difference lies in the update step of that algorithm. Though we are storing
Kemeny score in each table entry, we can enumerate Kemeny ranking(s) from them
within asymptotic bound of our current run time by iteratively ordering the
candidate(s) for which we get minimum partial Kemeny Score in a particular
table entry. We Output first $r$ number of optimal Kemeny rankings whose
K-scores are stored in the entry $T(m-1,c,P_{m-1}\setminus\left\\{c\right\\})$
where $r\leqslant 4d\leqslant 4m^{2}<<m!$. Correctness of Lemma 8 of [BFG+09]
ensures the correctness of our algorithm for generating at most
$min\left(r,4d\right)$ number of optimal Kemeny Rankings.

Updating each table entry takes time at most $\min(r,4d)\cdot(4d+nm\log m)$
time. Hence, the overall runtime is bounded above by
$\mathcal{O}^{\star}\left(16^{d}\right)$. $\square$

We next consider the “maximum range" $r_{max}$ of candidate positions in the
input rankings, as our parameter. We again present a dynamic programming based
$\mathsf{FPT}$ algorithm parameterized by $r_{max}$.

###### Theorem 4

Let $r_{max}$ be the maximum candidate position range of an election
$\left(\Pi,\mathcal{C}\right)$. There exists an $\mathsf{FPT}$ dynamic
programming algorithm for Distinct OPT Kemeny Ranking Aggregation
parameterized by $r_{max}$ which runs in time
$\mathcal{O}^{*}\left(32^{r_{max}}\right)$.

Proof. Following the proof of both Lemma 9 and Lemma 10 from [BFG+09], we have
here $|P_{i}|\leqslant 6r_{max}$. We maintain a dynamic programming table
$\mathcal{T}$ of size $\mathcal{O}\left(32^{r_{max}}\cdot r_{max}\cdot
m\right)$ indexed by $\forall i\in\left[m-1\right]_{0},\forall\text{ }c\in
P_{i}\text{ and }\forall P_{i}^{\prime}\subseteq
P_{i}\setminus\left\\{c\right\\}$. The proof of Theorem 4 follows immediately
from a complete analogy to the proof of Theorem 3. $\square$

Our final parameter is the unanimity width of the input rankings. We present a
dynamic programming based $\mathsf{FPT}$ algorithm.

###### Theorem 5

Distinct OPT Kemeny Rank Aggregation admits an $\mathsf{FPT}$ algorithm in the
combined parameter unanimity width $w$ and number of rankings $r$, which runs
in time $\mathcal{O}^{*}\big{(}2^{\mathcal{O}(w)}\cdot r\big{)}$.

Proof. The problem of finding a Kemeny consensus is known to admit an FPT
algorithm in the parameter $w$ (Section 3, [AFdOOW20]). We adapt this
algorithm to prove Theorem 5. Consider an instance $(\mathcal{C},\Pi,r)$ of
Distinct OPT Kemeny Ranking Aggregation. Let $m$ denote the number of
candidates in $\mathcal{C}$, and let $n$ denote the number of voters in $\Pi$.
For any candidates $a,b\in\mathcal{C}$, let $cost(a,b)$ denote the number of
voters in $\Pi$ who prefer $b$ over $a$. Note that for any linear ordering
$\pi$ of candidates, $\text{Kemeny}_{\Pi}(\pi)=\sum_{a,b\in\mathcal{C}:a\succ
b\text{ in }\pi}cost(a,b)$. Let $\rho$ denote the unanimity order of $\Pi$.
Let $G_{\rho}$ denote the cocomparability graph of $\rho$. Using Lemma 3 of
[AFL+21], let’s construct a nice $\rho$-consistent path decomposition, say
$\mathcal{P}=(B_{1},\ldots,B_{2m}),$ of $G_{\rho}$ of width $w^{\prime}\leq
5w+4$ in time $\mathcal{O}\big{(}2^{\mathcal{O}(w)}\cdot m\big{)}$.

For each $1\leq i\leq 2m$,

  * •

Let $forg(i)$ denote the set of candidates that have been forgotten up to
$i^{th}$ bag. That is, $forg(i)=\big{(}B_{1}\cup\ldots\cup
B_{i-1}\big{)}\setminus B_{i}$.

  * •

For each candidate $v\in B_{i}$, let $\mathcal{A}(i,v)$ denote the cost
incurred by the virtue of placing all candidates of $forg(i)$ before $v$. That
is, $\mathcal{A}(i,v)=\underset{u\in forg(i)}{\sum}cost(u,v)$.

  * •

For each candidate $v\in B_{i}$ and each $T\subseteq B_{i}\setminus\\{v\\}$,
let $\mathcal{B}(i,v,T)$ denote the cost incurred by the virtue of placing all
candidates of $T$ before $v$. That is, $\mathcal{B}(i,v,T)=\underset{u\in
T}{\sum}cost(u,v)$.

  * •

For each $T\subseteq B_{i}$, let $C(i,T)$ be a set that consists of first
$min\big{(}r,|forg(i)\uplus T|!\big{)}$ orderings, along with their Kemeny
scores, if all linear extensions of $\rho$ on $forg(i)\uplus T$ were to be
sorted in ascending order of their Kemeny scores. That is, $C(i,T)$ consists
of the tuples $(\pi_{1},k_{1}),(\pi_{2},k_{2}),\ldots$, where
$\pi_{1},\pi_{2},\ldots$ are the first $min\big{(}r,|forg(i)\uplus T|!\big{)}$
orderings in the sorted order, and $k_{1},k_{2},\ldots$ are their respective
Kemeny scores.

Recall that every Kemeny consensus extends $\rho$ (Lemma 1, [BFG+09]). So, if
all linear extensions of $\rho$ on $\mathcal{C}$ were to be sorted in
ascending order of their Kemeny scores, then all Kemeny consensuses would
appear in the beginning. Thus, $(\mathcal{C},\Pi,r)$ is a YES instance if and
only if $C(2m,\phi)$ contains $r$ orderings of the same Kemeny score.

Let’s use DP to find all $\mathcal{A}(\cdot,\cdot)$’s,
$\mathcal{B}(\cdot,\cdot,\cdot)$’s and $C(\cdot,\cdot)$’s as follows:

  * •

First, let’s compute and store $\mathcal{A}(i,\cdot)$’s in a table for
$i=1,\ldots,2m$ (in that order) in time $\mathcal{O}\big{(}w^{\prime}\cdot
m\cdot\log(m\cdot n)\big{)}$ as follows: We set $\mathcal{A}(1,u)=0$, where
$u$ denotes the candidate introduced by $B_{1}$. Now, consider $i\geq 2$ and a
candidate $v\in B_{i}$. Let’s describe how to find $\mathcal{A}(i,v)$.

Introduce node.
Suppose that $B_{i}$ introduces a candidate, say $x$. Note that
$forg(i)=forg(i-1)$. So, if $v\neq x$, we set
$\mathcal{A}(i,v)=\mathcal{A}(i-1,v)$. Now, suppose that $v=x$. Let’s show
that $cost(u,x)=0$ for all $u\in forg(i)$. Consider $u\in forg(i)$. In
$\mathcal{P}$, $u$ is forgotten before $x$ is introduced. So,
$\\{u,x\\}\not\in E(G_{\rho})$. That is, $u$ and $x$ are comparable in $\rho$.
Also, due to $\rho$-consistency of $\mathcal{P}$, we have $(x,u)\not\in\rho$.
Therefore, $(u,x)\in\rho$. That is, all voters in $\Pi$ prefer $u$ over $x$.
So, $cost(u,x)=0$. Thus, we set $\mathcal{A}(i,x)=0$.

Forget node.
Suppose that $B_{i}$ forgets a candidate, say $x$. Note that
$forg(i)=forg(i-1)\uplus\\{x\\}$. So, we set
$\mathcal{A}(i,v)=\mathcal{A}(i-1,v)+cost(x,v)$.

  * •

Next, let’s compute and store all $\mathcal{B}(\cdot,\cdot,\cdot)$’s in a
table in time $\mathcal{O}\big{(}w^{\prime}\cdot 2^{w^{\prime}}\cdot
m\cdot\log(m\cdot n)\big{)}$ as follows: Consider $1\leq i\leq 2m$ and $v\in
B_{i}$. We have $\mathcal{B}(i,v,\phi)=0$. Let’s set $\mathcal{B}(i,v,T)$ for
non-empty subsets $T\subseteq B_{i}\setminus\\{v\\}$ (in ascending order of
their sizes) as $\mathcal{B}(i,v,T\setminus\\{u\\})+cost(u,v)$, where $u$
denotes an arbitrary candidate in $T$.

  * •

Next, let’s compute and store $C(i,\cdot)$’s in a table in time
$\mathcal{O}\big{(}w^{\prime}\cdot 2^{w^{\prime}}\cdot m^{2}\cdot
r\cdot\log(m\cdot n\cdot r)\big{)}$ for $i=1,\ldots,2m$ (in that order) as
follows: We set $C(1,\phi)=\\{(,0)\\}$ and $C(1,\\{u\\})=\\{(u,0)\\}$, where
$u$ denotes the candidate introduced by $B_{1}$. Now, consider $i\geq 2$.
Let’s describe how to find $C(i,\cdot)$’s.

Introduce node.
Suppose that $B_{i}$ introduces a candidate, say $x$. For each $T\subseteq
B_{i}$ that does not contain $x$, we set $C(i,T)=C(i-1,T)$.

Now, let’s find $C(i,T)$ for all subsets $T\subseteq B_{i}$ that contain $x$
(in ascending order of their sizes) as follows: First, let’s consider
$T=\\{x\\}$. Recall that $(u,x)\in\rho$ for all $u\in forg(i)$. So, $x$ is the
last candidate in all linear extensions of $\rho$ on $forg(i)\uplus\\{x\\}$.
Also, in any such ordering, the pairs of the form $(u,x)$, where $u\in
forg(i)$, contribute $0$ to Kemeny score. Thus, we put the tuples
$\big{(}\pi_{1}>x,s_{1}\big{)},\big{(}\pi_{2}>x,s_{2}\big{)},\ldots$ in
$C(i,\\{x\\})$, where $(\pi_{1},s_{1}),(\pi_{2},s_{2}),\ldots$ denote the
tuples of $C(i-1,\phi)$, and $\pi_{1}>x,\pi_{2}>x,\ldots$ denote the orderings
obtained by appending $x$ to $\pi_{1},\pi_{2},\ldots$ respectively.

Now, let’s consider a subset $T\subseteq B_{i}$ of size $\geq 2$ that contains
$x$. Let’s describe how to find $C(i,T)$. Let $\Delta(i,T)$ denote the set of
all candidates $c\in T$ such that $c$ is not unanimously preferred over any
other candidate of $forg(i)\uplus T$. That is, there is no other candidate
$u\in forg(i)\uplus T$ such that $(c,u)\in\rho$. Recall that $x$ appears after
all candidates of $forg(i)$ in any linear extension of $\rho$ on
$forg(i)\uplus T$. So, it is clear that in any such ordering, the last
candidate (say $y$) belongs to $\Delta(i,T)$. Moreover,

    * –

The pairs of the form $(u,y)$, where $u\in forg(i)$, together contribute
$\mathcal{A}(i,y)$ to Kemeny score.

    * –

The pairs of the form $(u,y)$, where $u\in T\setminus\\{y\\}$, together
contribute $\mathcal{B}(i,y,T\setminus\\{y\\})$ to Kemeny score.

So, to find $C(i,T)$, let’s proceed as follows: We compute $\Delta(i,T)$. For
each possible choice $y\in\Delta(i,T)$ of the last candidate, let’s form a
set, say $\Gamma(y)$, that consists of the following tuples:

    * –

$\Big{(}\pi_{1}^{y}>y,s_{1}^{y}+\mathcal{A}(i,y)+\mathcal{B}\big{(}i,y,T\setminus\\{y\\}\big{)}\Big{)}$

    * –

$\Big{(}\pi_{2}^{y}>y,s_{2}^{y}+\mathcal{A}(i,y)+\mathcal{B}\big{(}i,y,T\setminus\\{y\\}\big{)}\Big{)}$
and so on

where $(\pi_{1}^{y},s_{1}^{y}),(\pi_{2}^{y},s_{2}^{y}),\ldots$ denote the
tuples of $C(i,T\setminus\\{y\\})$, and $\pi_{1}^{y}>y,\pi_{2}^{y}>y,\ldots$
denote the orderings obtained by appending $y$ to
$\pi_{1}^{y},\pi_{2}^{y},\ldots$ respectively. Finally, let’s sort all tuples
of $\underset{y\in\Delta(i,T)}{\biguplus}\Gamma(y)$ in ascending order of
their Kemeny scores, and put the first $min\big{(}r,|forg(i)\uplus T|!\big{)}$
of them in $C(i,T)$.

Forget node.
Suppose that $B_{i}$ forgets a candidate, say $x$. For each $T\subseteq
B_{i}$, as $forg(i)\uplus T=forg(i-1)\uplus\big{(}T\uplus\\{x\\}\big{)}$, we
set $C(i,T)=C(i-1,T\uplus\\{x\\})$.

This concludes the proof of Theorem 5. $\square$

###### Corollary 3

Distinct approximate Kemeny Ranking Aggregation is FPT in the combined
parameter unanimity width $w$ and number of rankings $r$.

Proof. Consider an instance Distinct approximate Kemeny Ranking Aggregation.
As in the algorithm described in the proof of Theorem 5, we find all
$\mathcal{A}(\cdot,\cdot)$’s, $\mathcal{B}(\cdot,\cdot,\cdot)$’s and
$C(\cdot,\cdot)$’s. Note that $(\mathcal{C},\Pi,\lambda,r)$ is a YES instance
if and only if $C(2m,\phi)$ contains $r$ orderings, and the Kemeny score of
the $r^{th}$ ordering is at most $\lambda$ times the Kemeny score of the first
ordering. The overall running time of the algorithm is at most
$\mathcal{O}^{*}\big{(}2^{\mathcal{O}(w)}\cdot r\big{)}$. This proves
Corollary 3. $\square$

Our last result is an $\mathsf{FPT}$ algorithm for Distinct approximate Kemeny
Ranking Aggregation parameterized by the average Kendall-Tau distance $d$ and
the approximation parameter $\lambda$. Here we aim to relate the position of a
candidate $c$ in a $\lambda$-approximate ranking $\pi$, i.e. a ranking whose
Kemeny Score denoted by $\text{K-score}\left(\pi\right)$ has value at most
$\lambda\cdot k_{OPT}\text{ where }k_{OPT}$ denotes the optimal Kemeny Score,
to its average position in the set of votes $\Pi$ denoted by $p_{avg}(c)$. Our
resulting Lemma 1 depends on Lemma 6 from [BFG+09].

######  Lemma 1 ($\star$)

$p_{avg}(c)-\lambda\cdot d\leq\pi(c)\leq p_{avg}(c)+\lambda\cdot d$ where
$\pi(c)$ denotes position of $c$ in $\pi$ and $d$ is average KT-distance.

Proof. There can be two cases for a vote $v\in\Pi$.

###### Case 1

$v(c)\leq\pi(c)$

In 1 there are $\pi(c)-1$ candidates that appear before $c$ in $\pi$. Note
that at most $v(c)-1$ of them can appear before $c$ in $v$. Hence, at least
$\pi(c)-v(c)$ of them must appear after $c$ in $v$. Thus,
$\text{d}_{\text{KT}}\left(v,\pi\right)\geq\pi(c)-v(c)$.

###### Case 2

$v(c)>\pi(c)$

Here in 2, we come up with $\text{d}_{\text{KT}}\left(v,\pi\right)\geq
v(c)-\pi(c)$ arguing similarly to 1.

$\displaystyle\text{K-score}\left(\pi\right)=\sum\limits_{v\in\Pi}\text{d}_{\text{KT}}(v,\pi)$
$\displaystyle=\sum\limits_{v\in\Pi:v(c)\leq\pi(c)}\text{d}_{\text{KT}}(v,\pi)+\sum\limits_{v\in\Pi:v(c)>\pi(c)}\text{d}_{\text{KT}}(v,\pi)$
$\displaystyle\geq\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)\leq\pi(c)\end{subarray}}\left(\pi(c)-v(c)\right)+\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)>\pi(c)\end{subarray}}\left(v(c)-\pi(c)\right)~{}~{}~{}\left[\text{using
}\lx@cref{creftypecap~refnum}{case:v(c)_le_pi(c)}\text{ and
}\lx@cref{creftypecap~refnum}{case:v(c)_grt_pi(c)}\right]$ (1)

Note that

$\displaystyle\sum\limits_{v\in\Pi:v(c)\leq\pi(c)}\left(\pi(c)-v(c)\right)+\sum\limits_{v\in\Pi:v(c)>\pi(c)}\left(v(c)-\pi(c)\right)$
$\displaystyle=\sum\limits_{v\in\Pi}v(c)-2\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)\leq\pi(c)\end{subarray}}v(c)+\pi(c)\cdot\left(2\cdot|\left\\{v\in\Pi:v(c)\leq\pi(c)\right\\}|-n\right)$
$\displaystyle=n\cdot
p_{avg}(c)-n\pi(c)-2\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)\leq\pi(c)\end{subarray}}v(c)+\pi(c)\cdot\left(2\cdot|\left\\{v\in\Pi:v(c)\leq\pi(c)\right\\}|\right)$
$\displaystyle\geq n\left(p_{avg}(c)-\pi(c)\right)$ (2)

Similarly,

$\displaystyle\sum\limits_{v\in\Pi:v(c)\leq\pi(c)}\left(\pi(c)-v(c)\right)+\sum\limits_{v\in\Pi:v(c)>\pi(c)}\left(v(c)-\pi(c)\right)$
$\displaystyle=-\sum\limits_{v\in\Pi}v(c)+2\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)>\pi(c)\end{subarray}}v(c)+\pi(c)\cdot\left(-2\cdot|\left\\{v\in\Pi:v(c)>\pi(c)\right\\}|+n\right)$
$\displaystyle=-n\cdot
p_{avg}(c)+n\pi(c)+2\sum\limits_{\begin{subarray}{c}v\in\Pi:\\\
v(c)>\pi(c)\end{subarray}}v(c)-\pi(c)\cdot\left(2\cdot|\left\\{v\in\Pi:v(c)>\pi(c)\right\\}|\right)$
$\displaystyle\geq-n\left(p_{avg}(c)-\pi(c)\right)$ (3)

Now let’s show that

$\text{K-score}\left(\pi\right)\leq\lambda\cdot n\cdot d$ (4)

We have

$\displaystyle d$
$\displaystyle=\frac{\sum\limits_{v\in\Pi}\sum\limits_{w\in\Pi}\text{d}_{\text{KT}}\left(v,w\right)}{n\cdot(n-1)}$
$\displaystyle d$ $\displaystyle\geq\frac{n\cdot\sum\limits_{w\in\Pi,w\neq
v^{\star}}\text{d}_{\text{KT}}\left(v^{\star},w\right)}{n\cdot\left(n-1\right)}>\frac{\sum\limits_{w\in\Pi,w\neq
v^{\star}}\text{d}_{\text{KT}}\left(v^{\star},w\right)}{n}$
$\displaystyle\left[\exists v^{\star}\in\Pi\text{ for which
}\sum\limits_{w\in\Pi,w\neq
v^{\star}}\text{d}_{\text{KT}}\left(v^{\star},w\right)\text{ is minimum
}\right]$ $\displaystyle\implies\text{ K-score}\left(v^{\star}\right)<n\cdot
d$ $\displaystyle\text{So,
}k_{OPT}\leq\text{K-score}\left(v^{\star}\right)<n\cdot d$ (5)
$\displaystyle\text{K-score}\left(\pi\right)\leq\lambda\cdot
k_{OPT}<\lambda\cdot n\cdot d~{}\left[\text{Using
\lx@cref{creftypecap~refnum}{eqn:k_OPT_n_d}}\right]$ (6) Equation 6 proves
Equation 4 $\displaystyle\text{Now }\lambda\cdot n\cdot
d\geq\text{K-score}\left(\pi\right)\geq n\cdot\left(p_{avg}(c)-\pi(c)\right)$
$\displaystyle\left[\text{Using \lx@cref{creftypecap~refnum}{eqn:1_K-score-
pi_ge_pi_c-v_c}, (\ref{eqn:2_sum_pi_c-v_c_ge_n_p_avg_c-pi_c}) \&
(\ref{eqn:4_pi_le_lambda_n_d}})\right]$ $\displaystyle\implies
p_{avg}(c)-\lambda\cdot d\leq\pi(c)$ (7) $\displaystyle\text{Again
}\lambda\cdot n\cdot d\geq-n\cdot\left(p_{avg}(c)-\pi(c)\right)$
$\displaystyle\left[\text{Using \lx@cref{creftypecap~refnum}{eqn:1_K-score-
pi_ge_pi_c-v_c}, (\ref{eqn:3_sum_pi_c-v_c_ge_-n_p_avg_c-pi_c}) \&
(\ref{eqn:4_pi_le_lambda_n_d})}\right]$ $\displaystyle\implies\pi(c)\leq
p_{avg}(c)+\lambda\cdot d$ (8) $\displaystyle\text{Hence
}p_{avg}\left(c\right)-\lambda\cdot d\leq\pi\left(c\right)\leq
p_{avg}\left(c\right)+\lambda\cdot d$ (9) $\displaystyle\left[\text{Using
\lx@cref{creftypecap~refnum}{eqn:approx_pi_c_part_1} \&
(\ref{eqn:approx_pi_c_part_2})}\right]$

Equation 9 concludes the proof of Lemma 1. $\square$

The following Lemma 2 depends on the Lemma 7 from [BFG+09].

######  Lemma 2 ($\star$)

$|P_{i}|\leq 4\lambda d-1~{}~{}\forall i\in[m-1]_{0}$

Proof. We prove this lemma by contradiction. For this, we assume that for a
position $i$, we have $|P_{i}|>4\lambda d$. Every candidate $c\in P_{i}$ has
at most $2\lambda d-1$ different positions around its average position in a
$\lambda$-approximately optimal Kemeny consensus $\pi$ based on the proof of
Lemma 1. In Lemma 1 we have established that
$p_{avg}\left(c\right)-\lambda\cdot
d<\pi(c)<p_{avg}\left(c\right)+\lambda\cdot d$. Hence, only those candidates
in $\pi$ have $i$ as their common position for which

$\displaystyle|i-\pi(c)|$ $\displaystyle\leq 2\lambda d-1$ (10)
$\displaystyle\Rightarrow i-(2\lambda d-1)$ $\displaystyle\leq\pi(c)\leq
i+(2\lambda d-1)$ (11)

Since, our assumption is $|P_{i}|\geq 4\lambda d$, therefore, each of these
$4\lambda d$ candidates must hold a position which differs at most by
$2\lambda d-1$ around position $i$. But from Equation 11, we know that only
those candidates in $\lambda$-approximately optimal Kemeny consensus $\pi$
qualify for $P_{i}$ whose $\pi(c)$ lies in the range $2\lambda d-1$ left and
$2\lambda d-1$ right around position $i$. Therefore, we have $4\lambda d-1$
such positions. Hence, we approach towards contradiction. $\square$

Having proved Lemma 1 we are now ready to design a dynamic programming
algorithm in the following Theorem 6 which has found its significant
importance in this current setting.

###### Theorem 6

There exists an FPT dynamic programming algorithm for Distinct approximate
Kemeny Ranking Aggregation parameterized by both $\lambda\text{ and }d$ which
runs in time $\mathcal{O}^{*}(16^{\lambda d})$.

Proof. From the proof of Lemma 2 and using similar arguments as in the proof
of Theorem 3 we can conclude the proof of Theorem 6. $\square$

##  5 Concluding Remarks and Future Work

We consider the problem of finding distinct rankings that have a good Kemeny
score in either exact or approximate terms, and propose algorithms that are
tractable for various natural parameterizations of the problem. We show that
many optimal or close to optimal solutions can be computed without significant
increase in the running time compared with the algorithms to output a single
solution, which is in sharp contrast with the diverse version of the problem.
We also establish a complete comparison between the five natural parameters
associated with the problem, and demonstrate these relationships through
experiments.

We propose three main themes for future work. The first would be to extend
these studies to other voting rules, and possibly identify meta theorems that
apply to classes of voting rules. The second would be to understand if the
structural parameters that we studied are correlated with some natural
distance notion on the solution space: in other words, for a given distance
notion, do all similar-looking instances have similar parameter values?
Finally, we would also like to establish algorithmic lower bounds for the
question of finding a set of diverse solutions that match the best known
algorithms in the current literature.

## Ethical Statement

This paper adheres to the principles of research ethics, research integrity,
and social responsibility. The research conducted in this paper is purely
theoretical, and no human or animal subjects were involved in the research.
Therefore, there were no ethical concerns related to the treatment of
participants or the use of personal data.

We acknowledge that scientific research has the potential to impact society in
significant ways, and we recognise our responsibility to consider the
potential consequences of our research. We have taken steps to ensure that our
research adheres to ethical and legal standards, and that it does not promote
or contribute to harmful or unethical practices.

We have also taken measures to ensure the accuracy and reliability of our
research results. We have followed established research protocols, and we have
taken steps to prevent bias or conflicts of interest from influencing our
findings.

Overall, we are committed to conducting research that is socially responsible
and that contributes to the advancement of theoretical computer science in a
responsible and ethical manner.

## References

  * [ACN08a] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: ranking and clustering.  Journal of the ACM (JACM), 55(5):1–27, 2008.
  * [ACN08b] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  J. ACM, 55(5):23:1–23:27, 2008.
  * [AFdOOW20] Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf.  Width notions for ordering-related problems.  2020\.
  * [AFL+21] Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Petra Wolf.  Diversity in kemeny rank aggregation: A parameterized approach.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 10–16. ijcai.org, 2021.
  * [BBD09] Therese Biedl, Franz J Brandenburg, and Xiaotie Deng.  On the complexity of crossings in permutations.  Discrete Mathematics, 309(7):1813–1823, 2009.
  * [BFG+09] Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond.  Fixed-parameter algorithms for kemeny rankings.  Theor. Comput. Sci., 410(45):4554–4570, 2009.
  * [BTT89] John Bartholdi, Craig A Tovey, and Michael A Trick.  Voting schemes for which it can be difficult to tell who won the election.  Social Choice and welfare, 6(2):157–165, 1989.
  * [CDK06] Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam.  Improved bounds for computing Kemeny rankings.  In AAAI, volume 6, pages 620–626, 2006.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [CGS13] Denis Cornaz, Lucie Galand, and Olivier Spanjaard.  Kemeny elections with bounded single-peaked or single-crossing width.  In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 76–82. IJCAI/AAAI, 2013.
  * [DK04] Andrew Davenport and Jayant Kalagnanam.  A computational study of the Kemeny rule for preference aggregation.  In AAAI, volume 4, pages 697–702, 2004.
  * [DKNS01a] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar.  Rank aggregation methods for the web.  In Vincent Y. Shen, Nobuo Saito, Michael R. Lyu, and Mary Ellen Zurko, editors, Proceedings of the Tenth International World Wide Web Conference, WWW 10, Hong Kong, China, May 1-5, 2001, pages 613–622. ACM, 2001.
  * [DKNS01b] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar.  Rank aggregation methods for the web.  In Proceedings of the 10th international conference on World Wide Web, pages 613–622, 2001.
  * [GHN04] Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  A structural view on parameterizing problems: Distance from triviality.  In Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne, editors, Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, volume 3162 of Lecture Notes in Computer Science, pages 162–173. Springer, 2004.
  * [HHOW05] Emmanuel Hebrard, Brahim Hnich, Barry O’Sullivan, and Toby Walsh.  Finding diverse and similar solutions in constraint programming.  In AAAI, volume 5, pages 372–377, 2005.
  * [HOW07] Emmanuel Hebrard, Barry O’Sullivan, and Toby Walsh.  Distance Constraints in Constraint Satisfaction.  In IJCAI, volume 2007, pages 106–111, 2007.
  * [HSV05] Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel.  The complexity of kemeny elections.  Theoretical Computer Science, 349(3):382–391, 2005.
  * [Kem59] John G. Kemeny.  Mathematics without numbers.  Daedalus, 88(4):577–591, 1959.
  * [Kla04] Christian Klamler.  The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule.  Social Choice and Welfare, 23(1):91–102, 2004.
  * [KMS07] Claire Kenyon-Mathieu and Warren Schudy.  How to rank with few errors.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 95–103, 2007.
  * [PHG00] David M. Pennock, Eric Horvitz, and C. Lee Giles.  Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering.  In Henry A. Kautz and Bruce W. Porter, editors, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30 \- August 3, 2000, Austin, Texas, USA, pages 729–734. AAAI Press / The MIT Press, 2000.
  * [SZ09] Frans Schalekamp and Anke van Zuylen.  Rank aggregation: Together we’re strong.  In 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), pages 38–51. SIAM, 2009.
  * [vZW07] Anke van Zuylen and David P. Williamson.  Deterministic algorithms for rank aggregation and other ranking and clustering problems.  In Christos Kaklamanis and Martin Skutella, editors, Approximation and Online Algorithms, 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers, volume 4927 of Lecture Notes in Computer Science, pages 260–273. Springer, 2007.
  * [VZW09] Anke Van Zuylen and David P Williamson.  Deterministic pivoting algorithms for constrained ranking and clustering problems.  Mathematics of Operations Research, 34(3):594–620, 2009.
  * [Zwi18] William S Zwicker.  Cycles and intractability in a large class of aggregation rules.  Journal of Artificial Intelligence Research, 61:407–431, 2018.