6
$\begingroup$

Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders

  • $1<2$
  • $2<1<3<4$
  • $2<3<1$

Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$). We seek to find a total order $L$ which minimizes $\sum_{i<j} C(i,j)$.

This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered?

$\endgroup$
  • 1
    $\begingroup$ What is your formal definition of a conflict? $\endgroup$ – Aaron Sterling Sep 21 '11 at 1:31
  • $\begingroup$ I thought I defined it formally in the question. Is it that my definition of $C(i,j)$ is unclear? $\endgroup$ – morgan Sep 21 '11 at 1:35
  • $\begingroup$ Perhaps an example would help. The ranking $1<2<3<4$ has three conflicts with the list in the question: two $(1,2)$-conflicts, one $(1,3)$ conflict, and zero $(1,4),(2,3), (2,4)$ conflicts. $\endgroup$ – morgan Sep 21 '11 at 1:36
5
$\begingroup$

This is a special case of metric $1$-medians, where the metric space is $S_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i<j$ s.t. $i$ and $j$ are ordered differently). This distance metric is also known as Kemeny distance and is related to the weak Bruhat order.

This paper by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:

Let $\pi$ be the optimal permutation and $\pi_{j^*}$ the best of $\pi_1, \ldots, \pi_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi_i, \pi) + d(\pi_j, \pi) \geq d(\pi_i, \pi_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi_{j^*}$ was chosen so that $\mathsf{ALG}(j^*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^*) \leq \sum_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^*) \leq 2\mathsf{OPT}$.

The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor.

Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the link

$\endgroup$
  • $\begingroup$ of course the simple 2-approximation works for finding an approximate median in any metric space $\endgroup$ – Sasho Nikolov Sep 21 '11 at 2:52
4
$\begingroup$

Your conflict measure is called the Kendall tau distance. The total order that minimizes these conflicts is the winner of the Kemeny-Young voting method. Computing the winner of the Kemney-Young voting method is NP-hard.

$\endgroup$
1
$\begingroup$

If you are looking for different approaches/algorithms to the problem, perhaps the right "google keywords" are Rank aggregation or Weighted rank aggregation.

For example see the paper "Rank Aggregation Revisited" by C.Dwork, R.Kumar, M.Naor, D.Sivakumar.

The rank aggregation problem is to combine many different rank orderings on the same set of candidates, or alternatives, in order to obtain a “better” ordering. Rank aggregation has been studied extensively in the context of social choice theory, where several “voting paradoxes” have been discovered. The problem also arises in many other settings:

  • Sports and Competition: How to determine the winner of a season, how to rank players or how to compare players from different eras?
  • Machine Learning: Collaborative filtering and meta-search; Statistics: Notions of Correlation;
  • Database Middleware: Combining results from multiple databases.

...

At the bottom of the article there are plenty of references.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.